1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory: a tree and it's complement proof

  1. May 11, 2010 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant 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."

    3. 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!
  2. jcsd
  3. May 12, 2010 #2
    A tree with k+1 edges would have a vertex of degree 1, because of the lemma. If you remove that you get a tree of k edges for wich you assumed p(k) was true.

    How many new edges will adding this vertex add to the complement?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook