# Finding the smallest number $n$ such that every two-colouring of the edges of $K_n$ contains a Path on 3 vertices

What is the smallest number $$n$$ such that every two-colouring of the edges of $$K_n$$ contains a (not necessarily induced) path on 3 vertices?

• Sorry, Do you mean a path where every edges has the same color? – mathpadawan Dec 6 '18 at 16:55
• @mathnoob yes, all edges should have to have the same color – ippon Dec 6 '18 at 17:01
• Seems like $K_3$ already does the job which makes me think that you meant to phrase the problem differently. (A path on $3$ edges, for example.) – Misha Lavrov Dec 6 '18 at 17:02

If it is a path on 3 vertices , $$K_3$$ works as it is garanted that two of the three edges have the same color, well then they form a path on three vertices. If what we want is a path of length $$3$$, my guess is $$5$$. Look at a vertex $$u \in V(K_n)$$, there are 4 edges connect to it. It is guarantee that at least two of the edges $$e_1,e_2$$ connected to it have the same color. So the edges connected to $$e_1$$ and $$e_2$$ not via $$u$$ must be color the other color. But then that gives a path of length 3 in the other color.
Also, here is an example of coloring of $$K_4$$ that does not admit a path of length 3, the edges are colored using numbers 1 and 3.
• Seems right to me, modulo a coloring of $K_4$ that does not contain a path of length $3$ (which is not hard to find). – Misha Lavrov Dec 6 '18 at 18:17