0
$\begingroup$

Given a connected, undirected, weighted graph $G$, the condition

The maximum-weight edge in any cycle of $G$ is unique.

is not necessary for $G$ to have a unique minimum spanning tree (MST).

However, is this condition sufficient for $G$ to have a unique MST?

|cite|improve this question
$\endgroup$
  • $\begingroup$ No. Consider {AB -> 3, BC -> 4, CD -> 3, DA -> 4}. ABC and ADC (and BCD and DAB) are minimal spanning trees. AB = CD and AD = BC. $\endgroup$ – Thumbnail May 29 '17 at 14:36
  • 1
    $\begingroup$ @Thumbnail The graph you use does not satisfy the condition above. You are showing that the condition is not necessary for $G$ to have the unique MST. However, I am wondering whether it is sufficient. $\endgroup$ – hengxin May 30 '17 at 4:22
1
$\begingroup$

Answer My Own Question by attempting to prove that the condition above is sufficient for a graph $G$ to have a unique MST. I am asking for reviews. Thanks in advance.

First, for each cycle, the unique heaviest edge in it must be not in any MST. Consider the remaining graph $G'$, obtained by keeping removing the unique heaviest edges in cycles from $G$. All MSTs are part of $G'$. If we can show that $G'$ is a spanning tree, then $G'$ is the unique MST of $G$.

$G'$ is connected because each edge removed belongs to a cycle when it was removed.
$G'$ is acyclic because we are keeping breaking cycles. Thus, $G'$ is a spanning tree.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I'd say your proof is valid. If you iteratively remove the heaviest edge from each cycle and the resulting graph is a spanning tree then it has to be minimal. The elimination ordering doesn't matter because a cycle won't break until an edge is removed, hence why the resulting graph is unique. $\endgroup$ – Roukah May 30 '17 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.