More of the prolog.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 0cdab6db59aac92ad8fe66c538155ee2f9c01f05..efc4d63238fe433e81007b922e78d9487b477198 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -185,6 +185,18 @@ $T_1$ and $T_2$ must be identical.
 When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
 its unique minimum spanning tree.
 
+The following trivial lemma will be often invaluable:
+
+\lemman{Edge removal}
+Let~$G$ be a~graph with distinct edge weights and $e$ any its edge
+which does not lie in~$\mst(G)$. Then $\mst(G-e) = \mst(G)$.
+
+\proof
+The tree $T=\mst(G)$ is also a~MST of~$G-e$, because every $T$-light
+edge in~$G-e$ is also $T$-light in~$G$. Then we apply the uniqueness of
+the MST of~$G-e$.
+\qed
+
 \paran{Comparison oracles}\id{edgeoracle}%
 To simplify the description of MST algorithms, we will assume that the weights
 of all edges are distinct and that instead of numeric weights we are given a~comparison oracle.