- #1
Magra2118
- 1
- 0
Homework Statement
The complement of T' of a tree T with n vertices has [(n-1)(n-2)]/2 edges, for all integers n greater than or equal to 2.
Homework Equations
Must prove using induction and using Lemma 18.2 which states "any tree that has more than one vertex has at least one vertex of degree 1."
The Attempt at a Solution
Verify the basis case: p(2) [(2-1)(2-2)]/2 = 0, which is true because a tree with two vertices would have to have one edge, there its complement would have 0 edges
assume p(k) to be true: [(k-1)(k-2)]/2
show p(k+1) to be true: [(k+1-1)(k+1-2)]/2 = [(k)(k-1)]/2
Let G be a particular but arbitrarily chosen tree that has k vertices and k-1 edges. Let G' be the complement of tree G. By definition complement, G' have k vertices.
Don't know where to start/go after this!