4
$\begingroup$

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?

1 Answers 1

4

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}$.

  • 0
    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)2011-06-08