In a lot of proofs in graph theory,it is useful to know various things about the

Question

In a lot of proofs in graph theory,it is useful to know various things about the addition of one new edge to an existing graph For instance, in the proof that Kruskal’s algorithm produces a minimal- weight spanning tree, we needed to add an edge to an existing tree. Without quite saying it, we used the fact that the resulting graph contains exactly one circuit.

To be more explicit about it: If we start with a tree T with n vertices and n 1 edges, and if we add an edge between two existing vertices, we now have n vertices and n edges. The new graph is still connected, but it has too many edges to be a tree; hence, it must contain at least one circuit.

Finish this up by proving the following fact: Theorem: A connected graph has n vertices and n edges. Then the graph contains no more than one simple circuit.

Explanation / Answer

if there are more than one circuit we can remove two edges(each from a circuit) from the graph and keep the graph connected.

Hence graph will be connected with n-2 edges. A contradiction

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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