of~$F$ that contains both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest in the cut~$\delta_G(T_1)$
and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
+\looseness=1 %%HACK%%
A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
\:Record~$v$ in the sequence.
\:For each son~$w$ of~$v$:
\::Call $\<ET>(w)$.
-\::Record~$w$.
+\::Record~$v$.
\endalgo
\>A~single tree can have multiple ET-sequences, corresponding to different orders in which the
sons can be enumerated in step~2.
\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes its ET-sequence from $vAwBwCv$ to $wBwCvAw$.
If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
-the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
+the sequence $vwv$ becomes $wvw$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
\em{Joining} the roots of two trees by a~new edge makes their ET-sequences $vAv$ and~$wBw$
combine to $vAvwBwv$. Again, we have to handle the cases when $v$ or~$w$ has degree~1 separately:
(see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$
and that all basic operations including insertion, deletion, search, splitting and joining the trees
run in time $\O(b\log_a n)$ in the worst case.
+\looseness=-1 %%HACK%%
We will use the ET-trees to maintain a~spanning forest of the dynamic graph. The auxiliary data of
each vertex will hold a~list of edges incident with the given vertex, that do not lie in the
\corn{Weighted ET-trees}\id{wtet}%
In weighted ET-trees, the operations \<InsertNontree> and \<DeleteNontree> have time
-complexity $\O(a\log_a n)$. All other operations take the same time as in Theorem
+complexity $\O(a\log_a n)$. All other operations take the same time as indicated by Theorem
\ref{etthm}.
-
%--------------------------------------------------------------------------------
\section{Dynamic connectivity}
increases.
To bring the complexity of the operation \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
-we apply the trick from Example \ref{accel} and store~$F_0$ in a~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
+we apply the trick from Example \ref{accel} and store~$F_0$ in an~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
This does not hurt the complexity of insertions and deletions, but allows for faster queries.
\qed
The best exchanges in~$T_1$ involving $t_1,\ldots,t_{K-1}$ produce~$K-1$ spanning trees
of increasing weights. Any exchange involving $t_K,\ldots,t_n$ produces a~tree
which is heavier or equal than all those trees. (We are ascertained by the Monotone exchange lemma
-that the gain of such exchanges need not be reverted by any later exchanges.)
+that the gain of such exchanges need not be reverted later.)
\qed
\lemma\id{gainb}%