1
$\begingroup$

This question seems confusing, take the following graph as an example:

enter image description here

In this graph, the minimum spanning tree holds edge weights as $4,5,6$, the maximum value of them is $6$.

There are other spanning trees in this graph as well. For example, edges with weight $5,6,9$, the maximum value of them if $9$, $9>6$.

In fact, for every spanning tree in this graph, the highest weight edge is higher than 6. The minimum value is held by minimum spanning tree.

Is this true for all graphs? Or there is a counterexample.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $m(T)$ denote the maximum weight of an edge in $T$. Your statement is not true in general, for trivial reasons, for instance all weights being the same. However, what is true is that a minimum spanning tree (MST) will minimize $m(T)$ among all spanning trees. The difference between these two statements is that it is not necessarily a strict inequality.

Let us prove that if $T$ is an MST, then $T$ minimizes $m(T)$ among all spanning trees. Suppose not. That is, there exists a spanning tree $T'$ such that $m(T)>m(T')$. Let $e\in T$ be an edge of weight $m(T)$. Now, the graph $T'\cup \{e\}$ contains a cycle $C_e$ (known as the fundamental cycle of $e$ with respect to $T'$). Observe that since $e$ is the only edge of $C_e$ in $T$, all other edges in $C_e$ are in $T'$, and thus have smaller weight. Let $T_1$ and $T_2$ be the two components of $T\backslash \{e\}$. Then there exists $f\in C_e$ distinct from $e$ joining $T_1$ and $T_2$, since $T'$ is a spanning tree. But then $T_1\cup T_2\cup\{f\}$ is a spanning tree of lower weight than $T$, a contradiction.

$\endgroup$

You must log in to answer this question.

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