Trees and their complements, proof by induction

May 2010
3
0
Prove using induction that the complement T` of a tree T with n vertices has ((n-1)(n-2))/2 edges, for all integers n>=2

A complement graph (T`) of T is a graph with the same vertices of T but with connected edges only where the original graph(T) doesn't have edges.

HINT:Any tree that has more than one vertex has at least one vertex of degree 1.
I know how induction works but I'm confused as to how to apply it to graphs like trees
 
Last edited:
Oct 2009
95
29
Prove using induction that the complement T` of a tree T with n vertices has ((n-1)(n-2))/2 edges, for all integers n>=2

A complement graph (T`) of T is a graph with the same vertices of T but with connected edges only where the original graph(T) doesn't have edges.

HINT:Any tree that has more than one vertex has at least one vertex of degree 1.
I know how induction works but I'm confused as to how to apply it to graphs like trees

You have to tell us what definition of a tree you are using. This is important because there are several equivalent definitions.

Consider the following definition of a tree:

A graph \(\displaystyle T\) with \(\displaystyle n\) vertices is a tree if and only if \(\displaystyle T\) is connected and \(\displaystyle T\) has \(\displaystyle n-1\) edges.

From the definition I gave above your result follows trivially:

Then \(\displaystyle T'\) must have

\(\displaystyle \binom{n}{2} - (n-1) = (n-2)(n-1)/2\) edges.