$K_{2,2}$ with the same color for every coloring of $K_{3,7}$

Question

How can I prove that for every way of coloring the edges of the bipartite graph $K_{3,7}$ with two colors (red, blue) there is a $K_{2,2}$ graph with the same color?

Answer 1

Count the monochromatic "V" shapes in the graph: pairs of edges like

which have the same color and meet in the part of size $7$.

(At @bof's advice, I've flipped the picture for an argument that works better.)

From each vertex in the bottom vertex, there are three edges up, and at least two of them share a color, forming one of these "V" shapes.

There are $7$ bottom vertices, and three possible "V" shapes, so one "V" shape occurs three times:

If it occurs three times, two of those share a color, and once you pick those two "V" shapes, you've found a monochromatic $K_{2,2}$.

---

By the way, a different way to think about the problem is to say that we are coloring a $3 \times 7$ grid and want to find a rectangle whose vertices are all given the same color:

Here, if we take the cell in position $(x,y)$ to correspond to the edge between the $x^{\text{th}}$ vertex in one part and the $y^{\text{th}}$ vertex in the other part, a rectangle precisely corresponds to a $K_{2,2}$.

We can prove the rectangle claim just like the argument above, by looking at how columns in this grid are colored.