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'=G\cup G^{k}$ is a fully connected graph where the number of edges is $\vert {E'}\vert ={\frac {\vert {V}\vert (\vert {V}\vert -1)}{2}}$. And by construction it applies that: $\vert {E'}\vert =\vert {E}\vert +\vert {E^{k}}\vert$

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 $\vert {E}\vert =\vert {V}\vert -1$ edges
Therefore for G the number of edges is $\vert {E}\vert =\sum _{i=1}^{m}{\left(\vert {V_{i}}\vert -1\right)}$ where $\vert {V_{i}}\vert$ is the number of nodes in one (sub)tree of the forest $G$

And this can be simplified a little bit:

$\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 $G^{k}$, where $l$ is the number of subtrees within this forest:

$\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: $\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 $m,l\in \mathbb {N} _{0}$ it is easy to see, that $\vert {E}\vert +\vert {E^{k}}\vert \leq 2\cdot \vert {V}\vert$. But at least $m$ or $l$ must be at least 1, because both forest can not be empty. So we can restate: $E''=\vert {E}\vert +\vert {E^{k}}\vert \leq 2\cdot \vert {V}\vert -1$

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

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