Results 1 to 2 of 2

Math Help - (Graph Theory)Prove that graph X is a tree.

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    3

    (Graph Theory)Prove that graph X is a tree.

    Let X be a graph with ONLY one spanning tree. Prove that X is a tree.

    What I proved so far is that X is connected since all graphs with a spanning tree should be connected. All I need to do now is to prove that it's acyclic or has n-1 edges.

    Any leads?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jul 2011
    Posts
    27

    Re: (Graph Theory)Prove that graph X is a tree.

    I propose this steps to prove the contraposition (it's not a complete proof, i let you fill the blank and formalize it all) :

    We suppose X isn't a tree (i.e. has at least one cycle).
    If X isn't connected, it's done (no spanning tree). So we assume that X is connected and choose a spanning tree.

    At least one edge of the cycle isn't an edge of the spanning tree.

    (1) Adding this edge produces at most one cycle. (I think it's even exactly one cycle, i let you prove that.)

    (2) Once this edge E added, let V and V' be the vertices of E. We know (by (1)) that E is involved in a cycle, so are V and V'.
    Removing one of the edges (other than E) adjacent to V or V' and involved in the cycle, we have a spanning tree. (It's clear that the number of edges is n-1, so you just have to prove that it's still connected.)

    (3) We found two spanning tree : done !


    (We just proved the contraposition of your lemma, so your lemma too.)

    I hope it helps.

    --
    Pece
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory:Tree
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 22nd 2011, 05:23 PM
  2. Graph theory: Prove min degree(G_n) >= k
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2011, 09:26 PM
  3. Replies: 6
    Last Post: November 12th 2010, 08:03 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Replies: 0
    Last Post: April 26th 2009, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum