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 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook