Edge coloring a graph to find a monochromatic $K_{2,n}$ 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?

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


*

*$G$ is a $K_{2,2}$ with three edges appended.

*Without loss of generality, $G$ is connected and has no leaves.

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