[Math] Algorithm to determine if a graph has more than one spanning tree

algorithmsgraph theory

I want to create an algorithm that determines if a given weighted undirected graph has a unique MST or not. I found an answer here, but I do not understand it. It says:

You can prove whether it has a unique MST in O(E log(V)).
First find a minimum spanning tree with standard techniques.
Go back to your original tree, and replace all weights with pairs of numbers, the original weight, and then 0 or 1 based on whether or not it is in the MST you found. These pairs of numbers can be added together pairwise, and compared pairwise as well – just like normal numbers.
Now use the standard techniques to find a minimum spanning tree with these funny weights. The MST that you find will be the MST which shares the least edges with your original tree. Thus if there are multiple MSTs, you are guaranteed to find a different one.

Can someone explain this more thoroughly? I don't really understand what we're supposed to be doing after we find out original tree. From what I understand, once we find our original tree, we add $1$ to all the weights that are in the tree and the graph, and 0 if it is not. We then run the MST-finding algorithm again, and if we find a different tree, then we have our answer.

Why does this work?

Thank you.

Best Answer

Suppose that you have a weighted graph $G$ on $n$ vertices with integer weights, and let $W_{MST}(G)$ be the weight of the minimum spanning tree of $G$. This is the same algorithm only using plain-number mapping for simplicity (at the cost of having integer weights, but you can fix that too if you really want). The general intuition is to create an MST, and then discourage the algorithm from using these particular edges by adding a small $\varepsilon$ weight that would change the weight by a negligible amount (at most $(n-1)\cdot \varepsilon$, that is, the number of edges in a tree times $\varepsilon$).

  1. Let $k$ be the any power of $10$ strictly bigger than $n$, for example, $k = 10^{1+\lfloor\log_{10}n\rfloor}$.
  2. Construct graph $G'$ by multiplying all the weights by $k$.
  3. Calculate one particular tree $T = \operatorname{MST}(G')$.
  4. Observe that the weight of $W(T) = k \cdot W_{MST}(G)$.
  5. Form graph $G''$ from $G'$ by adding $1$ to the weight of every edge of $T$.
  6. Observe that $W_{MST}(G') \leq W_{MST}(G'') < W_{MST}(G') + n$, because the tree has at most $n-1$ edges, and to each we added at most $1$.
  7. In particular, due to $n-1 < k$, we have that $$\left\lfloor \frac{W_{MST}(G'')}{k} \right\rfloor = \frac{W_{MST}(G'')}{k} = W_{MST}(G).$$
  8. Observe that any MST of both $G'$ and $G''$ map directly to MSTs of $G$.
  9. Observe that if the MST in $G''$ and MST in $G'$ use the same edges (in particular they map to the same MST in $G$), then $$W_{MST}(G'') = W_{MST}(G') + n-1.$$
  10. As using an edge outside of $T$ is cheaper in $G''$, the above equality is satisfied if and only if there is only one MST in $G$.
  11. In other words, $W_{MST}(G'') \neq W_{MST}(G') + n-1$ implies that you have at least two MSTs in $G$ (one is $T$, and the other one is the MST from $G''$).

I hope this helps $\ddot\smile$

Related Question