# $2$-coloring of graph has large connected subgraph with one color

Given a graph $G$ with $n$ vertices. Let $k$ denote the minimum degree among the vertices. Suppose that $k\geq 3n/4$. We color the edges of $G$ in $2$ colors. Prove that there is a connected subgraph with at least $k+1$ vertices whose edges have the same color.

Since $k$ is the minimum degree, it suffices to find a vertex $v$ such that the subgraph formed by $v$ and its neighbors can be connected using edges of only one color.

## 1 Answer

I find it easier to work with the following reformulation:

We have a graph $G$ with the aforementioned properties, we select some edges of the graph such that the graph $H$ formed by these edges does not have components of size exceeding $k$ and remove these edges. Prove that the resulting graph $G'$ has a connected component of size at least $k+1$.

Suppose there is a counterexample to this. Suppose that in the counterexample $H$ (The graph of removed edges) has connected component $K$. Then we obtain another counterexample if we add to $H$ all of the other edges between vertices of $K$.In other words we can remove even more edges while still satisfying the property that $H$ has no connected components of size exceeding $k$.

So we only have to check the cases when the removed edges are constructed as follows: Take a partition $P_1,P_2\dots P_k$ of the vertices of $G$ such that $|P_i|\leq k$. Remove all the edges that are between two vertices of the same set.

Also note if we have two sets $P_i$ and $P_j$ which have less thank $k$ vertices combined then we can obtain another counterexample by taking a partition very similar to $P_1,P_2\dots P_k$ with the difference that we substitute $P_i$ and $P_j$ for $P_i\cup P_j$

Since $k\geq\frac{3n}{4}$ We only have to check the partitions of the vertices of $G$ into two sets. Why? In a partition of three or more sets the smallest two have size less than or equal to $\frac{2n}{3}<\frac{3n}{4}\leq k$ so we could obtain a counterexample with one set less if we swapped the two smallest sets for the union. So we can obtain a counterexample with two sets from a counterexample of more than $2$ sets.

In other words if there was a counterexample there would also be a counterexample obtained by partitioning the vertices of the graph into two sets and removing the edges between vertices of the same set.

Suppose such a counterexample indeed exists:

We take our graph $G$ and partition the vertices of $G$ into two subsets of sizes not exceeding $k$, we remove the edges between vertices of the same set. The result is a bipartite graph.

Suppose our bipartite graph is $X,Y$ with $|X|=l,|Y|=n-l$. Then the vertices of $X$ have degree at least $k-l+1$ (since each loses at most $l-1$ edges) and the vertices of $|Y|$ have degree at least $k-n+l+1$ Since each loses at most $n-l-1$ edges. This tells us every connected component has size at least $2k-n+2\geq\frac{3n}{2}-n+2=\frac{n}{2}+2$ (because a connected component has at least $k-l+1$ vertices in $Y$ and at least $k-n+l+1$ vertices in $X$). So all connected components have size at least $\frac{n}{2}+2$ This is only possible if the graph has one connected component.

So we have proven something slightly stronger than what was desired:

If $G$ is a graph with minimum degree $k$ with $k\geq \frac{3n}{4}$ in which the edges are colored blue and red one of the following must hold:

• The graphs of the edges of both colors each have a connected component of size at least $k+1$
• The graph of one of the colors is connected.