Results 1 to 2 of 2

Math Help - simple graph is a tree?

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    14

    simple graph is a tree?

    Prove that a simple graph is a tree if and only if it is connected but the deletion of any of its edges produces a graph that is not connected.

    Can someone here please help me with this proof? Thanks in advance ...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    From
    Tokyo, Japan
    Posts
    46
    This really depends on the definition of a tree you were given.

    But for example if you were given the definition that a tree is a connected graph without any cycles, it follows straight from the definition that the graph is connected, and if you remove a path between a and b, then no path exists between a and b, because otherwise in the original situation there would exist two paths, and thus a cycle.
    The same argument works for other definitions like a tree is a connected graph with each vertice connected by only ONE path etc.
    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, 04:23 PM
  2. Every connected graph contains a maximal tree
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 4th 2011, 06:44 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 6
    Last Post: November 12th 2010, 07:03 AM
  5. graph + tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 4th 2010, 11:27 PM

Search Tags


/mathhelpforum @mathhelpforum