Thread: 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

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

From the definition I gave above your result follows trivially:

Then must have

edges.