# Edge-Cuts and Rooted Spanning Trees

Mohit Daga<EMAIL_ADDRESS>KTH Royal Institute of Technology, Stockholm - Sweden

###### Abstract

We give a closed form formula to determine the size of a $k$-respecting cut.
Further, we show that for any $k$, the size of the $k$-respecting cut can be
found only using the size of $2$-respecting cuts.

###### keywords:

##  1 Introduction

An edge-cut of a graph is said to $k$ respect a given spanning tree, if the
cut shares $k$ edges with the tree. The technique of finding cuts that
k-respect a given set of spanning trees is used in designing algorithms to
find the size of cuts. The pioneering use appears in two breakthrough results
by Karger (ACM STOC 1996 and JACM 2000) and Thorup (ACM STOC 2001 and
Combinatorica 2007). The former [12] gives the first linear time algorithm to
find the size of a min-cut, whereas the later [18] gives the first fully
dynamic algorithm for min-cuts. A common technique among these is to find the
size of a minimum 2-respecting cut in a given set of spanning trees. Over the
years this technique of finding a 2-respecting cut have found applications in
designing algorithms to find min-cuts in several different settings and
computational models: centralized, parallel, distributed, streaming, and
dynamic.

In the centralized setting post the breakthrough result by Karger, recent
results by Kwarabayashi and Thorup [13], improved further by Henzinger et al.
[11] give a deterministic linear time. Several simpler algorithms have been
designed that find the size of a min cut using new algorithms to find the size
of a 2-respecting cut given a set of trees [2, 8, 17]. Further, a recent
breakthrough result that finds all pairs max flow in $\tilde{O}(n^{2})$ uses
$4$-respecting cuts [1]. .

In the distributed setting the first sub linear algorithm [6] uses the concept
of 2-respecting cut. Here the algorithms to find the min-cut has two parts:
algorithm to reduce the size of the graph through a contraction mechanism and
given a set of trees provide efficient algorithm to find the size of a
2-respecting cut. The result in [6] is further improved by providing better
algorithm for one of the two parts, even leading to an optimal algorithm to
find the size of min-cut [5, 10, 9, 14]. Though, the underlying similarity of
finding the size of a minimum 2-respecting cut is common among all. There are
several open problems that still remain here, for example the size of a small
cut [16, 15], for a constant $k$.

Most of the aforementioned results rely on a closed form expression to find
size of 2-respecting cuts, and the fact that only a small number of trees are
required to be constructed in order to find a tree that 2-respects the minimum
cut. The guarantees regarding the small number of trees come from Nash
Williams, which states that the number of disjoint trees in a $k$-connected
graph is at most $k/2$ [4, 7]. In this paper, we extend the closed form
expression to find size of any k-respecting cut. Furthermore, we show that the
size of any k-respecting cut can just be found using the size of 2-respecting
cuts. Our results rely on the cut-space concept from graph-theory. First, we
give a closed form expression that finds the size of any k-respecting cut
(Theorem 1.1). Secondly, we show that the size of any k-respecting cut can be
find if we know the size of $1$-respecting cuts, and $2$-respecting cuts
(Theorem 1.2).

Let $G=(V,E)$ be the given tree. Given a rooted spanning tree T, let $E(T)$ be
the edges in the tree, and let ${{e}}_{{T}}\left(v\right)$, be the tree edge
between $v$ and its parent for all $v\in V$, except the root. For any
$A\subset V$, let $\delta(A)$ be the edges in the cut $(A,V\setminus A)$. For
any rooted spanning tree $T$, let ${v}^{\downarrow{T}}$ denote the set of
vertices that are decedents of $v$ in $T$, including $v$ itself.

######  Theorem 1.1.

Let $G=(V,E)$ be a given graph, let $T$ be a rooted spanning tree of $G$ and
$A\subset V$. Suppose
$E(T)\cap\delta(A)=\left\\{{{e}}_{{T}}\left(v_{1}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\right\\}$,
for some vertices $S=\left\\{v_{1},\ldots,v_{k}\right\\}$. Then

$\displaystyle|\delta(A)|=\sum_{l=1}^{k}(-1)^{l-1}2^{l-1}\sum_{S^{\prime}\subseteq[k]\atop|S^{\prime}|=l}\left|\bigcap_{i\in
S^{\prime}}\delta({v_{i}}^{\downarrow{T}})\right|$ (1)

Further using some combinatorial arguments we show that the size of any
$k$-respecting cut can just be found using pair-wise 2-respecting cuts.

######  Theorem 1.2.

Let $G=(V,E)$ be a given graph, let $T$ be a rooted spanning tree of $G$ and
$A\subset V$. Suppose
$E(T)\cap\delta(A)=\left\\{{{e}}_{{T}}\left(v_{1}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\right\\}$,
for some vertices $S=\left\\{v_{1},\ldots,v_{k}\right\\}$. Then $|\delta(A)|$
can be determined if the following is known

  * 1.

$|\delta({x}^{\downarrow{T}})|\ \forall x\in S$,

  * 2.

$|\delta({x}^{\downarrow{T}})\cap\delta({y}^{\downarrow{T}})|\ \forall x,y\in
S$ and

  * 3.

the path from root of $T$ to $x$ for all $x\in S$.

##  2 Preliminaries

For any rooted spanning tree $T$, we denote $r_{T}$ as its root. For any $v\in
V$, let ${v}^{\downarrow{T}}$ be the vertex set that are decedents of $v$ in
the tree $T$ including itself. Similarly, ${v}^{\uparrow{T}}$ is the set of
vertices which are on the path $r_{T}$ to $v$. For all vertices $v\in
V\setminus r_{T}$, we use $\pi_{{T}}\left(v\right)$ to denote the parent of
$v$ in $T$ and ${{e}}_{{T}}\left(v\right)$ to denote the tree edge between $v$
and $\pi_{{T}}\left(v\right)$. Let $\ell_{T}\left(v\right)$ be the distance of
vertex $v$ from the root $r_{T}$ in the tree $T$. Let
$\operatorname{children}_{T}(v)$ denote the children of the vertex $v$ in the
tree $T$. If $v$ is a leaf node, then define $\operatorname{children}_{T}(v)$
to be $\emptyset$. For any two vertices $v$ and $u$, we say that $v$ and $u$
are _independent w.r.t the tree $T$_, denoted using $v\perp_{T}u$ iff
${v}^{\downarrow{T}}\cap{u}^{\downarrow{T}}=\emptyset$. If they are not then
we say that they are not independent, and denote it using $v\not\perp_{T}u$.

We will use $\oplus$ to denote the symmetric difference operator. More
precisely, for any sets $A_{1},A_{2},\ldots,A_{k}$, we have
$a\in\bigoplus_{k^{\prime}=1}^{k}A_{k^{\prime}}$ iff
$|\\{k^{\prime}\in[k]:a\in A_{k^{\prime}}\\}|$ is odd. Throughout this paper,
when we use $\left\\{\right\\}$, we mean it to be set, and not multi-set. That
is each entry in $\\{\\}$ occurs exactly once. Whenever we use an index $k$,
it means a whole number less than the number of vertices in the graph.

We stress the readers to familiarize with $\oplus$ operator. We make the
following simple preposition to do the same. These qualify how the symmetric
difference operator appears when two sets are considered.

######  Proposition 2.3.

Let $A_{1}$ and $A_{2}$ be any two sets. Suppose $A_{1}\cap A_{2}=\emptyset$,
then $A_{1}\oplus A_{2}=A_{1}\cup A_{2}$. Further, suppose, $A_{2}\subseteq
A_{1}$, then $A_{1}\oplus A_{2}=A_{1}\setminus A_{2}$.

We use a well-known result that states that cut-spaces are a vector space with
respect to the $\oplus$ operator. This can be found in standard graph theory
books, for ex. Bondy and Murty [3].

######  Lemma 2.4 (Also noted as Proposition 2.1 in [16]).

Let $T$ be a given spanning tree and $v_{1},v_{2},\ldots,v_{k}\in V$. Then
$\delta({v_{1}}^{\downarrow{T}}\oplus{v_{2}}^{\downarrow{T}}\oplus\ldots\oplus{v_{k}}^{\downarrow{T}})=\delta({v_{1}}^{\downarrow{T}})\oplus\delta({v_{2}}^{\downarrow{T}})\oplus\ldots\oplus\delta({v_{k}}^{\downarrow{T}})$

We also mention a set-theoretic result for the cardinality of xor operation of
$k$ sets.

######  Proposition 2.5.

Suppose $A_{1},\ldots,A_{k}$ are some sets. Then

$\left|\bigoplus_{i=1}^{k}A_{i}\right|=\sum_{l=1}^{k}(-1)^{\ell-1}2^{l-1}\sum_{S\subseteq[k]\atop|S|=l}\left|\bigcap_{i\in
S}A_{i}\right|.$

##  3 Cut Characterization Lemma

In this section, we prove the characterization given in Theorem 1.1. We know
that $\delta(A)=\delta(V\setminus A)$. We show that for any $A\subset V$, if
$\delta(A)\cap
E(T)=\left\\{{{e}}_{{T}}\left(v_{1}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\right\\}$
for some vertex set $S=\left\\{v_{1},\ldots,v_{k}\right\\}$, where $v_{i}\in
V\setminus r_{T}$, then either
$A={v_{1}}^{\downarrow{T}}\oplus\ldots\oplus{v_{k}}^{\downarrow{T}}$ or
$V\setminus
A={v_{1}}^{\downarrow{T}}\oplus\ldots\oplus{v_{k}}^{\downarrow{T}}$. This
together with Lemma 2.4 and Proposition 2.5 leads to Theorem 1.1.

######  Proposition 3.6.

Let $T$ be a rooted spanning tree. For any vertex set $A\subset V$, either $A$
or $V\setminus A$ is equal to $\bigoplus_{v\in S}{v}^{\downarrow{T}}$for some
$S\subseteq V\setminus r_{T}$.

###### Proof.

Let the root $r_{T}\notin A$. For any $v\in A$, we know that for any
$c\in\operatorname{children}_{T}(v)$,
${c}^{\downarrow{T}}\subset{v}^{\downarrow{T}}$. Using Proposition 2.3,
$\left\\{v\right\\}={v}^{\downarrow{T}}\bigoplus\limits_{c\in\operatorname{children}_{T}(v)}{c}^{\downarrow{T}}$.
Thus,

$\displaystyle A$ $\displaystyle=\bigcup\limits_{v\in
A}{({v}^{\downarrow{T}}\bigoplus\limits_{c\in\operatorname{children}_{T}(v)}{c}^{\downarrow{T}})}$
$\displaystyle=\bigoplus\limits_{v\in
A}\left({v}^{\downarrow{T}}\bigoplus\limits_{c\in\operatorname{children}_{T}(v)}{c}^{\downarrow{T}}\right)$

Here the last equality is true because for any two sets $S_{1},S_{2}$ if
$S_{1}\cap S_{2}=\emptyset$, then $S_{1}\cup S_{2}=S_{1}\oplus S_{2}$ (see
Proposition 2.3). For avoiding multiplicity of occurrences and enforcing $S$
to be a set, we can remove any vertex $v$, if ${v}^{\downarrow{T}}$ occurs
even number of times, and keep it only once when it occur odd number of times.
When $r_{T}\in A$, then $V\setminus A$ can be represented similarly. ∎

######  Proposition 3.7.

For any $u,v\in V\setminus r_{T}$, if $u\neq v$ and $u\in{v}^{\downarrow{T}}$,
then $\pi_{{T}}\left(u\right)\in{v}^{\downarrow{T}}$.

######  Proposition 3.8.

For any, rooted spanning tree $T$ and $v\in V\setminus r_{T}$,
$\delta({v}^{\downarrow{T}})\cap E(T)={{e}}_{{T}}\left(v\right)$

###### Proof.

By definition, $v\in{v}^{\downarrow{T}}$ and
$\pi_{{T}}\left(v\right)\notin{v}^{\downarrow{T}}$, hence
${{e}}_{{T}}\left(v\right)\in{v}^{\downarrow{T}}$. Now for this proof, we need
to show that for $u\neq v$,
${{e}}_{{T}}\left(u\right)\notin{v}^{\downarrow{T}}$. Suppose not. Then both
$u,\pi_{{T}}\left(u\right)$ are not in ${v}^{\downarrow{T}}$ simultaneously.
But this cannot be true (see Proposition 3.7). ∎

Now we give a proposition that finds the tree edges in
$\delta({v_{1}}^{\downarrow{T}}\oplus{v_{2}}^{\downarrow{T}}\oplus\ldots\oplus{v_{k}}^{\downarrow{T}})$,
for any $v_{1},v_{2},\ldots,v_{k}\in V$.

######  Proposition 3.9.

Let $T$ be a rooted spanning tree. Let
$S=\left\\{v_{1},\ldots,v_{k}\right\\}\subset V\setminus r_{T}$. Then
$E(T)\cap\delta({v_{1}}^{\downarrow{T}}\oplus{v_{2}}^{\downarrow{T}}\oplus\cdots\oplus{v_{k}}^{\downarrow{T}})=\left\\{{{e}}_{{T}}\left(v_{1}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\right\\}$.

###### Proof.

From Lemma 2.4,
$\delta({v_{1}}^{\downarrow{T}}\oplus{v_{2}}^{\downarrow{T}}\oplus\cdots\oplus{v_{k}}^{\downarrow{T}})=\delta({v_{1}}^{\downarrow{T}})\oplus\delta({v_{2}}^{\downarrow{T}})\oplus\cdots\oplus\delta({v_{k}}^{\downarrow{T}})$.
From Proposition 3.8, $\delta({v}^{\downarrow{T}})\cap
E(T)={{e}}_{{T}}\left(v\right)$. Hence,
$\left\\{{{e}}_{{T}}\left(v_{1}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\right\\}$
are the only tree edge that survives in
$\delta({v_{1}}^{\downarrow{T}})\oplus\delta({v_{2}}^{\downarrow{T}})\oplus\ldots\oplus\delta({v_{k}}^{\downarrow{T}})$
because each one of these occurs only once, and no other edge in $E(T)$ is in
the set $\delta({v_{i}}^{\downarrow{T}})$. ∎

######  Proposition 3.10.

For any $A\subset V$, if $\delta(A)\cap
E(T)=\\{{{e}}_{{T}}\left(v_{1}\right),{{e}}_{{T}}\left(v_{2}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\\}$,
then either A, or $V\setminus A$ is equal to $v_{1}^{\downarrow}\oplus
v_{2}^{\downarrow}\oplus\cdots\oplus v_{k}^{\downarrow}$.

###### Proof.

We know that either $A$, or $V\setminus A$ can be written as $\bigoplus_{v\in
S}{v}^{\downarrow{T}}$ (see Proposition 3.6). Also,
$\delta(A)=\delta(V\setminus A)$. We claim that
$S=\left\\{v_{1},v_{2},\ldots,v_{k}\right\\}$, because if it is not, then
$\delta(A)\cap
E(T)\neq\\{{{e}}_{{T}}\left(v_{1}\right),{{e}}_{{T}}\left(v_{2}\right),\ldots,{{e}}_{{T}}\left(v_{k}\right)\\}$
(Proposition 3.9). ∎

###### Proof of Theorem 1.1.

According to the given condition, and Proposition 3.10
$\delta(A)=\delta(v_{1}^{\downarrow}\oplus
v_{2}^{\downarrow}\oplus\cdots\oplus
v_{k}^{\downarrow})=\delta({v_{1}}^{\downarrow{T}})\oplus\delta({v_{2}}^{\downarrow{T}})\oplus\cdots\oplus\delta({v_{k}}^{\downarrow{T}})$.
Using Proposition 2.5 concludes the proof. ∎

##  4 Proof of Theorem 1.2

We prove Theorem 1.2 in this section. For any vertex sets
$A_{1},A_{2},A_{3},\ldots A_{i}\subseteq V$ we define
$\gamma(A_{1},A_{2},\ldots,A_{i})\triangleq|\delta(A_{1})\cap\delta(A_{2})\cap\ldots\cap\delta(A_{i})|$.
For example $\gamma(A)=|\delta(A)|$,
$\gamma(A_{1},A_{2})=|\delta(A_{1})\cap\delta(A_{2})|$,
$\gamma(A_{1},A_{2},A_{3})=|\delta(A_{1})\cap\delta(A_{2})\cap\delta(A_{3})|$.
Note that $\gamma(\cdot)$ is an overloaded function.

The issue with Theorem 1.1 is the involvement of _$k$ -wise gamma_ values,
that is $\gamma(A_{1},\ldots,A_{k})$ for $k$ different vertex sets. We give
the following lemma which states that pair-wise gamma values are enough to
compute these $k$-wise gamma values, when our vertex sets are derived from a
spanning tree $T$, and are of the form ${x}^{\downarrow{T}}$ for any $x\in V$.
This combined with Theorem 1.1 proves Theorem 1.2.

######  Lemma 4.11.

Let $T$ be any spanning tree. Let
$S=\left\\{x_{1},x_{2},\ldots,x_{k}\right\\}$ be a subset of
$V\setminus\\{r_{T}\\}$, where $k\geq 2$. Then
$\gamma({{x_{1}}}^{\downarrow{T}},{{x_{2}}}^{\downarrow{T}},\ldots,{{x_{k}}}^{\downarrow{T}})$
is either equal to $0$ or
$\gamma({x_{i}}^{\downarrow{T}},{x_{j}}^{\downarrow{T}})$, for some
$x_{i},x_{j}\in S$.

We describe the proof in this section. We give four exhaustive cases based on
the ancestor-descendent relationships of the vertices in S with respect to the
spanning tree $T$. They are shown in Figure. 1.

${\textstyle x,y\ \in\ S}$$\begin{array}[]{l}{\textstyle\forall x,y\in
S,}{\textstyle\ x\perp_{T}y}\\\ {\textstyle\mathbf{CASE\ }-\ 1}\\\ \text{see
Proposition \ref{obs:gamma_1}}\end{array}$$\begin{array}[]{l}\exists x,y\in
S,\ x\not\perp_{T}y\end{array}$$\begin{array}[]{l}\exists x^{\prime}\in S,\
\forall y^{\prime}\in S,\\\ \ \ \ \ \ \ \ y^{\prime}\in x^{\prime\downarrow
T}\end{array}$$\begin{array}[]{l}\forall x^{\prime}\ \in S,\ \exists
y^{\prime}\in S,\\\ \ \ \ \ \ \ \ y^{\prime}\notin x^{\prime\downarrow T}\\\ \
\ \ \ \mathbf{CASE}\ -\ 4\\\ \text{see Proposition
\ref{obs:gamma_4}}\end{array}$$\begin{array}[]{l}\exists x^{\prime\prime}\in
S,\ \forall y^{\prime\prime}\in S,\\\ \ \ \ \ \ \ \ \ \ \ y^{\prime\prime}\in
x^{\prime\prime\uparrow T}\\\ \ \ \ \ \ \mathbf{CASE}\ -\ 2\\\ \text{see
Proposition \ref{obs:gamma_2}}\end{array}$$\begin{array}[]{l}\forall
x^{\prime\prime}\in S,\ \exists y^{\prime\prime}\in S,\\\ \ \ \ \ \ \ \ \ \ \
y^{\prime\prime}\notin x^{\prime\prime\uparrow T}\\\ \ \ \ \ \ \mathbf{CASE}\
-\ 3\\\ \text{see Proposition \ref{obs:gamma_3}}\end{array}$ Figure 1: The
figure represents the four different cases.

We show that the $k$ wise gamma value is zero in two of these cases: _CASE_ -1
and _CASE_ -3. Also, in the remaining two cases: _CASE_ -2 and _CASE_ -4, the
$k$ wise gamma value can be written in terms of pair-wise gamma value and
$k-1$ wise gamma value respectively, for any $k\geq 3$. Using recursion, this
implies that $k$ wise gamma value can be found from pair-wise gamma value if
we know the ancestor-decedent relationship of the vertices.

The cases in Figure 1 are based on the ancestor-decedent relationship of all
$x,y\in S$. Recall that $x\perp_{T}y$, if
${x}^{\downarrow{T}}\cap{y}^{\downarrow{T}}=\emptyset$. We show the following
simple observation. This shall enable the reader to get familiarized with the
$\perp_{T}$ operator.

######  Proposition 4.12.

Let $T$ be a rooted spanning tree. Let $x,y$ be any nodes. If
$x\not\perp_{T}y$, then either ${x}^{\downarrow{T}}\subset{y}^{\downarrow{T}}$
or ${y}^{\downarrow{T}}\subset{x}^{\downarrow{T}}$. Further, if
$x\not\perp_{T}y$, and $\ell_{T}\left(x\right)<\ell_{T}\left(y\right)$, then
${y}^{\downarrow{T}}\subset{x}^{\downarrow{T}}$.

###### Proof.

If $x\not\perp_{T}y$, then
${x}^{\downarrow{T}}\cap{y}^{\downarrow{T}}\neq\emptyset$. The set
${x}^{\downarrow{T}}$ contains $x$ and its decedents in the rooted spanning
tree $T$. If the intersection of ${x}^{\downarrow{T}}$ and
${y}^{\downarrow{T}}$ is not empty, it means that $x$ and $y$ have an
ancestor-decedent relationship in the tree $T$. Thus
${x}^{\downarrow{T}}\subset{y}^{\downarrow{T}}$ or
${y}^{\downarrow{T}}\subset{x}^{\downarrow{T}}$. When
$\ell_{T}\left(x\right)<\ell_{T}\left(y\right)$, then $y$ is a descendant of
$x$, hence ${y}^{\downarrow{T}}\subset{x}^{\downarrow{T}}$ ∎

We describe the four exhaustive cases from Figure 1. In _CASE_ -1,
$x\perp_{T}y$ $\forall x,y\in S$. In Proposition 4.14, we prove
$\gamma({{x_{1}}}^{\downarrow{T}},{{x_{2}}}^{\downarrow{T}},\ldots,{{x_{k}}}^{\downarrow{T}})=0$
for this case. _CASE_ -2,3,4 are negation of _CASE_ -1. In these cases,
$\exists x,y$ such that $x\not\perp_{T}y$. Further, these cases are divided
into two groups based on the statement: $\exists x^{\prime}\in S$ such that
$\forall y^{\prime}\in S$, $y^{\prime}\in x^{\prime\downarrow T}$
($y^{\prime}$ is a descendent of $x^{\prime}$). If this statement is false
then it is _CASE_ -4, if it is true, then it is one of _CASE_ -2 or _CASE_ -3.
For _CASE_ -4, in Proposition 4.17 we show that k-wise gamma value can be
found through $k-1$ wise gamma value. Lastly, _CASE_ -2,3 distinguish between
each other based on the statement: $\exists x^{\prime\prime}\in S$ such that
all $y^{\prime\prime}\in S$ are on the tree path from $r_{T}$ to
$x^{\prime\prime}$ ($y^{\prime\prime}\in x^{\prime\prime\uparrow T}$). If this
is true, then this is _CASE_ -2, and when it is false it is _CASE_ -3. In
Proposition 4.15, we show that for _CASE_ -2, k-wise gamma value can be found
through pair-wise gamma value. For _CASE_ -3, in Proposition 4.16, we show
that the k-wise gamma value is 0. Based on the aforementioned discussion, we
state the following lemma.

######  Lemma 4.13.

Let $T$ be any spanning tree. Let
$S=\left\\{x_{1},x_{2},\ldots,x_{k}\right\\}$ be a subset of
$V\setminus\\{r_{T}\\}$, where $k\geq 2$. If we know
$\gamma({x_{i}}^{\downarrow{T}},{x_{j}}^{\downarrow{T}})$ for all
$x_{i},x_{j}\in S$, and the ancestor decedent relationship between $x_{i}$ and
$x_{j}$ for all $x_{i},x_{j}\in S$, then
$\gamma({x}^{\downarrow{T}}_{1},{x}^{\downarrow{T}}_{2},\ldots,{x}^{\downarrow{T}}_{k})$
can be found.

######  Proposition 4.14.

Let $T$ be a rooted spanning tree and
$S=\left\\{x_{1},x_{2},\ldots,x_{k}\right\\}\subset
V\setminus\left\\{r_{T}\right\\}$ such that $|S|=k\geq 3$. If no child-
ancestor pair exists in $S$ i.e. $\forall x_{i},x_{j}\in S$,
$x_{i}\perp_{T}x_{j}$ , then
$\gamma({x}^{\downarrow{T}}_{1},{x}^{\downarrow{T}}_{2},\ldots,{x}^{\downarrow{T}}_{k})=0$.

$r_{T}$$x_{1}$$x_{2}$$x_{k}$${\textstyle x_{1}^{\downarrow T}}$${\textstyle
x_{2}^{\downarrow T}}$${\textstyle x_{k}^{\downarrow T}}$ Figure 2: Figure
shows the orientation of $x_{1},x_{2},\ldots,x_{k}$ in terms of their
ancestor-decedent relationships for _CASE_ -1

###### Proof.

Here, $\forall x_{i},x_{j}\in S$, we have $x_{i}\perp_{T}x_{j}$. This implies
${x_{i}}^{\downarrow{T}}\cap{x_{j}}^{\downarrow{T}}=\emptyset$. Since,
$|S|\geq 3$, no edge can have endpoints in ${x_{i}}^{\downarrow{T}}$ for all
$i$ simultaneously (an edge has only two endpoints). Thus
$\gamma({x}^{\downarrow{T}}_{1},{x}^{\downarrow{T}}_{2},\ldots,{x}^{\downarrow{T}}_{k})=0$.
∎

######  Proposition 4.15.

Let $T$ be a rooted spanning tree and
$S=\left\\{x_{1},x_{2},\ldots,x_{k}\right\\}\subset
V\setminus\left\\{r_{T}\right\\}$ such that $|S|=k\geq 3$. If

  1. 1.

$\exists x,y\in S,x\not\perp_{T}y$ (exists two nodes that are not
independent),

  2. 2.

$\exists x^{\prime}\in S,\ \forall y^{\prime}\in S,\
y^{\prime}\in{x^{\prime}}^{\downarrow{T}}$ (there exists an $x^{\prime}$ in
$S$ such that all $y^{\prime}$ in $S$ are decedents of x),

  3. 3.

$\exists x^{\prime\prime}\in S,\ \forall y^{\prime\prime}\in
S,y^{\prime\prime}\in x^{\prime\prime\uparrow T}$ (there exists an
$x^{\prime\prime}$ in $S$ such that all $y^{\prime\prime}$ in $S$ are
ancestors of $x$).

Then
$\gamma({x_{1}}^{\downarrow{T}},{x_{2}}^{\downarrow{T}},\ldots,{x}^{\downarrow{T}}_{k})=\gamma({p}^{\downarrow{T}},{q}^{\downarrow{T}})$,
where $p=\operatorname{argmax}_{x\in S}\ell_{T}\left(x\right)$ and
$q=\operatorname{argmin}_{x\in S}\ell_{T}\left(x\right)$.

$r_{T}$$x_{1}$$x_{2}$$x_{k}$${\textstyle x_{1}^{\downarrow T}}$${\textstyle
x_{2}^{\downarrow T}}$${\textstyle x_{k}^{\downarrow T}}$ Figure 3: Figure
shows the orientation of $x_{1},x_{2},\ldots,x_{k}$ in terms of their
ancestor-decedent relationships for _CASE_ -2

###### Proof.

Here, the third condition, subsumes the other two conditions. This is because,
if there exists a node $x^{\prime\prime}$ such that all other nodes are
ancestors of it (they are on the path from $x^{\prime\prime}$ to root
$r_{T}$). Then firstly, all of these are independent. Secondly, there also
exists a node such that all the other nodes are decedents of such a node.

WLOG, let
$\ell_{T}\left(x_{1}\right)>\ell_{T}\left(x_{2}\right)>\ldots>\ell_{T}\left(x_{k}\right)$.
Since all vertices in $S$ are on the tree path from $r_{T}$ to $x_{1}$, thus
we have,
${x_{1}}^{\downarrow{T}}\subset{x_{2}}^{\downarrow{T}}\ldots\subset{x_{k}}^{\downarrow{T}}$.
Similarly, $V\setminus{x_{1}}^{\downarrow{T}}\supset
V\setminus{x_{2}}^{\downarrow{T}}\ldots\supset
V\setminus{x_{k}}^{\downarrow{T}}$. By definition,
$\delta({x}^{\downarrow{T}})=\left\\{(u,v)|u\in{x}^{\downarrow{T}},v\in
V\setminus{x}^{\downarrow{T}}\right\\}$. Hence,

$\displaystyle\delta({x_{1}}^{\downarrow{T}})\cap\cdots\cap\delta({x_{k}}^{\downarrow{T}})$
$\displaystyle=$
$\displaystyle\left\\{(u,v)|u\in{x_{1}}^{\downarrow{T}},v\in\bigcap_{i}V\setminus{x_{1}}^{\downarrow{T}}\right\\}\bigcap\cdots\bigcap\left\\{(u,v)|u\in{x_{k}}^{\downarrow{T}},v\in\bigcap_{i}V\setminus{x_{k}}^{\downarrow{T}}\right\\}$
$\displaystyle=$ $\displaystyle\left\\{(u,v)|u\in{x_{1}}^{\downarrow{T}},v\in
V\setminus{x_{k}}^{\downarrow{T}}\right\\}\quad(\because{x_{1}}^{\downarrow{T}}\subset{x_{2}}^{\downarrow{T}}\ldots\subset{x_{k}}^{\downarrow{T}})$
$\displaystyle=$
$\displaystyle\left\\{(u^{\prime},v^{\prime})|u^{\prime}\in{x_{1}}^{\downarrow{T}},v^{\prime}\in
V\setminus{x_{1}}^{\downarrow{T}}\right\\}\cap\left\\{(u^{\prime\prime},v^{\prime\prime})|u^{\prime\prime}\in{x_{k}}^{\downarrow{T}},v^{\prime\prime}\in
V\setminus{x_{k}}^{\downarrow{T}}\right\\}$ $\displaystyle=$
$\displaystyle\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{k}}^{\downarrow{T}})$
(2)

Hence,
$\gamma({x_{1}}^{\downarrow{T}},{x_{2}}^{\downarrow{T}},\ldots,{x}^{\downarrow{T}}_{k})=|\delta({x_{1}}^{\downarrow{T}})\cap\cdots\cap\delta({x_{k}}^{\downarrow{T}})|=|\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{k}}^{\downarrow{T}})|=\gamma({x_{1}}^{\downarrow{T}},{x_{k}}^{\downarrow{T}})=\gamma({p}^{\downarrow{T}},{q}^{\downarrow{T}})$,
where $p=\operatorname{argmax}_{x\in S}\ell_{T}\left(x\right)$ and
$q=\operatorname{argmin}_{x\in S}\ell_{T}\left(x\right)$. ∎

######  Proposition 4.16.

Let $T$ be a rooted spanning tree and
$S=\left\\{x_{1},x_{2},\ldots,x_{k}\right\\}\subset
V\setminus\left\\{r_{T}\right\\}$ such that $|S|=k\geq 3$. If

  1. 1.

$\exists x,y\in S,x\not\perp_{T}y$ (exists two vertices that are not
independent),

  2. 2.

$\exists x^{\prime}\in S,\ \forall y^{\prime}\in S,\
y^{\prime}\in{x^{\prime}}^{\downarrow{T}}$ (there exists an $x^{\prime}$ in
$S$ such that all $y^{\prime}$ in $S$ are decedents of x),

  3. 3.

$\forall x^{\prime\prime}\in S,\ \exists y^{\prime\prime}\in
S,y^{\prime\prime}\not\in x^{\prime\prime\uparrow T}$ (for all
$x^{\prime\prime}$ in $S$ there exists a $y^{\prime\prime}$ in $S$ such that
$y^{\prime\prime}$ is not ancestor of $x^{\prime\prime}$).

Then
$\gamma({x_{1}}^{\downarrow{T}},{x_{2}}^{\downarrow{T}},\ldots,{x}^{\downarrow{T}}_{k})=0$.

$r_{T}$$x_{1}$$x_{2}$$x_{k}$${\textstyle x_{1}^{\downarrow T}}$${\textstyle
x_{2}^{\downarrow T}}$ Figure 4: Figure shows the orientation of
$x_{1},x_{2},\ldots,x_{k}$ in terms of their ancestor-decedent relationships
for _CASE_ -3

###### Proof.

Here, condition (2) subsumes condition (1). This is because there exists a
node such that all other nodes are its decedents. Let $x_{k}$ be such a node.
Hence $x_{k}\not\perp_{T}x_{i}$ for all $x_{i}\in S$, and $x_{i}\neq x_{k}$.
Let $x_{1}=\operatorname{argmax}_{x\in S}$ be the node that is furthest from
the root $r_{T}$ in the tree $T$. If many such nodes exist, then choose an
arbitrary node. Choosing a furthest node implies that there does not exist
$x\in S$, such that $x\in{x_{1}}^{\downarrow{T}}$. By condition (3), we know
that there is a node $x_{2}\notin x_{1}^{\uparrow T}$. But
$x_{2}\in{x}^{\downarrow{T}}_{k}$ (condition (2)), and by choice of $x_{1}$,
$x_{2}\notin{x_{1}}^{\downarrow{T}}$. Thus the set relationships of
${x_{1}}^{\downarrow{T}}$, ${x_{2}}^{\downarrow{T}}$, and
${x_{k}}^{\downarrow{T}}$ is as follows:
${x_{1}}^{\downarrow{T}}\subset{x_{k}}^{\downarrow{T}}$,
${x_{2}}^{\downarrow{T}}\subset{x_{k}}^{\downarrow{T}}$ and
${x_{1}}^{\downarrow{T}}\cap{x_{2}}^{\downarrow{T}}=\emptyset$.

In the remaining part we show
$\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{2}}^{\downarrow{T}})\cap\delta({x_{k}}^{\downarrow{T}})=\emptyset$.
Firstly, $\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{2}}^{\downarrow{T}})$
contains those edges which have one end point in ${x_{1}}^{\downarrow{T}}$ and
other in ${x_{2}}^{\downarrow{T}}$. Also, $\delta({x_{k}}^{\downarrow{T}})$
contains those edges which have one end point in ${x_{k}}^{\downarrow{T}}$ and
the other point outside of ${x_{k}}^{\downarrow{T}}$. Because of the
aforementioned set relationship, no edge in $\delta({x_{k}}^{\downarrow{T}})$
is contained in
$\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{2}}^{\downarrow{T}})$. Hence
$\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{2}}^{\downarrow{T}})\cap\delta({x_{k}}^{\downarrow{T}})=\emptyset$.
Thus
$\delta({x_{1}}^{\downarrow{T}})\cap\delta({x_{2}}^{\downarrow{T}})\cap\cdots\cap\delta({x_{k}}^{\downarrow{T}})=\emptyset$
which implies that
$\gamma({x}^{\downarrow{T}}_{1},{x}^{\downarrow{T}}_{2},\ldots,{x}^{\downarrow{T}}_{k})=0$.
∎

######  Proposition 4.17.

Let $T$ be a rooted spanning tree and
$S=\left\\{x_{1},x_{2},\ldots,x_{k}\right\\}\subset
V\setminus\left\\{r_{T}\right\\}$ such that $|S|=k\geq 3$. If

  1. 1.

$\exists x,y\in S,x\not\perp_{T}y$ (exists two vertices that are not
independent),

  2. 2.

$\forall x^{\prime}\in S,\exists y^{\prime}\in
S,y^{\prime}\notin{x^{\prime}}^{\downarrow{T}}$

Then
$\gamma({x_{1}}^{\downarrow{T}},{x_{2}}^{\downarrow{T}},\ldots,{x}^{\downarrow{T}}_{k})=\gamma({y_{1}}^{\downarrow{T}},\ldots,{y}^{\downarrow{T}}_{k-1})$
where
$\left\\{y_{1},y_{2},\ldots,y_{k-1}\right\\}=S\setminus\left\\{a\right\\}$ for
some $a\in S$.

$r_{T}$$v$$u$$a$${\textstyle v^{\downarrow T}}$${\textstyle u^{\downarrow
T}}$${\textstyle a^{\downarrow T}}$ Figure 5: Figure shows the orientation of
$a,v,u$ in terms of their ancestor-decedent relationships for _CASE_ -4

###### Proof.

Let $a,v$ be two nodes such that $a\not\perp_{T}v$ (condition (1)), where
$\ell_{T}\left(a\right)<\ell_{T}\left(v\right)$. Here we choose an $a,v$ pair
such that no other node $a^{\prime}$ exists in $S$ such that
$\ell_{T}\left(a^{\prime}\right)<\ell_{T}\left(a\right)$ and
$a^{\prime}\not\perp_{T}a$. If it exists then our chosen pair is
$a^{\prime},a$. Based on condition (3), we know that $\exists u$ such that
$u\notin{a}^{\downarrow{T}}$. According to the choice of $u,v$, and $a$, we
show that ${v}^{\downarrow{T}}\subset{a}^{\downarrow{T}}$, $a\perp_{T}u$, and
$v\perp_{T}u$. Firstly, ${v}^{\downarrow{T}}\subset{a}^{\downarrow{T}}$ is
true because $a\not\perp_{T}v$, and
$\ell_{T}\left(a\right)<\ell_{T}\left(v\right)$ (see Proposition 4.12). From
the choice, $u\notin{a}^{\downarrow{T}}$. Then either $a\perp_{T}u$, or $u$ is
the ancestor of $a$. The latter cannot be true because we have chosen $a$ such
that no $a^{\prime}\in S$ exists such that
$\ell_{T}\left(a^{\prime}\right)<\ell_{T}\left(a\right)$ and
$a^{\prime}\not\perp_{T}a$. Thus $u\perp_{T}a$. This also implies that
$u\perp_{T}v$, because ${v}^{\downarrow{T}}\subset{a}^{\downarrow{T}}$.

Lastly, in this proof we show that
$\delta({a}^{\downarrow{T}})\cap\delta({u}^{\downarrow{T}})\cap\delta({v}^{\downarrow{T}})=\delta({u}^{\downarrow{T}})\cap\delta({v}^{\downarrow{T}})$.
This implies that
$\gamma({x_{1}}^{\downarrow{T}},{x_{2}}^{\downarrow{T}}\ldots,{x}^{\downarrow{T}}_{k})=\gamma({y_{1}}^{\downarrow{T}},{y_{2}}^{\downarrow{T}}\ldots,{y}^{\downarrow{T}}_{k-1})$,
where
$\left\\{y_{1},y_{2},\ldots,y_{k-1}\right\\}=Q\setminus\left\\{a\right\\}$.
That is, we can eliminate ${a}^{\downarrow{T}}$ to compute
$\gamma({x_{1}}^{\downarrow{T}},{x_{2}}^{\downarrow{T}}\ldots,{x}^{\downarrow{T}}_{k})$.

$\displaystyle\delta({a}^{\downarrow{T}})\cap\delta({v}^{\downarrow{T}})\cap\delta({u}^{\downarrow{T}})$
$\displaystyle=$ $\displaystyle\left\\{(x,y)|x\in{a}^{\downarrow{T}},y\in
V\setminus{a}^{\downarrow{T}}\right\\}\cap\left\\{(x,y)|x\in{v}^{\downarrow{T}},y\in
V\setminus{v}^{\downarrow{T}}\right\\}$
$\displaystyle\cap\left\\{(x,y)|x\in{u}^{\downarrow{T}},y\in
V\setminus{u}^{\downarrow{T}}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{(x,y)|x\in{v}^{\downarrow{T}},y\in
V\setminus{a}^{\downarrow{T}}\right\\}\cap\left\\{(x,y)|x\in{u}^{\downarrow{T}},y\in
V\setminus{u}^{\downarrow{T}}\right\\}\quad(\therefore{v}^{\downarrow{T}}\subset{a}^{\downarrow{T}})$
$\displaystyle=$
$\displaystyle\left\\{(x,y)|x\in{v}^{\downarrow{T}},y\in{u}^{\downarrow{T}}\right\\}\quad(\because{v}^{\downarrow{T}}\subset
V\setminus{u}^{\downarrow{T}}\text{\ and\ }{u}^{\downarrow{T}}\subset
V\setminus{a}^{\downarrow{T}})$ $\displaystyle=$
$\displaystyle\delta\left({u}^{\downarrow{T}}\right)\cap\delta\left({v}^{\downarrow{T}}\right)$

The last inequality is true because $u\perp_{T}v$ and
$\left\\{(x,y)|x\in{v}^{\downarrow{T}},y\in{u}^{\downarrow{T}}\right\\}$
contain all the edges that have an endpoint in ${u}^{\downarrow{T}}$ and
${v}^{\downarrow{T}}$ ∎

## References

  * AKL+ [21] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi.  Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time.  November 2021.
  * BLS [20] Nalin Bhardwaj, Antonio Molina Lovett, and Bryce Sandlund.  A simple algorithm for minimum cuts in near-linear time.  In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, volume 162 of LIPIcs, pages 12:1–12:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * BM [76] J. Adrian Bondy and Uppaluri S. R. Murty.  Graph Theory with Applications.  Macmillan Education UK, 1976.
  * CMW+ [94] Boliong Chen, Makoto Matsumoto, Jianfang Wang, Zhongfu Zhang, and Jianxun Zhang.  A short proof of nash-williams’ theorem for the arboricity of a graph.  Graphs Comb., 10(1):27–28, 1994.
  * DEMN [21] Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai.  Distributed weighted min-cut in nearly-optimal time.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1144–1153. ACM, 2021.
  * DHNS [19] Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak.  Distributed edge connectivity in sublinear time.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 343–354. ACM, 2019.
  * Die [12] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * GMW [20] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Minimum cut in o(m log2 n) time.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 57:1–57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * GNT [20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup.  Faster algorithms for edge connectivity via random 2-out contractions.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1260–1279. SIAM, 2020.
  * GZ [22] Mohsen Ghaffari and Goran Zuzic.  Universally-optimal distributed exact min-cut.  pages 281–291, 2022.
  * HRW [20] Monika Henzinger, Satish Rao, and Di Wang.  Local flow partitioning for faster edge connectivity.  SIAM J. Comput., 49(1):1–36, 2020.
  * Kar [00] David R. Karger.  Minimum cuts in near-linear time.  J. ACM, 47(1):46–76, 2000.
  * KT [15] Ken-ichi Kawarabayashi and Mikkel Thorup.  Deterministic global minimum cut of a simple graph in near-linear time.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 665–674. ACM, 2015.
  * MN [20] Sagnik Mukhopadhyay and Danupon Nanongkai.  Weighted min-cut: sequential, cut-query, and streaming algorithms.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 496–509. ACM, 2020.
  * Par [19] Merav Parter.  Small cuts and connectivity certificates: A fault tolerant approach.  In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, volume 146 of LIPIcs, pages 30:1–30:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * PT [11] David Pritchard and Ramakrishna Thurimella.  Fast computation of small cuts via cycle space sampling.  ACM Trans. Algorithms, 7(4):46:1–46:30, 2011.
  * Sar [21] Thatchaphol Saranurak.  A simple deterministic algorithm for edge connectivity.  In Hung Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 80–85. SIAM, 2021.
  * Tho [07] Mikkel Thorup.  Fully-dynamic min-cut.  Comb., 27(1):91–127, 2007.