Prove that a connected undirected graph with n vertices and no cycles must have

Question

Prove that a connected undirected graph with n vertices and no cycles must have exactly n-1
edges. (This kind of a graph is called a tree). (Proof by induction)

Explanation / Answer

Denote the number of vertices in the graph G as n(G) and the number of edges as e(G). Claim: There exists a vertex of degree 1 Proof: If every vertex has degree >=2 then there exists a cycle in the graph which contradicts the hypothesis of the question. Thus the claim is proved. Now we use induction on the number of vertices on the graph. Base case: There are two vertices in the graph, that is n=2 Here its trivial that there will be exactly one edge in the graph, that is, e=1=2-1=n-1. So the base case is settled. Assume the theorem has been proved for all values of n

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.