$K_4$ is the complete graph with 4 vertices. Let's color the edges in the graph with two colors. How would one go about proving the following statement:
There is always a monochromatic path of length 3 on the graph.
It seems obvious, but I have no idea how to prove this. $K_4$ has 6 edges, so the best you can do to avoid coloring with the same color too much is to has 3 edges per color. It seems like it's not possible to choose any set of three edges in $K_4$ that don't form a single path. But how would one prove this?
Also, is there a meaningful result when you generalize this question:
Let $P_n$ be the length of the longest monochromatic path that must exist when you color the edges of $K_n$ with two colors.
It's trivial to show that $P_1 = 0$, $P_2 = 1$, and $P_3 = 2$. As stated above, I am pretty sure that $P_4 = 3$. Can we say anything about $P_n$?
Best Answer
If one of the $\binom{4}{3}=4$ triangles is monochromatic we are done. Otherwise, by the pigeonhole principle, there are at least two distinct triangles with two sides of one color, say color 1, and one side of the other one, say color 2. Then there is a monochromatic path of length 3 of color 1 along the sides of those two triangles (note that any couple of triangles in $K_4$ share two vertices).
For the general case see Theorem of Gerencser-Gyarfas ("On Ramsey-type problems", Ann. Sci. Budapest. Eotvos Sect. Math, 10 (1967), 167-170): Let $n$ be a positive integer. In every 2-coloring of the edges of $K_n$, there exists a monochromatic path on at least $\lceil(2n+ 1)/3\rceil$ vertices. Furthermore, there exists a 2-coloring of the edges of $K_n$ such that the longest monochromatic path has $\lceil(2n+ 1)/3\rceil$ vertices.