A graph with n vertices is a tree if and only if it has n - 1 edges and has no cycles. Data from Prob. 16 If a graph has no cycles, it must have at least 2 vertices of degree 1 Data from Prob. 18 A tree with n vertices has n - 1 edges. (Proof by induction.)
Chapter 23, PROBLEM SET 23.4 #20
A graph with n vertices is a tree if and only if it has n - 1 edges and has no cycles.
Data from Prob. 16
If a graph has no cycles, it must have at least 2 vertices of degree 1
Data from Prob. 18
A tree with n vertices has n - 1 edges. (Proof by induction.)
This problem has been solved!
Do you need an answer to a question different from the above? Ask your question!
Answer
If G is a tree, it has no cycles, and has n - 1 edges by Prob. 18. Conversely, …View the full answer
Related Book For 
PROBLEM SET 23.2:
PROBLEM SET 23.4:
PROBLEM SET 23.5:
PROBLEM SET 23.6:
PROBLEM SET 23.7:
PROBLEM SET 23.8: