In the proof that Kruskal\'s algorithm produces a minimal spanning tree, we impl

Question

In the proof that Kruskal's algorithm produces a minimal spanning tree, we implicitly used the fact that adding one edge to a tree can produce at most one new circuit. Note that, if a tree T has n vertices, then it has n-1 edges. Adding one edge gives n edges, so the graph graph (call it T') cannot be a tree. Therefore, T' contains at least one circuit. Your task is to finish this up by proving the following theorem: A connected graph has n vertices and n edges. Then the graph contains no more than one circuit. Note: two circuits are the same if they contain the same vertices and the same edges; the order in which you happen to name the vertices is not important. It is possible that mathematical induction can be used to prove this theorem.

Explanation / Answer

Let us use induction to prove this :

Base case : n=3 then one circuit only as number of possible edges are 3C2 = 3 , v1 -> v2 , v2 -> v3 , v3 -> v1

Let this theorem be true for all graphs of n-1 vertices and edges

Let there be a new vertex Vn and a new edge from Vn to Vk.
If there was no circuit before (n-1 vertices and edges case) then none of the edge can be broken to add a edge to Vn otherwise graph will not remain connected.

If there was a circuit before (n-1 vertices and edges case) then only edge from that circuit can be broken to add a edge to Vn otherwise graph will not remain connected.
In that case addition of new edge to Vn may result in new circuit but at the previous circuit .

Hence, Number of circuits in n vertices < Number of circuits in n-1 vertices <= 1

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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