Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to prove or disprove the following statement: Let $n>1$ be a positive integer. Then there exists a graph $G$ of size 4n-1 such that if the edges of $G$ are colored red or blue, no matter in which way, $G$ definitely contains a monochromatic $K_{2,n}$.

I tried to check a few cases in the hope of discovering a counter-example. For n=2 $G$ has to have size 7. The graph certainly is of the form "Square + 3 edges". Moreover, it should have the property that if among the 7 edges any 3 are deleted the remaining graph is a square. I couldnt construct any such graph. Is there any justification why such a graph cant exist, thereby negating the statement?

share|cite|improve this question
up vote 4 down vote accepted

The claim does not hold for $n = 2$. Consider the following observations for any graph $G$ hoping to satisfy the claim.

  1. $G$ is a $K_{2,2}$ with three edges appended.
  2. Without loss of generality, $G$ is connected and has no leaves.
  3. $G$ has at least five vertices.

Draw a $K_{2,2}$ and plus one more vertex. Since the vertex is not isolated and is not a leaf, it has two edges adjoining it to the $K_{2,2}$, which can be done in two nonisomorphic ways. Note now that we have only one edge remaining, so we can't add another vertex, as this would be a leaf. Thus, $G$ has exactly five vertices. The last edge can be added to the two nonisomorphic six-edge graphs in a total of four nonisomorphic ways (two for each - you can check the cases). For each of these candidates, it is easy to find an edge-coloring that avoids a monochromatic $K_{2,2}$.

share|cite|improve this answer
Thanks. What about the general case though? Do you think that for bigger n also the claim will fail? (If it helps, although I doubt it has a bearing, I have also proved that the for a graph when the claim holds the order $\ge R(K_{2,n},K_{2,n})$ where $R(K_{2,n},K_{2,n})$ is the generalized Ramsey number. This bound is sharp) – Shahab Jun 8 '11 at 6:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.