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.


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.

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.