(adsbygoogle = window.adsbygoogle || []).push({}); 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph Theory Proof

**Physics Forums | Science Articles, Homework Help, Discussion**