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? – mathnoob Dec 6 at 16:55
  • @mathnoob yes, all edges should have to have the same color – ippon Dec 6 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 at 17:02
up vote 2 down vote accepted

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. enter image description here

  • Am I right???????????? – mathnoob Dec 6 at 17:19
  • 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 at 18:17
  • Great! Thank you! – mathnoob Dec 6 at 18:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.