1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Henning Makholm Oct 18 '18 at 19:38
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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.

$\endgroup$

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.