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

coloringcontest-mathdiscrete mathematicsgraph theory

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.

Best Answer

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.

Related Question