# unique MST's of a graph?

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.

-
Welcome to mathSE. Since you are new one comment to your question: Although it is obvious from the context what MST stands for. Please consider explaining your abreviations in the next questions in the beginning. – Julian Kuelshammer Oct 22 '12 at 6:43

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.

-
thank you Michael that explanation is helpful. I think I was on the right track. – revera Oct 22 '12 at 3:23
so this means that there will be 5 unique MST's if we take only 2 edges with same weights. – revera Oct 22 '12 at 3:26
Well, not at the same time. Given the graph and the edge weights, depending on the case, you'll have either $1$ or $2$ minimum spanning trees. – Michael Biro Oct 22 '12 at 3:31
got it :) .This discussion helped in understanding MST's a little better. – revera Oct 22 '12 at 3:37