# In the complete graph with n vertices, all edges are colored in three colors.

In the complete graph with $$n$$ vertices, all edges are colored in three colors. Prove that exists a monochromatic connected subgraph with at least $$\frac{n}{2}$$ vertices.

I got this task in math contest.

I know that $$|E| = \frac{n(n-1)}{2}$$ and amount of edges of complete graph with $$\frac{n}{2}$$ vertices is $$|E'| = \frac{(\frac{n}{2})(\frac{n}{2} - 1)}{2}$$ Also if $$k_i$$ - amount of edges with color number $$i$$, then
$$k_1 + k_2 + k_3 = |E| \Rightarrow \exists k_i: k_i \ge \frac{n(n-1)}{6}$$ So I can prove that $$k_i \ge |E'|$$ But this statement doesn't solve the task.

• Suggestion: For $K_3$ this is easy. For $K_4$ and larger, by Pigeonhole, there will be at least two edges of the same color. We have no restriction on coloring so we should try to build a minimal chain of edges of the same color. Draw it out! – Sean Roberson Mar 2 at 18:20
• @SeanRoberson I have tried to prove the task using induction, but i don't know how to do an inductive step. – hpaapipny Mar 2 at 18:27

Lemma: Let $$K_{m, n}$$ be the complete bipartite graph on sets of vertices $$A$$ and $$B$$ with respective sizes $$m$$ and $$n$$. If the edges of $$K_{m, n}$$ are two-colored, then there is a monochromatic connected subgraph spanning at least $$\frac{m+n}{2}$$ vertices.

Proof: Call the colors red and blue. Call a vertex red-primary if it has more red than blue edges, blue-primary if it has more blue than red edges, and neutral if the numbers are equal. There are two cases.

Case 1. For some set $$X \in \{A, B\}$$ and for some color $$C \in \{\text{red}, \text{blue}\}$$, at least one vertex in $$X$$ is $$C$$-primary, and at least $$|X|/2$$ vertices in $$X$$ are either $$C$$-primary or neutral.

Suppose without loss of generality that $$A$$ has at least one red-primary vertex, and the majority of vertices in $$A$$ are red-primary or neutral. If $$a_1 \in A$$ is red-primary and $$a_2$$ is either red-primary or neutral, then by the pigeonhole principle, some vertex in $$B$$ has red edges to both $$a_1$$ and $$a_2$$. Thus, there is a red connected graph spanning at least any red-primary or neutral vertex in $$A$$ (which makes up at least half of $$A$$) and any vertex in $$B$$ with red edges to any of these vertices (which makes up at least half of $$B$$, as any single red-primary or neutral vertex has red connections to at least half of the other set).

Case 2. Every vertex is neutral. Then any vertex $$A$$ has red connections to exactly half the vertices of $$B$$. Each of those vertices has a red connection to exactly half of $$A$$ (perhaps a different half each time). This gives us a red monochromatic subgraph.

Now to the main problem. The cases $$n = 1, 2, 3, 4$$ can be established trivially. The required subgraph for $$n = 2m-1$$ odd is has the same size as that for $$n = 2m$$ even, so it suffices to prove the case for odd $$n$$.

We work by induction, showing that the claim for $$n=2m-1$$ implies the claim for $$n=2m+1$$. Let the colors be red, blue, and green, and let $$K_{2m+1}$$ be a complete edge-3-colored graph on $$2m+1$$ vertices. By the induction hypothesis, $$K_{2m+1}$$ has a connected monochromatic (without loss of generality, green) subgraph of $$m$$ vertices. Let $$G$$ be this set of vertices, and let $$H$$ be the rest of $$K_{2m+1}$$. If any of the edges from $$G$$ to $$H$$ is green, then we have a connected green graph of the required size $$m+1$$. Otherwise, erasing every edge internal to $$G$$ or to $$H$$ gives a complete bipartite graph on $$m$$ and $$m+1$$ vertices with every edge colored either red or blue, and the lemma guarantees either a red or a blue monochromatic subgraph with the required size.

Remark: It is possible to construct instances in which the given bound is tight. For example, for $$n = 4m$$ even, one may construct a graph with no monochromatic graph larger than $$2n$$ by taking four equally sized sets of vertexes $$A, B, C, D$$ and coloring all edges internal to the sets $$A \cup B$$ and $$C \cup D$$ green, edges from $$A$$ to $$C$$ or $$B$$ to $$D$$ red, and edges from $$A$$ to $$D$$ or $$B$$ to $$C$$ blue.