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.

  • $\begingroup$ 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! $\endgroup$ – Sean Roberson Mar 2 at 18:20
  • $\begingroup$ @SeanRoberson I have tried to prove the task using induction, but i don't know how to do an inductive step. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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