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 ?
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.