# Trees and their complements, proof by induction

#### jsdieorksw

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:

#### gmatt

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.