2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ How would you generalize this to all $n$? $\endgroup$
    – XYZT
    Dec 12, 2019 at 8:44
  • $\begingroup$ @XYZT Please see my edit $\endgroup$
    – Robert Z
    Dec 12, 2019 at 9:15
  • $\begingroup$ Wow, that's incredible that this exact problem has been solved (the formulation is identical too!). Thanks! $\endgroup$
    – XYZT
    Dec 12, 2019 at 9:21
  • $\begingroup$ How is the second statement of the theorem you mention different from the first statement? $\endgroup$
    – XYZT
    Dec 12, 2019 at 9:22
  • $\begingroup$ The two statements are not in contradiction. Together they say that $\lceil(2n+ 1)/3\rceil$ is the exact lower bound. $\endgroup$
    – Robert Z
    Dec 12, 2019 at 12:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .