$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$?