0
$\begingroup$

Given any undirected connected graph. If we redefine the weight of a spanning tree to the maximum weight of an edge (if the largest weight is 10 the weight of the tree is 10) are there any cases where there minimum spanning tree will be different based on this assumption? By this I mean are there any cases where we can use a more costly route in order to have a lower maximum edge weight?

$\endgroup$
1
$\begingroup$

Yes and no. A spanning tree of minimal total weight must have minimal "heaviest edge" too, but the opposite is not necessarily the case.

Suppose that $A$ and $B$ are both spanning trees in the same graph, but that $A$ has an edge that is heavier than every edge in $B$. Then $A$ cannot have minimal total weight.

To wit, let $(v_1,v_2)$ be the heavy edge in $A$. Removing that edge causes $A$ to fall apart into two trees. Consider the path from $v_1$ and $v_2$ along $B$. It contains at least one edge that will connect the two pieces of $A$ at a lower price than the edge we removed.

On the other hand, in a graph such as

*--7--*--3--*
      |     |
      2     5
      |     |
      *--4--*

every spanning tree has 7 as the heaviest edge, but they have different sums of weights.

$\endgroup$
  • $\begingroup$ Thanks! That's what I was finding when trying to come up with a counterexample, just wanted to be sure. $\endgroup$ – Nick May 6 '15 at 22:10
  • 1
    $\begingroup$ @Nick: beware that the answer was partially wrong at the time of your comment. $\endgroup$ – Henning Makholm May 6 '15 at 22:17

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.