Graph theory: Trees

• Oct 3rd 2009, 08:03 AM
zhupolongjoe
Graph theory: Trees
Let T be a tree of order n. Show that the size of the complement of T (T bar) is the same as the size of K(n-1)

Thanks
• Oct 3rd 2009, 12:30 PM
Plato
Quote:

Originally Posted by zhupolongjoe
Let T be a tree of order n. Show that the size of the complement of T (T bar) is the same as the size of K(n-1)

If $T$ is a tree with $n$ vertices the you know that $T$ has $n-1$ edges.

The complement $\overline{T}$ has $\binom{n}{2}-(n-1)$ edges.

The graph $K_{n-1}$ has $\binom{n-1}{2}$ edges.