Search code examples
algorithmgraph-theoryminimum-spanning-tree

Minimum Spanning Tree count given an edge that must be included


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 ?


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.