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

Printable View

- Oct 3rd 2009, 08:03 AMzhupolongjoeGraph 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 PMPlato
If $\displaystyle T$ is a tree with $\displaystyle n$ vertices the you know that $\displaystyle T$ has $\displaystyle n-1$ edges.

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

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