= Solution
{c}
Assume throughout (c) that the <graph> is finite and connected, as needed for the asserted spanning <trees>. List its <edge> weights as $w_1<\cdots<w_m$. The stated separation implies $w_{j+1}>2w_j$, so for every $k$,
$$
\sum_{j<k}w_j<w_k\sum_{r=1}^{k-1}2^{-r}<w_k.
$$
Thus the weights form a <superincreasing sequence>. If $A,B$ are distinct <edge> sets, let $e$ be the heaviest <edge> in their <symmetric difference>. Suppose $e\in A$. All other uncancelled <edges> are lighter, so
$$
\sum_{a\in A}w(a)-\sum_{b\in B}w(b)\ge w(e)-\sum_{w(f)<w(e)}w(f)>0.
$$
Therefore different <edge> sets have different total costs. In particular all distinct <spanning trees> have different costs. Since a finite <connected graph> has at least one <spanning tree> and only finitely many choices,
$$
\boxed{\text{the minimum spanning tree exists and is unique}.}
$$
This domination of every collection of smaller <edges> will also be used in (iii).
Back to article page
