$T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
either identical to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter we have
-$w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
+$w(f)\ge w(e')$ due to the choice of~$e'$ and all other edges on~$C$ are lighter
than~$e'$ as $e'$ was not $T$-light.
\qed
these edge exchanges must be in fact strictly increasing. On the other hand,
we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
$T_1$ and $T_2$ must be identical.
+\looseness=1 %%HACK%%
\qed
\nota\id{mstnota}%
we do not need the Red rule to explicitly exclude edges.
It remains to show that adding the edges simultaneously does not
-produce a cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
+produce a~cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
loss of generality we can assume that:
$$C=T_1[u_1,v_1]\,v_1u_2\,T_2[u_2,v_2]\,v_2u_3\,T_3[u_3,v_3]\, \ldots \,T_k[u_k,v_k]\,v_ku_1.$$
Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation
of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and we can continue in the same way,
-getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction.
+getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a~contradiction.
(Note that distinctness of edge weights was crucial here.)
\qed
The Jarn\'\i{}k's algorithm computes the MST of a~given graph in time $\O(m\log n)$.
\rem
-We will show several faster implementations in section \ref{iteralg}.
+We will show several faster implementations in Section \ref{iteralg}.
\paran{Kruskal's algorithm}%
The last of the three classical algorithms processes the edges of the
\lemman{Contraction of MST edges}\id{contlemma}%
Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
produced by contracting~$e$ in~$G$, and $\pi$ the bijection between edges of~$G-e$ and
-their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$
+their counterparts in~$G/e$. Then $\mst(G) = \pi^{-1}[\mst(G/e)] + e.$
\proof
% We seem not to need this lemma for multigraphs...
\figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)}
\lemma
-A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a graph isomorphic with $H_{a,k-1}$.
+A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a~graph isomorphic with $H_{a,k-1}$.
\proof
Each vertex is incident with an edge of some distractor, so the algorithm does not select