1. Not finding help here? Sign up for a free 30min 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!

Graph Theory Proof

  1. Jun 23, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that a graph is a tree if and only if it has no cycles and the insertion of any new edge always creates exactly one cycle.

    3. The attempt at a solution

    Assume that a graph G is connected and contains no vertices with a degree of zero.

    So would I get my proof by proving that the graph is a tree and it is connected and has n-1 edges which proves it has no cycles and then prove that adding a edge would create a cycle making the first statement false. Does this work?
     
  2. jcsd
  3. Jun 24, 2010 #2
    Two directions. In the first, you have a tree. Facts about trees: they are connected and acyclic. It is a fact that a tree has exactly n-1 edges, but depending on what you are allowed to assume, you may need to prove this. Starting from these facts, you must prove that adding any additional edge will create a cycle. In the second, you have a graph such that the insertion of any edge creates a cycle. You must prove that this graph is a tree, i.e. connected and acyclic.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Graph Theory Proof
  1. Graph Theory Proof (Replies: 21)

  2. Graph theory trail proof (Replies: 11)

  3. Graph Theory Proof (Replies: 3)

Loading...