Complete graph with N vertexes with two colored edges: prove that either one colored graph or another colored graph is connected

Question

There are n vertices in a complete graph. There is edge between every two vertices. All edges are blue or red.

And the problem is to prove that you

• always can choose one of two colors (either blue or red, but iyndoes not mean that we can choose both, it is enough just one)
• then delete all edges of given color (so graph would be only one colored)
• and in the result graph there would still be path between every two vertices

I tried to prove it with some logical reasoning. And I think I understand it, but description is very vague. I am looking for more mathematical/graph language description.

My reasoning steps:

1. We assume that this is not possible, then the result graph would contain some vertices A and B so that there is no path between them. We assume that we deleted all blue edges and now only red ones are left.

2. There is some subgraph that contains vertex B and there is path from B to every other vertex in this subgraph. Remember that all edges are red.

3. The same is for vertex A and subgraph that contains vertex A and there is path from A to every other vertex. Edges are red.

4. So we have two subgraphs Asub and Bsub, there are no paths from Asub to Bsub. Otherwise our first assumption would not be true.

5. This means that those subgraphs where connected with blue edges before we deleted them. Each vertex in subgraph A were connected to subgraph B every vertex (with blue edge).

And now logically thinking if we put back all blue edges and remove red edges, then we would be able to go from every vertex to every other vertex using blue edges. This part is very vague...

I also tried another approach - to start with 3 vertexes, then add the fourth one etc. But it doesn't work for me either.

Answer 1

Suppose you have a counterexample. Then there are two vertices $A$ and $B$ which can't be connected by a red path, and there are two vertices $C$ and $D$ which can't be connected with a blue path. Then the subgraph induced by $\{A,B,C,D\}$ is a counterexample with $3$ or $4$ vertices.

I've shown that, if there is a counterexample, then there is a counterexample with $3$ or $4$ vertices. Thus it will suffice to prove the theorem for $n=3$ and $n=4$; it will then follow that it holds for every $n$.

$n=3$: the complete graph has $3$ vertices and $3$ edges. By the pigeonhole principle, there are $2$ edges of the same color. Any (simple) graph with $3$ vertices and $2$ edges is connected.

$n=4$: the complete graph has $4$ vertices and $6$ edges. It's easy to see that any graph with $4$ vertices and $4$ edges is connected, so the only way things can go wrong is if we have $3$ edges of each color. But the only way the $3$ red edges can fail to connect is if they form a triangle, in which case the $3$ blue edges form a star $K_{1,3}$ which is connected. Q.E.D.

Remark. In the same way it's easy to see that either every pair of vertices is connected by a red path of length at most $3$, or else every pair of vertices is connected by a blue path of length at most $2$. This is best possible: if $n\ge4$ and the red subgraph is a spanning tree with maximum degree $n-2$, then the red subgraph and the blue subgraph both have diameter $3$; if $n\ge3$ dne the blue subgraph is a spanning tree with maximum degree $n-1$, then the red subgraph is disconnected and the blue subgtraph has diameter $2$.

Answer 2

There is a simpler way to do this.

Let us suppose that the graph $G^{\text{red}}$ consisting of the red edges is not connected, for if it were connected we would be done already. Then the graph $G^{\text{blue}}$ consisting of only the blue edges is connected. To see this, we show that a vertex $x$ is in the same component of $G^{\text{blue}}$ as every other vertex:

1. Suppose $x$ and $y$ are distinct vertices in different components of $G^{\text{red}}$. Then they are in the same component of $G^{\text{blue}}$ as each other. [Indeed, there is no edge from $x$ to $y$ in $G^{\text{red}}$, and so there is an edge from $x$ to $y$ in $G^{\text{blue}}$. So $x$ and $y$ are in the same component of $G^{\text{blue}}$.]

2. Suppose that $x$ and $x'$ are distinct vertices in the same component of $G^{\text{red}}$ as each other. Then they are also in the same component of $G^{\text{blue}}$. [Indeed, we use the fact that $G^{\text{red}}$ is not connected. So let $y$ be a vertex such that $y$ is in a different component of $G^{\text{red}}$ from $x$ and $x'$; such a $y$ exists because $G^{\text{red}}$ is not connected. Then both $x$ and $x'$ are in the same component of $G^{\text{blue}}$ as $y$, as the edges $xy$ and $x'y$ are in $G^{\text{blue}}$ [why is that]. But then this gives $x$ and $x'$ are in the same component of $G^{\text{blue}}$ as each other because they both are in the component of $G^{\text{blue}}$ that contains $y$.]

So from 1. and 2., a vertex $x$ is indeed in the same component of $G^{\text{blue}}$ as every other vertex if $G^{\text{red}}$ is not connected, so $G^{\text{blue}}$ is indeed connected if $G^{\text{red}}$ is not. Note that there is nothing special about the "$2022$" except that it is a positive integer.

---

This exercise should look familiar to some: It is equivalent to showing that given a set $V$ of vertices and a graph $G$ on $V$, then at least one of $G,G^c$ is connected, where $G^c$ denotes the complement of $G$.

Answer 3

If the red graph is connected, then you are happy.

If not, take any two vertices $u$ and $v$.

1. If they are in different red components, they can't be connected with a red edge, so they are connected with a blue edge.
2. If they are in the same component, let $w$ be a vertex in a different component in the red graph. Then $uw$ is a blue edge and $vw$ is a blue edge, so $u$ and $v$ are connected in the blue graph.

Answer 4

Induction works as well:

Let's call the graphs you described two-edge colored complete graphs. Let $G_R$ or $G_B$ denote the subgraphs of $G$ obtained by deleting all red or blue edges.

Our induction hypothesis is:
For every $n\in\mathbb N$, for every two-edge colored complete graph $G$ with $n$ vertices we have that $G_R$ or $G_B$ is connected.

It is obvious that the induction hypothesis holds for $n=1$.

For the induction step, we now assume that the induction hypothesis holds for a fixed $n$, and we have to show that it then also holds for $n+1$.

Let $G$ be a two-edge colored complete graphs with $n+1$ vertices. We choose a vertex $x$ of $G$, and let $G'$ denote the subgraph of $G$ induced by all vertices of $G$ but $x$. Our induction hypothesis now tells us that for $G'$ we have that $G'_R$ or $G'_B$ is connected. Let wlog $G'_R$ be connected.

Then, if any of the edges between $x$ and the remaining vertices in $G$ is red, then $G$ is connected as well. And if all edges edges between $x$ and the remaining vertices in $G$ are blue, then we also have that $G$ is connected.

Therefore we have shown that $G$ is connected, and thus that the induction holds.