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

From VoWi
Jump to navigation Jump to search
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 EK if and only if vw 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!

Theory[edit | edit source]

Solution[edit | edit source]

Way 1[edit | edit source]

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[edit | edit source]

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 is a fully connected graph where the number of edges is . And by construction it applies that:

Again we assume that in both parts there is no cycle. So are forests which are containing trees:
Let us assume G contains m trees. We know that one tree has edges
Therefore for G the number of edges is where is the number of nodes in one (sub)tree of the forest

And this can be simplified a little bit:

The very same can be done for , where is the number of subtrees within this forest:

Now the number of edged is easy to compute:

If you take into consideration that it is easy to see, that . But at least or must be at least 1, because both forest can not be empty. So we can restate:

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

Indeed for it holds that 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.