Distinct Minimum Weight Spanning Trees

Question

I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider Isomorphic trees(if it is present) as a single minimum weight spanning tree or not while counting the distinct MWSTs because graph is unlabeled.

For example, If I have a graph as :

Now, I have to find the Total number of distinct minimum weight spanning trees(MWST) in the above weighted graph.

I got total $3\times2 =6 $ possibilities of MWSTs but I also found the possibility of Isomorphic trees in these total $6$ MWSTs because graph is unlabeled. For example,the below $2$ MWSTs are Isomorphic in nature for the above given graph.

Similarly , If I have a simple, weighted, undirected and unlabeled graph as :

Now, I got total $2^{2} \times 2^{4} = 64$ MWSTs but If I consider Isomorphism property in a graph then I am getting 2 Isomorphic Trees as :

So, If I consider the possibility of many Isomorphic trees like above in the given graph then total number of distinct MWSTs will be less than $6$ and $64$ in the above 2 cases respectively. But I am not sure whether it is correct or not.

So, My doubt is :- While counting the total number of distinct MWSTs in an unlabeled weighted graph, Should I have to consider Isomorphic MWSTs as a single minimum weight spanning tree or not ?

Answer 1

There could be a few reasonable answers.

The simplest answer is that there are 6 minimum weight spanning trees (MSTs) in the first case and 64 MSTs in the second case. Look, the fact that you have said the same numbers and I can understand you perfectly means that interpretation makes some sense. Indeed, a strict definition/procedure can be given to yield those two numbers, although I will not be doing that here.

Let me proceed with another natural and interesting approach according to the conditions. How can we count distinct distinct MSTs of a given unlabelled weighted graph $G$? Here is one reasonable procedure. Initially we have counted 0 MST. Now someone will present to us the MSTs one at a time together with $G$ to us. Every information that is available should be presented to us accurately, including whether two vertices are connected and what is the weight of each edge and which edge is selected as part of the current MST. How these information will be presented can be arbitrary. Vertices can be labelled arbitrarily. The order of edges presented can be arbitrary. If drawn graphically, the shape of each edge and the location of the each vertex can be arbitrary. Etc. Whenever we can be confident that we are seeing a new MST, we will increase the count by 1. Using this approach, which is probably what you meant by considering "isomorphic MWSTs as a single minimum weight spanning tree", we will count 3 MSTs for the first graph and 20 MSTs for the second graph.

In practice, the second approach is too difficult for us to come up with results that we can understand or that could be beautiful. So, while I like the second approach very much as a challenge, I would suggest that you go with the first approach in a casual setting.

Note that there are a few ambiguities inherent in the question that needs to be defined formally (a.k.a. rigorously) before we can agree what is the way to count. For example, what does it mean by an "unlabelled weighted tree"? Do we require that the same weight be assigned to all edges that could be mapped to each other under an graph isomorphism (which happens to be the cases here)? How will we distinguish two "unlabelled weighted" trees? These questions should have been answered before we can count the number of distinct MSTs in a definitive way.