Fix proof of the local contractive algorithm.

[saga.git] / adv.tex

diff --git a/adv.tex b/adv.tex
index f4dc358d8344eb18b9c629a8615567b20f7d88f2..bf78611bd049ccefe34e60f65a047923b01a11ed 100644 (file)
--- a/adv.tex
+++ b/adv.tex
@@ -194,10 +194,11 @@ 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.
+guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
+have degree at most~$t$. Each selected edge removes one such vertex and
+possibly increases the degree of another, so at least $n_i/4$ edges get selected.
+Hence $n_i\le 3/4\cdot n_{i-1}$ and 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 $\delta(v)$ (see the Blue Rule in \ref{rbma}).