-\rem
-The proof can be also viewed
-probabilistically: let $X$ be the degree of a vertex of~$G$ chosen uniformly at
-random. Then ${\bb E}X \le 2\varrho$, hence by the Markov's inequality
-${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have
-$\deg(v)\le 4\varrho$.
-
-\algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}%
-\algo
-\algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t$.
-\:$T\=\emptyset$.
-\:$\ell(e)\=e$ for all edges~$e$.
-\:While $n(G)>1$:
-\::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
-\:::Select the lightest edge~$e$ incident with~$v$.
-\:::Contract~$G$ along~$e$.
-\:::$T\=T\cup \{ \ell(e_i) \}$.
-\::Flatten $G$, removing parallel edges and loops.
-\algout Minimum spanning tree~$T$.
-\endalgo
-
-\thm
-When $\cal C$ is a minor-closed class of graphs with density~$\varrho$, the
-Local Bor\o{u}vka's Algorithm with the parameter~$t$ set to~$4\varrho$
-finds the MST of any graph from this class in time $\O(n)$. (The constant
-in the~$\O$ depends on~the class only.)
-
-\proof
-Let us denote by $G_i$, $n_i$ and $m_i$ the graph considered by the
-algorithm at the beginning of the $i$-th iteration of the outer loop,
-and the number of its vertices and edges respectively. As in the proof
-of the previous algorithm (\ref{mstmcc}), we observe that all the $G_i$'s
-are minors of the graph~$G$ given as the input.
-
-For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
-guarantees that at least $n_i/2$ edges get selected in the $i$-th iteration.
-Hence at least a half of the vertices participates in contractions, so
-$n_i\le 3/4\cdot n_{i-1}$. Therefore $n_i\le n\cdot (3/4)^i$ and the algorithm terminates
-after $\O(\log n)$ iterations.
-
-Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
-the trivial cut separating~$v$ from the rest of the graph (see the Blue
-Rule in \ref{rbma}). The steps 6 and~7 therefore correspond to the operation
-described by the Lemma on contraction of MST edges (\ref{contlemma}) and when
-the algorithm stops, $T$~is indeed the minimum spanning tree.
-
-It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have
-$m_i\le \varrho n_i \le \varrho n/2^i$.
-We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
-Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
-over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$.
-Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting
-Bor\o{u}vka's Algorithm (see \ref{contiter}).
-
-The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
-\qed
-
-\rem
-For planar graphs, we can get a sharper version of the low-degree lemma,
-showing that the algorithm works with $t=8$ as well (we got $t=12$ from the
-general version). While this does not change the asymptotic time complexity
-of the algorithm, the constant-factor speedup can still delight the hearts of
-its practical users.
-
-\lemman{Low-degree vertices in planar graphs}%
-Let $G$ be a planar graph with $n$~vertices. Then at least $n/2$ vertices of~$v$
-have degree at most~8.
-
-\proof
-It suffices to show that the lemma holds for triangulations (if there
-are any edges missing, the situation can only get better) with at
-least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$.
-The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
-hence by the same argument as in the previous proof, for at least $n/2$
-vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$.
-\qed
-
-
-
-
-\section{Using Fibonacci heaps}
-\id{fibonacci}