Prove: for a graph $G=(V,E)$, if$ |V| \ge 5$, there is a cycle in $G$ or in complement $G$

Question

I tried to do this with number of edges: if $|E| \ge n$ there is a cycle in $G$. I got stuck when $|E|\lt n$. Thanks!

Answer 1

Let's suppose that there is no cycle neither in $G$ nor complement of $G$. In complement of $G$ there are $\frac{n(n-1)}{2}-E$ edges. If in both graphs there are no cycles, then number of edges in both graph is less than $n$. This means that the sum of number of edges in both graph is less than $2n$. So $\frac{n(n-1)}{2} < 2n \iff n < 5$ contradiction.

Answer 2

Let $K=\{\{v,w\}:v,w\in V\}$ be the set of all possible edges for $V$, note that $|K|=(|V|^{2}-|V|)/2$. In particular, for $|V|\geq 5$ we find that $|K|\geq 2|V|$. Now let $G=(V,E)$ be a graph with $|V|\geq 5$.

If $|E|\geq|V|$, then $G$ has a cycle. If $|E|<|V|$, then in the complement graph of $G$, $\hat{G}=(V,K\setminus E)$ we find that $$K\setminus E=(|V|^{2}-|V|)/2-|E|\geq 2|V|-|V|=|V|,$$ so the complement graph of $G$ has a cycle.