Question

I am confused about the general form of a minimum spanning tree that includes an edge e that is not part of the minimum spanning tree. My question is:

Let G be a weighted graph with all the edges weight equal to 1. The MST of G does not include an edge e. How many MSTs can be made with the constraint that they include edge e ?

Was it helpful?

Solution

When a graph is unweighted, any spanning tree is a Minimum Spanning Tree.

Identical weight of 1 can be considered the same as unweighted.

In the mathematical field of graph theory Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph.

Number (MST including e) = Number (All MST)<1> - Number (MST without e)<2>

<1> can be derived by Kirchhoff's theorem, and

<2> can be derived by Kirchhoff's theorem after removing e from the graph.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top