unique MST's of a graph?

Question

Me and my friend were arguing over how to calculate the number of unique MST's in the following situation: if I have a weighted graph G with E edges and all the edges have unique weights then I know that we can have only 1 unique MST. I was thinking what will be the case if only some of the edges 2 or 3 have same weights then how many minimum spanning trees are possible in such a case? I had the idea that there are three cases if I take exactly 2 edges as having same weight: 1) both the edges are in MST 2)neither of the 2 edges is in MST 3) either of the two is in MST.

but we didnt reached an answer with this approach.

Answer 1

You can argue something like this:

Take a weighted graph $G = (V,E)$, with unique weights $w_2 < w_3 < \dots < w_E$, and equal weights $w_0 = w_1$. Start a minimum spanning tree algorithm (like Kruskal's) and examine the algorithm's actions when edge $e_0$ and edge $e_1$ are reached. There are multiple cases -

1. If $e_0$ and $e_1$ can both be inserted without closing a cycle.
2. If $e_0$ and $e_1$ can both be inserted individually, but they close a cycle together.
3. If $e_0$ cannot be inserted, but $e_1$ can (or vice versa).
4. If neither $e_0$ nor $e_1$ can be inserted.

In cases $1,3$, and $4$, the algorithm treats edges $e_0$ and $e_1$ like uniquely weighted edges (say $w_0$ and $w_1 + \epsilon$), inserts them with the correct procedure, and continues on to find a unique solution.

In case $2$, there are two possible minimum spanning trees, one where $e_0$ was inserted and one where $e_1$ was inserted.