Cycles induced by replacement edges contain edge being replaced I am reading the proof of Lemma 4 in Holm, De Lichtenberg and Thorup (2001) - the publication is titled "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity".
Why do the authors conclude that $e \in C_i$?
Consider $G = K_4$, the complete graph of order four, where $V = \{a, b, c, d\}$ and $F = (V(G), \{ab, bc, ad\})$. $F - ab$ is disconnected and $cd$ is a replacement edge for $e = ab$. Then with reference to the authors' argument, which cycle does $cd$ induce i.e. if $e_1 = cd$, then what is $C_1$?
 A: I feel stupid answering the question directly without providing some context, so here is some context for what the paper actually says.
We have a spanning forest $F$ of a graph $G$. An edge $e = ab$ is deleted from $G$, and we want to obtain a spanning forest $F'$ of $G' = G \setminus ab$. Nothing needs to be done when:


*

*$a$ and $b$ are not connected in $G'$; then $F$ is still a spanning forest of $G'$, and we may take $F = F'$.

*$e \notin F$; then $F$ is still a spanning forest of $G'$, and we may, again, take $F = F'$.


In the proof of Lemma 4 of the paper, we're considering the remaining case; $e \in F$, but its endpoints $a$ and $b$ are still connected in $G'$. Then we need to find a replacement edge $e'$ such that $F' = (F \setminus e) \cup e'$ is a spanning forest of $G'$.

Here's now the answer to the question. The definition of the "cycle induced by $e_1$" is the unique cycle in $F \cup e_1$. (Since $F$ is a spanning forest, whenever $e_1$ is an edge of $G$, this cycle exists and is unique.)
The reason we need a replacement edge in the first place is to connect $a$ and $b$: the endpoints of the edge $e$ we deleted. So if $e_1$ is a replacement edge, then there is a path $P_1$ (my notation) from $a$ to $b$ using $e_1$. So $P_1 \cup e$ is a cycle in $F \cup e_1$, and therefore $C_1 = P_1 \cup e$ is the cycle induced by $e_1$. Obviously, this includes $e$.
In your example, if $e_1 = cd$ is a replacement edge for $e = ab$, then $P_1$ is the path $(a, ad, d, dc, c, cb, b)$ and $C_1$ is the cycle $(a, ad, d, dc, c, cb, b, ba)$.
