# 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 GK= (VK, EK) of G is defined as follows: VK = V and vw ${\displaystyle \in }$ EK if and only if vw ${\displaystyle \notin }$ E. Show that either G or GK (or both) must contain a cycle! Furthermore, determine all trees T such that TK 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 ${\displaystyle G'=G\cup G^{k}}$ is a fully connected graph where the number of edges is ${\displaystyle \vert {E'}\vert ={\frac {\vert {V}\vert (\vert {V}\vert -1)}{2}}}$. And by construction it applies that: ${\displaystyle \vert {E'}\vert =\vert {E}\vert +\vert {E^{k}}\vert }$

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

And this can be simplified a little bit:

${\displaystyle \vert {E}\vert =\sum _{i=1}^{m}{\left(\vert {V_{i}}\vert -1\right)}=\sum _{i=1}^{m}{\vert {V_{i}}\vert }+\sum _{i=1}^{m}{-1}=\vert {V}\vert -m}$

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

${\displaystyle \vert {E^{k}}\vert =\sum _{i=1}^{l}{\left(\vert {V_{i}^{k}}\vert -1\right)}=\sum _{i=1}^{l}{\vert {V_{i}^{k}}\vert }+\sum _{i=1}^{l}{-1}=\vert {V^{k}}\vert -l}$

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

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

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

Indeed for ${\displaystyle \vert {V}\vert >4}$ it holds that ${\displaystyle E'' 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.