Graph Theory Proof

  • Thread starter pupeye11
  • Start date
  • #1
100
0

Homework Statement



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.

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?
 

Answers and Replies

  • #2
737
0
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.
 

Related Threads on Graph Theory Proof

  • Last Post
Replies
3
Views
708
  • Last Post
Replies
21
Views
6K
  • Last Post
Replies
3
Views
577
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
837
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
0
Views
1K
Top