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

I want to 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?

• This is not necessarily true unless the graph has more than $4$ vertices. The path graph with $4$ vertices has no cycle, and neither does its complement (which is itself a path graph). – Henning Makholm Oct 18 '18 at 19:38

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.

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 monocromatic 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 momocromatic cycle.

• It's also true for $n=5$, by counting. – Henning Makholm Oct 18 '18 at 19:44

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.