Edge replacement in spanning forest using a cut

Dependencies:

  1. Spanning forest
  2. Cut in a graph
  3. Deleting edge from tree gives 2 trees
  4. Adding edge between 2 trees gives a tree

Let $C = (S, V-S)$ be a non-trivial cut of an undirected graph $G = (V, E)$. Let $(u, v)$ be an edge that crosses $C$. Let $F$ be a spanning forest of $G$ which does not contain $(u, v)$.

Then there exists an edge $(x, y) \in F$ that crosses $C$ such that $F' = (F - \{(x, y)\}) \cup \{(u, v)\}$ is a spanning forest of $G$.

$w(F') = w(F) - w(x, y) + w(u, v)$. So if $w(u, v) \le w(x, y)$ (which is guaranteed if $(u, v)$ is a light edge for $C$), then $w(F') \le w(F)$.

Proof

Let $C = (S, V-S)$ be a cut of a connected undirected graph $G$. Let $(u, v)$ be an edge crossing $C$. Without loss of generality, assume that $u \in S$ and $v \in V-S$. Let $F$ be a spanning forest of $G$ which does not contain $(u, v)$.

Let $G'$ be the connected component of $G$ which $(u, v)$ belongs to. Let $T$ be the spanning tree of $G'$. Since every pair of vertices in a tree has a unique simple path between them, $u$ and $v$ are connected by a path $p$ in $T$. Since $u \in S$ and $v \in V-S$, there is an edge $(x, y)$ in $p$ such that $x \in S$ and $y \in V-S$. Therefore, $(x, y) \in T \subseteq F$ and $(x, y)$ crosses $C$.

Deleting $(x, y)$ from $T$ breaks $T$ into 2 trees $T_1$ and $T_2$. Adding $(u, v)$ to $T_1 \cup T_2$ results in another tree $T' = (T - \{(x, y)\}) \cup \{(u, v)\}$. Since $T'$ contains all the vertices in $V$, it is a spanning tree of $G'$. Therefore, $F' = (F - \{(x, y)\}) \cup \{(u, v)\} = (F - T) \cup T'$ is a spanning forest of $G$.

Dependency for:

  1. Generic Greedy MSF Growth Algorithm (GGMSFGA)

Info:

Transitive dependencies:

  1. /sets-and-relations/equivalence-classes
  2. /sets-and-relations/relation-composition-is-associative
  3. /sets-and-relations/equivalence-relation
  4. Graph
  5. Cut in a graph
  6. Path in Graph
  7. Tree
  8. Spanning tree
  9. Adding edge between 2 trees gives a tree
  10. Forest
  11. Spanning forest
  12. Bridge in graph
  13. Deleting bridge from graph gives 2 components
  14. Deleting edge from tree gives 2 trees