D)$ is an ancestor of $\mathit{nca}\\{x,y\\}$, and therefore an ancestor of
$M(B(v)\setminus S)$. This shows that $M(B(v)\setminus
S)=\mathit{nca}(\\{L_{1}(v),\dots,L_{k+1}(v),R_{1}(v),\dots,R_{k+1}(v)\\}\setminus
D)$. ∎

######  Proposition 6.20.

Let $(v_{1},S_{1}),\dots,(v_{N},S_{N})$ be a collection of pairs of vertices
and sets of back-edges, such that $v_{i}\neq r$ and $\emptyset\neq
S_{i}\subseteq B(v_{i})$ for every $i\in\\{1,\dots,N\\}$. Then the values
$M(B(v_{1})\setminus{S_{1}}),\dots,M(B(v_{N})\setminus{S_{N}})$ can be
computed in $O(m+|S_{1}|+\dots+|S_{N}|)$ time in total.

###### Proof.

For every $i\in\\{1,\dots,N\\}$, let $k_{i}=|S_{i}|$. Then we compute the sets
$L(v_{i},v_{i},k_{i+1})$ and $R(v_{i},v_{i},k_{i+1})$, for every
$i\in\\{1,\dots,N\\}$. According to Proposition 6.17 (and the comments after
Algorithm 9), this takes $O(m+|S_{1}|+\dots+|S_{N}|)$ time in total. Then, for
every $i\in\\{1,\dots,N\\}$, we can compute the $L_{1}(v),\dots,L_{k+1}(v)$
and the $R_{1}(v),\dots,R_{k+1}(v)$ values, by gathering the higher endpoints
of the back-edges in $L(v_{i},v_{i},k_{i+1})\cup R(v_{i},v_{i},k_{i+1})$. Let
$D_{i}$ be the set of the higher endpoints of the back-edges in $S_{i}$. Then,
by Lemma 6.19 we have $M(B(v_{i})\setminus
S_{i})=\mathit{nca}(\\{L_{1}(v_{i}),\dots,L_{k+1}(v_{i}),R_{1}(v_{i}),\dots,R_{k+1}(v_{i})\\}\setminus
D_{i})$. (We note that the sets
$\\{L_{1}(v_{i}),\dots,L_{k+1}(v_{i}),R_{1}(v_{i}),\dots,R_{k+1}(v_{i})\\}\setminus
D_{i}$ can be computed in $O(n+|S_{1}|+\dots+|S_{N}|)$ time in total with
bucket-sort.) Notice that
$\mathit{nca}(\\{L_{1}(v_{i}),\dots,L_{k+1}(v_{i}),R_{1}(v_{i}),\dots,R_{k+1}(v_{i})\\}\setminus
D_{i})$ can be broken up into $O(k_{i})$ $\mathit{nca}$ queries. Thus, we can
compute all values $M(B(v_{i})\setminus S_{i})$ with the use of
$O(k_{1}+\dots+k_{N})=O(|S_{1}|+\dots+|S_{N}|)$ $\mathit{nca}$ queries. By
[20] or [3], we know that there is a linear-time preprocessing of $T$, so that
we can answer a collection of $N^{\prime}$ $\mathit{nca}$ queries in
$O(N^{\prime})$ time in total. We conclude that the values
$M(B(v_{1})\setminus{S_{1}}),\dots,M(B(v_{N})\setminus{S_{N}})$ can be
computed in $O(m+|S_{1}|+\dots+|S_{N}|)$ time in total. ∎

###  6.7 Two lemmata concerning paths

######  Lemma 6.21.

Let $u$ and $v$ be two vertices, and let $P$ be a path in $G$ from $u$ to $v$.
Then, $P$ passes from an ancestor of $\mathit{nca}\\{u,v\\}$.

###### Proof.

Let $w$ be the lowest vertex that is used by $P$. Let us suppose, for the sake
of contradiction, that $w$ is not an ancestor of $\mathit{nca}\\{u,v\\}$.
Then, either $w$ is not an ancestor of $u$, or $w$ is not an ancestor of $v$.
Let us assume w.l.o.g. that $w$ is not an ancestor of $u$. Since $u$ is not a
descendant of $w$, we may consider the first predecessor $z$ of $w$ in $P$
that is not a descendant of $w$. Let $z^{\prime}$ be the successor of $z$ in
$P$. Then, we have that $P$ uses the edge $(z,z^{\prime})$, and $z^{\prime}$
is a descendant of $w$. Let us suppose, first, that $(z,z^{\prime})$ is a
tree-edge. Then, since $z^{\prime}$ is a descendant of $w$, but $z$ is not, we
have that $z$ cannot be a child of $z^{\prime}$. Thus, $z$ is the parent of
$z^{\prime}$. But since $z^{\prime}$ is a descendant of $w$ and its parent is
not, we have that $z^{\prime}=w$, and therefore $z$ is the parent of $w$. But
this contradicts the minimality of $w$. Thus, we have that $(z,z^{\prime})$ is
a back-edge. Then, since $z^{\prime}$ is a descendant of $w$, but $z$ is not,
we have that $z$ cannot be a descendant of $z^{\prime}$, and therefore it is
an ancestor of $z^{\prime}$. Then, $z^{\prime}$ is a common descendant of $w$
and $z$, and therefore $w$ and $z$ are related as ancestor and descendant. But
since $z$ is not a descendant of $w$, it must be a proper ancestor of $w$, and
therefore $z<w$. This again contradicts the minimality of $w$. Thus, our
initial supposition cannot be true, and therefore $w$ is an ancestor of
$\mathit{nca}\\{u,v\\}$. ∎

######  Lemma 6.22.

Let $u$ be a vertex and let $v$ be a proper ancestor of $u$. Let $P$ be a path
that starts from a descendant of $u$ and ends in $v$. Then, the first
occurrence of an edge that is used by $P$ and leads outside of the subtree of
$u$ is either a back-edge that leaps over $u$ or the tree-edge $(u,p(u))$.

###### Proof.

Let $(x,y)$ be the first occurrence of an edge that is used by $P$ and leads
outside of the subtree of $u$. We may assume w.l.o.g. that $x$ is a descendant
of $u$ and $y$ is not a descendant of $u$. Then, we have that $y$ is not a
descendant of $x$, because otherwise it would be a descendant of $u$. Suppose
first that $(x,y)$ is a tree-edge. Then, since $y$ is not a descendant of $x$,
it must be the parent of $x$. Thus, since $x$ is a descendant of $u$ but its
parent is not, we have that $x=u$ and therefore $y=p(u)$. Now let us suppose
that $(x,y)$ is a back-edge. Then, since $y$ is not a descendant of $x$, it
must be a proper ancestor of $x$. Thus, $x$ is a common descendant of $u$ and
$y$, and therefore $u$ and $y$ are related as ancestor and descendant. Then,
since $y$ is not a descendant of $u$, we have that $y$ is a proper ancestor of
$u$. This shows that $(x,y)$ is a back-edge that leaps over $u$. ∎

###  6.8 An oracle for back-edge queries

Our goal in this section is to prove the following.

######  Lemma 6.23.

Let $T$ be a DFS-tree of a connected graph $G$. We can construct in linear
time a data structure of size $O(n)$ that we can use in order to answer in
constant time queries of the form: given three vertices $u,v,w$, such that $u$
is a proper descendant of $v$, and $v$ is a proper descendant of $w$, is there
a back-edge $(x,y)\in B(v)\setminus B(u)$ such that $y\leq w$?

###### Proof.

First we compute the $\mathit{low}$ points of all vertices. This takes linear
time. Then we compute, for every vertex $v$ that is not a leaf, a child $c(v)$
of $v$ that has the lowest $\mathit{low}$ point among all the children of $v$
(breaking ties arbitrarily). We call this the $\mathit{low}$ child of $v$.
Then, starting from any vertex $v$ that is either $r$ or a vertex that is not
the $\mathit{low}$ child of its parent, we consider the path that starts from
$v$ and ends in a leaf by following the $\mathit{low}$ children. In other
words, this is the path $v,c(v),c(c(v)),\dots$. Notice that every vertex $v$
of $G$ belongs to precisely one such path. We call this the $\mathit{low}$
path that contains $v$, and we maintain a pointer from $v$ to the
$\mathit{low}$ path that contains it. Furthermore, we consider those paths
indexed, starting from their lowest vertex. In other words, if
$v,c(v),c(c(v)),\dots$ is a $\mathit{low}$ path, then $v$ has index $1$,
$c(v)$ has index $2$, and so on, on this path. We also maintain, for every
vertex $v$, a pointer to the index of $v$ on the $\mathit{low}$ path that
contains it.

Now, for every vertex $v$, we compute a value $m(v)$ that is defined as
follows. If $v$ has less than two children, then $m(v):=l(v)$. Otherwise, let
$c_{1},\dots,c_{k}$ be the list of the children of $v$, excluding $c(v)$.
Then,
$m(v):=\mathit{min}\\{l(v),\mathit{low}(c_{1}),\dots,\mathit{low}(c_{k})\\}$.
Notice that the $m$ values of all vertices can be easily computed in total
linear time. Now, for every $\mathit{low}$ path, we initialize a data
structure for answering range-minimum queries w.r.t. the $m$ values. (We
consider a $\mathit{low}$ path as an array, corresponding to the indexes of
its vertices.) More precisely, for every $\mathit{low}$ path $P$ we initialize
a range-minimum query data structure $\mathit{RMQ_{P}}$. We can use
$\mathit{RMQ_{P}}$ in order to answer queries of the form: given two vertices
$u$ and $v$ on $P$ with indices $i$ and $j$, respectively, such that $i\leq
j$, return the minimum of $m(u_{1}),\dots,m(u_{j-i+1})$, where
$u_{1},\dots,u_{j-i+1}$ is the set of the vertices on $P$ with indices
$i,i+1,\dots,j$. Using the RMQ data structure described, e.g., in [2], the
initialization of all those data structures takes $O(n)$ time in total
(because the total size of the $\mathit{low}$ paths is $O(n)$), and every
range-minimum query on every such data structure can be answered in $O(1)$
worst-case time. This completes the description of the data structure and its
construction.

Now let $u,v,w$ be three vertices such that $u$ is a proper descendant of $v$,
and $v$ is a proper descendant of $w$. We will show how we can determine in
constant time whether there is a back-edge $(x,y)\in B(v)\setminus B(u)$ such
that $y\leq w$. First, suppose that $\mathit{low}(v)>w$. Then we know that
there is no back-edge $(x,y)\in B(v)$ such that $y\leq w$, and we are done. So
let us assume that $\mathit{low}(v)\leq w$. If $l(v)\leq w$, then $(v,l(v))$
is a back-edge in $B(v)\setminus B(u)$ such that $l(v)\leq w$, and we are
done. So let us assume that $l(v)>w$.

First, suppose that $u$ does not belong to the same $\mathit{low}$ path as
$v$. Then we claim that there is a proper descendant $c^{\prime}$ of $v$ on
the $\mathit{low}$ path $P$ that contains $v$ such that $l(c^{\prime})\leq w$.
To see this, let us assume the contrary. Now, since $l(v)>w$ and
$\mathit{low}(v)\leq w$, we have that $\mathit{low}(c(v))\leq w$ (because
$c(v)$ has the lowest $\mathit{low}$ point among all the children of $v$).
Then, by assumption, we have $l(c(v))>w$. Thus, since $\mathit{low}(c(v))\leq
w$, we have that $c(c(v))$ exists, and $\mathit{low}(c(c(v)))\leq w$. Then,
again by assumption, we have $l(c(c(v)))>w$. Therefore, since
$\mathit{low}(c(c(v)))\leq w$, we have that $c(c(c(v)))$ exists, and
$\mathit{low}(c(c(c(v))))\leq w$. We can see that this process must continue
endlessly, in contradiction to the fact that the graph contains a finite
number of vertices. Thus, there is indeed a proper descendant $c^{\prime}$ of
$v$ on $P$ such that $l(c^{\prime})\leq w$. Then we can see that
$(c^{\prime},l(c^{\prime}))$ is a back-edge in $B(v)\setminus B(u)$ such that
$l(c^{\prime})\leq w$, and we are done.

So let us assume that $u$ and $v$ belong to the same $\mathit{low}$ path $P$.
Let $i$ be the index of $v$ on $P$, and let $j$ be the index of $p(u)$ on $P$.
(We note that $i\leq j$.) Let $m^{\prime}$ be the answer to the range-minimum
query on $\mathit{RMQ_{P}}$ on the range $[i,j]$. Then we claim that there is
a back-edge $(x,y)\in B(v)\setminus B(u)$ such that $y\leq w$ if and only if
$m^{\prime}\leq w$. So let us suppose, first, that there is a back-edge
$(x,y)\in B(v)\setminus B(u)$ such that $y\leq w$. Then $x$ is a descendant of
$v$, but not a descendant of $u$. Now let $z$ be the maximum vertex on
$T[v,p(u)]$ (i.e, the one closest to $p(u)$) such that $x$ is a descendant of
$z$. Then, we have that either $x=z$, or $x$ is a descendant of a child
$c^{\prime}$ of $z$ such that $c^{\prime}\neq c(z)$ (since all the vertices on
$T[v,p(u)]$ are part of the $\mathit{low}$ path that contains $u$ and $v$). If
$x=z$, then we have that $l(z)\leq y\leq w$, and therefore $m(z)\leq w$.
Therefore, since $m^{\prime}\leq m(z)$, we have $m^{\prime}\leq w$, as
desired. Otherwise, suppose that $x$ is a descendant of a child $c^{\prime}$
of $z$ such that $c^{\prime}\neq c(z)$. Then, we have that $(x,y)\in
B(c^{\prime})$, and therefore $\mathit{low}(c^{\prime})\leq y\leq w$. Then,
since $m(z)\leq\mathit{low}(c^{\prime})$, we have that $m(z)\leq w$. And since
$m^{\prime}\leq m(z)$, this shows that $m^{\prime}\leq w$.

Conversely, let us suppose that $m^{\prime}\leq w$. There is a vertex $z$ on
the tree-path $T[v,p(u)]$ such that $m^{\prime}=m(z)$. Then, we have that
either $m^{\prime}=l(z)$, or there is a child $c^{\prime}$ of $z$, with
$c^{\prime}\neq c(z)$, such that $\mathit{low}(c^{\prime})=m^{\prime}$. If
$m^{\prime}=l(z)$, then, since $m^{\prime}\leq w$ and $w$ is a proper ancestor
of $v$, we have that there is a back-edge $(z,l(z))$. Then we have that
$(z,l(z))\in B(v)$, but $(z,l(z))\notin B(u)$ (since $z$ is a proper ancestor
of $u$). Thus, $(z,l(z))$ is the desired back-edge. Otherwise, suppose that
there is a child $c^{\prime}$ of $z$, with $c^{\prime}\neq c(z)$, such that
$\mathit{low}(c^{\prime})=m^{\prime}$. Then, there is a back-edge $(x,y)\in
B(c^{\prime})$ such that $y=\mathit{low}(c^{\prime})$. Since
$\mathit{low}(c^{\prime})=m^{\prime}\leq w$, we can see that $(x,y)\in B(v)$.
But since $c^{\prime}$ and $c(z)$ are two different children of $z$, we have
that $x$ is cannot be a descendant of $u$ (because $u$ is a descendant of
$c(z)$ and $x$ is a descendant of $c^{\prime}$), and therefore we have
$(x,y)\notin B(u)$. Thus, $(x,y)$ is a back-edge in $B(v)\setminus B(u)$ such
that $y\leq w$.

This concludes the method by which we can determine in constant time whether
there exists a back-edge $(x,y)\in B(v)\setminus B(u)$ such that $y\leq w$.
This process is shown in Algorithm 10. ∎

1 if  _$\mathit{low}(v) >w$_ then return false

2 if  _$l(v)\leq w$_ then return true

3 if  _$u$ and $v$ do not belong to the same $\mathit{low}$ path_ then return
true

4 let $P$ be the $\mathit{low}$ path that contains $u$ and $v$

5 let $i$ be the index of $v$ on $P$, and let $j$ be the index of $p(u)$ on
$P$

6 let $m^{\prime}$ be the answer to the range-minimum query on
$\mathit{RMQ_{R}}$ on the range $[i,j]$

7 if  _$m^{\prime}\leq w$_ then return true

8 return false

Algorithm 10 Determine whether there is a back-edge $(x,y)\in B(v)\setminus
B(u)$ such that $y\leq w$, where $u$ is a proper descendant of $v$, and $v$ is
a proper descendant of $w$

###  6.9 Segments of vertices that have the same $\mathit{high}$ point

Throughout this section, we assume that $G$ is a $3$-edge-connected graph.
According to Proposition 6.8, this implies that $|B(v)|>2$ for every vertex
$v\neq r$, and therefore the $\mathit{high}_{1}$ and $\mathit{high}_{2}$
points of $v$ are defined.

Let $x$ be a vertex of $G$, and let $H(x)$ be the list of all vertices $v\neq
r$ such that $\mathit{high}(v)=x$, sorted in decreasing order. For a vertex
$v\in H(x)$, we let $S(v)$ denote the segment of $H(x)$ that contains $v$ and
is maximal w.r.t. the property that its elements are related as ancestor and
descendant. The collection of those segments constitutes a partition of
$H(x)$, as shown in the following.

######  Lemma 6.24.

Let $x$ be a vertex. Then, the collection $\mathcal{S}$ of all segments of
$H(x)$ that are maximal w.r.t. the property that their elements are related as
ancestor and descendant is a partition of $H(x)$.

###### Proof.

Every vertex $v\in H(x)$ is contained in $S(v)\in\mathcal{S}$, and therefore
the collection of all segments in $\mathcal{S}$ covers $H(x)$. Now let $S$ and
$S^{\prime}$ be two distinct segments in $\mathcal{S}$. Let us suppose, for
the sake of contradiction, that $S\cap S^{\prime}\neq\emptyset$. Then there is
a vertex $z\in S\cap S^{\prime}$.

We will show that all vertices in $S\cup S^{\prime}$ are related as ancestor
and descendant. So let $u$ and $u^{\prime}$ be two vertices in $S\cup
S^{\prime}$. If both $u$ and $u^{\prime}$ are either in $S$ or in
$S^{\prime}$, then we have that $u$ and $u^{\prime}$ are related as ancestor
and descendant. So let assume w.l.o.g. that $u\in S$ and $u^{\prime}\in
S^{\prime}$. Since $u,z\in S$, we have that $u$ and $z$ are related as
ancestor and descendant. Also, since $u^{\prime},z\in S^{\prime}$, we have
that $u^{\prime}$ and $z$ are related as ancestor and descendant. Thus, we
have the following cases to consider: either $(1)$ both $u$ and $u^{\prime}$
are ancestors of $z$, or $(2)$ one of $u$ and $u^{\prime}$ is an ancestor of
$z$, and the other is a descendant of $z$, or $(3)$ both $u$ and $u^{\prime}$
are descendants of $z$.

In case $(1)$, we have that $z$ is a common descendant of $u$ and
$u^{\prime}$, and therefore $u$ and $u^{\prime}$ are related as ancestor and
descendant. In case $(2)$, we may assume w.l.o.g. that $u$ is an ancestor of
$z$, and $u^{\prime}$ is a descendant of $z$. Then, we obviously have that $u$
is an ancestor of $u^{\prime}$ (due to the transitivity of the ancestry
relation). So let us consider case $(3)$. This implies that $u\geq z$ and
$u^{\prime}\geq z$. If $u\geq u^{\prime}$, then we have $u\geq u^{\prime}\geq
z$. Then, since $H(x)$ is sorted in decreasing order and $S$ is a segment of
$H(x)$ and $u,z\in S$, we have $u^{\prime}\in S$. Then, $u\geq u^{\prime}$
implies that $u^{\prime}$ is an ancestor of $u$. Otherwise, supppose that
$u<u^{\prime}$. Then we have $u^{\prime}>u\geq z$. Then, since $H(x)$ is
sorted in decreasing order and $S^{\prime}$ is a segment of $H(x)$ and
$u^{\prime},z\in S^{\prime}$, we have $u\in S^{\prime}$. Then, $u<u^{\prime}$
implies that $u$ is a proper ancestor of $u^{\prime}$. Thus, in any case we
have shown that $u$ and $u^{\prime}$ are related as ancestor and descendant.

Now we will show that $S\cup S^{\prime}$ is a segment of $H(x)$. So let us
suppose, for the sake of contradiction, that $S\cup S^{\prime}$ is not a
segment of $H(x)$. Since $H(x)$ is sorted in decreasing order, this means that
there are two vertices $u$ and $u^{\prime}$ in $S\cup S^{\prime}$, with
$u>u^{\prime}$, and a vertex $w\in H(x)$, such that $u>w>u^{\prime}$ and
$w\notin S\cup S^{\prime}$. Notice that we cannot have that both $u$ and
$u^{\prime}$ are either in $S$ or in $S^{\prime}$, because $S$ and
$S^{\prime}$ are segments of $H(x)$, and therefore $u>w>u^{\prime}$ implies
that $w\in S$ or $w\in S^{\prime}$, respectively. Thus, we may assume w.l.o.g.
that $u\in S$ and $u^{\prime}\in S^{\prime}$. Since $u$ and $z$ are in $S$, we
have that $u$ and $z$ are related as ancestor and descendant. First, let us
suppose that $z$ is a descendant of $u$. This implies that $z\geq u$. Thus, we
have $z\geq u>w>u^{\prime}$. Since $S^{\prime}$ is a segment of $H(x)$ that
contains both $z$ and $u^{\prime}$, this implies that $w\in S^{\prime}$, a
contradiction. Thus, we have that $z$ is a proper ancestor of $u$, and
therefore $u>z$. Since $u^{\prime}$ and $z$ are in $S^{\prime}$, we have that
$u^{\prime}$ and $z$ are related as ancestor and descendant. Let us suppose
that $u^{\prime}$ is a descendant of $z$. This implies that $u^{\prime}\geq
z$. Then, we have $u>w>u^{\prime}\geq z$. Since $S$ is a segment of $H(x)$
that contains both $u$ and $z$, this implies that $w\in S$, a contradiction.
Thus, we have that $u^{\prime}$ is a proper ancestor of $z$, and therefore
$z>u^{\prime}$. Thus, since $u>w>u^{\prime}$ and $u>z>u^{\prime}$, we have
that either $u>w\geq z$ or $z\geq w>u^{\prime}$. Any of those cases implies
that either $w\in S$ or $w\in S^{\prime}$, since $S$ and $S^{\prime}$ are
segments of $H(x)$. A contradiction. This shows that $S\cup S^{\prime}$ is a
segment of $H(x)$.

Thus, we have shown that $S\cup S^{\prime}$ is a segment of $H(x)$ with the
property that its elements are related as ancestor and descendant. But since
$S\neq S^{\prime}$, this contradicts the maximality of both $S$ and
$S^{\prime}$ with this property. We conclude that the segments in
$\mathcal{S}$ partition $H(x)$. ∎

For every vertex $x$, we will need to compute the collection of the segments
of $H(x)$ that are maximal w.r.t. the property that their elements are related
as ancestor and descendant. This can be done with a straightforward method
that is shown in Algorithm 11. The idea is to traverse the list $H(x)$, and
greedily collect all consecutive vertices that are related as ancestor and
descendant in order to get a segment. The proof of correctness in given in
Lemma 6.25.

1 let $\mathcal{S}\leftarrow\emptyset$

2 let $z$ be the first element of $H(x)$

3 while  _$z\neq\bot$_ do

4 let $S\leftarrow\\{z\\}$

5 let $z^{\prime}\leftarrow\mathit{next}_{\mathit{H(x)}}(z)$

6 while  _$z^{\prime}\neq\bot$ and $z^{\prime}$ is an ancestor of $z$_ do

7 insert $z^{\prime}$ into $S$

8 $z^{\prime}\leftarrow\mathit{next}_{\mathit{H(x)}}(z^{\prime})$

9

10 end while

11 insert $S$ into $\mathcal{S}$

12 $z\leftarrow z^{\prime}$

13

14 end while

Algorithm 11 Compute the collection $\mathcal{S}$ of the segments of $H(x)$
that are maximal w.r.t. the property that their elements are related as
ancestor and descendant

######  Lemma 6.25.

Let $x$ be a vertex. Then, Algorithm 11 correctly computes the collection
$\mathcal{S}$ of the segments of $H(x)$ that are maximal w.r.t. the property
that their elements are related as ancestor and descendant. The running time
of Algorithm 11 is $O(|H(x)|)$.

###### Proof.

The while loop in Line 11 begins the processing of $H(x)$ from its first
vertex $z$. Then, the while loop in Line 11 collects all the consecutive
successors $z^{\prime}$ of $z$ that are ancestors of $z$, and stops until it
reaches a vertex $z^{\prime}$ that is not an ancestor of $z$. Let $S$ be the
resulting set (in Line 11). Then, we have that all vertices in $S$ have $z$ as
a common descendant, and therefore all of them are related as ancestor and
descendant. Furthermore, by construction, $S$ is a segment of $H(x)$. Then,
notice that $S$ is a maximal segment of $H(x)$ with the property that its
elements are related as ancestor and descendant, because the successor of the
lowest element in $S$ is not an ancestor of $z$, and therefore it is not
related as ancestor and descendant with $z$ (because, if it was, it would be
an ancestor of $z$, due to the ordering of $H(x)$). By Lemma 6.24, we have
that no other segment of $\mathcal{S}$ intersects with $S$. Thus, it is proper
to move on to the processing of $z^{\prime}$, and always move forward in
processing the vertices of $H(x)$. Thus, we can see that the while loop in
Line 11 correctly computes the segment $S(z)$, for every $z$ that it
processes, and every vertex in $H(x)$ will be inserted in such a segment
eventually (either at the beginning of the while loop of Line 11 in Line 11,
or by the while loop of Line 11 in Line 11). It is easy to see that the number
of steps performed by Algorithm 11 is $O(|H(x)|)$. ∎

For every vertex $x$, we also define the list $\widetilde{H}(x)$ that consists
of all vertices $v\neq r$ such that either $\mathit{high}_{1}(v)=x$ or
$\mathit{high}_{2}(v)=x$, sorted in decreasing order. Notice that, for every
vertex $v\neq r$, there are at most two distinct $x$ and $x^{\prime}$ such
that $v\in\widetilde{H}(x)$ and $v\in\widetilde{H}(x^{\prime})$. More
precisely, if a vertex $v\neq r$ satisfies that
$\mathit{high}_{1}(v)\neq\mathit{high}_{2}(v)$, then $v$ belongs to both
$\widetilde{H}(\mathit{high}_{1}(v))$ and
$\widetilde{H}(\mathit{high}_{2}(v))$. But there is no other set of the form
$\widetilde{H}(x)$ that contains $v$. Thus, the collection
$\\{\widetilde{H}(x)\mid x\mbox{ is a vertex}\\}$ has total size $O(n)$. For
every vertex $v\neq r$, we let $\widetilde{S}_{1}(v)$ denote the segment of
$\widetilde{H}(\mathit{high}_{1}(v))$ that contains $v$ and is maximal w.r.t.
the property that its elements are related as ancestor and descendant.
Similarly, we let $\widetilde{S}_{2}(v)$ denote the segment of
$\widetilde{H}(\mathit{high}_{2}(v))$ that contains $v$ and is maximal w.r.t.
the property that its elements are related as ancestor and descendant. We can
see that the collection of the segments of $\widetilde{H}(x)$ that are maximal
w.r.t. the property that their elements are related as ancestor and descendant
constitutes a partition of $\widetilde{H}(x)$. The proof of this property is
precisely the same as in Lemma 6.24, because it only relies on the fact that
$\widetilde{H}(x)$ is sorted in decreasing order. Furthermore, we can apply a
procedure as that shown in Algorithm 11, in order to compute the collection of
all those maximal segments in $O(|\widetilde{H}(x)|)$ time. We state this
result in the following lemma, which has the same proof as Lemma 6.25.

######  Lemma 6.26.

Let $x$ be a vertex. Then, in $O(|\widetilde{H}(x)|)$ time, we can compute the
collection of the segments of $\widetilde{H}(x)$ that are maximal w.r.t. the
property that their elements are related as ancestor and descendant.

###### Proof.

We can use Algorithm 11, where we have replaced every occurrence of “$H(x)$”
with “$\widetilde{H}(x)$”. The proof of correctness is the same as in Lemma
6.25. ∎

Since every vertex $v\neq r$ belongs to at most two sets of the form
$\widetilde{H}(x)$, for a vertex $x$, the collection
$\bigcup{\\{\mathcal{S}(x)\mid x\mbox{ is a vertex }\\}}$, where
$\mathcal{S}(x)$ is the collection of the segments of $\widetilde{H}(x)$ that
are maximal w.r.t. the property that their elements are related as ancestor
and descendant, has total size $O(n)$. That is,
$\sum_{x}{\sum_{S\in\mathcal{S}(x)}|S|}=O(n)$.

We conclude this section with the following lemma, which shows that the
vertices in every segment from $\mathcal{S}(x)$ are sorted in decreasing order
w.r.t. their $\mathit{low}$ point.

######  Lemma 6.27.

Let $x$ be a vertex, and let $u$ and $v$ be two vertices in $\widetilde{H}(x)$
such that $u$ is a descendant of $v$. Then
$\mathit{low}(u)\geq\mathit{low}(v)$.

###### Proof.

Since $u\in\widetilde{H}(x)$, we have that either $\mathit{high}_{1}(u)=x$ or
$\mathit{high}_{2}(u)=x$. Since $v\in\widetilde{H}(x)$, we have that either
$\mathit{high}_{1}(v)=x$ or $\mathit{high}_{2}(v)=x$. In either case then, we
have that $x$ is a proper ancestor of $v$.

Let us suppose first that $\mathit{high}_{1}(u)=x$. Let $(z,w)$ be a back-edge
in $B(u)$. Then $z$ is a descendant of $u$, and therefore a descendant of $v$.
Furthermore, we have that $w$ is an ancestor of $\mathit{high}_{1}(u)$, and
therefore an ancestor of $x$, and therefore a proper ancestor of $v$. This
shows that $(z,w)\in B(v)$. Due to the generality of $(z,w)\in B(u)$, this
implies that $B(u)\subseteq B(v)$. From this we infer that
$\mathit{low}(u)\geq\mathit{low}(v)$.

Now let us suppose that $\mathit{high}_{1}(u)\neq x$. This implies that
$\mathit{high}_{2}(u)=x$. Let $(z,w)$ be a back-edge in
$B(u)\setminus\\{e_{\mathit{high}}(u)\\}$ (such a back-edge exists, because
the graph is $3$-edge-connected, and therefore $|B(u)|>1$). Then, we have that
$z$ is a descendant of $u$, and therefore a descendant of $v$. Furthermore,
$w$ is an ancestor of $\mathit{high}_{2}(u)$, and therefore an ancestor of
$x$, and therefore a proper ancestor of $v$. This shows that $(z,w)\in B(v)$.
Due to the generality of $(z,w)\in B(u)\setminus\\{e_{\mathit{high}}(u)\\}$,
this implies that $B(u)\setminus\\{e_{\mathit{high}}(u)\\}\subseteq B(v)$.
Since $\mathit{high}_{1}(u)\neq x$ and $\mathit{high}_{2}(u)=x$, we have
$\mathit{high}_{1}(u)\neq\mathit{high}_{2}(u)$. This implies that
$\mathit{high}_{1}(u)>\mathit{high}_{2}(u)$, and therefore
$\mathit{low}(u)<\mathit{high}_{1}(u)$. Thus, the $\mathit{low}$ point of $u$
is given by the lowest lower endpoint of all back-edges in
$B(u)\setminus\\{e_{\mathit{high}}(u)\\}$. Since this set is a subset of
$B(v)$, we conclude that $\mathit{low}(v)\leq\mathit{low}(u)$. ∎

##  7 Connectivity queries under $4$ edge failures

Our goal in this section is to prove the following.

######  Proposition 7.1.

Let $G$ be a connected graph with $n$ vertices and $m$ edges. Then there is a
data structure with size $O(n)$, that we can use in order to answer
connectivity queries in the presence of at most four edge-failures in constant
time. Specifically, given an edge-set $E^{\prime}$ with $|E^{\prime}|\leq 4$,
and two vertices $x$ and $y$, we can determine whether $x$ and $y$ are
connected in $G\setminus E^{\prime}$ in $O(1)$ time. The data structure can be
constructed in $O(m+n)$ time.

Let $G$ be a connected graph, and let $T$ be a rooted spanning tree of $G$.
Let $E^{\prime}$ be a set of edges of $G$, and let $k$ be the number of tree-
edges in $E^{\prime}$. Then $T\setminus E^{\prime}$ is split into $k+1$
connected components. Every connected component of $T\setminus E^{\prime}$ is
a subtree of $T$, and the connectivity in $G\setminus E^{\prime}$ can be
reduced to the connectivity of those subtrees as follows. Let $x$ and $y$ be
two vertices of $G$, let $C_{1}$ be the connected component of $T\setminus
E^{\prime}$ that contains $x$, and let $C_{2}$ be the connected component of
$T\setminus E^{\prime}$ that contains $y$. Then we have that $x$ and $y$ are
connected in $G\setminus E^{\prime}$ if and only if $C_{1}$ and $C_{2}$ are
connected in $G\setminus E^{\prime}$. In particular, since $C_{1}$ and $C_{2}$
are subtrees of the rooted tree $T$, we can consider the roots $r_{1}$ and
$r_{2}$ of $C_{1}$ and $C_{2}$ as representatives of $C_{1}$ and $C_{2}$,
respectively. Then, we have that $x$ and $y$ are connected in $G\setminus
E^{\prime}$ if and only if $r_{1}$ and $r_{2}$ are connected in $G\setminus
E^{\prime}$. Thus, the connectivity relation of $G\setminus E^{\prime}$ can be
captured by the connectivity relation of the roots of the connected components
of $T\setminus E^{\prime}$ in $G\setminus E^{\prime}$. In order to capture
this connectivity relation, we introduce the concept of a _connectivity graph_
for $G\setminus E^{\prime}$.

######  Definition 7.2.

Let $T$ be a fixed rooted spanning tree of $G$, and let $E^{\prime}$ be a set
of edges of $G$. Let $\\{C_{1},\dots,C_{k}\\}$ be the set of the connected
components of $T\setminus E^{\prime}$. Thus, for every $i\in\\{1,\dots,k\\}$,
$C_{i}$ is a rooted subtree of $T$, and let $r_{i}$ be its root. Then, a
connectivity graph for $G\setminus E^{\prime}$ is a graph $\mathcal{R}$ with
vertex set $\\{\bar{r_{i}}\mid i\in\\{1,\dots,k\\}\\}$ such that: for every
$i,j\in\\{1,\dots,k\\}$, $r_{i}$ is connected with $r_{j}$ in $G\setminus
E^{\prime}$ if and only if $\bar{r_{i}}$ is connected with $\bar{r_{j}}$ in
$\mathcal{R}$.

We allow a connectivity graph $\mathcal{R}$ for $G\setminus E^{\prime}$ to be
a multigraph. (The important thing is that it captures the connectivity
relation of the roots of the connected components of $T\setminus E^{\prime}$.)
In particular, if we shrink every connected component of $T\setminus
E^{\prime}$ with root $z$ into a node $\bar{z}$, then the quotient graph of
$G\setminus E^{\prime}$ that we get is a connectivity graph for $G\setminus
E^{\prime}$. The main challenge is to compute a connectivity graph for
$G\setminus E^{\prime}$ without explicitly computing the connected components
of $T\setminus E^{\prime}$. We can achieve this if we assume that $T$ is a
DFS-tree of the graph. Then, with a creative use of the DFS-concepts that we
defined in Section 6, we can determine enough edges of $G\setminus E^{\prime}$
between the connected components of $T\setminus E^{\prime}$, so that we can
construct a connectivity graph for $G\setminus E^{\prime}$ in constant time,
if $|E^{\prime}|\leq 4$.

We distinguish five different cases, depending on the number of tree-edges
contained in $E^{\prime}$. Then, for each case, we consider all the different
possibilities for the edges from $E^{\prime}$ on $T$ (i.e., all the different
topologies of their endpoints w.r.t. the ancestry relation). In order to
reduce the number of cases considered, we will use the following three facts
(which we make precise and prove in the following paragraphs). First, if we
have established that the endpoints of a tree-edge $e$ in $E^{\prime}$ remain
connected in $G\setminus E^{\prime}$, then it is sufficient to set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{e\\}$, and then revert to the
previous case, where the number of tree-edges is that of $E^{\prime}$ minus
$1$ (see Lemma 7.4). Second, if there are at least two tree-edges in
$E^{\prime}$ that are not descendants of other tree-edges in $E^{\prime}$,
then we can handle the subtrees induced by those tree-edges separately, by
reverting to previous cases (see Lemma 7.5). And third, if for a tree-edge
$(u,p(u))$ in $E^{\prime}$ we have that $G\setminus E^{\prime}$ contains no
back-edges that leap over $u$, then we can handle the subtree induced by this
tree-edge separately from the rest of the tree, by reverting to previous cases
(see Lemma 7.6).

In the following, we assume that $T$ is a fixed DFS-tree of $G$ with root $r$.
All connectivity graphs refer to this tree. First, we will need the following
technical lemma.

######  Lemma 7.3.

Let $E^{\prime}$ be a set of edges, and let $E^{\prime\prime}$ be a subset of
$E^{\prime}$ that contains all the back-edges from $E^{\prime}$, and has the
property that no tree-edge from $E^{\prime}\setminus E^{\prime\prime}$ is
related as ancestor and descendant with a tree-edge from $E^{\prime\prime}$.
Let $U$ be the collection of the higher endpoints of the tree-edges in
$E^{\prime\prime}$, and let $z$ and $z^{\prime}$ be two vertices in
$U\cup\\{r\\}$. Suppose that $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime\prime}$. Then $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime}$.

###### Proof.

Since $z$ and $z^{\prime}$ are connected in $G\setminus E^{\prime\prime}$,
there is a path $P$ from $z$ to $z^{\prime}$ in $G\setminus E^{\prime\prime}$.
If $P$ does not use any tree-edge from $E^{\prime}\setminus E^{\prime\prime}$,
then we have that $P$ is a path in $G\setminus E^{\prime}$, and therefore $z$
and $z^{\prime}$ are connected in $G\setminus E^{\prime}$. So let us assume
that $P$ uses a tree-edge from $E^{\prime}\setminus E^{\prime\prime}$. Let $C$
be the connected component of $T\setminus E^{\prime}$ that contains $r$. Then,
we claim that $P$ has the form $P_{1}+Q+P_{2}$, where $P_{1}$ is path from $z$
to a vertex $w\in C$ that does not use any tree-edge from $E^{\prime}\setminus
E^{\prime\prime}$, $Q$ is a path from $w$ to a vertex $w^{\prime}\in C$ (that
uses tree-edges from $E^{\prime}\setminus E^{\prime\prime}$), and $P_{2}$ is a
path from $w^{\prime}$ to $z^{\prime}$ that does not use any tree-edge from
$E^{\prime}\setminus E^{\prime\prime}$ $(*)$. This implies that $P_{1}$ is a
path from $z$ to $w$ in $G\setminus E^{\prime}$, and $P_{2}$ is a path from
$w^{\prime}$ to $z^{\prime}$ in $G\setminus E^{\prime}$. Then, since $w$ and
$w^{\prime}$ lie in the same connected component of $T\setminus E^{\prime}$,
we have that there is a path $Q^{\prime}$ from $w$ to $w^{\prime}$ in
$G\setminus E^{\prime}$. Thus, $P_{1}+Q^{\prime}+P_{2}$ is a path from $z$ to
$z^{\prime}$ in $G\setminus E^{\prime}$, and therefore we have that $z$ and
$z^{\prime}$ are connected in $G\setminus E^{\prime}$.

Now we will prove $(*)$. Let $U^{\prime}$ be the collection of the higher
endpoints of the tree-edges in $E^{\prime}\setminus E^{\prime\prime}$. Then,
we have that no vertex from $U$ is related as ancestor and descendant with a
vertex from $U^{\prime}$. Now let $(v,p(v))$ be the first occurrence of a
tree-edge from $E^{\prime}\setminus E^{\prime\prime}$ that is used by $P$, and
let $(v^{\prime},p(v^{\prime}))$ be the last occurrence of a tree-edge from
$E^{\prime}\setminus E^{\prime\prime}$ that is used by $P$. Then, since $P$
starts from $z$ and visits $v$, Lemma 6.21 implies that $P$ contains a subpath
from an ancestor $w$ of $\mathit{nca}\\{z,v\\}$ to $v$, and let $w$ be the
first vertex visited by $P$ with this property. Let $P_{1}$ be the initial
part of $P$ from $z$ to the first occurrence of $w$. Then, we have that
$P_{1}$ does not use any tree-edge from $E^{\prime}\setminus
E^{\prime\prime}$. Notice that there is no $u\in U$ such that $u$ is an
ancestor of $w$, because otherwise we would have that $u$ is an ancestor of
$v$. Also, there is no $u^{\prime}\in U^{\prime}$ such that $u^{\prime}$ is an
ancestor of $w$, because otherwise $u^{\prime}$ would be an ancestor of $z$.
Thus, there is no tree-edge from $E^{\prime}$ on the tree-path $T[r,w]$.
Similarly, since $P$ visits $v^{\prime}$ and ends in $z^{\prime}$, Lemma 6.21
implies that $P$ contains a subpath from $v^{\prime}$ to an ancestor
$w^{\prime}$ of $\mathit{nca}\\{v^{\prime},z^{\prime}\\}$, and let
$w^{\prime}$ be the last vertex visited by $P$ with this property. Let $P_{2}$
be the final part of $P$ from the last occurrence of $w^{\prime}$ to
$z^{\prime}$. Then, we have that $P_{2}$ does not use any tree-edge from
$E^{\prime}\setminus E^{\prime\prime}$. Again, we can see that there is no
tree-edge from $E^{\prime}$ on the tree-path $T[r,w^{\prime}]$. Now we can
consider the part $Q$ of $P$ from the first occurrence of $w$ to the last
occurrence of $w^{\prime}$, and the proof is complete, because
$P=P_{1}+Q+P_{2}$, and the endpoints of $Q$ lie in the connected component of
$T\setminus E^{\prime}$ that contains $r$. ∎

######  Lemma 7.4.

Let $E^{\prime}$ be a set of edges, and let $(u,p(u))$ and $(v,p(v))$ be two
distinct tree-edges in $E^{\prime}$. Suppose that $u$, $p(u)$ and $v$ are
connected in $G\setminus E^{\prime}$. Let
$E^{\prime\prime}=E^{\prime}\setminus\\{(u,p(u))\\}$, and let
$\mathcal{R}^{\prime}$ be a connectivity graph for $G\setminus
E^{\prime\prime}$. Then, $\mathcal{R}^{\prime}\cup\\{(\bar{u},\bar{v})\\}$ is
a connectivity graph for $G\setminus E^{\prime}$.

###### Proof.

Let $(u_{1},p(u_{1})),\dots,(u_{k},p(u_{k}))$ be the tree-edges in
$E^{\prime}$, where $u_{1}=u$. Let
$E^{\prime\prime}=E^{\prime}\setminus\\{(u,p(u))\\}$, and let
$\mathcal{R}^{\prime}$ be a connectivity graph for $G\setminus
E^{\prime\prime}$. Then we have that
$V(\mathcal{R}^{\prime})=\\{\bar{u}_{2},\dots,\bar{u}_{k},\bar{r}\\}$. Let
$\mathcal{R}$ be the graph with
$V(\mathcal{R})=V(\mathcal{R}^{\prime})\cup\\{\bar{u}\\}$ and
$E(\mathcal{R})=E(\mathcal{R}^{\prime})\cup\\{(\bar{u},\bar{v})\\}$. We will
show that $\mathcal{R}$ is a connectivity graph for $G\setminus E^{\prime}$.

Let $z$ and $z^{\prime}$ be two vertices in $\\{u_{2},\dots,u_{k},r\\}$.
First, suppose that $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime}$. Then, since $E^{\prime\prime}\subset E^{\prime}$, we have that
$z$ and $z^{\prime}$ are connected in $G\setminus E^{\prime\prime}$. Thus,
$\bar{z}$ and $\bar{z}^{\prime}$ are connected in $\mathcal{R}^{\prime}$, and
therefore they are connected in $\mathcal{R}$. Conversely, suppose that
$\bar{z}$ and $\bar{z}^{\prime}$ are connected in $\mathcal{R}$. Then, it is
easy to see that $\bar{z}$ and $\bar{z}^{\prime}$ are connected in
$\mathcal{R}^{\prime}$. This implies that $z$ and $z^{\prime}$ are connected
in $G\setminus E^{\prime\prime}$. Thus, there is a path $P$ from $z$ to
$z^{\prime}$ in $G\setminus E^{\prime\prime}$. If $P$ does not use the edge
$(u,p(u))$, then $P$ is a path in $G\setminus E^{\prime}$, and therefore $z$
and $z^{\prime}$ are connected in $G\setminus E^{\prime}$. Otherwise, since
$u$ and $p(u)$ are connected in $G\setminus E^{\prime}$, there is a path $Q$
from $u$ to $p(u)$ in $G\setminus E^{\prime}$ that avoids the edge $(u,p(u))$.
Now replace every occurrence of $(u,p(u))$ in $P$ with $Q$, and let
$P^{\prime}$ be the resulting path. Then, we have that $P^{\prime}$ is a path
from $z$ to $z^{\prime}$ in $G\setminus E^{\prime}$. This shows that $z$ and
$z^{\prime}$ are connected in $G\setminus E^{\prime}$.

Now let $z$ be a vertex in $\\{u_{2},\dots,u_{k},r\\}$. First, suppose that
$u$ and $z$ are connected in $G\setminus E^{\prime}$. Then, since
$E^{\prime\prime}\subset E^{\prime}$, we have that $u$ and $z$ are connected
in $G\setminus E^{\prime\prime}$. Furthermore, since $u$ and $v$ are connected
in $G\setminus E^{\prime}$, we have that $u$ and $v$ are connected in
$G\setminus E^{\prime\prime}$. Thus, $v$ and $z$ are connected in $G\setminus
E^{\prime\prime}$, and therefore $\bar{v}$ and $\bar{z}$ are connected in
$\mathcal{R}^{\prime}$. Thus, the existence of the edge $(\bar{u},\bar{v})$ in
$\mathcal{R}$ implies that $\bar{u}$ and $\bar{z}$ are connected in
$\mathcal{R}$. Conversely, suppose that $\bar{u}$ and $\bar{z}$ are connected
in $\mathcal{R}$. Then, since $(\bar{u},\bar{v})$ is the only edge of
$\mathcal{R}$ that is incident to $\bar{u}$, we have that $\bar{v}$ is
connected with $\bar{z}$ in $\mathcal{R}$ through a path that avoids
$\bar{u}$. Therefore, $\bar{v}$ is connected with $\bar{z}$ in
$\mathcal{R}^{\prime}$. Thus, we have that $v$ and $z$ are connected in
$G\setminus E^{\prime\prime}$. So let $P$ be a path from $v$ to $z$ in
$G\setminus E^{\prime\prime}$. Since $u$ and $p(u)$ are connected in
$G\setminus E^{\prime}$, we have that there is a path $Q$ from $u$ to $p(u)$
in $G\setminus E^{\prime}$. Now, if $P$ uses the edge $(u,p(u))$, then we
replace every occurrence of $(u,p(u))$ in $P$ with the path $Q$. Let
$P^{\prime}$ be the resulting path. Then, $P^{\prime}$ is a path from $v$ to
$z$ in $G\setminus E^{\prime}$, and therefore $v$ is connected with $z$ in
$G\setminus E^{\prime}$. Therefore, since $u$ is connected with $v$ in
$G\setminus E^{\prime}$, we have that $u$ is connected with $z$ in $G\setminus
E^{\prime}$.

Thus, we have shown that, for every pair of vertices $z$ and $z^{\prime}$ in
$\\{u_{1},\dots,u_{k},r\\}$, we have that $z$ and $z^{\prime}$ are connected
in $G\setminus E^{\prime}$ if and only if $\bar{z}$ and $\bar{z}^{\prime}$ are
connected in $\mathcal{R}$. This means that $\mathcal{R}$ is a connectivity
graph for $G\setminus E^{\prime}$. ∎

######  Lemma 7.5.

Let $E^{\prime}$ be a set of edges, and let $(u,p(u))$ be a tree-edge in
$E^{\prime}$ with the property that no tree-edge in $E^{\prime}$ is a proper
ancestor of $(u,p(u))$. Let $E_{1}$ be the set of the tree-edges in
$E^{\prime}$ that are descendants of $(u,p(u))$, plus the back-edges in
$E^{\prime}$, and let $E_{2}$ be the set of the tree-edges in $E^{\prime}$
that are not descendants of $(u,p(u))$, plus the back-edges in $E^{\prime}$.
Let $\mathcal{R}_{1}$ be a connectivity graph for $G\setminus E_{1}$, and let
$\mathcal{R}_{2}$ be a connectivity graph for $G\setminus E_{2}$. Then,
$\mathcal{R}_{1}\cup\mathcal{R}_{2}$ is a connectivity graph for $G\setminus
E^{\prime}$.

###### Proof.

Let $(u_{1},p(u_{1})),\dots,(u_{t},p(u_{t}))$ be the tree-edges in $E_{1}$,
and let $(v_{1},p(v_{1})),\dots,(v_{s},p(v_{s}))$ be the tree-edges in
$E_{2}$. (Notice that we may have $s=0$, in which case the conclusion of the
lemma follows trivially.) Then, we have that all vertices in
$\\{u_{1},\dots,u_{t}\\}$ are descendants of $u$, and none of the vertices in
$\\{v_{1},\dots,v_{s}\\}$ is related as ancestor and descendant with $u$. This
implies that no vertex from $\\{u_{1},\dots,u_{t}\\}$ is related as ancestor
and descendant with a vertex from $\\{v_{1},\dots,v_{s}\\}$. Let
$\mathcal{R}_{1}$ be a connectivity graph for $G\setminus E_{1}$, and let
$\mathcal{R}_{2}$ be a connectivity graph for $G\setminus E_{2}$. Then we have
that $V(\mathcal{R}_{1})=\\{\bar{u}_{1},\dots,\bar{u}_{t},\bar{r}\\}$ and
$V(\mathcal{R}_{2})=\\{\bar{v}_{1},\dots,\bar{v}_{s},\bar{r}\\}$. Let
$\mathcal{R}=\mathcal{R}_{1}\cup\mathcal{R}_{2}$. We will show that
$\mathcal{R}$ is a connectivity graph for $G\setminus E^{\prime}$.

Let $z$ and $z^{\prime}$ be two vertices in $\\{u_{1},\dots,u_{t},r\\}$.
First, suppose that $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime}$. Then, since $E_{1}\subseteq E^{\prime}$, we have that $z$ and
$z^{\prime}$ are connected in $G\setminus E_{1}$. This implies that $\bar{z}$
and $\bar{z}^{\prime}$ are connected in $\mathcal{R}_{1}$. Therefore,
$\bar{z}$ and $\bar{z}^{\prime}$ are connected in $\mathcal{R}$. Conversely,
suppose that $\bar{z}$ and $\bar{z}^{\prime}$ are connected in $\mathcal{R}$.
Since $\bar{z}$ and $\bar{z}^{\prime}$ are connected in $\mathcal{R}$ and are
both in $\\{u_{1},\dots,u_{t},r\\}$, it is easy to see that $\bar{z}$ and
$\bar{z}^{\prime}$ are connected in $\mathcal{R}_{1}$. This implies that $z$
and $z^{\prime}$ are connected in $G\setminus E_{1}$. Then, Lemma 7.3 implies
that $z$ and $z^{\prime}$ are connected in $G\setminus E^{\prime}$.

With the analogous argument we can show that, if $z$ and $z^{\prime}$ are two
vertices in $\\{v_{1},\dots,v_{s},r\\}$, then $z$ and $z^{\prime}$ are
connected in $G\setminus E^{\prime}$ if and only if they are connected in
$\mathcal{R}$.

Now let $z$ be a vertex in $\\{u_{1},\dots,u_{t}\\}$, and let $z^{\prime}$ be
a vertex in $\\{v_{1},\dots,v_{s}\\}$. First, suppose that $z$ and
$z^{\prime}$ are connected in $G\setminus E^{\prime}$. Then there is a path
$P$ from $z$ to $z^{\prime}$ in $G\setminus E^{\prime}$. By Lemma 6.21, we
have that $P$ passes from an ancestor $w$ of $\mathit{nca}\\{z,z^{\prime}\\}$.
Notice that there is no $i\in\\{1,\dots,t\\}$ such that $u_{i}$ is an ancestor
of $w$, because otherwise we would have that $u_{i}$ is an ancestor of
$z^{\prime}$. Similarly, there is no $i\in\\{1,\dots,s\\}$ such that $v_{i}$
is an ancestor of $w$, because otherwise we would have that $v_{i}$ is an
ancestor of $z$. Thus, there is no tree-edge from $E^{\prime}$ on the tree-
path $T[w,r]$, and therefore $w$ is connected with $r$ in $G\setminus
E^{\prime}$. Thus, both $z$ and $z^{\prime}$ are connected with $r$ in
$G\setminus E^{\prime}$. Since $E_{1}\subseteq E^{\prime}$, we have that $z$
is connected with $r$ in $G\setminus E_{1}$. This implies that $\bar{z}$ is
connected with $\bar{r}$ in $\mathcal{R}_{1}$, and therefore $\bar{z}$ is
connected with $\bar{r}$ in $\mathcal{R}$. Similarly, since $E_{2}\subset
E^{\prime}$, we have that $z^{\prime}$ is connected with $r$ in $G\setminus
E_{2}$. This implies that $\bar{z}^{\prime}$ is connected with $\bar{r}$ in
$\mathcal{R}_{2}$, and therefore $\bar{z}^{\prime}$ is connected with
$\bar{r}$ in $\mathcal{R}$. Thus, we infer that $\bar{z}$ is connected with
$\bar{z}^{\prime}$ in $\mathcal{R}$.

Conversely, suppose that $\bar{z}$ and $\bar{z}^{\prime}$ are connected in
$\mathcal{R}$. Since $\bar{z}\in V(\mathcal{R}_{1})$ and $\bar{z}^{\prime}\in
V(\mathcal{R}_{2})$, this implies that $\bar{z}$ is connected with $\bar{r}$
in $\mathcal{R}_{1}$, and $\bar{z}^{\prime}$ is connected with $\bar{r}$ in
$\mathcal{R}_{2}$. Therefore, $z$ is connected with $r$ in $G\setminus E_{1}$,
and $z^{\prime}$ is connected with $r$ in $G\setminus E_{2}$. Then, Lemma 7.3
implies that $z$ is connected with $r$ in $G\setminus E^{\prime}$, and
$z^{\prime}$ is connected with $r$ in $G\setminus E^{\prime}$. Therefore, $z$
is connected with $z^{\prime}$ in $G\setminus E^{\prime}$.

Thus, we have shown that, for every pair of vertices $z$ and $z^{\prime}$ in
$\\{u_{1},\dots,u_{t},v_{1},\dots,v_{s},r\\}$, we have that $z$ and
$z^{\prime}$ are connected in $G\setminus E^{\prime}$ if and only if $\bar{z}$
and $\bar{z}^{\prime}$ are connected in $\mathcal{R}$. Since the tree-edges in
$E^{\prime}$ are given by
$\\{(u_{1},p(u_{1})),\dots,(u_{t},p(u_{t})),(v_{1},p(v_{1})),\dots,(v_{s},p(v_{s}))\\}$,
this means that $\mathcal{R}$ is a connectivity graph for $G\setminus
E^{\prime}$. ∎

######  Lemma 7.6.

Let $E^{\prime}$ be a set of edges, and let $(u,p(u))$ be a tree-edge in
$E^{\prime}$ with the property that $B(u)\setminus E^{\prime}=\emptyset$. Let
$E_{1}$ be the set of the tree-edges in $E^{\prime}$ that are proper
descendants of $(u,p(u))$, plus the back-edges in $E^{\prime}$, and let
$E_{2}$ be the set of the tree-edges in $E^{\prime}$ that are not descendants
of $(u,p(u))$, plus the back-edges in $E^{\prime}$. Let $\mathcal{R}_{1}$ be a
connectivity graph for $G\setminus E_{1}$, and let $\mathcal{R}_{2}$ be a
connectivity graph for $G\setminus E_{2}$. Let $\mathcal{R}_{1}^{\prime}$ be
the graph that is derived from $\mathcal{R}_{1}$ by replacing every occurrence
of $\bar{r}$ with $\bar{u}$. Then,
$\mathcal{R}_{1}^{\prime}\cup\mathcal{R}_{2}$ is a connectivity graph for
$G\setminus E^{\prime}$.

###### Proof.

Let $(u_{1},p(u_{1})),\dots,(u_{t},p(u_{t}))$ be the tree-edges in $E_{1}$,
and let $(v_{1},p(v_{1})),\dots,(v_{s},p(v_{s}))$ be the tree-edges in
$E_{2}$. (We note that $u\notin\\{u_{1},\dots,u_{t},v_{1},\dots,v_{s}\\}$, and
both $t$ and $s$ may be $0$.) Then, we have that all vertices in
$\\{u_{1},\dots,u_{t}\\}$ are proper descendants of $u$, and no vertex from
$\\{v_{1},\dots,v_{s}\\}$ is a descendant of $u$. Now let $\mathcal{R}_{1}$,
$\mathcal{R}_{1}^{\prime}$, $\mathcal{R}_{2}$, and $\mathcal{R}$ be as in the
statement of the lemma. We will show that $\mathcal{R}$ is a connectivity
graph for $G\setminus E^{\prime}$.

Since $V(\mathcal{R}_{1})=\\{\bar{u}_{1},\dots,\bar{u}_{t},\bar{r}\\}$ and
$V(\mathcal{R}_{2})=\\{\bar{v}_{1},\dots,\bar{v}_{s},\bar{r}\\}$, we have that
$V(\mathcal{R}_{1})\cap V(\mathcal{R}_{2})=\\{\bar{r}\\}$. This implies that
$V(\mathcal{R}_{1}^{\prime})\cap V(\mathcal{R}_{2})=\emptyset$. Therefore, it
is easy to see that no vertex from
$\\{\bar{u}_{1},\dots,\bar{u}_{t},\bar{u}\\}$ is connected with a vertex from
$\\{\bar{v}_{1},\dots,\bar{v}_{s},\bar{r}\\}$ in $\mathcal{R}$.

Now let $z$ be a vertex in $\\{u_{1},\dots,u_{t},u\\}$ and let $z^{\prime}$ be
a vertex in $\\{v_{1},\dots,v_{s},r\\}$. Let us suppose, for the sake of
contradiction, that $z$ is connected with $z^{\prime}$ in $G\setminus
E^{\prime}$. Then there is a path $P$ from $z$ to $z^{\prime}$ in $G\setminus
E^{\prime}$. Lemma 6.21 implies that $P$ passes from an ancestor $w$ of
$\mathit{nca}\\{z,z^{\prime}\\}$. We have that $z$ is a common descendant of
$w$ and $u$. Thus, $u$ and $w$ are related as ancestor and descendant. But $u$
cannot be an ancestor of $w$, because otherwise it would be an ancestor of
$z^{\prime}$. Thus, we have that $u$ is a proper descendant of $w$. Since $P$
starts from a descendant of $u$ and reaches a proper ancestor of $u$, by Lemma
6.22 we have that $P$ must either use a back-edge that leaps over $u$, or it
passes from the tree-edge $(u,p(u))$. But both of these cases are impossible,
since $B(u)\setminus E^{\prime}=\emptyset$ and $(u,p(u))\in E^{\prime}$. This
shows that $z$ is not connected with $z^{\prime}$ in $G\setminus E^{\prime}$.

Now let $z$ and $z^{\prime}$ be two vertices in $\\{u_{1},\dots,u_{t}\\}$.
First, suppose that $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime}$. Then, since $E_{1}\subset E^{\prime}$, we have that $z$ and
$z^{\prime}$ are connected in $G\setminus E_{1}$. This implies that $\bar{z}$
and $\bar{z}^{\prime}$ are connected in $\mathcal{R}_{1}$, and therefore they
are connected in $\mathcal{R}_{1}^{\prime}$, and therefore they are connected
in $\mathcal{R}$. Conversely, suppose that $\bar{z}$ and $\bar{z}^{\prime}$
are connected in $\mathcal{R}$. Then, we have that $\bar{z}$ and
$\bar{z}^{\prime}$ are connected in $\mathcal{R}_{1}^{\prime}$, and therefore
they are connected in $\mathcal{R}_{1}$. This implies that there is a path $P$
from $z$ to $z^{\prime}$ in $G\setminus E_{1}$. If $P$ does not use a tree-
edge from $E_{2}^{\prime}=E_{2}\cup\\{(u,p(u))\\}$, then we have that $P$ is a
path in $G\setminus E^{\prime}$, and this shows that $z$ is connected with
$z^{\prime}$ in $G\setminus E^{\prime}$. Otherwise, let us suppose that $P$
uses a tree-edge from $E_{2}^{\prime}$. Then we claim that $P$ has the form
$P_{1}+(u,p(u))+Q+(p(u),u)+P_{2}$, where $P_{1}$ is a path from $z$ to $u$
that does not use tree-edges from $E_{2}^{\prime}$, $Q$ is a path from $p(u)$
to $p(u)$ that may use tree-edges from $E_{2}^{\prime}$, and $P_{2}$ is a path
from $u$ to $z^{\prime}$ that does not use tree-edges from $E_{2}^{\prime}$
$(*)$. This implies that $P_{1}$ is a path from $z$ to $u$ in $G\setminus
E^{\prime}$, and $P_{2}$ is a path from $u$ to $z^{\prime}$ in $G\setminus
E^{\prime}$. Thus, $P_{1}+P_{2}$ is a path from $z$ to $z^{\prime}$ in
$G\setminus E^{\prime}$, and therefore $z$ is connected with $z^{\prime}$ in
$G\setminus E^{\prime}$.

Now we will prove $(*)$. Let $(v,p(v))$ be the first occurrence of a tree-edge
from $E_{2}^{\prime}$ in $P$. Then, since $P$ starts from $z$, by Lemma 6.21
we have that $P$ passes from an ancestor $w$ of $\mathit{nca}\\{z,v\\}$. Then,
we have that $z$ is a common descendant of $u$ and $w$, and therefore $u$ and
$w$ are related as ancestor and descendant. Notice that we cannot have that
$u$ is a proper ancestor of $w$, because this would imply that $u$ is a proper
ancestor of $v$ (and we have that either $v\in\\{v_{1},\dots,v_{s}\\}$, or
$v=u$). Thus, $u$ is a descendant of $w$. Then, since $P$ starts from a
descendant of $u$ and reaches a proper ancestor of $u$ (which is either $w$ or
$p(u)$), by Lemma 6.22 we have that $P$ must either use a back-edge from
$B(u)$, or the tree-edge $(u,p(u))$, before it leaves the subtree of $u$.
Since $P$ is a path in $G\setminus E_{1}$ and $E_{1}$ contains all the back-
edges from $E^{\prime}$ and $B(u)\setminus E^{\prime}=\emptyset$, the only
viable option is that $P$ uses the tree-edge $(u,p(u))$ in order to leave the
subtree of $u$. Thus, there is a part $P_{1}$ of $P$ from $z$ to $u$ that lies
entirely within the subtree of $u$. In particular, we have that $P_{1}$ does
not use a tree-edge from $E_{2}^{\prime}$. Similarly, by considering the last
occurrence of a tree-edge from $E_{2}^{\prime}$ in $P$, we can show that there
is a part $P_{2}$ of $P$ from $u$ to $z^{\prime}$ that does not use a tree-
edge from $E_{2}^{\prime}$. This establishes $(*)$.

Now let $z$ be a vertex in $\\{u_{1},\dots,u_{t}\\}$. First, suppose that $u$
and $z$ are connected in $G\setminus E^{\prime}$. Then there is a path $P$
from $u$ to $z$ in $G\setminus E^{\prime}$. Since $E_{1}\subset E^{\prime}$,
we have that $P$ is a path from $u$ to $z$ in $G\setminus E_{1}$. We have that
there is no tree-edge from $E_{1}$ on the tree-path $T[r,u]$. Thus, $T[r,u]+P$
is a path from $r$ to $z$ in $G\setminus E_{1}$, and therefore $r$ is
connected with $z$ in $G\setminus E_{1}$. This implies that $\bar{r}$ is
connected with $\bar{z}$ in $\mathcal{R}_{1}$, and therefore $\bar{u}$ is
connected with $\bar{z}$ in $\mathcal{R}_{1}^{\prime}$. Thus, $\bar{u}$ is
connected with $\bar{z}$ in $\mathcal{R}$. Conversely, suppose that $\bar{u}$
is connected with $\bar{z}$ in $\mathcal{R}$. This implies that $\bar{u}$ is
connected with $\bar{z}$ in $\mathcal{R}_{1}^{\prime}$, and therefore
$\bar{r}$ is connected with $\bar{z}$ in $\mathcal{R}_{1}$. This implies that
$r$ is connected with $z$ in $G\setminus E_{1}$. Thus, there is a path $P$
from $r$ to $z$ in $G\setminus E_{1}$. Since $r$ is a proper ancestor of $u$
and $z$ is a descendant of $u$, Lemma 6.22 implies that $P$ must either use a
back-edge from $B(u)$, or the tree-edge $(p(u),u)$, and then it finally lies
entirely within the subtree of $u$. Thus, since $E_{1}$ contains all the back-
edges from $E^{\prime}$ and $B(u)\setminus E^{\prime}=\emptyset$, we have that
$P$ eventually passes from the tree-edge $(p(u),u)$, and stays within the
subtree of $u$. Thus, we have that $u$ is connected with $z$ in $G\setminus
E_{1}$, through a path $P^{\prime}$ that lies entirely within the subtree of
$u$. This implies that $P^{\prime}$ does not use tree-edges from $E_{2}$.
Thus, $P^{\prime}$ is a path from $u$ to $z$ in $G\setminus E^{\prime}$, and
therefore $u$ is connected with $z$ in $G\setminus E^{\prime}$.

Now let $z$ and $z^{\prime}$ be two vertices in $\\{v_{1},\dots,v_{s},r\\}$.
First, suppose that $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime}$. Then, since $E_{2}\subset E^{\prime}$, we have that $z$ and
$z^{\prime}$ are connected in $G\setminus E_{2}$. This implies that $\bar{z}$
is connected with $\bar{z}^{\prime}$ in $\mathcal{R}_{2}$. Thus, we have that
$\bar{z}$ is connected with $\bar{z}^{\prime}$ in $\mathcal{R}$. Conversely,
suppose that $\bar{z}$ and $\bar{z}^{\prime}$ are connected in $\mathcal{R}$.
Then we have that $\bar{z}$ and $\bar{z}^{\prime}$ are connected in
$\mathcal{R}_{2}$. This implies that $z$ and $z^{\prime}$ are connected in
$G\setminus E_{2}$. Thus, there is a path $P$ from $z$ to $z^{\prime}$ in
$G\setminus E_{2}$. If $P$ does not use any tree-edge from
$E_{1}^{\prime}=E_{1}\cup\\{(u,p(u))\\}$, then $P$ is a path in $G\setminus
E^{\prime}$, and therefore $z$ and $z^{\prime}$ are connected in $G\setminus
E^{\prime}$. So let us assume that $P$ uses a tree-edge from $E_{1}^{\prime}$.
Then we claim that $P$ has the form $P_{1}+Q+P_{2}$, where $P_{1}$ is a path
from $z$ to $p(u)$ that does not use tree-edges from $E_{1}^{\prime}$, $Q$ is
a path from $p(u)$ to $p(u)$ (that uses tree-edges from $E_{1}$), and $P_{2}$
is a path from $p(u)$ to $z^{\prime}$ that does not use tree-edges from
$E_{1}^{\prime}$ $(**)$. This implies that $P_{1}+P_{2}$ is a path from $z$ to
$z^{\prime}$ in $G\setminus E^{\prime}$, and therefore $z$ and $z^{\prime}$
are connected in $G\setminus E^{\prime}$.

Now we will prove $(**)$. Since $P$ uses a tree-edge from $E_{1}^{\prime}$, we
may consider the first occurrence $(u^{\prime},p(u^{\prime}))$ of an edge from
$E_{1}^{\prime}$ that is used by $P$. Then, we have that $u^{\prime}$ is a
descendant of $u$. Since $P$ starts from $z$, Lemma 6.21 implies that $P$
contains a subpath from $z$ to $u^{\prime}$ that passes from an ancestor $w$
of $\mathit{nca}\\{z,u^{\prime}\\}$, and let $w$ be the first vertex visited
by $P$ with this property. Let $P^{\prime}$ be the initial part of $P$ from
$z$ to the first occurrence of $w$. Then we have that $P^{\prime}$ does not
use any tree-edge from $E_{1}^{\prime}$. Since $u^{\prime}$ is a descendant of
$u$ but $z$ is not, we have that $\mathit{nca}\\{z,u^{\prime}\\}$ is a proper
ancestor of $u$, and therefore $w$ is a proper ancestor of $u$. Then, Lemma
6.22 implies that the part of $P$ from $w$ to $u^{\prime}$ must either use the
tree-edge $(u,p(u))$, or a back-edge that leaps over $u$. Since $P$ is a path
in $G\setminus E_{2}$ and $E_{2}$ contains all the back-edges from
$E^{\prime}$ and $B(u)\setminus E^{\prime}=\emptyset$, we infer that the part
of $P$ from $w$ to $u^{\prime}$ must use the tree-edge $(u,p(u))$ in order to
enter the subtree of $u$. Now let $P^{\prime\prime}$ be the part of $P$ from
the first occurrence of $w$ to the first occurrence of $p(u)$ that is followed
by $(u,p(u))$. Then, we have that $P_{1}=P^{\prime}+P^{\prime\prime}$ is a
path from $z$ to $p(u)$ that does not use any tree-edge from $E_{1}^{\prime}$.
Similarly, since $P$ ends in $z^{\prime}$, we can show that the final part of
$P$ is a subpath $P_{2}$ that starts from $p(u)$ and ends in $z^{\prime}$. We
let $Q$ denote the middle part of $P$ (i.e., the one between $P_{1}$ and
$P_{2}$), and this establishes $(**)$.

Thus, we have shown that, for any two vertices $z$ and $z^{\prime}$ in
$\\{u_{1},\dots,u_{t},u,v_{1},\dots,v_{s},r\\}$, we have that $z$ is connected
with $z^{\prime}$ in $G\setminus E^{\prime}$ if and only if $\bar{z}$ is
connected with $\bar{z}^{\prime}$ in $\mathcal{R}$. This means that
$\mathcal{R}$ is a connectivity graph for $G\setminus E^{\prime}$. ∎

Given a set of edges $E^{\prime}$ with $|E^{\prime}|\leq 4$, we will show how
to construct a connectivity graph $\mathcal{R}$ for $G\setminus E^{\prime}$.
We distinguish five cases, depending on the number of tree-edges in
$E^{\prime}$. Whenever possible, we use Lemmata 7.4, 7.5 and 7.6, in order to
revert to previous cases. This simplifies the analysis a lot, because the
number of cases that may appear is very large. If $A$ and $B$ are two subtrees
of $T$, we use $(A,B)$ to denote the set of the back-edges that connect $A$
and $B$.

###  7.1 $E^{\prime}$ contains zero tree-edges

In this case, $T\setminus E^{\prime}$ is connected, and therefore $G\setminus
E^{\prime}$ is also connected. Thus, we know that every connectivity query in
$G\setminus E^{\prime}$ is positive. (The connectivity graph $\mathcal{R}$ of
$G\setminus E^{\prime}$ consists of a single vertex $\bar{r}$.)

###  7.2 $E^{\prime}$ contains one tree-edge

Let $(u,p(u))$ be the tree-edge contained in $E^{\prime}$. The connected
components of $T\setminus\\{(u,p(u))\\}$ are $A=T(u)$ and $B=T(r)\setminus
T(u)$. Thus, $\mathcal{R}$ consists of the vertices $\\{\bar{u},\bar{r}\\}$.
We can see that $A$ is connected with $B$ in $G\setminus E^{\prime}$ if and
only if there is a back-edge in $B(u)\setminus{E^{\prime}}$. Since
$E^{\prime}$ contains at most three back-edges, it is sufficient to have
collected at most four back-edges of $B(u)$ in a set $B_{4}(u)$, and then
check whether $B_{4}(u)\setminus E^{\prime}=\emptyset$. We may pick the four
lowest $\mathit{low}$-edges of $u$ in order to build $B_{4}(u)$, since these
are easy to compute. (I.e., $B_{4}(u)$ consists of the non-null
$\mathit{low}_{i}$-edges of $u$, for all $i\in\\{1,2,3,4\\}$.) If
$B_{4}(u)\setminus E^{\prime}\neq\emptyset$, then we add the edge
$(\bar{u},\bar{r})$ to $\mathcal{R}$. Otherwise, $\bar{u}$ is disconnected
from $\bar{r}$ in $\mathcal{R}$.

###  7.3 $E^{\prime}$ contains two tree-edges

Let $(u,p(u))$ and $(v,p(v))$ be the two tree-edges contained in $E^{\prime}$.
Then we have that $\mathcal{R}$ consists of the vertices
$\\{\bar{u},\bar{v},\bar{r}\\}$. Let us assume w.l.o.g. that $u>v$. Suppose
that $u$ and $v$ are not related as ancestor and descendant. Then, we set
$E_{1}=E^{\prime}\setminus\\{(u,p(u))\\}$ and
$E_{2}=E^{\prime}\setminus\\{(v,p(v))\\}$. Each of the sets $E_{1}$ and
$E_{2}$ contains only one tree-edge, and therefore we can revert to the
previous case in order to build a connectivity graph $\mathcal{R}_{1}$ and
$\mathcal{R}_{2}$ for $G\setminus E_{1}$ and $G\setminus E_{2}$, respectively.
Then, by Lemma 7.5 we have that $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ is a
connectivity graph for $G\setminus E^{\prime}$. So let us assume that the two
tree-edges in $E^{\prime}$ are related as ancestor and descendant. Since
$u>v$, this implies that $u$ is a descendant of $v$. Let $A=T(u)$,
$B=T(v)\setminus T(u)$, and $C=T(r)\setminus T(v)$.

First, we will check whether there is a back-edge from $A$ to $B$ in
$G\setminus E^{\prime}$. Since $E^{\prime}$ contains at most two back-edges,
we have that $(A,B)\setminus E^{\prime}\neq\emptyset$ if and only if at least
one of the three highest $\mathit{high}$-edges of $u$ is not in $E^{\prime}$
and has its lower endpoint in $B$. In other words, $(A,B)\setminus
E^{\prime}\neq\emptyset$ if and only if the $\mathit{high}_{i}$-edge of $u$
(exists, and) is not in $E^{\prime}$, and $\mathit{high}_{i}(u)\in B$, for
some $i\in\\{1,2,3\\}$. If that is the case, then we know that $u$ is
connected with $p(u)$ in $G\setminus E^{\prime}$. Thus, we add the edge
$(\bar{u},\bar{v})$ to $\mathcal{R}$. Then we can set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(u,p(u))\\}$, and revert to the previous case (where
$E^{\prime}$ contains one tree-edge), according to Lemma 7.4.

Otherwise, we have that all the back-edges in $B(u)\setminus E^{\prime}$ (if
there are any), have their lower endpoint in $C$. In this case, we have that
there is a back-edge from $A$ to $C$ if and only if $B(u)\setminus
E^{\prime}\neq\emptyset$. Since $E^{\prime}$ contains at most two back-edges,
we have that $B(u)\setminus E^{\prime}\neq\emptyset$ if and only if at least
one of the $\mathit{low}_{i}$-edges of $u$, for $i\in\\{1,2,3\\}$, (exists
and) does not lie in $E^{\prime}$. If we have that $B(u)\setminus
E^{\prime}=\emptyset$, then we know that $A$ is not connected with the rest of
the graph in $G\setminus E^{\prime}$. Thus, we can set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(u,p(u))\\}$ and revert to the previous case (where
$E^{\prime}$ contains one tree-edge), according to Lemma 7.6.

Thus, let us assume that there is a back-edge between $A$ and $C$ in
$G\setminus E^{\prime}$. Then we add the edge $(\bar{u},\bar{r})$ to
$\mathcal{R}$. Now it remains to check whether there is a back-edge from $B$
to $C$ in $G\setminus E^{\prime}$. Since we assume that there is no back-edge
from $A$ to $B$ in $G\setminus E^{\prime}$, we can distinguish three
possibilities: either $(1)$ no edge from $E^{\prime}$ is in $(A,B)$, or $(2)$
precisely one edge $e$ from $E^{\prime}$ is in $(A,B)$, or $(3)$ both the
back-edges $e$ and $e^{\prime}$ from $E^{\prime}$ are in $(A,B)$. In case
$(1)$, we have that $B(u)\subseteq B(v)$. Thus, there is a back-edge from $B$
to $C$ in $G\setminus E^{\prime}$ if and only if
$\mathit{bcount}(v)-\mathit{bcount}(u)>|E^{\prime}\cap(B(v)\setminus B(u))|$.
We note that it is easy to compute $|E^{\prime}\cap(B(v)\setminus B(u))|$: we
simply count how many back-edges from $E^{\prime}$ leap over $v$ but not over
$u$. Now, in case $(2)$ we have $B(u)\setminus\\{e\\}\subseteq B(v)$. Thus,
there is a back-edge from $B$ to $C$ in $G\setminus E^{\prime}$ if and only if
$\mathit{bcount}(v)-\mathit{bcount}(u)+1>|E^{\prime}\cap(B(v)\setminus
B(u))|$. Finally, in case $(3)$ we have
$B(u)\setminus\\{e,e^{\prime}\\}\subseteq B(v)$, and $E^{\prime}$ contains no
back-edge from $B(v)\setminus B(u)$. Thus, there is a back-edge from $B$ to
$C$ in $G\setminus E^{\prime}$ if and only if
$\mathit{bcount}(v)-\mathit{bcount}(u)+2>0$. We note that it is easy to
determine which case $(1)-(3)$ applies: we simply count how many back-edges
from $E^{\prime}$ (if $E^{\prime}$ contains back-edges) leap over $u$, but not
over $v$. If we have determined that there is a back-edge from $B$ to $C$ in
$G\setminus E^{\prime}$, then we add the edge $(\bar{v},\bar{r})$ to
$\mathcal{R}$.

###  7.4 $E^{\prime}$ contains three tree-edges

Let $(u,p(u))$, $(v,p(v))$ and $(w,p(w))$ be the three tree-edges contained in
$E^{\prime}$. Then we have that $\mathcal{R}$ consists of the vertices
$\\{\bar{u},\bar{v},\bar{w},\bar{r}\\}$. Let us assume w.l.o.g. that $u>v>w$.
We may also assume that one of the three tree-edges in $E^{\prime}$ is an
ancestor of the other two. Otherwise, we can use Lemma 7.5 in order to revert
to the previous case (where $E^{\prime}$ contains two tree-edges), because
then there are at least two tree-edges in $E^{\prime}$ with the property that
no tree-edge in $E^{\prime}$ is a proper ancestor of them.

Thus, since one of the three tree-edges in $E^{\prime}$ is an ancestor of the
other two and $w<v<u$, we have that $w$ is a common ancestor of $u$ and $v$.
Now there are two cases to consider: either $(1)$ $u$ and $v$ are not related
as ancestor and descendant, or $(2)$ $u$ and $v$ are related as ancestor and
descendant. Since $u>v$, in case $(2)$ we have that $v$ is an ancestor of $u$.

####  7.4.1 $u$ and $v$ are not related as ancestor and descendant

Let $A=T(u)$, $B=T(v)$, $C=T(w)\setminus(T(u)\cup T(v))$, and $D=T(r)\setminus
T(w)$.

If there is no back-edge in $G\setminus E^{\prime}$ that connects $A$, or $B$,
or $A\cup B\cup C$, with the rest of the graph in $G\setminus E^{\prime}$,
then we can use Lemma 7.6 in order to revert to the previous case (where
$E^{\prime}$ contains two tree-edges). Every one of those conditions is
equivalent to [$\mathit{bcount}(u)=0$ or $B(u)=\\{e\\}$, where $e$ is the
back-edge in $E^{\prime}$], or [$\mathit{bcount}(v)=0$ or $B(v)=\\{e\\}$,
where $e$ is the back-edge in $E^{\prime}$], or [$\mathit{bcount}(w)=0$ or
$B(w)=\\{e\\}$, where $e$ is the back-edge in $E^{\prime}$], respectively, and
so we can check them easily in constant time.

Otherwise, if there is a back-edge that connects $A$ with $C$ in $G\setminus
E^{\prime}$, or a back-edge that connects $B$ with $C$ in $G\setminus
E^{\prime}$, then we add the edge $(\bar{u},\bar{w})$, or $(\bar{v},\bar{w})$,
respectively, to $\mathcal{R}$. Then we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(u,p(u))\\}$, or $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(v,p(v))\\}$, respectively, and we revert to the
previous case (where $E^{\prime}$ contains two tree-edges) according to Lemma
7.4. Notice that there is a back-edge that connects $A$ with $C$ in
$G\setminus E^{\prime}$ if and only if: either $(i)$ $\mathit{high}_{1}(u)\in
C$ and the $\mathit{high}_{1}$-edge of $u$ is not in $E^{\prime}$, or $(ii)$
$\mathit{high}_{2}(u)\in C$ and the $\mathit{high}_{2}$-edge of $u$ is not in
$E^{\prime}$. Similarly, we can easily check whether there is a back-edge that
connects $B$ with $C$ in $G\setminus E^{\prime}$.

So let us assume that none of the above is true. This means that, in
$G\setminus E^{\prime}$, there is a back-edge from $A$ to $D$, a back-edge
from $B$ to $D$, no back-edge from $A$ to $C$, and no back-edge from $B$ to
$C$. Then, we add the edges $(\bar{u},\bar{r})$ and $(\bar{v},\bar{r})$ to
$\mathcal{R}$. Now it remains to determine whether there is a back-edge from
$C$ to $D$ in $G\setminus E^{\prime}$. Suppose first that $E^{\prime}$
contains a back-edge $e$, that connects either $A$ and $C$, or $B$ and $C$.
Then, there is a back-edge from $C$ to $D$ in $G\setminus E^{\prime}$ if and
only if $\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)-1$. (This is
because $B(u)\sqcup B(v)\subseteq B(w)\sqcup\\{e\\}$ in this case.) Thus, if
this condition is satisfied, then we add the edge $(\bar{w},\bar{r})$ to
$\mathcal{R}$. Now, let us assume that $E^{\prime}$ contains a back-edge from
$C$ to $D$. Then, there is a back-edge from $C$ to $D$ in $G\setminus
E^{\prime}$ if and only if
$\mathit{bcount}(w)-1>\mathit{bcount}(u)+\mathit{bcount}(v)$. Thus, if this
condition is satisfied, then we add the edge $(\bar{w},\bar{r})$ to
$\mathcal{R}$. Finally, let us assume that the back-edge in $E^{\prime}$ (if
it contains a back-edge) does not connect $A$ and $C$, or $B$ and $C$, or $C$
and $D$. Then, there is a back-edge from $C$ to $D$ in $G\setminus E^{\prime}$
if and only if $\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)$.
Thus, if this condition is satisfied, then we add the edge $(\bar{w},\bar{r})$
to $\mathcal{R}$.

####  7.4.2 $v$ is an ancestor of $u$

Let $A=T(u)$, $B=T(v)\setminus T(u)$, $C=T(w)\setminus T(v)$, and
$D=T(r)\setminus T(w)$.

If there is no back-edge in $G\setminus E^{\prime}$ that connects $A$, or
$A\cup B$, or $A\cup B\cup C$, with the rest of the graph in $G\setminus
E^{\prime}$, then we can use Lemma 7.6 in order to revert to the previous case
(where $E^{\prime}$ contains either one or two tree-edges). Every one of those
conditions is equivalent to [$\mathit{bcount}(u)=0$ or $B(u)=\\{e\\}$, where
$e$ is the back-edge in $E^{\prime}$], or [$\mathit{bcount}(v)=0$ or
$B(v)=\\{e\\}$, where $e$ is the back-edge in $E^{\prime}$], or
[$\mathit{bcount}(w)=0$ or $B(w)=\\{e\\}$, where $e$ is the back-edge in
$E^{\prime}$], respectively, and so we can check them easily in constant time.

If in $G\setminus E^{\prime}$ there is a back-edge that connects $A$ and $B$,
then we add the edge $(\bar{u},\bar{v})$ to $\mathcal{R}$. Then we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains two tree-edges) according to Lemma
7.4. Notice that there is a back-edge in $G\setminus E^{\prime}$ that connects
$A$ and $B$ if and only if: either $(i)$ $\mathit{high}_{1}(u)\in B$ and the
$\mathit{high}_{1}$-edge of $u$ is not in $E^{\prime}$, or $(ii)$
$\mathit{high}_{2}(u)\in B$ and the $\mathit{high}_{2}$-edge of $u$ is not in
$E^{\prime}$. Thus, we can easily check this condition in constant time.

So let us assume that there is no back-edge that connects $A$ and $B$ in
$G\setminus E^{\prime}$. If in $G\setminus E^{\prime}$ there is a back-edge
that connects $A$ and $C$, and a back-edge that connects $A$ and $D$, then the
parts $C$ and $D$ are connected in $G\setminus E^{\prime}$ through the
mediation of $A$. Thus, we add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$,
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(w,p(w))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains two tree-edges) according to
Lemma 7.4. Since there is no back-edge that connects $A$ and $B$ in
$G\setminus E^{\prime}$, notice that there is a back-edge in $G\setminus
E^{\prime}$ that connects $A$ and $C$ if and only if: either $(i)$
$\mathit{high}_{1}(u)\in C$ and the $\mathit{high}_{1}$-edge of $u$ is not in
$E^{\prime}$, or $(ii)$ $\mathit{high}_{2}(u)\in C$ and the
$\mathit{high}_{2}$-edge of $u$ is not in $E^{\prime}$. Also, there is a back-
edge in $G\setminus E^{\prime}$ that connects $A$ and $D$ if and only if:
either $(i)$ $\mathit{low}_{1}(u)\in D$ and the $\mathit{low}_{1}$-edge of $u$
is not in $E^{\prime}$, or $(ii)$ $\mathit{low}_{2}(u)\in D$. Thus, we can
easily check those conditions in constant time.

So let us assume that none of the above is true. Thus, there are two cases to
consider in $G\setminus E^{\prime}$: either $(1)$ there is a back-edge from
$A$ to $C$, but no back-edge from $A$ to $D$, or $(2)$ there is a back-edge
from $A$ to $D$, but no back-edge from $A$ to $C$.

Let us consider case $(1)$ first. Then, we add the edge $(\bar{u},\bar{w})$ to
$\mathcal{R}$. First, we will determine whether there is a back-edge from $B$
to $D$ in $G\setminus E^{\prime}$. Since there is no back-edge from $A$ to $D$
in $G\setminus E^{\prime}$, notice that there is a back-edge from $B$ to $D$
in $G\setminus E^{\prime}$ if and only if: either $\mathit{low}_{1}(v)\in D$
and the $\mathit{low}_{1}$-edge of $v$ is not in $E^{\prime}$, or
$\mathit{low}_{2}(v)\in D$ and the $\mathit{low}_{2}$-edge of $v$ is not in
$E^{\prime}$. Thus, we can check in constant time whether there is a back-edge
from $B$ to $D$ in $G\setminus E^{\prime}$. If we have determined that there
is no back-edge from $B$ to $D$ in $G\setminus E^{\prime}$, then, since we
have supposed that there is a back-edge in $B(w)\setminus E^{\prime}$, we have
that there is a back-edge from $C$ to $D$ in $G\setminus E^{\prime}$ (since
$(A,D)\setminus E^{\prime}=(B,D)\setminus E^{\prime}=\emptyset$). This implies
that $w$ remains connected with $p(w)$ in $G\setminus E^{\prime}$. Thus, we
add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(w,p(w))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains two tree-edges) according to Lemma
7.4. So let us suppose that there is a back-edge from $B$ to $D$ in
$G\setminus E^{\prime}$. Then, we add the edge $(\bar{v},\bar{r})$ to
$\mathcal{R}$. Now it remains to determine if $(B,C)\setminus
E^{\prime}\neq\emptyset$ or $(C,D)\setminus E^{\prime}\neq\emptyset$. Notice
that either of those cases implies that $G\setminus E^{\prime}$ is connected.

We have $B(u)=(A,B)\cup(A,C)\cup(A,D)$,
$B(v)=(A,C)\cup(A,D)\cup(B,C)\cup(B,D)$ and $B(w)=(A,D)\cup(B,D)\cup(C,D)$.
Thus, we have
$N=\mathit{bcount}(w)-\mathit{bcount}(v)+\mathit{bcount}(u)=|(C,D)|-|(B,C)|+|(A,B)|+|(A,D)|$
and
$s=\mathit{SumAnc}(w)-\mathit{SumAnc}(v)+\mathit{SumAnc}(u)=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))+\mathit{SumAnc}((A,B))+\mathit{SumAnc}((A,D))$,
where we let $\mathit{SumAnc}(S)$, for a set $S$ of back-edges, be the sum of
the lower endpoints of the back-edges in $S$.

Here we distinguish two cases: either $(1.1)$ the back-edge in $E^{\prime}$
(if it exists) does not lie in $(A,B)\cup(A,D)$, or $(1.2)$ the back-edge $e$
in $E^{\prime}$ (exists and) lies in $(A,B)\cup(A,D)$. (It is easy to
determine in constant time which case applies.)

First, let us consider case $(1.1)$. Then we have $N=|(C,D)|-|(B,C)|$ and
$s=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))$. Here we distinguish two
cases: either $(1.1.1)$ the back-edge in $E^{\prime}$ (if it exists) does not
lie in $(C,D)\cup(B,C)$, or $(1.1.2)$ $E^{\prime}$ contains a back-edge $e$
that lies in $(C,D)\cup(B,C)$. (Again, it is easy to determine in constant
time which case applies.) So let us consider case $(1.1.1)$ first. Thus, if we
have $N\neq 0$, then at least one of $(C,D)$ and $(B,C)$ is not empty, and
therefore $G\setminus E^{\prime}$ is connected. Thus, it is sufficient to add
one more edge to $\mathcal{R}$ in order to make it connected (e.g., we may add
$(\bar{w},\bar{r})$). Otherwise, suppose that $N=0$. Then we have
$|(C,D)|=|(B,C)|$. Since the lower endpoint of every back-edge in $(C,D)$ is
lower than the lower endpoint of every back-edge in $(B,C)$, this implies that
$s=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))<0$ if and only if
$(C,D)\neq\emptyset$ (and $(B,C)\neq\emptyset$). Thus, it is sufficient to add
e.g. the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$ if and only if $s<0$.

Now let us consider case $(1.1.2)$. Let $z$ be the lower endpoint of $e$.
First, suppose that $e\in(C,D)$. Thus, if $N>1$, then $(C,D)\setminus
E^{\prime}$ is not empty, and therefore $G\setminus E^{\prime}$ is connected.
Similarly, if $N<1$, then $(B,C)$ is not empty, and therefore $G\setminus
E^{\prime}$ is connected. Thus, in those cases, it is sufficient to add one
more edge to $\mathcal{R}$ in order to make it connected (e.g., we may add
$(\bar{w},\bar{r})$). Otherwise, suppose that $N=1$. Then we have
$|(C,D)|=|(B,C)|+1$. Thus, if $|(B,C)|=0$, then we have $(C,D)=\\{e\\}$, and
therefore $s$ coincides with $z$. Otherwise, if $|(B,C)|>0$, then, since the
lower endpoint of every back-edge in $(C,D)$ is lower than the lower endpoint
of every back-edge in $(B,C)$, we have that
$s=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))<z$. Thus, it is sufficient to
add e.g. the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$ if and only if $s<z$.
Now let us suppose that $e\in(B,C)$. Thus, if $N>-1$, then $(C,D)$ is not
empty, and therefore $G\setminus E^{\prime}$ is connected. Similarly, if
$N<-1$, then $(B,C)\setminus E^{\prime}$ is not empty, and therefore
$G\setminus E^{\prime}$ is connected. Thus, in those cases, it is sufficient
to add one more edge to $\mathcal{R}$ in order to make it connected (e.g., we
may add $(\bar{w},\bar{r})$). Otherwise, suppose that $N=-1$. Then we have
$|(C,D)|+1=|(B,C)|$. Thus, if $|(C,D)|=0$, then we have $(B,C)=\\{e\\}$, and
therefore $s$ coincides with $-z$. Otherwise, if $|(C,D)|>0$, then, since the
lower endpoint of every back-edge in $(C,D)$ is lower than the lower endpoint
of every back-edge in $(B,C)$, we have that
$s=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))<-z$. Thus, it is sufficient
to add e.g. the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$ if and only if
$s<-z$.

Now let us consider case $(1.2)$. Then, since there is no back-edge from $A$
to $B$ in $G\setminus E^{\prime}$, and no back-edge from $A$ to $D$ in
$G\setminus E^{\prime}$, we have that one of $(A,B)$ and $(A,D)$ coincides
with $\\{e\\}$, and the other is empty. Then, we have $N=|(C,D)|-|(B,C)|+1$
and
$s=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))+\mathit{SumAnc}(\\{e\\}$).
Thus, if we have $N\neq 1$, then at least one of $(C,D)$ and $(B,C)$ is not
empty, and therefore $G\setminus E^{\prime}$ is connected. Thus, it is
sufficient to add one more edge to $\mathcal{R}$ in order to make it connected
(e.g., we may add $(\bar{w},\bar{r})$). Otherwise, suppose that $N=1$. Then we
have $|(C,D)|-|(B,C)|=0$. Since the lower endpoint of every back-edge in
$(C,D)$ is lower than the lower endpoint of every back-edge in $(B,C)$, this
implies that $\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))<0$ if and only if
$(C,D)\neq\emptyset$ (and $(B,C)\neq\emptyset$). Thus, it is sufficient to add
e.g. the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$ if and only if
$s<\mathit{SumAnc}(\\{e\\})$. (Notice that it is easy to compute
$\mathit{SumAnc}(\\{e\\})$: this is just the (DFS number of the) lower
endpoint of $e$.)

Now let us consider case $(2)$. Then, we add the edge $(\bar{u},\bar{r})$ to
$\mathcal{R}$. Now, if there is a back-edge that connects $B$ and $C$ in
$G\setminus E^{\prime}$, then we add the edge $(\bar{v},\bar{w})$ to
$\mathcal{R}$, we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v)\\}$,
and we revert to the previous case (where $E^{\prime}$ contains two tree-
edges) according to Lemma 7.4. Notice that, since there is no back-edge from
$A$ to $C$ in $G\setminus E^{\prime}$, this condition is equivalent to: either
$\mathit{high}_{1}(v)\in C$ and the $\mathit{high}_{1}$-edge of $v$ is not in
$E^{\prime}$, or $\mathit{high}_{2}(v)\in C$ and the $\mathit{high}_{1}$-edge
of $v$ is not in $E^{\prime}$. Thus, we can easily check whether there is a
back-edge that connects $B$ and $C$ in $G\setminus E^{\prime}$, in constant
time.

Now let us assume that there is no back-edge that connects $B$ and $C$ in
$G\setminus E^{\prime}$. Then, if there is a back-edge that connects $B$ and
$D$ in $G\setminus E^{\prime}$ $(*)$, then we have that $A$ and $B$ remain
connected in $G\setminus E^{\prime}$ through the mediation of $D$. Thus, we
add the edge $(\bar{u},\bar{v})$ to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains two tree-edges) according to Lemma
7.4. In order to check condition $(*)$, i.e., whether there is a back-edge
that connects $B$ and $D$ in $G\setminus E^{\prime}$, we distinguish the
following cases. First, suppose that the back-edge in $E^{\prime}$ (if it
exists), is neither in $B(u)$ nor in $B(v)$. Then, since all the back-edges in
$B(u)$ connect $A$ and $D$, and since all the back-edges in $B(v)$ connect
either $A$ and $D$ or $B$ and $D$, we have that $(*)$ is true if and only if
$\mathit{bcount}(v)>\mathit{bcount}(u)$. Now, suppose that the back-edge $e$
in $E^{\prime}$ is in $B(u)$, but not in $B(v)$. Then, all the back-edges in
$B(u)$, except $e$, connect $A$ and $D$, and all back-edges in $B(v)$ connect
either $A$ and $D$ or $B$ and $D$. Thus, we have that $(*)$ is true if and
only if $\mathit{bcount}(v)\geq\mathit{bcount}(u)$. Now, suppose that the
back-edge $e$ in $E^{\prime}$ is in both $B(u)$ and $B(v)$. Then, we have that
all the back-edges in $B(u)$, except possibly $e$, connect $A$ and $D$, and
all the back-edges in $B(v)$, except possibly $e$, connect $A$ and $D$ or $B$
and $D$. Thus, we have that $(*)$ is true if and only if
$\mathit{bcount}(v)>\mathit{bcount}(u)$. Finally, suppose that the back-edge
$e$ in $E^{\prime}$ is in $B(v)$, but not in $B(u)$. Then, all the back-edges
in $B(u)$ connect $A$ and $D$, and all the back-edges in $B(v)$, except
possibly $e$, connect $A$ and $D$ or $B$ and $D$. Thus, we have that $(*)$ is
true if and only if $\mathit{bcount}(v)>\mathit{bcount}(u)+1$. Thus, we can
easily check whether there is a back-edge that connects $B$ and $D$ in
$G\setminus E^{\prime}$, in constant time.

Finally, suppose that neither of the above two is the case (i.e., we have
$(B,C)\setminus E^{\prime}=\emptyset$ and $(B,D)\setminus
E^{\prime}=\emptyset$). Then we only have to check whether there is a back-
edge in $G\setminus E^{\prime}$ that connects $C$ and $D$. We distinguish the
following cases: either $(2.1)$ $E^{\prime}$ contains a back-edge $e\in(C,D)$,
or $(2.2)$ $E^{\prime}$ contains a back-edge $e\in(A,C)\cup(B,C)$, or $(2.3)$
none of the previous is true. (Notice that it is easy to determine in constant
time which case holds.) In case $(2.1)$ we have
$B(w)=(A,D)\cup((C,D)\setminus\\{e\\})\cup\\{e\\}$. Thus, there is a back-edge
from $C$ to $D$ in $G\setminus E^{\prime}$ if and only if
$\mathit{bcount}(w)>\mathit{bcount}(u)+1$. In case $(2.2)$ we have
$B(w)=(B(v)\setminus\\{e\\})\cup(C,D)$, and $e\in B(v)\setminus(C,D)$. Thus,
there is a back-edge from $C$ to $D$ in $G\setminus E^{\prime}$ if and only if
$\mathit{bcount}(w)>\mathit{bcount}(v)-1$. In case $(2.3)$ we have
$B(w)=B(v)\cup(C,D)$ and $e\notin(C,D)$. Thus, there is a back-edge from $C$
to $D$ in $G\setminus E^{\prime}$ if and only if
$\mathit{bcount}(w)>\mathit{bcount}(v)$. Thus, in either of those cases, if we
determine that there is a back-edge from $C$ to $D$ in $G\setminus
E^{\prime}$, then we add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$.

###  7.5 $E^{\prime}$ contains four tree-edges

Let $(u,p(u))$, $(v,p(v))$, $(w,p(w))$ and $(z,p(z))$ be the tree-edges that
are contained in $E^{\prime}$. Then we have that $\mathcal{R}$ consists of the
vertices $\\{\bar{u},\bar{v},\bar{w},\bar{z},\bar{r}\\}$. We may assume
w.l.o.g. that $u>v>w>z$. Suppose that there are at least two distinct edges
$(u^{\prime},p(u^{\prime}))$ and $(v^{\prime},p(v^{\prime}))$ in $E^{\prime}$
with the property that no edge in $E^{\prime}$ is a proper ancestor of them.
Let $E_{1}$ be the subset of $E^{\prime}$ that consists of the descendants of
$(u^{\prime},p(u^{\prime}))$, and let $E_{2}$ be the subset of $E^{\prime}$
that consists of the non-descendants of $(u^{\prime},p(u^{\prime}))$. Then, we
have that $(v^{\prime},p(v^{\prime}))\notin E_{1}$, and
$(u^{\prime},p(u^{\prime}))\notin E_{2}$. Thus, we can construct connectivity
graphs $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ for $G\setminus E_{1}$ and
$G\setminus E_{2}$, respectively, by reverting to the previous cases. Then, by
Lemma 7.5, we have that $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ is a connectivity
graph for $G\setminus E^{\prime}$.

Thus, we may assume that one of the tree-edges in $E^{\prime}$ is an ancestor
of the other three, because otherwise we can construct the graph $\mathcal{R}$
by reverting to the previous cases. Then, since $u>v>w>z$, we have that $z$ is
a common ancestor of all vertices in $\\{u,v,w\\}$. Now, there are four cases
to consider: either $(1)$ no two vertices in $\\{u,v,w\\}$ are related as
ancestor and descendant, or $(2)$ only two among $\\{u,v,w\\}$ are related as
ancestor and descendant, or $(3)$ one of $\\{u,v,w\\}$ is an ancestor of the
other two, but the other two are not related as ancestor and descendant, or
$(4)$ every two vertices in $\\{u,v,w\\}$ are related as ancestor and
descendant.

In case $(2)$, we can either have that $w$ is an ancestor of $v$ (and $u$ is
not related as ancestor and descendant with $w$ and $v$), or $v$ is an
ancestor of $u$ (and $w$ is not related as ancestor and descendant with $u$
and $v$). Both of these cases can be handled with essentially the same
argument (it is just that the roles of $w$, $v$ and $u$ in the first case are
exchanged with $v$, $u$ and $w$, respectively, in the second case), and so we
will assume w.l.o.g. that $v$ is an ancestor of $u$ in this case. In cases
$(3)$ and $(4)$, we have that the ancestry relation between the vertices in
$\\{u,v,w\\}$ is fixed by the assumption $u>v>w$. Thus, in case $(3)$ we have
that $w$ is an ancestor of both $v$ and $u$ (but $u,v$ are not related as
ancestor and descendant), and in case $(4)$ we have that $w$ is an ancestor of
$v$, and $v$ is an ancestor of $u$.

In any case, notice that there are no back-edges in $E^{\prime}$ (since we
have assumed that $|E^{\prime}|\leq 4$, and therefore $E^{\prime}$ consists of
four tree-edges).

####  7.5.1 No two vertices in $\\{u,v,w\\}$ are related as ancestor and
descendant

Let $A=T(u)$, $B=T(v)$, $C=T(w)$, $D=T(z)\setminus(T(u)\cup T(v)\cup T(w))$
and $E=T(r)\setminus T(z)$.

If we have that either $\mathit{high}_{1}(u)=\bot$, or
$\mathit{high}_{1}(v)=\bot$, or $\mathit{high}_{1}(w)=\bot$, then there is no
back-edge in $G\setminus E^{\prime}$ that connects $A$, or $B$, or $C$,
respectively, with the rest of the graph. Therefore, we can use Lemma 7.6 in
order to revert to the previous case (where $E^{\prime}$ contains three tree-
edges).

Otherwise, if we have that either $\mathit{high}_{1}(u)\in D$, or
$\mathit{high}_{1}(v)\in D$, or $\mathit{high}_{1}(w)\in D$, then we have that
$A$ is connected with $D$, or $B$ is connected with $D$, or $C$ is connected
with $D$, respectively, through a back-edge in $G\setminus E^{\prime}$.
Therefore, we add the edge $(\bar{u},\bar{z})$, or $(\bar{v},\bar{z})$, or
$(\bar{w},\bar{z})$, respectively, to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, or
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, or
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(w,p(w))\\}$, respectively, and we
revert to the previous case (where $E^{\prime}$ contains three tree-edges),
according to Lemma 7.4.

Thus, let us assume that $\mathit{high}_{1}(u)\in E$, and
$\mathit{high}_{1}(v)\in E$, and $\mathit{high}_{1}(w)\in E$. Then, we add the
edges $(\bar{u},\bar{r})$, $(\bar{v},\bar{r})$ and $(\bar{w},\bar{r})$ to
$\mathcal{R}$. Now, if $D$ is connected with the rest of the graph in
$G\setminus E^{\prime}$, then this can only be through a back-edge that starts
from $D$ and ends in $E$ (since $\mathit{high}_{1}(u)\in E$ and
$\mathit{high}_{1}(v)\in E$ and $\mathit{high}_{1}(w)\in E$, implies that
$(A,D)=(B,D)=(C,D)=\emptyset$). Then, the existence of a back-edge in $(D,E)$
is equivalent to the condition
$\mathit{bcount}(z)>\mathit{bcount}(u)+\mathit{bcount}(v)+\mathit{bcount}(w)$.
Thus, if this condition is satisfied, then we add the edge $(\bar{z},\bar{r})$
to $\mathcal{R}$.

####  7.5.2 $w$ and $v$ are not related as ancestor and descendant, and $v$ is
an ancestor of $u$

Let $A=T(u)$, $B=T(v)\setminus T(u)$, $C=T(w)$, $D=T(z)\setminus(T(v)\cup
T(w))$ and $E=T(r)\setminus T(z)$.

If we have that either $\mathit{high}_{1}(u)=\bot$, or
$\mathit{high}_{1}(w)=\bot$, then there is no back-edge in $G\setminus
E^{\prime}$ that connects $A$, or $C$, respectively, with the rest of the
graph. Therefore, we can use Lemma 7.6 in order to revert to the previous case
(where $E^{\prime}$ contains three tree-edges).

Otherwise, if we have that either $\mathit{high}_{1}(u)\in B$, or
$\mathit{high}_{1}(w)\in D$, then we have that $A$ is connected with $B$, or
$C$ is connected with $D$, respectively, through a back-edge in $G\setminus
E^{\prime}$. Therefore, we add the edge $(\bar{u},\bar{v})$, or
$(\bar{w},\bar{z})$, respectively, to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, or
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(w,p(w))\\}$, respectively, and we
revert to the previous case (where $E^{\prime}$ contains three tree-edges),
according to Lemma 7.4.

Similarly, if we have $\mathit{high}_{1}(u)\in D$ and $\mathit{low}_{1}(u)\in
E$, then we have that $A$ is connected with both $D$ and $E$, through back-
edges in $G\setminus E^{\prime}$. Therefore, we add the edge
$(\bar{z},\bar{r})$ to $\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(z,p(z))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4.

So let us assume that none of the above holds. This means that
$\mathit{high}_{1}(w)\in E$, and either $(1)$ $\mathit{high}_{1}(u)\in D$ and
$\mathit{low}_{1}(u)\in D$, or $(2)$ $\mathit{high}_{1}(u)\in E$.

Let us consider case $(1)$ first. Then we add the edges $(\bar{w},\bar{r})$
and $(\bar{u},\bar{z})$ to $\mathcal{R}$, and it remains to determine the
connectivity between $B$ and $D$ with the rest of the graph.

First, we check whether there is a back-edge that stems from $B$ and ends in
either $D$ or $E$. This is equivalent to checking whether
$\mathit{bcount}(v)>\mathit{bcount}(u)$ (since $\mathit{high}_{1}(u)\in D$
implies that $B(u)\subseteq B(v)$). If we have
$\mathit{bcount}(v)=\mathit{bcount}(u)$, then we have that $B$ is isolated
from the rest of the graph in $G\setminus E^{\prime}$. Thus, it remains to
determine whether $D$ is connected with $E$ through a back-edge. This is
equivalent to the condition $\mathit{bcount}(z)>\mathit{bcount}(w)$ (since
$\mathit{low}_{1}(u)\notin E$ implies that $B(u)\cap B(z)=\emptyset$, and then
$\mathit{high}_{1}(w)\in E$ implies that $B(w)\subseteq B(z)$). Thus, if this
is satisfied, then we add the edge $(\bar{z},\bar{r})$ to $\mathcal{R}$.

Otherwise, suppose that $\mathit{bcount}(v)>\mathit{bcount}(u)$. Let us
assume, first, that $\mathit{low}(v)\in D$. Then we have that
$B(v)=B(u)\sqcup(B,D)$. Thus, there is a back-edge from $B$ to $D$, and
therefore we add the edge $(\bar{v},\bar{z})$ to $\mathcal{R}$. Then we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains three tree-edges), according to
Lemma 7.4. Now let us assume that $\mathit{low}(v)\in E$. Then, since
$\mathit{low}(u)\in D$, we have that there is a back-edge from $B$ to $E$.
Thus, we insert the edge $(\bar{v},\bar{r})$ to $\mathcal{R}$. Now it remains
to determine whether $(B,D)\neq\emptyset$ or $(D,E)\neq\emptyset$. Notice that
either of those cases implies that $G\setminus E^{\prime}$ is connected
(because $\mathcal{R}$ already contains the edges $(\bar{u},\bar{z})$,
$(\bar{w},\bar{r})$ and $(\bar{v},\bar{r})$, and either of those cases implies
that we have to add the edge $(\bar{v},\bar{z})$ or $(\bar{z},\bar{r})$,
respectively). Since $\mathit{high}_{1}(u)\in D$ and $\mathit{low}_{1}(u)\in
D$, we have $B(u)=(A,D)$, $B(v)=(A,D)\cup(B,D)\cup(B,E)$, and
$B(z)=(B,E)\cup(C,E)\cup(D,E)$. Since $\mathit{high}_{1}(w)\in E$, we have
$B(w)=(C,E)$. Thus, we have the following:

  * •

$\mathit{bcount}(u)=|(A,D)|$.

  * •

$\mathit{bcount}(v)=|(A,D)|+|(B,D)|+|(B,E)|$.

  * •

$\mathit{bcount}(w)=|(C,E)|$.

  * •

$\mathit{bcount}(z)=|(B,E)|+|(C,E)|+|(D,E)|$.

This implies that
$N=\mathit{bcount}(z)-\mathit{bcount}(w)-\mathit{bcount}(v)+\mathit{bcount}(u)=|(D,E)|-|(B,D)|$.
Also, we have
$s=\mathit{SumAnc}(z)-\mathit{SumAnc}(w)-\mathit{SumAnc}(v)+\mathit{SumAnc}(u)=\mathit{SumAnc}((D,E))-\mathit{SumAnc}((B,D))$.
Now, if $N\neq 0$, then at least one of $(D,E)$ and $(B,D)$ is not empty, and
therefore $G\setminus E^{\prime}$ is connected. Thus, it is sufficient to add
one more edge to $\mathcal{R}$ in order to make it connected (e.g., we may add
$(\bar{v},\bar{z})$). Otherwise, we have $|(D,E)|=|(B,D)|$. Then, since the
lower endpoint of every back-edge in $(D,E)$ is lower than the lower endpoint
of every back-edge in $(B,D)$, we have that $s<0$ if and only if $|(D,E)|>0$
(and $|(B,D)|>0$). Thus, we add one more edge to $\mathcal{R}$ in order to
make it connected (e.g., $(\bar{v},\bar{z})$), if and only if $s<0$.

Now let us consider case $(2)$. Then we add the edges $(\bar{w},\bar{r})$ and
$(\bar{u},\bar{r})$ to $\mathcal{R}$. Since $\mathit{high}_{1}(u)\in E$, we
have that there is a back-edge from $B$ to $D$ if and only if
$\mathit{high}_{1}(v)\in D$. In this case, we add the edge $(\bar{v},\bar{z})$
to $\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(v,p(v))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4. So let us
suppose that $\mathit{high}_{1}(v)\in E$. In this case, it may be that there
is a back-edge from $B$ to $E$. Since $\mathit{high}_{1}(u)\in E$ and
$\mathit{high}_{1}(v)\in E$, the existence of a back-edge from $B$ to $E$ is
equivalent to $\mathit{bcount}(v)>\mathit{bcount}(u)$. If that is the case,
then we have that $A$ is connected with $B$ in $G\setminus E^{\prime}$ through
the mediation of $E$. Thus, we add the edge $(\bar{u},\bar{v})$ to
$\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4. So let us
assume that there is no back-edge from $B$ to $E$. Since
$\mathit{high}_{1}(u)\in E$ and $\mathit{high}_{1}(v)\in E$, this implies that
$B$ is isolated from the rest of the graph in $G\setminus E^{\prime}$. Then,
it remains to check whether there is a back-edge from $D$ to $E$. Since
$\mathit{high}_{1}(u)\in E$ and $\mathit{high}_{1}(w)\in E$ (and $B(v)=B(u)$),
we have that $B(z)=B(u)\sqcup B(w)$. Thus, there is a back-edge from $D$ to
$E$ if and only if $\mathit{bcount}(z)>\mathit{bcount}(u)+\mathit{bcount}(w)$.
In this case, we simply add the edge $(\bar{z},\bar{r})$ to $\mathcal{R}$.

####  7.5.3 $w$ is an ancestor of both $u$ and $v$, and $\\{u,v\\}$ are not
related as ancestor and descendant

Let $A=T(u)$, $B=T(v)$, $C=T(w)\setminus(T(u)\cup T(v))$, $D=T(z)\setminus
T(w)$, and $E=T(r)\setminus T(z)$.

If we have that either $\mathit{high}_{1}(u)=\bot$, or
$\mathit{high}_{1}(v)=\bot$, then there is no back-edge in $G\setminus
E^{\prime}$ that connects $A$, or $B$, respectively, with the rest of the
graph. Therefore, we can use Lemma 7.6 in order to revert to the previous case
(where $E^{\prime}$ contains three tree-edges).

Otherwise, if we have that either $\mathit{high}_{1}(u)\in C$, or
$\mathit{high}_{1}(v)\in C$, then we have that $A$ is connected with $C$, or
$B$ is connected with $C$, respectively, through a back-edge in $G\setminus
E^{\prime}$. Therefore, we add the edge $(\bar{u},\bar{w})$, or
$(\bar{v},\bar{w})$, respectively, to $\mathcal{R}$. Then we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, or
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, respectively, and we
revert to the previous case (where $E^{\prime}$ contains three tree-edges),
according to Lemma 7.4.

Similarly, if we have that either $\mathit{high}_{1}(u)\in D$ and
$\mathit{low}_{1}(u)\in E$, or $\mathit{high}_{1}(v)\in D$ and
$\mathit{low}_{1}(v)\in E$, then we have that $D$ remains connected with $E$
in $G\setminus E^{\prime}$, through the mediation of $A$ or $B$, respectively.
Therefore, we add the edge $(\bar{z},\bar{r})$ to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(z,p(z))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains three tree-edges), according to
Lemma 7.4. Also, if we have that $M(z)\in D$, then $D$ is connected with $E$
through a back-edge in $G\setminus E^{\prime}$. Therefore, we add the edge
$(\bar{z},\bar{r})$ to $\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(z,p(z))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4.

Thus, we may assume that none of the above is true. Therefore, we have that
$M(z)\notin D$, and there are four possibilities to consider: either $(1)$
$\mathit{high}_{1}(u)\in D$, $\mathit{low}_{1}(u)\in D$,
$\mathit{high}_{1}(v)\in D$ and $\mathit{low}_{1}(v)\in D$, or $(2)$
$\mathit{high}_{1}(u)\in D$, $\mathit{low}_{1}(u)\in D$,
$\mathit{high}_{1}(v)\in E$ and $\mathit{low}_{1}(v)\in E$, or $(3)$
$\mathit{high}_{1}(u)\in E$, $\mathit{low}_{1}(u)\in E$,
$\mathit{high}_{1}(v)\in D$ and $\mathit{low}_{1}(v)\in D$, or $(4)$
$\mathit{high}_{1}(u)\in E$, $\mathit{low}_{1}(u)\in E$,
$\mathit{high}_{1}(v)\in E$ and $\mathit{low}_{1}(v)\in E$. In either of those
cases, the problem will be to determine whether $C$ is connected with either
$D$ or $E$ through back-edges.

Let us consider case $(1)$ first. In this case, we add the edges
$(\bar{u},\bar{z})$ and $(\bar{v},\bar{z})$ to $\mathcal{R}$. If we have
$\mathit{low}_{1}(w)\in D$, then there are no back-edges from $C$ to $E$.
Thus, in order to check whether there is a back-edge from $C$ to $D$, it is
sufficient to check whether
$\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)$ (because
$\mathit{high}_{1}(u)\in D$ and $\mathit{high}_{1}(v)\in D$ imply that
$B(u)\cup B(v)\subseteq B(w)$; this can be strengthened to $B(u)\sqcup
B(v)\subseteq B(w)$, since $u$ and $v$ are not related as ancestor and
descendant). If that is the case, then we add the edge $(\bar{w},\bar{z})$ to
$\mathcal{R}$. (Otherwise, there is nothing to do.) On the other hand, if we
have $\mathit{low}_{1}(w)\in E$, then there is a back-edge from $C$ to $E$
(since $\mathit{low}_{1}(u)\in D$ and $\mathit{low}_{1}(v)\in D$). Thus, we
add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$. Now it remains to determine
whether there is a back-edge that connects $C$ with $D$. We claim that this is
equivalent to checking whether
$\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)+\mathit{bcount}(z)$.
To see this, first notice that $B(u)\sqcup B(v)\subseteq B(w)$ (since
$\mathit{high}_{1}(u)\in D$ and $\mathit{high}_{1}(v)\in D$). We also have
that $(B(u)\cup B(v))\cap B(z)=\emptyset$ (since $\mathit{low}_{1}(u)\in D$
and $\mathit{low}_{1}(v)\in D$). We also have $B(z)\subseteq B(w)$ (since
$M(z)\notin D$). This shows that $B(u)\sqcup B(v)\sqcup B(z)\subseteq B(w)$.
Finally, notice that $B(w)\setminus(B(u)\cup B(v)\cup B(z))$ contains
precisely the back-edges that connect $C$ with $D$. Thus, it is sufficient to
check whether
$\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)+\mathit{bcount}(z)$.
If that is the case, then we add the edge $(\bar{w},\bar{z})$ to
$\mathcal{R}$.

Now let us consider case $(2)$. In this case, we add the edges
$(\bar{u},\bar{z})$ and $(\bar{v},\bar{r})$ to $\mathcal{R}$. Now we have to
determine whether there is a back-edge from $C$ to $D$, or from $C$ to $E$. We
claim that there is a back-edge from $C$ to $E$ if and only if $M(z)\in C$.
The necessity is obvious (since $M(z)\notin D$). To see the sufficiency,
notice that, since $\mathit{low}_{1}(u)\in D$, we have that all back-edges in
$B(z)$ have their higher endpoint either in $B$, or in $C$, or in $D$. The
last case is rejected, since $M(z)\notin D$. If all the back-edges in $B(z)$
have their higher endpoint in $B$, then $M(z)\in B$. Thus, if we have $M(z)\in
C$, then at least one back-edge in $B(z)$ must stem from $C$. Thus, if we have
$M(z)\in C$, then we add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$. Now it
remains to determine whether there is a back-edge from $C$ to $D$. Notice that
$B(w)$ can be partitioned into: the back-edges in $B(u)$ (since
$\mathit{high}_{1}(u)\in D$), the back-edges in $B(v)$ (since
$\mathit{high}_{1}(v)\in E$), the back-edges from $C$ to $D$, and the back-
edges from $C$ to $E$. Since $\mathit{low}_{1}(u)\in D$ and $M(z)\notin D$, we
have $(C,E)=B(z)\setminus B(v)$. Thus, in order to determine whether there is
a back-edge from $C$ to $D$, it is sufficient to check whether
$\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)+(\mathit{bcount}(z)-\mathit{bcount}(v))=\mathit{bcount}(u)+\mathit{bcount}(z)$.
If that is the case, then we add the edge $(\bar{w},\bar{z})$ to
$\mathcal{R}$. (Otherwise, there is nothing to do.) On the other hand, if
$M(z)\notin C$, then we know that there is no back-edge from $C$ to $E$. Thus,
in order to determine whether there is a back-edge from $C$ to $D$, it is
sufficient to check whether
$\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)$. If that is the
case, then we add the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$. Case $(3)$ is
treated with a similar argument.

Finally, let us consider case $(4)$. In this case, we add the edges
$(\bar{u},\bar{r})$ and $(\bar{v},\bar{r})$ to $\mathcal{R}$. Then, notice
that there is a back-edge from $C$ to $D$ if and only if
$\mathit{high}_{1}(w)\in D$ (since $\mathit{high}_{1}(u)\in E$ and
$\mathit{high}_{1}(v)\in E$). If that is the case, then we add the edge
$(\bar{w},\bar{z})$ to $\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(w,p(w))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4. Otherwise,
all the back-edges in $B(w)$ that stem from $C$ (if there are any), end in
$E$. Thus, in order to determine whether such a back-edge exists, we simply
check whether $\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(v)$
(because $B(u)\sqcup B(v)\subseteq B(w)$). If that is the case, then we add
the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$.

####  7.5.4 $w$ is an ancestor of $v$, and $v$ is an ancestor of $u$

Let $A=T(u)$, $B=T(v)\setminus T(u)$, $C=T(w)\setminus T(v)$, $D=T(z)\setminus
T(w)$, and $E=T(r)\setminus T(z)$.

If we have that either $\mathit{high}_{1}(u)\in B$, or $M(z)\in D$, then we
have that $A$ is connected with $B$, or $D$ is connected with $E$,
respectively, through a back-edge. Thus, we insert the edge
$(\bar{u},\bar{v})$, or $(\bar{z},\bar{r})$, respectively, to $\mathcal{R}$.
Then we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, or
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(z,p(z))\\}$, respectively, and we
revert to the previous case (where $E^{\prime}$ contains three tree-edges),
according to Lemma 7.4.

If we have that either $\mathit{high}_{1}(u)\in C$ and $\mathit{low}_{1}(u)\in
D$, or $\mathit{high}_{1}(u)\in D$ and $\mathit{low}_{1}(u)\in E$, then we
have that $C$ is connected with $D$, or $D$ is connected with $E$,
respectively, through the mediation of $A$. Thus, we insert the edge
$(\bar{w},\bar{z})$, or $(\bar{z},\bar{r})$, respectively, to $\mathcal{R}$.
Then we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(w,p(w))\\}$, or
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(z,p(z))\\}$, respectively, and we
revert to the previous case (where $E^{\prime}$ contains three tree-edges),
according to Lemma 7.4.

So let us assume that neither of the above is true. (In particular, we have
$M(z)\notin D$, and therefore $B(z)=(A,E)\cup(B,E)\cup(C,E)$.) Then there are
four cases to consider. Either $(1)$ $\mathit{high}_{1}(u)\in C$ and
$\mathit{low}_{1}(u)\in C$, or $(2)$ $\mathit{high}_{1}(u)\in C$ and
$\mathit{low}_{1}(u)\in E$, or $(3)$ $\mathit{high}_{1}(u)\in D$ and
$\mathit{low}_{1}(u)\in D$, or $(4)$ $\mathit{high}_{1}(u)\in E$ and
$\mathit{low}_{1}(u)\in E$.

Let us consider case $(1)$ first. Then we add the edge $(\bar{u},\bar{w})$ to
$\mathcal{R}$. Notice that $\mathit{high}_{1}(v)\in C$. Thus, there are three
different cases to consider. Either $(1.1)$ $\mathit{low}_{1}(v)\in C$, or
$(1.2)$ $\mathit{low}_{1}(v)\in D$, or $(1.3)$ $\mathit{low}_{1}(v)\in E$. Let
us consider case $(1.1)$. Then, there is a back-edge from $B$ to $C$ if and
only if $\mathit{bcount}(v)>\mathit{bcount}(u)$. If that is the case, then we
add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains three tree-edges), according to
Lemma 7.4. Otherwise, we have that $B$ is isolated from the rest of the graph
in $G\setminus E^{\prime}$. It remains to determine whether $C$ is connected
with $D$ or $E$. If $\mathit{bcount}(z)=0$, then there is no back-edge from
$C$ to $E$. Then, since $\mathit{low}(v)\in C$, we have that $B(w)=(C,D)$.
Thus, there is a back-edge from $C$ to $D$ if and only if
$\mathit{bcount}(w)>0$. If that is the case, then we add the edge
$(\bar{w},\bar{z})$ to $\mathcal{R}$ (and we are done). So let us assume that
$\mathit{bcount}(z)>0$. Then, since $M(z)\notin D$ and $\mathit{low}(v)\in C$,
we have that $M(z)\in C$. Thus, there is a back-edge from $C$ to $E$, and so
we add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$. Since $M(z)\in C$ and
$\mathit{low}(v)\in C$, we have that $B(z)=(C,E)$. Furthermore, we have
$B(w)=(C,D)\cup(C,E)$. Thus, there is a back-edge from $C$ to $D$ if and only
if $\mathit{bcount}(w)>\mathit{bcount}(z)$. If that is the case, then we add
the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$.

Now let us consider case $(1.2)$. This means that $B$ is connected with $D$
with a back-edge, and so we add the edge $(\bar{v},\bar{z})$ to $\mathcal{R}$.
Notice that $\mathit{high}_{1}(w)\in D$. Thus, there are two cases to
consider. Either $(1.2.1)$ $\mathit{low}_{1}(w)\in D$, or $(1.2.2)$
$\mathit{low}_{1}(w)\in E$. Let us consider case $(1.2.1)$. Then, since
$M(z)\notin D$, we have that there are no back-edges from $D$ to $E$, and
therefore $B(z)=\emptyset$ (since $\mathit{low}(w)\in D$). This means that $E$
is isolated from the rest of the graph in $G\setminus E^{\prime}$. Thus, we
can use Lemma 7.6 in order to revert to the previous case (where $E^{\prime}$
contains three tree-edges). Now let us consider case $(1.2.2)$. Then there is
a back-edge from $C$ to $E$, and so we add the edge $(\bar{w},\bar{r})$ to
$\mathcal{R}$. Thus far, $\mathcal{R}$ contains the edges $(\bar{u},\bar{w})$,
$(\bar{v},\bar{z})$ and $(\bar{w},\bar{r})$. It remains to determine whether
$(B,C)\neq\emptyset$ or $(C,D)\neq\emptyset$. Observe that either of those
cases implies that $G\setminus E^{\prime}$ is connected, and therefore it is
sufficient to add one more edge to $\mathcal{R}$ in order to make it connected
(e.g., we may add $(\bar{v},\bar{w})$). Since $\mathit{high}_{1}(u)\in C$ and
$\mathit{low}_{1}(u)\in C$, we have $B(u)=(A,C)$. Then, since
$\mathit{low}_{1}(v)\in D$, we have $B(v)=(A,C)\cup(B,C)\cup(B,D)$. We also
have $B(w)=(B,D)\cup(C,D)\cup(C,E)$, and $B(z)=(C,E)$ (since $M(z)\notin D$).
Thus, we have the following:

  * •

$\mathit{bcount}(u)=|(A,C)|$.

  * •

$\mathit{bcount}(v)=|(A,C)|+|(B,C)|+|(B,D)|$.

  * •

$\mathit{bcount}(w)=|(B,D)|+|(C,D)|+|(C,E)|$.

  * •

$\mathit{bcount}(z)=|(C,E)|$.

This implies that
$N=\mathit{bcount}(w)-\mathit{bcount}(z)-\mathit{bcount}(v)+\mathit{bcount}(u)=|(C,D)|-|(B,C)|$.
Furthermore, we have
$s=\mathit{SumAnc}(w)-\mathit{SumAnc}(z)-\mathit{SumAnc}(v)+\mathit{SumAnc}(u)=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))$.
Thus, if $N\neq 0$, then at least one of $(C,D)$ and $(B,C)$ is not empty, and
therefore it is sufficient to add e.g. $(\bar{v},\bar{w})$ to $\mathcal{R}$ in
order to make it connected. Otherwise, if $N=0$, then we have
$|(C,D)|=|(B,C)|$. Then, since the lower endpoint of every back-edge in
$(C,D)$ is lower than the lower endpoint of every back-edge in $(B,C)$, we
have that $s=\mathit{SumAnc}((C,D))-\mathit{SumAnc}((B,C))<0$ if and only if
$(C,D)\neq\emptyset$ (and $(B,C)\neq\emptyset$). Thus, in the case $N=0$, we
add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$ if and only if $s<0$.

Now let us consider case $(1.3)$. Then, there is a back-edge from $B$ to $E$,
and so we add the edge $(\bar{v},\bar{r})$ to $\mathcal{R}$. Now there are two
cases to consider. Either $(1.3.1)$ $\mathit{high}_{1}(w)\in D$, or $(1.3.2)$
$\mathit{high}_{1}(w)\in E$. Let us consider case $(1.3.1)$. Then, since
$\mathit{low}_{1}(u)\in C$, we have that the $\mathit{high}_{1}$-edge of $w$
either stems from $B$ or from $C$. If the $\mathit{high}_{1}$-edge of $w$
stems from $B$, then we have that $D$ and $E$ remain connected in $G\setminus
E^{\prime}$ through the mediation of $B$. Thus, we add the edge
$(\bar{z},\bar{r})$ to $\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(z,p(z))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4. Otherwise, if
the $\mathit{high}_{1}$-edge of $w$ stems from $C$, then we have that this is
a back-edge from $C$ to $D$. Thus, we add the edge $(\bar{w},\bar{z})$ to
$\mathcal{R}$, we set $E^{\prime}\leftarrow
E^{\prime}\setminus\\{(w,p(w))\\}$, and we revert to the previous case (where
$E^{\prime}$ contains three tree-edges), according to Lemma 7.4. Now let us
consider case $(1.3.2)$. In this case, we have that $D$ is isolated from the
rest of the graph in $G\setminus E^{\prime}$, and therefore $\bar{z}$ should
be isolated in $\mathcal{R}$. Furthermore, all the back-edges in $B(w)$ that
stem from $C$ (if there are any), end in $E$. If $M(z)\in C$, then there is a
back-edge from $C$ to $E$. Thus, we add the edge $(\bar{w},\bar{r})$ to
$\mathcal{R}$, and we are done, because now $\mathcal{R}$ has enough edges to
make the vertices $\bar{u}$, $\bar{v}$, $\bar{w}$ and $\bar{r}$ connected.
Otherwise, let us assume that $M(z)\notin C$. Then there is no back-edge from
$C$ to $E$. Since $\mathit{high}(w)\in E$, there is no back-edge from $B$ to
$D$, or from $C$ to $D$. Notice that we have $B(u)=(A,C)$,
$B(v)=(A,C)\cup(B,C)\cup(B,E)$ and $B(w)=(B,E)$. Thus, there is a back-edge
from $B$ to $C$, if and only if
$\mathit{bcount}(v)>\mathit{bcount}(u)+\mathit{bcount}(w)$. If that is the
case, then we add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$. Thus, we have
exhausted all possibilities for case $(1.3)$.

Now let us consider case $(2)$. Then, we have that $A$ is connected with both
$C$ and $E$ in $G\setminus E^{\prime}$, and so we add the edges
$(\bar{u},\bar{w})$ and $(\bar{u},\bar{r})$ to $\mathcal{R}$. First, we check
whether there is back-edge from $B$ to $E$. Such a back-edge exists if and
only if there is a back-edge $(x,y)\in B(v)\setminus B(u)$ such that $y\leq
p(z)$. Thus, we can determine the existence of such a back-edge in constant
time, using the data structure from Lemma 6.23 (we assume that we have
performed the linear-time preprocessing that is required in order to build
this data structure). If there is a back-edge from $B$ to $E$, then we have
that $A$ and $B$ are connected in $G\setminus E^{\prime}$ through the
mediation of $E$. Thus, we add the edge $(\bar{u},\bar{v})$ to $\mathcal{R}$,
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains three tree-edges), according
to Lemma 7.4. Otherwise, suppose that there is no back-edge from $B$ to $E$.
Then, we check whether there is a back-edge $(x,y)\in B(v)\setminus B(u)$ such
that $y\leq p(w)$. (Again, we can perform this check in constant time using
Lemma 6.23.) If that is the case, then, since there is no back-edge from $B$
to $E$, we have that $(x,y)$ is a back-edge from $B$ to $D$. Otherwise, we
have that there is no back-edge from $B$ to $D$. So here we can distinguish in
constant time two cases: either $(2.1)$ there is a back-edge from $B$ to $D$,
or $(2.2)$ there is no back-edge from $B$ to $D$.

Let us consider case $(2.1)$. Then, we add the edge $(\bar{v},\bar{z})$ to
$\mathcal{R}$. We will determine whether there is a back-edge from $A$ to $D$,
or a back-edge from $B$ to $C$, or a back-edge from $C$ to $D$. Notice that,
in either of those cases, we have that $G\setminus E^{\prime}$ is connected,
and so it is sufficient to return a connected graph $\mathcal{R}$. Otherwise,
we have that $\mathcal{R}$ is a connectivity graph for $G\setminus
E^{\prime}$. (It is irrelevant whether there is a back-edge from $C$ to $E$,
because this does not add any new connectivity information, since we know that
the parts $C$ and $E$ are connected in $G\setminus E^{\prime}$ through the
mediation of $A$.) Since $\mathit{high}_{1}(u)\in C$, we have that
$B(u)=(A,C)\cup(A,D)\cup(A,E)$. Since there is no back-edge from $B$ to $E$,
we have that $B(v)=(A,C)\cup(A,D)\cup(A,E)\cup(B,C)\cup(B,D)$ and
$B(w)=(A,D)\cup(A,E)\cup(B,D)\cup(C,D)\cup(C,E)$. And since $M(z)\notin D$ and
there is no back-edge from $B$ to $E$, we have that $B(z)=(A,E)\cup(C,E)$.
Thus, we have the following:

  * •

$\mathit{bcount}(u)=|(A,C)|+|(A,D)|+|(A,E)|$.

  * •

$\mathit{bcount}(v)=|(A,C)|+|(A,D)|+|(A,E)|+|(B,C)|+|(B,D)|$.

  * •

$\mathit{bcount}(w)=|(A,D)|+|(A,E)|+|(B,D)|+|(C,D)|+|(C,E)|$.

  * •

$\mathit{bcount}(z)=|(A,E)|+|(C,E)|$.

This implies that
$\mathit{bcount}(z)-\mathit{bcount}(w)+\mathit{bcount}(v)-\mathit{bcount}(u)=|(B,C)|-|(C,D)|-|(A,D)|$.
Thus, if we have that
$\mathit{bcount}(z)-\mathit{bcount}(w)+\mathit{bcount}(v)-\mathit{bcount}(u)\neq
0$, then at least one of $(B,C)$, $(C,D)$ or $(A,D)$ is not empty. Thus, it
suffices to return a connected graph $\mathcal{R}$. Otherwise, suppose that
$\mathit{bcount}(z)-\mathit{bcount}(w)+\mathit{bcount}(v)-\mathit{bcount}(u)=0$.
Then we have that $|(B,C)|=|(C,D)|+|(A,D)|$. Consider the value
$\mathit{SumAnc}(z)-\mathit{SumAnc}(w)+\mathit{SumAnc}(v)-\mathit{SumAnc}(u)=\mathit{SumAnc}(B,C)-\mathit{SumAnc}(C,D)-\mathit{SumAnc}(A,D)$.
If we have that $|(B,C)|=0$, then we also have that $|(C,D)|+|(A,D)|=0$, and
therefore $\mathit{SumAnc}(B,C)-\mathit{SumAnc}(C,D)-\mathit{SumAnc}(A,D)=0$.
Otherwise, if $|(B,C)|>0$, then we have that
$\mathit{SumAnc}(B,C)>\mathit{SumAnc}(C,D)+\mathit{SumAnc}(A,D)$, because
$|(B,C)|=|(C,D)|+|(A,D)|$ and the lower endpoint of every back-edge in $(B,C)$
is greater than, or equal to, $w$, whereas the lower endpoint of every back-
edge in $(C,D)\cup(A,D)$ is lower than $w$. This implies that
$\mathit{SumAnc}(B,C)-\mathit{SumAnc}(C,D)-\mathit{SumAnc}(A,D)>0$. Thus, we
have shown that $|(B,C)|>0$ if and only if
$\mathit{SumAnc}(B,C)-\mathit{SumAnc}(C,D)-\mathit{SumAnc}(A,D)>0$. Thus, if
$\mathit{bcount}(z)-\mathit{bcount}(w)+\mathit{bcount}(v)-\mathit{bcount}(u)=0$,
then it is sufficient to check whether
$\mathit{SumAnc}(z)-\mathit{SumAnc}(w)+\mathit{SumAnc}(v)-\mathit{SumAnc}(u)>0$.
If that is the case, then we only have to add one more edge to $\mathcal{R}$
in order to make it connected (e.g., $(\bar{u},\bar{z})$). Otherwise, we have
that all of the sets $(A,D)$, $(B,C)$ and $(C,D)$ are empty, and $\mathcal{R}$
is already a connectivity graph for $G\setminus E^{\prime}$.

Now let us consider case $(2.2)$. Since there is no back-edge from $B$ to $E$
or from $B$ to $D$, it remains to check whether there is a back-edge from $B$
to $C$. Since $\mathit{high}_{1}(u)\in C$, we have that $B(u)\subseteq B(v)$.
Thus, there is a back-edge in $B(v)\setminus B(u)$ (and therefore a back-edge
from $B$ to $C$), if and only if $\mathit{bcount}(v)>\mathit{bcount}(u)$. If
that is the case, then we add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$.
Then we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, and we
revert to the previous case (where $E^{\prime}$ contains three tree-edges),
according to Lemma 7.4. Otherwise, let us assume that $B(v)=B(u)$. This
implies that $B$ is isolated from the rest of the graph in $G\setminus
E^{\prime}$. Now it remains to determine whether there is a back-edge from $A$
to $D$, or from $C$ to $D$. Since $B(v)=B(u)$, this is equivalent to
$\mathit{high}_{1}(w)\in D$. If that is the case, then at least one of $(A,D)$
and $(C,D)$ is not empty. Thus, we have that the parts $A$, $C$, $D$ and $E$,
are connected in $G\setminus E^{\prime}$. Therefore, it is sufficient to add
the edge $(\bar{u},\bar{z})$ to $\mathcal{R}$, in order to have a connectivity
graph for $G\setminus E^{\prime}$. Otherwise, if $\mathit{high}_{1}(w)\notin
D$, then $\mathcal{R}$ is already a connectivity graph for $G\setminus
E^{\prime}$.

Now let us consider case $(3)$. Then we add the edge $(\bar{u},\bar{z})$ to
$\mathcal{R}$. Since $\mathit{high}_{1}(u)\in D$, we have that, if
$\mathit{high}_{1}(v)\in C$, then there is a back-edge from $B$ to $C$. Then,
we add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$, we set
$E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, and we revert to the
previous case (where $E^{\prime}$ contains three tree-edges), according to
Lemma 7.4. So let us assume that $\mathit{high}_{1}(v)\notin C$. Here we
distinguish two cases: either $(3.1)$ $\mathit{low}(v)\in D$, or $(3.2)$
$\mathit{low}(v)\in E$.

Let us consider case $(3.1)$. Then we have that $B(v)=(A,D)\cup(B,D)$. Thus,
we have that there is a back-edge from $B$ to $D$ if and only if
$\mathit{bcount}(v)>\mathit{bcount}(u)$. If that is the case, then we have
that $A$ remains connected with $B$ in $G\setminus E^{\prime}$ through the
mediation of $D$. Thus, we add the edge $(\bar{u},\bar{v})$ to $\mathcal{R}$,
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains three tree-edges), according
to Lemma 7.4. So let us assume that there is no back-edge from $B$ to $D$.
Thus, $B$ is isolated from the rest of the graph in $G\setminus E^{\prime}$.
Now it remains to determine whether there is a back-edge from $C$ to $D$, or
from $C$ to $E$. We distinguish two cases: $(3.1.1)$ $\mathit{low}(w)\in D$,
or $(3.1.2)$ $\mathit{low}(w)\in E$. Let us consider case $(3.1.1)$. Then, we
have that $B(w)=(A,D)\cup(C,D)$. Thus, there is a back-edge from $(C,D)$ if
and only if $\mathit{bcount}(w)>\mathit{bcount}(u)$. If that is the case, then
we simply add the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$. Now let us
consider case $(3.1.2)$. Then, since $\mathit{low}(v)\in D$ and $M(z)\notin
D$, we have that there is a back-edge from $C$ to $E$. Thus, we add
$(\bar{w},\bar{r})$ to $\mathcal{R}$. Notice that we have $B(z)=(C,E)$, and
$B(w)=(A,D)\cup(C,D)\cup(C,E)$. Thus, there is a back-edge from $C$ to $D$ if
and only if $\mathit{bcount}(w)>\mathit{bcount}(u)+\mathit{bcount}(z)$. If
that is the case, then we add the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$.

Now let us consider case $(3.2)$. Then, since $\mathit{low}(u)\in D$, there is
a back-edge from $B$ to $E$. Thus, we add the edge $(\bar{v},\bar{r})$ to
$\mathcal{R}$. If $M(z)\in C$, then there is a back-edge from $C$ to $E$, and
therefore $B$ and $C$ remain connected in $G\setminus E^{\prime}$ through the
mediation of $E$. Thus, we add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$,
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains three tree-edges), according
to Lemma 7.4. So let us suppose that $M(z)\notin C$. Then it remains to
determine whether there is a back-edge from $B$ to $D$, or from $C$ to $D$.
Since $\mathit{high}_{1}(u)\in D$ and $\mathit{low}_{1}(u)\in D$, we have
$B(u)=(A,D)$. Since $M(z)\notin C$ and $\mathit{low}(v)\in E$, we have that
$B(z)=(B,E)$. Furthermore, we have $B(v)=(A,D)\cup(B,D)\cup(B,E)$. Thus, there
is a back-edge from $B$ to $D$ if and only if
$\mathit{bcount}(v)>\mathit{bcount}(u)+\mathit{bcount}(z)$. If that is the
case, then we add the edge $(\bar{v},\bar{z})$ to $\mathcal{R}$. Since
$M(z)\notin C$, we have that $B(w)=(A,D)\cup(B,D)\cup(B,E)\cup(C,D)$. Thus,
there is a back-edge from $C$ to $D$ if and only if
$\mathit{bcount}(w)>\mathit{bcount}(v)$. If that is the case, then we add the
edge $(\bar{w},\bar{z})$ to $\mathcal{R}$.

Now let us consider case $(4)$. Then there is a back-edge from $A$ to $E$, and
so we add the edge $(\bar{u},\bar{r})$ to $\mathcal{R}$. If we have that
$\mathit{high}_{1}(v)\in C$, then $B$ is connected with $C$ in $G\setminus
E^{\prime}$, and so we add the edge $(\bar{v},\bar{w})$ to $\mathcal{R}$. Then
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(v,p(v))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains three tree-edges), according
to Lemma 7.4. Thus, we may assume that $\mathit{high}_{1}(v)\notin C$. Then
there are two cases to consider: either $(4.1)$ $\mathit{high}_{1}(v)\in D$,
or $(4.2)$ $\mathit{high}_{1}(v)\in E$.

Now let us consider case $(4.1)$. Then there is a back-edge from $B$ to $D$,
and so we add the edge $(\bar{v},\bar{z})$ to $\mathcal{R}$. Now we
distinguish three cases, depending on the location of $M(z)$. Since
$M(z)\notin D$, we have that either $(4.1.1)$ $M(z)\in A$, or $(4.1.2)$
$M(z)\in B$, or $(4.1.3)$ $M(z)\in C$. Let us consider case $(4.1.1)$. Then we
have that $B(v)=(A,E)\cup(B,D)$. Furthermore, there is no back-edge from $C$
to $E$. Thus, it remains to determine whether there is a back-edge from $C$ to
$D$. Notice that we have $B(w)=(C,D)\cup(B,D)\cup(A,E)$. Thus,
$(C,D)=B(w)\setminus B(v)$. Thus, there is a back-edge from $C$ to $D$, if and
only if $\mathit{bcount}(w)>\mathit{bcount}(v)$. In this case, we simply add
the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$. Now let us consider case
$(4.1.2)$. This implies that there is a back-edge from $B$ to $E$, and
therefore $A$ and $B$ are connected in $G\setminus E^{\prime}$ through the
mediation of $E$. Thus, we add the edge $(\bar{u},\bar{v})$ to $\mathcal{R}$,
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains three tree-edges), according
to Lemma 7.4. Now let us consider case $(4.1.3)$. This implies that there is a
back-edge from $C$ to $E$, and so we add the edge $(\bar{w},\bar{r})$ to
$\mathcal{R}$. It remains to determine whether there is a back-edge from $B$
to $E$, or a back-edge from $C$ to $D$. Notice that either case implies that
$G\setminus E^{\prime}$ is connected. Thus, we only need to check whether
$(B,E)\cup(C,D)\neq\emptyset$. Since $\mathit{high}_{1}(u)\in E$, we have that
$B(u)=(A,E)$. Since $\mathit{high}_{1}(v)\in D$, we have that
$B(v)=(A,E)\cup(B,D)\cup(B,E)$. Furthermore, we have
$B(w)=(A,E)\cup(B,D)\cup(B,E)\cup(C,D)\cup(C,E)$, and
$B(z)=(A,E)\cup(B,E)\cup(C,E)$. Thus, we have the following:

  * •

$|B(u)|=|(A,E)|$.

  * •

$|B(v)|=|(A,E)|+|(B,D)|+|(B,E)|$.

  * •

$|B(w)|=|(A,E)|+|(B,D)|+|(B,E)|+|(C,D)|+|(C,E)|$.

  * •

$|B(z)|=|(A,E)|+|(B,E)|+|(C,E)|$.

This implies that $|B(z)|-|B(w)|+|B(v)|-|B(u)|=|(B,E)|-|(C,D)|$. Thus, if we
have that
$\mathit{bcount}(z)-\mathit{bcount}(w)+\mathit{bcount}(v)-\mathit{bcount}(u)\neq
0$, then we can be certain that one of $(B,E)$ and $(C,D)$ is not empty, and
therefore $G\setminus E^{\prime}$ is connected. Thus, it suffices to add
either $(\bar{v},\bar{r})$ or $(\bar{w},\bar{z})$ to $\mathcal{R}$, in order
to make it connected. Otherwise, if $|(B,E)|-|(C,D)|=0$, then we must use
other means in order to determine whether one of $(B,E)$ and $(C,D)$ is non-
empty. For this purpose, we consider the values $\mathit{SumAnc}$ of those
sets. Thus, we have that
$\mathit{SumAnc}(B,E)-\mathit{SumAnc}(C,D)=\mathit{SumAnc}B(z)-\mathit{SumAnc}B(w)+\mathit{SumAnc}B(v)-\mathit{SumAnc}B(u)$.
Then, if both $(B,E)$ and $(C,D)$ are empty, we have that
$\mathit{SumAnc}(B,E)-\mathit{SumAnc}(C,D)=0$. Otherwise, since $(B,E)$ and
$(C,D)$ have the same number of back-edges, and since the lower endpoints of
all back-edges in $(B,E)$ are lower than the lower endpoints of all back-edges
in $(C,D)$, we have that $\mathit{SumAnc}(B,E)-\mathit{SumAnc}(C,D)<0$. Thus,
we have that both $(B,E)$ and $(C,D)$ are non-empty if and only if
$\mathit{SumAnc}(B,E)-\mathit{SumAnc}(C,D)<0$. If that is the case, then it is
sufficient to return a connected graph $\mathcal{R}$.

Now let us consider case $(4.2)$. Since $\mathit{high}_{1}(u)\in E$, we have
that $B(u)\subseteq B(v)$. And since $\mathit{high}_{1}(v)\in E$, we have that
$B(v)=B(u)\sqcup(B,E)$. Thus, there is a back-edge from $B$ to $E$ if and only
if $\mathit{bcount}(v)>\mathit{bcount}(u)$. If that is the case, then we have
that $A$ is connected with $B$ in $G\setminus E^{\prime}$ through the
mediation of $E$. Thus, we add the edge $(\bar{u},\bar{v})$ to $\mathcal{R}$,
we set $E^{\prime}\leftarrow E^{\prime}\setminus\\{(u,p(u))\\}$, and we revert
to the previous case (where $E^{\prime}$ contains three tree-edges), according
to Lemma 7.4. So let us assume that there is no back-edge from $B$ to $E$.
This implies that $B$ is isolated from the remaining parts in $G\setminus
E^{\prime}$. Now, since $M(z)\notin D$, we have that either $(4.2.1)$ $M(z)\in
A$, or $(4.2.2)$ $M(z)\in C$. (The case $M(z)\in B$ is rejected, since
$(B,E)=\emptyset$.) Let us consider case $(4.2.1)$. Then, there is no back-
edge from $C$ to $E$, and it just remains to determine whether there is a
back-edge from $C$ to $D$. We have that $B(u)=(A,E)$ and
$B(w)=(A,E)\cup(C,D)$. Thus, there is a back-edge from $C$ to $D$ if and only
if $\mathit{bcount}(w)>\mathit{bcount}(u)$. If that is the case, then we
simply add the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$. Now let us consider
case $(4.2.2)$. In this case, there is a back-edge from $C$ to $E$, and so we
add the edge $(\bar{w},\bar{r})$ to $\mathcal{R}$. It remains to determine
whether there is a back-edge from $C$ to $D$. Since $\mathit{high}_{1}(u)\in
E$ and $\mathit{high}_{1}(v)\in E$, we have that there is a back-edge from $C$
to $D$ if and only if $\mathit{high}_{1}(w)\in D$. If that is the case, then
we simply add the edge $(\bar{w},\bar{z})$ to $\mathcal{R}$.

###  7.6 The data structure

According to the preceding analysis, in order to be able to answer
connectivity queries in the presence of at most four edge-failures in constant
time, it is sufficient to have computed the following items:

  * •

A DFS-tree of the graph rooted at a vertex $r$.

  * •

The values $\mathit{ND}(v)$, $\mathit{bcount}(v)$, $M(v)$ and
$\mathit{SumAnc}(v)$, for all vertices $v\neq r$.

  * •

The $\mathit{low}_{1}$, $\mathit{low}_{2}$, $\mathit{low}_{3}$,
$\mathit{low}_{4}$, $\mathit{high}_{1}$, $\mathit{high}_{2}$ and
$\mathit{high}_{3}$ edges of $v$, for every vertex $v\neq r$.

  * •

The data structure in Lemma 6.23 for answering back-edge queries.

Thus, we need $O(n)$ space to store all these items, and the results of
Section 6 imply that we can compute all of them in linear time in total.

Finally, let us describe how to answer the queries. First, given the set of
edges $E^{\prime}$ that failed (with $|E^{\prime}|\leq 4$), we build a
connectivity graph $\mathcal{R}$ of $G\setminus E^{\prime}$, by going through
the case analysis that is described in the preceding subsections. This takes
$O(1)$ time in total. Now let $x$ and $y$ be the two query vertices. Then we
determine the root of the connected component of $T\setminus E^{\prime}$ that
contains $x$. This is given either by the largest higher endpoint of the tree-
edges in $E^{\prime}$ that is an ancestor of $x$, or by $r$ if there is no
tree-edge in $E^{\prime}$ whose higher endpoint is an ancestor of $x$. Thus,
retrieving this root takes $O(1)$ time. Then we do the same for the other
query vertex too, and let $r_{1}$ and $r_{2}$ be the two roots that we have