Minimum Spanning Tree count given an edge that must be included

2
votes

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 ?

1
algorithmgraph-theoryminimum-spanning-tree
How can include be at the same time not part of? – Dante May Code
thats my question.is there any general form let say we have a tree with n vertices.there is one edge e when include this edge the MST has a cycle and it will not be MST any more. now what i have to do is to make an MST which has this edge e.is there any generic form through which i can find out how many MSTs are possible? – Bushra
@Princess, would you please share a link about what you were saying? – Dante May Code
I don't have any link. That statement is given me as a quiz. I did not find its answer. the answer which sir told is, "If there is an MST with n vertices then there would be n-1 MSTs that include the edge e". but as per my knowledge, its not possible. I saw in a presentation on internet that If we have a tree with 4 vertices then there possible MST would be 8.I am very much confused about this statement. I tried to find answer of this question on internet too but i could not get answer. after then i found the link of this site so i posted my question here. – Bushra
So the question is actually whether If there is an MST with n vertices then there would be n-1 MSTs that include the edge e is right? – Dante May Code

1 Answers

1
votes

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.