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

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: