Results 1 to 2 of 2

Math Help - Graph theory: Trees

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Graph theory: Trees

    Let T be a tree of order n. Show that the size of the complement of T (T bar) is the same as the size of K(n-1)

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    Let T be a tree of order n. Show that the size of the complement of T (T bar) is the same as the size of K(n-1)
    If T is a tree with n vertices the you know that T has n-1 edges.

    The complement \overline{T} has \binom{n}{2}-(n-1) edges.

    The graph K_{n-1} has \binom{n-1}{2} edges.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 2nd 2011, 05:39 AM
  2. Graph Theory - Trees and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2010, 11:14 PM
  3. Graph Theory question about trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 02:52 AM
  4. [SOLVED] Graph Theory and Labeled Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2009, 07:10 AM
  5. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2007, 12:29 AM

Search Tags


/mathhelpforum @mathhelpforum