TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 7

7) Let G = (V, E) be a simple and undirected graph with |V|>4. The complement G^K= (V^K, E^K) of G is defined as follows: V^K = V and vw $\in$ E^K if and only if vw $\notin$ E. Show that either G or G^K (or both) must contain a cycle! Furthermore, determine all trees T such that T^K is a tree as well!

Solution

Way 1

We assume that G and Gk with |V| > 4 has no cycles. All possible edges should no be split in two groups E and Ek. (|V| over 2) = |E| + |Ek|

The indicitor for a graph that must have cycles is the number of edges. As both graphs should have no cycles we try to split the edges in a way that the max(E, Ek) is minimal. So the best way to do that is to split it in two groups of equals size, so |E|=|Ek|.

Therefore: (|V| over 2) = |E| + |Ek| => |V|*(|V|-1)/2 = 2*|E|

Now we can calculate the number of edges in every group: |E| = |V|*(|V|-1)/4

Now we look at a tree. It is the graph with most possible edges without cycles. Its |E|=|V|-1 as we learned.

So |E| from above must be smaller or equal to the maximum number of edges in a non-cyclic graph (tree):

|V|*(|V|-1)/4 <= |V|-1

As this is false for every |V| > 4 the initial assumption is disproved.

The second task is to find all trees G where Gk is also a tree. As proved above it can only work for |V| element of {1,2,3,4}. You can try it by hand now, the only two trees where its complement is also a tree should be one with |V| = 1 or |V| = 4.

---

Way 2

Even though my approach is similar to above, I'm not completely pleased with the one above. So here is my solution:

First note that $G^{\prime }=G\cup G^k$ is a fully connected graph where the number of edges is $|E^{\prime }|=\frac{|V|(|V|-1)}{2}$. And by construction it applies that: $|E^{\prime }|=|E|+|E^k|$

Again we assume that in both parts there is no cycle. So $G,G^k$ are forests which are containing trees:
Let us assume G contains m trees. We know that one tree has $|E|=|V|-1$ edges
Therefore for G the number of edges is $|E|=\sum _{i=1}^m(|V_i|-1)$ where $|V_i|$ is the number of nodes in one (sub)tree of the forest $G$

And this can be simplified a little bit:

$|E|=\sum _{i=1}^m(|V_i|-1)=\sum _{i=1}^m|V_i|+\sum _{i=1}^m-1=|V|-m$

The very same can be done for $G^k$, where $l$ is the number of subtrees within this forest:

$|E^k|=\sum _{i=1}^l(|V_i^k|-1)=\sum _{i=1}^l|V_i^k|+\sum _{i=1}^l-1=|V^k|-l$

Now the number of edged is easy to compute: $|E|+|E^k|=|V|-m+|V^k|-l=2\cdot |V|-m-l$

If you take into consideration that $m,l\in {\mathbb{N}}_0$ it is easy to see, that $|E|+|E^k|\le 2\cdot |V|$. But at least $m$ or $l$ must be at least 1, because both forest can not be empty. So we can restate: $E^{″}=|E|+|E^k|\le 2\cdot |V|-1$

Now we compare that with the fact, that $G^{\prime }$ is a fully connected graph as mentioned above:
If we can now show that $E^{″}$ is not equal to $E^{\prime }$ we are done.

Indeed for $|V|>4$ it holds that $E^{″}<E^{\prime }$ which can be easily checked

Therefore the initial assumption is wrong and at least one Graph must include a cycle.

Because we just showed that there is always a cycle in one of the graphs there can not be trees like requested.