5
$\begingroup$

$G$ is a connected graph with cost $p:E(G)\to\mathbb{R}$ defined on its edges. Let $e' \in E(G)$ be such that $p(e')<p(e)$ for every $e\in E(G)-\{e'\} $. Is it possible to find two spanning trees of minimium weight, $T_1$, $T_2$ ($T_1 \neq T_2$), such that one of them has $e'$ and the other one doesn't?

$\endgroup$

1 Answer 1

4
$\begingroup$

No.

Every minimum spanning tree of $G$ contains the minimum weighted edge. Suppose not. Then the inclusion of the minimum weighted edge creates a cycle. Remove the maximum weight edge in the cycle to remove the cycle. The resulting tree has lesser total weight (contradicting the fact that the initial minimum spanning tree had minimal weight) and now includes this edge.

$\endgroup$
2
  • $\begingroup$ Thank you so much! $\endgroup$
    – Fabrizio G
    Jul 2, 2020 at 19:22
  • 1
    $\begingroup$ Happy to help :) $\endgroup$ Jul 2, 2020 at 22:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .