# Thread: Trees and their complements, proof by induction

1. ## Trees and their complements, proof by induction

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

2. Originally Posted by 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

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 $T$ with $n$ vertices is a tree if and only if $T$ is connected and $T$ has $n-1$ edges.

From the definition I gave above your result follows trivially:

Then $T'$ must have

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