965 views

1 Answer

Best answer
2 2 votes

Depends on the method used to find number of MST's.

If you are using KIRCHOFF's THEOREM, then nothing special (except the theorem itself) is to be kept in mind.

If you are finding them manually using some counting tools (such as P and C etc), then :

1.Any spanning tree of a connected graph with n vertices will have exactly n-1 edges.

2. Look for the vertices which can be reached from multiple paths.Count the number of ways to reach that vertex.

3. Find a cycle(if any) whose edges are necessarily required to be traversed in order to make it an MST. Try to eliminate 1 edge at a time of that cycle and see how many ways are there to use edges of that cycle.

4.If it is a complete a graph that we have formula for number of MST's of a complete graph(google that).

All these points vary on individual basis.One may use them or not.I use these points.

• selected by
Position:
Show:

Related questions

64 64 votes
7 answers 7 answers
36.1k
36.1k views
Arjun asked Feb 7, 2019
36,057 views
Let $G$ be any connected, weighted, undirected graph.$G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight.$G$ has a unique minimum spanning...
1 1 vote
1 1 answer
154
154 views
GO Classes asked Aug 29
154 views
Consider the following statement:For every connected weighted graph $G$, there exists some vertex $v$ such that a shortest path tree rooted at $v$ is identical to a minim...
1 1 vote
1 1 answer
137
137 views
GO Classes asked Aug 26
137 views
Let, $G=(V,E)$ be a connected undirected graph. Edge weights may be negative.We want to choose, $E'\subseteq E$ such that $G'=(V,E')$ is connected and: $\sum_{e\in E'}w(e...
0 0 votes
0 0 answers
857
857 views
Logger_cat17 asked Jul 18, 2024
857 views
What is the maximum number of minimum cost spanning trees possible for this graph? Is there any efficient way to find the maximum number of possible minimum cost spanning...