Given a simple graph and its complement. Prove that either of them has a cycle.

Question

Prove that when given two graphs $G$ and $\bar{G}$ (complement), at least one of them must contain a cycle.

I thought about showing it by the number of edges: Suppose $G$ and $\bar{G}$ both don't contain cycles, then they are both forests. The number of edges is then $|V|-m$, where $|V|$ is the number of vertices and $m$ is the number of subtrees in the forest G.

As far as I've read, we can then consider the number of edges in a fully connected graph, which is $|E|+\bar{|E|}=2|V|-2m$ and this is smaller or equals $2|V|-1$.

Now I'm not sure how to continue. In other proves I've seen that they say that a fully connected graph must have $\frac{|V|(|V|-1)}{2}$ edges and therefore one of the graphs must have a cycle. But I don't understand this conclusion as $2|V|-2m$ is smaller than $\frac{|V|(|V|-1)}{2}$. So if we have less edges than a fully connected graph has, where should be the problem?

So can anyone help me to continue this proof or tell me if there is a better and easier way to show that?

Answer 1

You're almost done.

You can restate the problem as

Suppose in the complete graph $K_n$ we color some of the edges red and the rest blue. Show that there is either a an all-red cycle or an all-blue cycle.

If there are more than $n-1$ red edges, then the subgraph consisting of red edges has a cycle.

On the other hand if there are more than $n-1$ blue edges, then the blue subgraph has a cycle.

Conversely, if neither of these are true, then there are at most $2(n-1)$ edges. On the other hand, we know that $K_n$ has $\frac12 n(n-1)$ edges, so if $\frac12 n(n-1) > 2n-2$, then this case is not possible and one of the two previous cases (where there is either a red or a blue cycle) must have been the case.

If $n$ is small enough, then $\frac 12 n(n-1)\le 2n-2$, and then there are counterexamples to the claim.

Answer 2

Clearly this is true if $n\geq 6$. It is due to a famous problem. If we color edges of $K_6$ with two colors then we get monochromatic triangle. The proof uses Pigeonhole principle.

If we take point $A$ then it is connected with 3 other (say $B,C,D$) (among 5 of them) with the same color edges, say red. If some 2 (say $B$ and $C$) of those 3 are connected with red edge we have red cycle $ABC$. Else all edges beetwen $B,C,D$ are blue and we have again monochromatic cycle.

Answer 3

In your argumentation you have arrived at a contradiction, because you have that $2 |V| - 2m < |V|(|V| - 1) / 2$ but the edges of G and it's complement should add up to $|V|(|V| - 1) / 2$. So you assumed that there was no cycle, now you have a contradiction and thus you can conclude that either G or it's complement contains a cycle.

Answer 4

If $G$ is a graph of order $n$, then $\chi(G)\chi(\overline G)\ge n$. Therefore, if $G$ has order $n\ge5$, then at least one of the graphs $G$ and $\overline G$ has chromatic number $\gt2$, so it contains an odd cycle.