# Strengthened chain theorems for different versions of 4-connectivity

Guoli Ding
Department of Mathematics, Louisiana State University, Baton Rouge, USA
Chengfu Qin
Department of Mathematics, Nanning Normal University, Nanning, China
Corresponding author

###### Abstract

The chain theorem of Tutte states that every 3-connected graph can be
constructed from a wheel $W_{n}$ by repeatedly adding edges and splitting
vertices. It is not difficult to prove the following strengthening of this
theorem: every non-wheel 3-connected graph can be constructed from $W_{4}$ by
repeatedly adding edges and splitting vertices. In this paper we similarly
strengthen several chain theorems for various versions of 4-connectivity.

##  1 Introduction

If a graph $G$ contains a minor $H$ then by a $(G,H)$-chain we mean a sequence
$G_{0},G_{1},...,G_{t}$ of graphs such that $G_{0}=G$, $G_{t}=H$, and each
$G_{i}$ $(1\leq i\leq t)$ is a minor of $G_{i-1}$. If $\cal H$ is a class of
graphs then by a $(G,\cal H)$-chain we mean a $(G,H)$-chain for some $H\in\cal
H$. A result that asserts the existence of a chain of certain type is often
called a chain theorem. Probably the best known chain theorem is the following
result of Tutte. Let $\mathcal{W}=\\{W_{n}:n\geq 3\\}$, where $W_{n}$ is the
wheel on $n+1$ vertices. Let $|G|$ and $\|G\|$ denote the number of vertices
and edges, respectively, of a graph $G$.

######  Theorem 1.1 ([9]).

For every $3$-connected graph $G$ there exists a $(G,\cal W)$-chain
$G_{0},G_{1},...,G_{t}$ of $3$-connected graphs such that
$\|G_{i}\|=\|G_{i-1}\|-1$ for all $i=1,...,t$.

This theorem is a very powerful induction tool for analyzing 3-connected
graphs since it says that every 3-connected graph can be reduced to a wheel,
by reducing only one edge at a time, while maintaining 3-connectivity. If we
reverse this reduction process we see that every 3-connected graph can be
constructed from a wheel by repeatedly performing “undeletion” and
“uncontraction” (note that both operations preserve 3-connectivity). When such
a chain theorem is used to generate all 3-connected graphs, it is desirable to
limit the number of starting graphs (wheels). This in fact can be done. It is
not difficult to show that every non-wheel 3-connected graph can be
constructed using the same operations starting from $W_{4}$, instead of a
general unknown wheel. For completeness we include a proof of this result at
the end of the paper. From the algorithmic point of view, this strengthened
chain theorem is much more efficient since, in order to generate all
3-connected graphs, there is no need for us to consider extensions of all
wheels, it is enough for us to only consider extensions of a single wheel
$W_{4}$.

Currently, there are no known chain theorems for 5- or higher connectivity.
However, there are several results for different versions of 4-connectivity.
The purpose of this paper is to obtain similar strengthenings for three chain
theorems, respectively, for 4-connectivity, weakly 4-connectivity, and quasi
4-connectivity. In some cases we also refine the involved operations.

In the next three sections we discuss these three connectivities separately.
Our main results are Theorem 2.3, Theorem 3.2, and Theorem 4.2. Before closing
this section we introduce a few definitions. Let $G=(V,E)$ be a graph. For any
$X\subseteq V$, let $N_{G}(X)=\\{y\in V\backslash X$: there exists $x\in X$
with $xy\in E\\}$. Suppose $x\in V$. We will write $N_{G}(x)$ for
$N_{G}(\\{x\\})$. As usual, $|N_{G}(x)|$ is the degree of $x$, which is
denoted by $d_{G}(x)$. We will drop the subscript $G$ if there is no
confusion.

A separation of a graph $G=(V,E)$ is a pair of subgraphs $G_{i}=(V_{i},E_{i})$
($i=1,2$) of $G$ such that $G_{1}\cup G_{2}=G$, $E_{1}\cap E_{2}=\emptyset$,
and $V_{i}\neq V$ for both $i=1,2$. If $|V_{1}\cap V_{2}|=k$ then the
separation is called a $k$-separation and $V_{1}\cap V_{2}$ is called a
$k$-cut. For any integer $k\geq 3$, note that $G$ is $k$-connected if and only
if $G$ is simple, $|G|>k$, and $G$ has no $k^{\prime}$-separation for any
$k^{\prime}<k$.

For any two subgraphs $G_{1},G_{2}$ of a graph $G$, we will write
$G_{1}\backslash G_{2}$ for $G_{1}\backslash V(G_{2})$. We will use $si(G)$ to
denote the simplification of $G$. If $e$ is an edge of $G$, we use $\bar{e}$
to denote the vertex of $G/e$ obtained from contracting $e$. Further, if $e$
is contained in exactly one triangle which contains three edges $\\{e,f,h\\}$,
then we see that $si(G/e)\cong G/e\backslash f$. In the rest of the paper,
$si(G/e)$ will be replaced by $G/e\backslash f$ if $e$ is contained in exactly
one triangle and $si(G/e)$ will be replaced by $G/e$ if $e$ is contained in no
triangle. See [2] for undefined notation and terminology.

##  2 On 4-connected graphs

Let $\mathcal{C}=\\{C^{2}_{n}:n\geq 5\\}$, where $C^{2}_{n}$ is the graph
obtained from the $n$-cycle $C_{n}$ by joining vertices of distance two on the
cycle. Note that each $C^{2}_{n}$ is 4-connected, and in addition,
$C^{2}_{5}=K_{5}$ and $C^{2}_{6}=K_{2,2,2}=$ octahedron. A cubic graph with at
least six vertices is called internally $4$-connected if its line graph is
4-connected. Let $\mathcal{L}=\\{L:L$ is the line graph of an internally
4-connected cubic graph}. The following is a well known chain theorem for
4-connected graphs.

######  Theorem 2.1 ([3] and [5]).

For every $4$-connected graph $G$ there exists a $(G,\cal C\cup L)$-chain
$G_{0},G_{1},...,G_{t}$ of $4$-connected graphs such that
$G_{i}=si(G_{i-1}/e_{i})$ for all $i=1,...,t$.

This chain theorem has been strengthened as follows.

######  Theorem 2.2 ([8]).

For every $4$-connected graph $G\not\in\cal C\cup L$ there exists a
$(G,\\{C_{5}^{2},C_{6}^{2}\\})$-chain $G_{0},G_{1},...,G_{t}$ of $4$-connected
graphs such that $G_{i}=si(G_{i-1}/e_{i})$ for all $i=1,...,t$. In addition,
if $G$ is nonplanar then $G_{t}=C_{5}^{2}$.

This result implies that every 4-connected graph $G\not\in{\cal L}\cup{\cal
L}$ must contain a 4-connected minor on $|G|-1$ vertices. With this
formulation in mind, we can say that both Theorem 2.1 and Theorem 2.2 are
extension of Tutte Theorem to 4-connected graphs. However, this extension is
not totally satisfactory since in these two theorems the gap
$\|G_{i-1}\|-\|G_{i}\|$ could be arbitrarily large while the gap in Tutte
Theorem is only 1. Our main result in this section is to bound this gap.

For any integer $n\geq 3$, let $B_{n}$ (biwheel) be the graph obtained from
$C_{n}$ by adding two nonadjacent vertices (hubs) and joining them to all
vertices of $C_{n}$ (rim). Let $B_{n}^{+}$ be obtained from $B_{n}$ by adding
an edge (axle) between the two hubs. Note that $B_{3}^{+}=K_{5}=C_{5}^{2}$,
$B_{4}=C_{6}^{2}$, and $B_{4}^{+}=K_{1,1,2,2}$. In addition, every $B_{n}$ is
planar while every $B_{n}^{+}$ is nonplanar. Let
$\mathcal{B}=\\{B_{n},B_{n}^{+}:n\geq 4\\}$. Then every $B\in{\cal B}$ is
4-connected. Finally, let $O_{1}$ be the operation illustrated in Figure 2.1.
That is, $O_{1}(G)=G/xy\backslash xz$, where $d(x)=d(y)=4$, and $xyz$ is the
only triangle containing $xy$. The following is the main theorem of this
section.

Figure 2.1: Operation $O_{1}$, where $d(x)=d(y)=4$.

######  Theorem 2.3.

For every $4$-connected graph $G\not\in\cal B\cup C\cup L$ there exists a
$(G,\\{B_{4}^{+},B_{5}\\})$-chain $G_{0},G_{1},...,G_{t}$ of $4$-connected
graphs such that, for each $i=1,...,t$, either $\|G_{i}\|=\|G_{i-1}\|-1$ or
$G_{i}=O_{1}(G_{i-1})$. In addition, if $G$ is nonplanar then
$G_{t}=B_{4}^{+}$.

The following is a useful lemma, which says that “splitting” a vertex in a
$k$-connected graph also results in a $k$-connected graph. This lemma suggests
that Theorem 2.3 can be formulated in a slightly stronger form. Together with
this lemma, Theorem 2.3 implies that a graph $G\not\in\cal B\cup C\cup L$ is
4-connected if and only if there exists a $(G,\\{B_{4}^{+},B_{5}\\})$-chain
$G_{0},G_{1},...,G_{t}$ such that $\delta(G_{i})\geq 4$ ($0\leq i\leq t$) and
either $\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=O_{1}(G_{i-1})$ ($1\leq i\leq t$).
This formulation is very useful for generating 4-connected graphs since it
ensures that graphs generated according to the theorem are precisely
4-connected graphs that are not contained in $\cal B\cup C\cup L$.

######  Lemma 2.4.

Suppose a simple graph $G$ has an edge $xy$ such that
$\min\\{d_{G}(x),d_{G}(y)\\}\geq k$ and $si(G/xy)$ is $k$-connected. Then $G$
is also $k$-connected.

Proof. Suppose on the contrary that $G$ is not $k$-connected. Then $G$ has a
$k^{\prime}$-separation $(G_{1},G_{2})$ with $k^{\prime}<k$. Assume without
loss of generality that $xy\in G_{1}$. If $G_{1}\cap G_{2}$ contains both $x$
and $y$ then $G/xy$ admits a $(k^{\prime}-1)$-cut, contradicting the
$k$-connectivity of $si(G/xy)$. Hence, we may assume $x\in G_{1}\backslash
G_{2}$. If $G_{1}\backslash G_{2}$ contains a vertex different from $x$ then
$(G_{1}/xy,G_{2})$ is a $k^{\prime}$-separation of $G/xy$, again contradicting
the $k$-connectivity of $si(G/xy)$. Consequently, $x$ is the only vertex of
$G_{1}\backslash G_{2}$, which is impossible as $d_{G}(x)\geq k$. This
contradiction proves the lemma. ∎

We also need two other small technical lemmas for proving Theorem 2.3.

######  Lemma 2.5.

Let $G$ be a $k$-connected graph with a triangle $xyz$. If $si(G/xy)$ is
$k$-connected but $G\backslash xz$ is not, then $d_{G}(x)=k$ and $d_{G}(z)>k$.

Proof. First, since $si(G/xy)$ is $k$-connected, we must have
$d_{G}(z)=d_{si(G/xy)}(z)+1\geq k+1$. Next, suppose on the contrary that
$d_{G}(x)>k$. Let us consider a $k^{\prime}$-separation $(G_{1},G_{2})$ of
$G\backslash xz$ with $k^{\prime}<k$. Without loss of generality, let $x\in
G_{1}$. Then $x\in G_{1}\backslash G_{2}$ and $z\in G_{2}\backslash G_{1}$,
because otherwise $(G_{1},G_{2})$ would induce a $k^{\prime}$-separation of
$G$, which violates the $k$-connectivity of $G$. As a result, $y\in G_{1}\cap
G_{2}$. Since $d_{G}(x)>k$, $G_{1}\backslash G_{2}$ contains a vertex
different from $x$. It follows that $(G_{1},G_{2})$ induces a
$k^{\prime}$-separation of $G/xy$, which violates the $k$-connectivity of
$si(G/xy)$. This contradiction proves the lemma. ∎

######  Lemma 2.6.

Let $G$ and $si(G/xy)$ be $k$-connected. If $N_{G}(x)\backslash
N_{G}(y)=\\{y,z\\}$ then $si(G/xz)$ is $k$-connected.

Proof. Suppose otherwise. Then $G$ has a $k$-separation $(G_{1},G_{2})$ with
$x,z\in G_{1}\cap G_{2}$. Since $si(G/xy)$ is $k$-connected, we have $y\not\in
G_{1}\cap G_{2}$. By symmetry, let $y\in G_{1}\backslash G_{2}$. Then $x$ is
not adjacent to any vertex of $G_{2}\backslash G_{1}$, which implies that
$V(G_{1}\cap G_{2})\backslash x$ is a $(k-1)$-cut of $G$, a contradiction. ∎

The next lemma is the main part of our proof of Theorem 2.3. We consider the
following two assertions.

($*$) $G$ has a $4$-connected minor $H=G\backslash e$, $G/e$, or $O_{1}(G)$
such that
$H\not\in\mathcal{C}\cup\mathcal{L}\cup\mathcal{B}\backslash\\{B_{5},B_{4}^{+}\\}$.
Moreover, $H$ is not planar if $G$ is not.
($**$) $si(G/e)$ is $4$-connected, and $G/e$ is not planar if $G$ is not.

######  Lemma 2.7.

Suppose a $4$-connected graph $G$ does not satisfy $(*)$. If $e=xy$ is an edge
of $G$ that satisfies $(**)$ then $G\backslash\\{x,y\\}$ has four distinct
vertices $x^{\prime}$, $y^{\prime}$, $z$, $z^{\prime}$ such that
$N_{G}(x)=\\{x^{\prime},y,z,z^{\prime}\\}$,
$N_{G}(y)=\\{x,y^{\prime},z,z^{\prime}\\}$, and both $xx^{\prime},yy^{\prime}$
satisfy $(**)$.

Proof. We divide the proof into a few claims.

Claim 1. $e$ must be contained in a triangle.

Suppose $e$ belongs to no triangle. It follows that $d_{G/e}(\bar{e})\geq 6$.
Then $G/e$ is not 4-regular and thus $G/e\not\in\cal C\cup L$. If
$G/e\not\in\mathcal{B}\backslash\\{B_{5},B_{4}^{+}\\}$ then, by ($**$), $G$
satisfies ($*$) with $H=G/e$, a contradiction. Hence, we must have
$G/e=B\in\mathcal{B}\backslash\\{B_{5},B_{4}^{+}\\}$. Since
$d_{G/e}(\bar{e})\geq 6$, we see that $B=B_{n+1}$ or $B_{n}^{+}$, for some
$n\geq 5$, and $\bar{e}$ is a hub of $B$. In other words, $G$ is obtained from
$B_{n+1}$ or $B_{n}^{+}$ by splitting a hub. Let $uv$ be a rim edge of $B$ so
that neither $uvx$ nor $uvy$ is a triangle. Let $H=si(G/uv)$.

We first prove that $H$ is 4-connected. From the choice of $uv$ we have
$d_{H}(x)=d_{G}(x)$ and $d_{H}(y)=d_{G}(y)$, which imply
$\min\\{d_{H}(x),d_{H}(y)\\}\geq 4$. In addition, note that
$si(H/e)=si(G/e/uv)=si(B/uv)=B_{n}$ or $B_{n-1}^{+}$, which are 4-connected.
Therefore, by Lemma 2.4, $H$ is 4-connected.
Next, we observe that, in $G$, both $u$, $v$ have degree 4 and $uv$ is
contained in only one triangle $uvh$, where $h$ is the hub of $B$ with
$h\neq\bar{e}$. Hence, $H=O_{1}(G)$. From $d_{H}(\bar{uv})=5$ we also see that
$H\not\in\mathcal{C}\cup\mathcal{L}\cup\mathcal{B}\backslash\\{B_{5},B_{4}^{+}\\}$.

Since $G$ does not satisfy $(*)$, we deduce that $H$ is planar but $G$ is not.
However, since $e$ satisfies $(**)$, $G/e$ must be nonplanar, implying that
$G/e=B_{n}^{+}$. As a result, $H/e=B^{+}_{n-1}$. Since $n\geq 5$, we see that
$H/e$, and thus $H$, is in fact nonplanar. This contradiction proves Claim 1.

From now on we assume that $e$ is contained in a triangle $xyz$.

Claim 2. Neither $G\backslash xz$ nor $G\backslash yz$ is $4$-connected.

Suppose otherwise. By symmetry, let us assume that $G^{\prime}=G\backslash xz$
is 4-connected. We first prove that
$G^{\prime}\in\mathcal{B}\backslash\\{B_{5},B_{4}^{+}\\}$. To do so, we verify
that $G^{\prime}$ can almost play the role of $H$ in $(*)$.

(1) If $G$ is nonplanar then $G^{\prime}$ is also nonplanar.
To see this, note that $G/e$ is nonplanar, as $e$ satisfies $(**)$. Also note
that $si(G/e)=si(G^{\prime}/e)$, as $xyz$ is a triangle. Consequently,
$G^{\prime}/e$, and thus $G^{\prime}$, is nonplanar, which proves (1).

(2) $G^{\prime}\not\in\cal C\cup L$.
Suppose on the contrary that $G^{\prime}\in\cal C\cup L$. Then every edge of
$G^{\prime}$ belongs to triangle of $G^{\prime}$. As a result, $G$ contains a
triangle $xyz_{1}$ with $d_{G}(z_{1})=4$. It follows that
$d_{si(G/e)}(z_{1})=3$, which violates the 4-connectivity assumption on
$si(G/e)$. This contradiction proves (2).

Since $G$ does not satisfy $(*)$, we deduce from (1), (2), and the fact
$B_{4}=C_{6}^{2}\in\cal C$ that $G^{\prime}=B$ for some
$B\in\mathcal{B}\backslash\\{B_{4},B_{5},B_{4}^{+}\\}$. In other words,
$G=B+xz$, where $B$ contains both $xy$ and $yz$. Since $si(G/e)=si(G\backslash
xz/e)=si(B/e)$ and, by ($**$), $si(G/e)$ is 4-connected, we see that $e$ is
not incident with a hub of $B$. That is, $e$ must be a rim edge. Since $xz$ is
not an edge of $B$, $z$ can not be a hub and thus $yz$ is also a rim edge. Now
we see that $G$ is nonplanar since it is obtained by adding a chord to the rim
cycle of $B$. By ($**$), $si(G/e)$ is nonplanar, which means $si(B/e)$ is
nonplanar and thus $B=B_{n}^{+}$ for some $n\geq 5$. Let $f$ be the axle of
$B$. Then $H=G\backslash f$ is 4-connected and nonplanar (as $H=B_{n}+xz$) and
$H\not\in\mathcal{C}\cup\mathcal{L}\cup\mathcal{B}$ (as $H$ contains four
vertices of degree exceeding 4). It follows that $H$ satisfies $(*)$, which
violates our assumption. This contradiction proves Claim 2.

From Claim 2 and Lemma 2.5 we deduce that $d_{G}(x)=d_{G}(y)=4$ and
$d_{G}(z)>4$.

Claim 3. $e$ is contained in exactly two triangles.

If $xy$ belongs to more than two triangles than $|N_{G}(\\{x,y\\})|=3$, since
$d_{G}(x)=d_{G}(y)=4$. It follows that $V(G)=\\{x,y\\}\cup N_{G}(\\{x,y\\})$.
This implies $G=K_{5}$ and thus $si(G/e)$ is not 4-connected, a contradiction.

If $xy$ belongs to only one triangle $xyz$, let $H=si(G/e)$. Then
$H=G/xy\backslash xz$ and thus $H=O_{1}(G)$. Since $H$ has a vertex $\bar{e}$
of degree five,
$H\not\in\mathcal{C}\cup\mathcal{L}\cup\mathcal{B}\backslash\\{B_{5},B_{4}^{+}\\}$.
Now, by ($**$), $H$ satisfies ($*$), a contradiction. Hence, $e$ is contained
in exactly two triangles, which is Claim 3.

Now Claim 3 implies that $G\backslash\\{x,y\\}$ has four distinct vertices
$x^{\prime},y^{\prime},z,z^{\prime}$ such that
$N_{G}(x)=\\{x^{\prime},y,z,z^{\prime}\\}$ and
$N_{G}(y)=\\{x,y^{\prime},z,z^{\prime}\\}$.

Claim 4. Both $xx^{\prime}$ and $yy^{\prime}$ satisfy $(**)$.

By symmetry, we only need to consider $xx^{\prime}$. By Lemma 2.6,
$G^{\prime}=si(G/xx^{\prime})$ is 4-connected. If $G^{\prime}$ is planar then
$xyz$ and $xyz^{\prime}$ are faces of $G^{\prime}$, as $G^{\prime}$ is
4-connected. Since $N_{G}(x)=\\{x^{\prime},y,z,z^{\prime}\\}$ and
$x^{\prime}xy$ is not a triangle of $G$, any multiple edge of $G/xx^{\prime}$
must be parallel to $xz$ or $xz^{\prime}$. It follows that the planar
embedding of $G^{\prime}$ can be naturally extended into a planar embedding of
$G$, which means $G$ is planar. Hence, we conclude that $xx^{\prime}$
satisfies ($**$). This confirms Claim 4 and also completes our proof of the
lemma. ∎

######  Lemma 2.8.

If a $4$-connected graph $G$ does not satisfy $(*)$ then $G\in\cal B\cup C\cup
L$.

Proof. Let us assume $G\not\in\cal C\cup L$, for otherwise we are done.
Clearly, we only need to show that $G\in\cal B$. By Theorem 2.2, $G$ has an
edge $e=x_{1}x_{2}$ satisfying ($**$). Then, by Lemma 2.7,
$G\backslash\\{x_{1},x_{2}\\}$ has distinct vertices $x_{0},y,z,x_{3}$ such
that $N(x_{1})=\\{x_{0},y,z,x_{2}\\}$, $N(x_{2})=\\{x_{1},y,z,x_{3}\\}$, and
$x_{2}x_{3}$ satisfies ($**$). Next, by applying Lemma 2.7 to $x_{2}x_{3}$ we
deduce that $N(x_{3})=\\{u,v,x_{2},x_{4}\\}$ and $x_{3}x_{4}$ satisfies
($**$), where $x_{4}\not\in N(x_{2})\cup\\{x_{2}\\}$ and $u,v$ are distinct
vertices of $N(x_{2})\backslash\\{x_{3}\\}=\\{x_{1},y,z\\}$. To determine $u$
and $v$ we observe from the definition of $x_{3}$ that $x_{3}\not\in
N(x_{1})$. Equivalently, $x_{1}\not\in N(x_{3})$, which implies that $x_{1}$
is not $u$ or $v$. Therefore, $\\{u,v\\}=\\{y,z\\}$ and thus
$N(x_{3})=\\{x_{2},y,z,x_{4}\\}$.

In general, suppose we have found in $G$ a path $x_{1}x_{2}...,x_{k}$ ($k\geq
4$) and distinct vertices $y,z$ such that $d(x_{1})=...=d(x_{k-1})=4$,
$\\{x_{1},...,x_{k-1}\\}\subseteq N(y)\cap N(z)$, and $x_{k-1}x_{k}$ satisfies
$(**)$. By applying Lemma 2.7 to $x_{k-1}x_{k}$ we can either extend this path
or conclude that $x_{k}$ is adjacent to $x_{1}$, which implies $G=B_{k}$ or
$B_{k}^{+}$. This proves the lemma. ∎

Proof of Theorem 2.3. Let $G\not\in\cal B\cup C\cup L$ be 4-connected. Then a
required chain is obtained by repeatedly applying Lemma 2.8. ∎

##  3 On weakly 4-connected graphs

In this paper we also consider two variations of 4-connectivity. Let $G$ be
3-connected. Then $G$ is called weakly $4$-connected if every 3-separation
$(G_{1},G_{2})$ of $G$ satisfies $\min\\{\|G_{1}\|$, $\|G_{2}\|\\}\leq 4$. We
call $G$ quasi $4$-connected if every 3-separation $(G_{1},G_{2})$ of $G$
satisfies $\min\\{|G_{1}|$, $|G_{2}|\\}\leq 4$. Observe that if $\|G\|\leq 9$
then $G$ is weakly 4-connected if and only if $G$ is 3-connected, and
similarly, if $|G|\leq 6$ then $G$ is quasi 4-connected if and only if $G$ is
3-connected. It is not difficult to see that weakly 4-connectivity implies
quasi 4-connectivity. However, the reverse implication does not hold, as shown
by $W_{5}$. Nevertheless, it is easy to see that a quasi 4-connected graph
with ten or more edges is weakly 4-connected if and only if every cubic vertex
is contained in at most one triangle. In this section we consider weakly
4-connected graphs. A chain theorem for these graphs has been obtained by
Geelen and Zhou [4]. To describe this theorem we need some preparations.

A subgraph of a graph $G$ is called a paw if it consists of four edges
$wx,xy,xz,yz$, and it satisfies $d_{G}(x)=3$. The graph illustrated in Figure
3.1, denoted $\Pi$, is called a pyramid. It is routine to verify that $\Pi$ is
the only weakly 4-connected graph on seven vertices such that its edges can be
partitioned into three paws. (One may consider the three possible ways to
arrange the three triangles of the paws.)

Figure 3.1: Pyramid $\Pi$.

Let $\mathcal{B}^{\diamond}$ denote the set of planar biwheels $B_{n}$ for
$n\geq 4$. For any integer $n\geq 3$, let $L_{n}$ be the graph consisting of
two paths $x_{1}x_{2}...x_{n}$, $y_{1}y_{2}...y_{n}$ and a matching
$x_{1}y_{1},...,x_{n}y_{n}$. Let $A_{n}$ and $A_{n}^{\prime}$ (see Figure 3.2)
be the two graphs obtained from $L_{n}$ by adding a pair of edges
$x_{1}x_{n},y_{1}y_{n}$, or $x_{1}y_{n},y_{1}x_{n}$, respectively. Note that
$A_{3}$ is the prism, $A_{4}$ is the cube, and $A_{3}^{\prime}=K_{3,3}$. In
addition, $A_{n}$ is the planar dual of $B_{n}$ while $A_{n}^{\prime}$ is
nonplanar. Let $\mathcal{A}=\\{A_{n},A_{n}^{\prime}:n\geq 4\\}$.

Figure 3.2: Graphs $A_{6}$ and $A_{6}^{\prime}$.

######  Theorem 3.1 ([4]).

For every weakly $4$-connected graph $G$ there exists a
$(G,\\{K_{4},\Pi\\}\cup\mathcal{A}\cup\mathcal{B}^{\diamond}\\})$-chain of
weakly $4$-connected graphs $G_{0},G_{1},...,G_{t}$ such that, for each
$i=1,...,t$, either $\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=G_{i-1}\backslash
e/f$, where $G_{i-1}$ has a paw containing both $e$ and $f$.

In [4], this theorem was established and stated for general matroids. The
formulation provided here is a straightforward restriction of this general
result to graphic matroids. We will not get into a detailed matroidal
discussion on how the restriction is obtained, since it would require some
preparations on matroid theory. Instead, we provide a few remarks for readers
who are interested in these details. First, it is well known that a connected
graph is 3-connected if and only if its graphic matroid is 3-connected (see
8.1.9 of [6]). Also, for any 3-connected graph $G$ and any $k\geq 4$, the
graphic matroid of $G$ has a 3-separation $(E_{1},E_{2})$ with
$\min\\{|E_{1}|,|E_{2}|\\}\geq k$ if and only if $G$ has a 3-separation
$(G_{1},G_{2})$ with $\min\\{\|G_{1}\|,\|G_{2}\|\\}\geq k$ (see 4.1 of [1]).
Therefore, a connected graph is weakly 4-connected if and only if its graphic
matroid is weakly 4-connected. Moreover, a 4-element 3-separating set of the
graphic matroid of $G$ is exactly a paw of $G$. Finally, as we remarked
earlier, a graphic matroid is a trident if and only if the graph is $\Pi$.

Let $K_{6}^{-}$ denote the graph obtained from $K_{6}$ by deleting an edge and
let $K_{3,3}^{+}$ denote the graph obtained from $K_{3,3}$ by adding an edge.
Let $\mathcal{A}_{3}=\mathcal{A}\cup\\{A_{3},A_{3}^{\prime}\\}$ and
$\mathcal{B}_{3}=\mathcal{B}\cup\\{B_{3},B_{3}^{+}\\}$. Our strengthened chain
theorem requires the following operation. Let $G$ contain seven distinct
vertices as shown in Figure 3.3, where $d(x)=d(x^{\prime})=3$ and $d(z)=4$.
Let $O_{2}(G)$ denote $G/xz\backslash xy$.

Figure 3.3: Operation $O_{2}$, where $d(x)=d(x^{\prime})=3$ and $d(z)=4$.

######  Theorem 3.2.

For every weakly $4$-connected graph $G$ not contained in
$\\{K_{4},W_{4},K_{6},K_{6}^{-}\\}\cup\mathcal{A}_{3}\cup\mathcal{B}_{3}$
there exists a $(G,\\{K_{3,3}^{+},\Pi\\})$-chain of weakly $4$-connected
graphs $G_{0},G_{1},...,G_{t}$ such that, for each $i=1,...,t$, either
$\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=O_{2}(G_{i-1})$.

We prove the theorem by proving a sequence of lemmas. We first prove that the
2-edge reduction stated in Theorem 3.1 can be replaced by the more restrictive
operation $O_{2}$.

######  Lemma 3.3.

Suppose a paw $P$ of a weakly $4$-connected graph $G$ contains two edges $e,f$
such that $G\backslash e/f$ is weakly $4$-connected. Then at least one of the
following holds:
(i) $G=W_{4}$;
(ii) $G$ has a weakly $4$-connected minor with $\|G\|-1$ edges;
(iii) $G\backslash e/f=O_{2}(G)$.

Proof. Since $G\backslash e/f$ is weakly $4$-connected, we must have
$|G\backslash e/f|\geq 4$, which implies $|G|\geq 5$. Let $wx$, $xy$, $xz$,
$yz$ be the four edges of $P$.

Claim 1. If $yw$ or $zw$ is an edge of $G$ then either (i) or (ii) holds.

By symmetry, suppose $yw\in G$. Let $G_{1}=P+yw$ and let $G_{2}$ be formed by
all other edges of $G$. Then $(G_{1},G_{2})$ is a 3-separation of $G$. Since
$G$ is weakly 4-connected and $\|G_{1}\|\geq 5$, we must have $\|G_{2}\|\leq
4$. Since very vertex outside $G_{1}$ is incident with at least three edges,
any two of such vertices must be incident with at least five distinct edges.
Therefore, $|G_{2}|=4$. Now it is clear that $G=W_{4}$ or $B_{3}$, which
proves Claim 1.

In the following we assume $yw,zw\not\in G$. Since $d(w)\geq 3$, we must have
$|G|\geq 6$.

Claim 2. If $d(y)=3$ or $d(z)=3$ then (ii) holds.

By symmetry, we assume $d(y)=3$. Let $v$ be the third neighbor of $y$. Then
$v\neq w$ and thus $\\{v,w,z\\}$ is a cut of $G$. Since $G$ is weakly
$4$-connected, we must have $|G|=6$ and further, $G=A_{3}$. Now we see that
(ii) holds, which proves Claim 2.

In the following we assume $d_{G}(y)\geq 4$ and $d_{G}(z)\geq 4$.

Claim 3. $G\backslash yz$ is 3-connected.

Suppose on the contrary that $G\backslash yz$ has a 2-separation
$(G_{1},G_{2})$. If some $G_{i}$ contains both $y,z$ then $(G_{i}+yz,G_{3-i})$
would be a 2-separation of $G$, which is impossible. Hence, by symmetry, we
may assume $y\in G_{1}\backslash G_{2}$ and $z\in G_{2}\backslash G_{1}$. It
follows that $V(G_{1}\cap G_{2})$ consists of $x$ and another vertex $v$.
Again, by symmetry, we assume $xw\in G_{1}$. Then, as $d_{G}(x)=3$, we have
$N_{G_{2}}(x)=\\{z\\}$. In addition, since $d_{G}(z)\geq 4$, we see that
$|G_{2}|\geq 4$. Now, $\\{v,z\\}$ is a 2-cut of $G$, a contradiction, which
proves Claim 3.

If $G\backslash yz$ is weakly 4-connected then (ii) holds. Hence, we assume
that $G\backslash yz$ is not weakly 4-connected. By Claim 3, $G\backslash yz$
has a 3-separation $(G_{1},G_{2})$ with $\|G_{i}\|\geq 5$ for both $i=1,2$.
Since $(G_{1},G_{2})$ cannot be extended into a 3-separation of $G$, we may
assume without loss of generality that $y\in G_{1}\backslash G_{2}$ and $z\in
G_{2}\backslash G_{1}$. Consequently, $x\in G_{1}\cap G_{2}$.

Claim 4. $w\not\in G_{1}\cap G_{2}$.

Suppose $w\in G_{1}\cap G_{2}$. Since $zw\not\in G$, $yw\not\in G$,
$d_{G}(z)\geq 4$, and $d_{G}(y)\geq 4$, we must have $|G_{1}|\geq 5$ and
$|G_{2}|\geq 5$. It follows that both $(G_{1}\cup P,G_{2}\backslash x)$ and
$(G_{1}\backslash x,G_{2}\cup P)$ are 3-separations of $G$. Therefore,
$|G_{1}\backslash x|=|G_{2}\backslash x|=4$. Now it is straightforward to
verify that $G$ is the pyramid $\Pi$. This is impossible since $G\backslash
e/f$ is not weakly 4-connected. This contradiction proves Claim 4.

By Claim 4, we may assume without loss of generality that $w\in
G_{1}\backslash G_{2}$. Then $N_{G_{2}}(x)=\\{z\\}$. Since $\|G_{2}\|\geq 5$,
we have $\|G_{2}\backslash x\|\geq 4$ and thus $|G_{2}\backslash x|\geq 4$. It
follows that $(G_{1}\cup P,G_{2}\backslash x)$ is a 3-separation of $G$. As a
result, we must have $\|G_{2}\backslash x\|=4=|G_{2}\backslash x|=d_{G}(z)$.
Thus $G$ is as shown in Figure 3.3. From $d_{G}(y)\geq 4$ and
$d_{G}(w),d_{G}(y^{\prime}),d_{G}(w^{\prime})\geq 3$ we see that $\|G\|\geq
12$.

Now we need to determine the locations for $e$ and $f$. Note that $f\neq yz$
since $G/yz\backslash e$ has a vertex of degree 2 (no matter how $e$ is
chosen), which should not happen in a weakly 4-connected graph. Then it is
routine to see that there are three possibilities: $G/xz\backslash e\cong
G/xw\backslash xy$, $G/xy\backslash e\cong G/xw\backslash xz$, and
$G/xw\backslash yz$. Let $H$ denote the resulting graph. In the last two
cases, let $H_{1}=H\backslash\\{z,x^{\prime}\\}$ and let $H_{2}$ be the
subgraph of $H$ formed by the five edges incident with $z$ or $x^{\prime}$.
Then $(H_{1},H_{2})$ is a 3-separation of $H$. Moreover, since
$\|H\|=\|G\|-2\geq 10$, we conclude that $\|H_{1}\|\geq 5$ and thus $H$ is not
weakly 4-connected. Therefore, the first case must happen and thus
$H=O_{2}(G)$, so (iii) holds. ∎

######  Lemma 3.4.

If $G\backslash e\in\cal A$ then $G/f$ is weakly 4-connected for some $f$
disjoint from $e$.

Proof. Let $A=G\backslash e$ and $n=|G|/2$. Then
$A\in\\{A_{n},A_{n}^{\prime}\\}$ and $G=A+e$. Let
$x_{1},...,x_{n},y_{1},...,y_{n}$ be the vertices of $A$ and let their
adjacency be specified as in the definition of $A_{n}$ and $A_{n}^{\prime}$.
In this proof the indices are taken modulo $n$. We first consider the case
$n=4$.

Claim 1. The lemma holds if $n=4$.

For $A=A_{4}$ or $A_{4}^{\prime}$, it is straightforward to verify
(separately) that, up to isomorphism, there are only two ways to add $e$ to
$A$, and we may assume they are $y_{3}x_{4}$ and $y_{3}x_{1}$. So we have four
cases, with two choices of $A$ and two choices of $e$. Let $f=x_{2}x_{3}$. It
is routine to check that $(A_{4}+y_{3}x_{4})/f\cong\Pi$ and in the other three
cases $G/f\cong K$, which (known as a kite) is the graph shown in Figure 4.2.
Since $\Pi$ and $K$ are weakly 4-connected, Claim 1 is proven.

In the following we assume $n\geq 5$. To simplify our analysis we first
“place” $e$ in a special position.

Claim 2. We may assume without loss of generality that $e=y_{3}z$, where
$z\not\in\\{x_{2},y_{1}\\}$.

Since $\\{x_{1}y_{1},...,x_{n}y_{n}\\}$ is a perfect matching of $A$, there
must exist distinct $i$ and $j$ such that $e$ is between $\\{x_{i},y_{i}\\}$
and $\\{x_{j},y_{j}\\}$. Because of the rotational circular symmetry between
$\\{x_{1},y_{1}\\},...,\\{x_{n},y_{n}\\}$, we may assume $i=3$ and $j=i+t$,
where $1\leq t\leq n/2$. Then $4\leq j\leq 3+\lfloor n/2\rfloor\leq n$. Now,
by the symmetry between $x_{3}$ and $y_{3}$, we may assume $e=y_{3}z$, where
$z\in\\{x_{j},y_{j}\\}$. Hence Claim 2 is satisfied.

In the following we prove that $f=x_{2}x_{3}$ satisfies the lemma. We first
observe that $A/f$ is 3-connected, as deleting any vertex from it results in a
2-connected graph. Hence $G/f=A/f+e$ is 3-connected. Therefore, if $G/f$ is
not weakly 4-connected, $G/f$ must have a 3-separation $(G_{1},G_{2})$ with
$\|G_{2}\|\geq\|G_{1}\|\geq 5$. We need the following observation.

Claim 3. $G$ is weakly $4$-connected.

For each vertex $v$ of $A$, note that $A\backslash v$ can be obtained from a
3-connected graph by subdividing each edge at most once, which implies that
any 2-cut of $A\backslash v$ may cut off at most one vertex. It follows that
every 3-cut of $A$ may cut off at most one vertex. That is, for every
3-separation $(H_{1},H_{2})$ of $A$, we must have
$\min\\{|H_{1}|,|H_{2}|\\}=4$. Since $A$ has no triangles, we conclude that
$\min\\{\|H_{1}\|,\|H_{2}\|\\}=3$, which implies $G=A+e$ is weakly
4-connected, as every 3-separation of $G$ induces a 3-separation of $A$.

Figure 3.4: $A\backslash\\{x_{2},x_{3}\\}$.

Claim 3 implies that, in the above 3-separation $(G_{1},G_{2})$, vertex
$\bar{f}$ must be contained in both $G_{1}$ and $G_{2}$. Let $S$ denote the
3-cut $V(G_{1}\cap G_{2})$. It follows that $S\backslash\bar{f}$ is a 2-cut of
$G/f\backslash\bar{f}=G\backslash\\{x_{2},x_{3}\\}=A\backslash\\{x_{2},x_{3}\\}+e$.
Since $n\geq 5$, $A\backslash\\{x_{2},x_{3}\\}$ is a subdivision of a
3-connected graph (see Figure 3.4). Thus any 2-cut of
$A\backslash\\{x_{2},x_{3}\\}$ can only separate some degree-2 vertices from
the rest of the graph. It is straightforward to check that these cuts are:
$\\{y_{1},y_{3}\\}$, $\\{y_{1},y_{4}\\}$, $\\{y_{2},y_{4}\\}$,
$\\{y_{4},x_{5}\\}$, and $\\{y_{1},z_{n}\\}$, where $z_{n}=x_{n}$ if $A=A_{n}$
and $z_{n}=y_{n}$ if $A=A_{n}^{\prime}$. By Claim 2, $\\{y_{1},y_{4}\\}$ and
$\\{y_{2},y_{4}\\}$ are not 2-cuts of $A\backslash\\{x_{2},x_{3}\\}+e$. So we
only need to consider the other three 2-cuts. If $S=\\{\bar{f},y_{1},z_{n}\\}$
or $S=\\{\bar{f},y_{4},x_{5}\\}$, then $G_{1}$ consists of the three edges
incident with $x_{1}$ or $x_{4}$, respectively. If
$S=\\{\bar{f},y_{1},y_{3}\\}$, then $G_{1}$ consists of the three edges
incident with $y_{2}$, and possibly also $y_{3}\bar{f}$ ($y_{3}y_{1}$ is not
an edge, by Claim 2). In all cases, $\|G_{1}\|\geq 5$ is not satisfied. This
contradiction proves that $G/f$ is weakly 4-connected. ∎

The following can be considered as the dual of the last lemma.

######  Lemma 3.5.

Let $e=xy$ be an edge of a $3$-connected graph $G$. If $G/e\in\cal B$ then $G$
has an edge $f$ such that $G\backslash f$ is weakly $4$-connected with
$\delta(G\backslash f)=3$.

Proof. Let $B=G/e$. Then $B=B_{n}$ or $B_{n}^{+}$ for some $n\geq 4$. Let
$h_{1}$, $h_{2}$ be the two hubs of $B$ and let $C=v_{1}v_{2}...v_{n}v_{1}$ be
the rim cycle. We first make two observations.

Claim 1. $B\backslash h_{1}v_{1}$ is quasi $4$-connected.

Since $B$ is 4-connected, it follows that $B\backslash h_{1}v_{1}$ is
3-connected. Now let $(H_{1},H_{2})$ be a 3-separation of $B\backslash
h_{1}v_{1}$. If $n=4$ then $|H_{1}|+|H_{2}|=|B|+3=9$, which implies
$\min\\{|H_{1}|,|H_{2}|\\}\leq 4$. So we assume $n\geq 5$. In this case it is
routine to see that any two vertices different from $v_{1}$ are linked in
$B\backslash h_{1}v_{1}\backslash h_{2}v_{1}$ by four independent paths. It
follows that some $H_{i}$ has to contain all vertices different from $v_{1}$.
Therefore, $H_{3-i}$ must contain precisely $v_{1}$ and its three neighbors,
implying $\min\\{|H_{1}|,|H_{2}|\\}\leq 4$ again.

Claim 2. Let $uv$ be an edge of a $3$-connected graph $H$. If $H$ is not quasi
$4$-connected but $H/uv$ is, then $H$ has a cubic vertex $w\neq u,v$ such that
$|N_{H}(\\{u,w\\})|=3$ or $|N_{H}(\\{v,w\\})|=3$.

Since $H$ is 3-connected but not quasi 4-connected, it has a $3$-separation
$(H_{1},H_{2})$ with $\min\\{|H_{1}|,|H_{2}|\\}\geq 5$. By symmetry, let
$uv\in H_{1}$. Note that $|\\{u,v\\}\cap V(H_{2})|\leq 1$ because otherwise
$H/uv$ would admit a 2-cut, which is not the case. It follows that
$(H_{1}/uv,H_{2})$ is a 3-separation of $H/uv$. Since $H/uv$ is quasi
4-connected and $d_{H/uv}(\overline{uv})\geq 4$, we must have $|H_{1}|=5$ and
$|\\{u,v\\}\cap V(H_{2})|=1$. Therefore, $V(H_{1}\backslash H_{2})$ consists
of a vertex $w$ and exactly one of $u$ and $v$. It follows that either
$|N_{H}(\\{u,w\\})|=3$ or $|N_{H}(\\{v,w\\})|=3$. Finally, note that $3\leq
d_{H}(w)\leq 4$ since $H$ is 3-connected and $|H_{1}|=5$. If $d_{H}(w)=4$ then
$uvw$ is a triangle, implying that $H/uv$ has a parallel edge, a
contradiction. Thus, $d_{H}(w)=3$, which completes the proof of Claim 2.

Now we prove the lemma by finding a required edge $f$. We first consider the
case when $\bar{e}$ is a rim vertex. Without loss of generality, let
$\bar{e}=v_{2}$. Up to isomorphism, there are two ways to split $v_{2}$, as
shown in Figure 3.5. Let us assume by symmetry that
$N_{G}(x)=\\{y,v_{1},h_{1}\\}$ or $\\{y,v_{1},v_{3}\\}$. We prove that
$f=h_{1}v_{1}$ satisfies the lemma. Let $H=G\backslash f$. Note that each
cubic vertex of $H$ (consisting of $x,y,v_{1}$, and possibly $h_{1}$) is
contained in at most one triangle, so we only need to prove that $H$ is quasi
4-connected. By Claim 1, $H/e$ is quasi 4-connected. Then, by Lemma 2.4, $H$
is 3-connected. Hence, by Claim 2, if $H$ is not quasi 4-connected then $H$
has a cubic vertex $z\neq x,y$ such that $|N_{H}(\\{t,z\\})|=3$ for $t=x$ or
$y$. Now it is routine to verify that no such $t,z$ exist, which proves that
$H$ is weakly 4-connected.

Figure 3.5: $H=G\backslash f$.

It remains to consider the case when $\bar{e}$ is a hub of $B$. We assume that
$B\neq B_{4}$ because in this case $\bar{e}$ can also be considered as a rim
vertex and thus this is a case considered in the last paragraph. As a result,
we have $d_{B}(h_{i})\geq 5$ ($i=1,2$). Without loss of generality, let us
assume $\bar{e}=h_{2}$ and $d_{G}(x)\geq d_{G}(y)$. Then we have $d_{G}(x)\geq
4$. We further assume, without loss of generality, that $xv_{1},yv_{2}\in G$,
as illustrated in Figure 3.5. If $N_{G}(y)=\\{x,v_{2},v_{n}\\}$ then we choose
$f=h_{1}v_{2}$, else we choose $f=h_{1}v_{1}$. We prove that our choice of $f$
satisfies the lemma. Let $H=G\backslash f$. If $f=h_{1}v_{2}$, neither of the
two cubic vertices of $H$, $v_{2}$ and $y$, is contained in a triangle. If
$f=h_{1}v_{1}$, each cubic vertex of $H$ (consisting of $v_{1}$ and possibly
$y$) is contained in at most one triangle. Therefore, in both cases, to
establish the weak 4-connectivity of $H$ we only need to show that $H$ is
quasi 4-connected. Let $i=1$ or 2 with $f=h_{1}v_{i}$. Note that $v_{i}$ is
the only cubic vertex of $H$ outside $\\{x,y\\}$. By Claim 1, $H/e$ is quasi
4-connected. By Lemma 2.4, $H$ is 3-connected. Hence, by Claim 2, if $H$ is
not quasi 4-connected then $|N_{H}(\\{v_{i},x\\})|=3$ or
$|N_{H}(\\{v_{i},y\\})|=3$. We need to deduce a contradiction.

Suppose $i=2$. Then we have $N_{H}(\\{v_{2},x\\})=N_{H}(x)$ and
$N_{H}(\\{v_{2},y\\})=\\{v_{1},v_{3},v_{n},x\\}$. It follows that
$|N_{H}(\\{v_{2},x\\})|=|N_{H}(x)|=d_{G}(x)\geq 4$ and
$|N_{H}(\\{v_{2},y\\})|=4$, which give us the desired contradiction. Next,
suppose $i=1$. Since $N_{H}(\\{v_{1},x\\})\supseteq(N_{H}(x)\backslash
v_{1})\cup\\{v_{2}\\}$, we again have
$|N_{H}(\\{v_{1},x\\})|\geq|N_{H}(x)|=d_{G}(x)\geq 4$. On the other hand, the
choice of $f=h_{1}v_{1}$ implies $N_{H}(y)\neq N_{H}(v_{1})$ and thus
$N_{H}(\\{v_{1},y\\})$ properly contains $N_{H}(v_{1})$. Hence,
$|N_{H}(\\{v_{1},y\\})|>3$, and we obtain the desired contradiction again. ∎

######  Lemma 3.6.

Suppose $G$ is weakly $4$-connected and
$G\not\in\\{K_{4},W_{4},K_{6}^{-},\Pi\\}\cup\cal A\cup B$. Then $G$ must
contain a weakly $4$-connected minor $H\not\in\\{K_{4}\\}\cup\cal A\cup B$
such that either $\|H\|=\|G\|-1$ or $H=O_{2}(G)$.

Proof. By Theorem 3.1, $G$ has a weakly 4-connected minor $G^{\prime}$ such
that either $\|G^{\prime}\|=\|G\|-1$ or $G^{\prime}=G\backslash e/f$, where
$G$ has a paw containing both $e,f$. Then, by Lemma 3.3, we may assume that
either $\|G^{\prime}\|=\|G\|-1$ or $G^{\prime}=O_{2}(G)$. It is clear that
$G^{\prime}\neq K_{4}$ since there is no 3-connected graph $H$ satisfying any
of $H\backslash e=K_{4}$, $H/e=K_{4}$, or $O_{2}(H)=K_{4}$. If
$G^{\prime}\not\in\cal A\cup B$ then $H=G^{\prime}$ satisfies the lemma.
Hence, we assume $G^{\prime}\in\cal A\cup B$ and we will use $G^{\prime}$ to
find $H$ that satisfies the lemma.

We first consider the case $G^{\prime}\in\cal A$. If $G^{\prime}=G/e$ or
$O_{2}(G)$ then $G^{\prime}$ would have a vertex of degree 4, which is not the
case. So $G^{\prime}=G\backslash e$. By Lemma 3.4, $G$ has an edge $f$
disjoint from $e$ such that $G/f$ is weakly 4-connected. Since $G^{\prime}$ is
3-regular, $G/f$ has three vertices ($\bar{f}$ and the two ends of $e$) of
degree 4 and all its other vertices are cubic. It follows that
$G/f\not\in\\{K_{4}\\}\cup\cal A\cup B$ and thus $H=G/f$ satisfies the lemma.

Next, assume $G^{\prime}\in\cal B$. Note that $G^{\prime}\neq O_{2}(G)$
because this would require $G^{\prime}$ to have a cubic vertex, which is not
the case. Hence, $G^{\prime}=G\backslash e$ or $G/e$. We consider these two
cases separately. Let $e=xy$ and let $h_{1},h_{2}$ be the two hubs of
$G^{\prime}$.

Suppose $G^{\prime}=G\backslash e$. It is clear $|G^{\prime}|\geq 6$. If
$|G^{\prime}|=6$ then $G^{\prime}=B_{4}$ or $B_{4}^{+}$, which implies
$G=B_{4}^{+}$ or $K_{6}^{-}$, respectively. This violates our assumption on
$G$. Hence we must have $|G^{\prime}|\geq 7$. Since $G\not\in\cal B$, both
$x,y$ are rim vertices of $G^{\prime}$. Let $H=G\backslash xh_{1}$. Since
$G^{\prime}$ is 4-connected, $G$ is 4-connected and thus $H$ is 4-connected,
as $H$ contains four independent paths between $x$ and $h_{1}$. Consequently,
$H$ is weakly 4-connected. We also have $H\not\in\cal A$ since $H$ is not
3-regular. Furthermore, $H\not\in\cal B$ since $d_{H}(h_{2})\geq 5=d_{H}(y)$
yet $H\backslash\\{h_{2},y\\}$ is not a cycle. Therefore, $H$ satisfies the
lemma.

Finally, let $G^{\prime}=G/e\in\cal B$. By Lemma 3.5, $G$ has an edge $f$ such
that $G\backslash f$ is weakly 4-connected with $\delta(G\backslash f)=3$.
Note that all vertices of $G\backslash f$, other than the ends of $e$ and $f$,
must have degree exceeding 3. It follows that $G\backslash
f\not\in\\{K_{4}\\}\cup\cal A\cup B$. Hence, $H=G\backslash f$ satisfies the
lemma, which completes our proof. ∎

Proof of Theorem 3.2. Let $G$ be weakly 4-connected and let
$G\not\in\\{K_{4},W_{4},K_{6},K_{6}^{-}\\}\cup\mathcal{A}_{3}\cup\mathcal{B}_{3}$.
We assume $G\not\in\\{K_{3,3}^{+},\Pi\\}$ because otherwise we are done. We
only need to show that there exists $H$ satisfying
($*$) $H\in\\{G\backslash e,G/e,O_{2}(G)\\}$ (for some $e$), $H$ is weakly
4-connected, and
$H\not\in\\{K_{4},W_{4},K_{6},K_{6}^{-}\\}\cup\mathcal{A}_{3}\cup\mathcal{B}_{3}$
because repeatedly using this result will generate the desired chain.

By Lemma 3.6, $G$ has a weakly 4-connected minor
$G^{\prime}\not\in\\{K_{4}\\}\cup\mathcal{A}\cup\mathcal{B}$ such that either
$\|G^{\prime}\|=\|G\|-1$ or $G^{\prime}=O_{2}(G)$. If
$G^{\prime}\not\in\\{W_{4},K_{6},K_{6}^{-},A_{3},A_{3}^{\prime},B_{3},B_{3}^{+}\\}$
then $H=G^{\prime}$ satisfies ($*$). Hence, we assume that $G^{\prime}$ is one
of these seven. In the following we exam each of these seven graph and we
either obtain a contradiction (indicating $G^{\prime}$ cannot be that graph)
or find $H$ satisfying ($*$).

If $G^{\prime}=W_{4}$ then $G^{\prime}=G\backslash e$ or $G/e$ ($G$ is too
small for applying $O_{2}$). In the first case $G=B_{3}$ and in the second
case $G=A_{3}$ or $A_{3}^{\prime}$. Since both cases contradict
$G\not\in\mathcal{A}_{3}\cup\mathcal{B}_{3}$, we conclude that $G^{\prime}\neq
W_{4}$.

If $G^{\prime}=A_{3}$ or $A_{3}^{\prime}$ then $G^{\prime}=G\backslash e$, as
$G^{\prime}\in\\{G/e,O_{2}(G)\\}$ would imply that $G^{\prime}$ has a vertex
of degree exceeding 3, which is not the case. If $G^{\prime}=A_{3}$, note that
$G=A_{3}+e$ is not weakly 4-connected, as it has a cubic vertex belonging to
two triangles. If $G^{\prime}=A_{3}^{\prime}$, note that
$G=A_{3}^{\prime}+e=K_{3,3}^{+}$, which violates the assumption
$G\not\in\\{K_{3,3}^{+},\Pi\\}$. These contradictions prove that
$G^{\prime}\not\in\\{A_{3},A_{3}^{\prime}\\}$.

If $G^{\prime}=B_{3}$ then $G^{\prime}=G\backslash e$ or $G/e$ ($G$ is too
small for applying $O_{2}$). In the first case $G=B_{3}^{+}$ and in the second
case $G=A_{3}+f$ (which is not weakly 4-connected) or $A_{3}^{\prime}+f$
(which is $K_{3,3}^{+}$). These again contradicts our assumptions on $G$ and
thus $G^{\prime}\neq B_{3}$.

If $G^{\prime}=B_{3}^{+}$ or $K_{6}$ then $G^{\prime}=G/e$. To see this, note
that $G^{\prime}$ is a complete graph and thus $G^{\prime}\neq G\backslash e$.
Meanwhile, $G^{\prime}\neq O_{2}(G)$ since $G^{\prime}$ has no cubic vertices.
Hence $G^{\prime}=G/e$. If $G^{\prime}=B_{3}^{+}$ then $G$ can also be
obtained from $K_{3,3}^{+}$ by adding an edge $f$. In this case $H=G\backslash
f$ satisfies ($*$). If $G^{\prime}=K_{6}$ then we may assume
$N_{G}(v_{1})=\\{v_{2},v_{3},v_{4}\\}$,
$N_{G}(v_{2})=\\{v_{1},v_{5},v_{6},v_{7}\\}$, and
$G\backslash\\{v_{1},v_{2}\\}=K_{5}$. Then it is routine to verify that
$H=G\backslash v_{2}v_{7}$ (isomorphic to the first graph in Figure 3.6)
satisfies ($*$).

Figure 3.6: $G/e=K_{6}^{-}$ and $G\backslash f$ is weakly 4-connected.

Finally, suppose $G^{\prime}=K_{6}^{-}$. Note that $G^{\prime}\neq O_{2}(G)$
since $G^{\prime}$ has no cubic vertices. If $G^{\prime}=G\backslash e$ then
$G=K_{6}$, contradicting our assumption on $G$. Hence $G^{\prime}=G/e$. It is
routine to verify that there are four choices for $G$, as illustrated in
Figure 3.6 (they can be obtained from $K_{6}$ by splitting a vertex and then
deleting an appropriate edge). In all four cases, deleting $f$ results in the
same graph, which we denote by $H$. Note that $H$ is weakly 4-connected (as
$|N_{H}(\\{u,v\\})|\geq 4$ for all $u,v$) and thus $H$ satisfies ($*$). This
completes our proof of the theorem. ∎

##  4 On quasi 4-connected graphs

In this section we obtain a similar result for quasi 4-connected graphs. We
first state a known chain theorem. To do so, we need the following operation.
Suppose $N(w)=\\{x,y,z\\}$, $xz,yz\in G$, $xy\not\in G$, $d(x),d(y)\geq 4$ and
$d(z)\geq 5$, as shown in Figure 4.1. Then $O_{3}(G)=G/xw\backslash wz$.

Figure 4.1: Operation $O_{3}$, where $d_{G}(x)\geq 4$, $d_{G}(y)\geq 4$,
$d_{G}(z)\geq 5$.

######  Theorem 4.1 ([7]).

For every quasi $4$-connected graph $G$ there exists a
$(G,\\{W_{3},W_{4},W_{5}\\}\cup\cal A)$-chain of quasi $4$-connected graphs
$G_{0},G_{1},...,G_{t}$ such that, for each $i=1,...,t$, either
$\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=O_{3}(G_{i-1})$.

Let $\mathcal{G}_{6}$ denote the set of 3-connected graphs with at most six
vertices. It is clear that every graph $G\in\mathcal{G}_{6}$ is quasi
4-connected since $G$ is too small to admit a 3-cut that separates two
vertices of $G$ from another two vertices of $G$. Outside $\mathcal{G}_{6}$
the two smallest quasi 4-connected graphs are pyramid $\Pi$ and the graph $K$
shown below, which we call a kite. Both $\Pi$ and $K$ have seven vertices and
twelve edges. The following is our strengthened chain theorem.

Figure 4.2: Kite $K$.

######  Theorem 4.2.

For every quasi $4$-connected graph $G\not\in\mathcal{G}_{6}\cup\mathcal{A}$
there exists a $(G$, $\\{\Pi,K\\})$-chain of quasi $4$-connected graphs
$G_{0}$, $G_{1}$, …, $G_{t}$ such that, for each $i=1,...,t$, either
$\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=O_{3}(G_{i-1})$.

In the following we divide our proof into two lemmas. The first is a weaker
version of the theorem. Recall that $A_{3}=$ prism is planar and
$A_{3}^{\prime}=K_{3,3}$ is nonplanar.

######  Lemma 4.3.

For every quasi $4$-connected graph $G$ not contained in $\\{W_{3}$, $W_{4}$,
$W_{5}$, $B_{3}$, $B_{3}^{+}\\}\cup\mathcal{A}_{3}$ there exists a $(G$,
$\\{A_{3},A_{3}^{\prime}\\})$-chain of quasi $4$-connected graphs $G_{0}$,
$G_{1}$, …, $G_{t}$ such that, for each $i=1,...,t$, either
$\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=O_{3}(G_{i-1})$.

Proof. Let $G$ be quasi 4-connected and let
$G\not\in\\{W_{3},W_{4},W_{5},B_{3},B_{3}^{+}\\}\cup\mathcal{A}_{3}$. We only
need to show that there exists $H$ satisfying
($*$) $H\in\\{G\backslash e,G/e,O_{3}(G)\\}$ (for some $e$), $H$ is quasi
4-connected, and
$H\not\in\\{W_{3},W_{4},W_{5},B_{3},B_{3}^{+}\\}\cup\mathcal{A}$
because repeatedly using this result will generate the desired chain.

By Theorem 4.1, $G$ has a quasi 4-connected minor $G^{\prime}$ such that
either $\|G^{\prime}\|=\|G\|-1$ or $G^{\prime}=O_{3}(G)$. We assume
$G^{\prime}\in\\{W_{3},W_{4},W_{5},B_{3},B_{3}^{+}\\}\cup\mathcal{A}$ because
otherwise $H=G^{\prime}$ satisfies ($*$). Depending on how $G^{\prime}$ is
obtained from $G$ we consider three cases. Each case will be further divided
into subcases. In each subcase we will either obtain a contradiction
(indicating that the subcase cannot happen) or find $H$ satisfying ($*$).

If $G^{\prime}=O_{3}(G)$ then $G^{\prime}$ contains at least three vertices of
degree exceeding 3. It follows that $G^{\prime}=B_{3}$ or $B_{3}^{+}$. By
reversing operation $O_{3}$ we see that $G$ is a graph obtained from $K_{3,3}$
by adding, respectively, two edges $e,f$ or three edges $e,f,g$. Therefore,
$H=G\backslash e$ satisfies ($*$).

If $G^{\prime}=G/e$ then $d_{G^{\prime}}(\bar{e})>3$, which implies
$G^{\prime}\in\\{W_{4},W_{5},B_{3},B_{3}^{+}\\}$. If $G^{\prime}=W_{4}$ then
$G=A_{3}$ or $A_{3}^{\prime}$, contradicting our assumption on $G$. If
$G^{\prime}=B_{3}$ then $G$ can be expressed as $A_{3}+f$ or
$A_{3}^{\prime}+f$ for an edge $f$. In both cases $H=G\backslash f$ satisfies
($*$). If $G^{\prime}=B_{3}^{+}$ then $G$ is a graph obtained from $K_{3,3}$
by adding two edges $f,g$. Consequently, $H=G\backslash f$ satisfies ($*$). If
$G^{\prime}=W_{5}$, let $e=xy$ and let $v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}$ be the
rim cycle of $W_{5}$. Without loss of generality, let
$N_{G}(x)=\\{y,v_{1},v_{2},v_{3}\\}$ or $\\{y,v_{1},v_{3}\\}$. In both cases,
$\\{y,v_{1},v_{3}\\}$ is a 3-cut separating $\\{x,v_{2}\\}$ from
$\\{v_{4},v_{5}\\}$. It follows that $G$ is not quasi 4-connected, which is a
contradiction.

It remains to consider the case $G^{\prime}=G\backslash e$. Note that
$G^{\prime}\neq W_{3}$ or $B_{3}^{+}$ since they are complete graphs and thus
they cannot be expressed as $G\backslash e$. If $G^{\prime}=W_{4}$ or $B_{3}$
then $G=B_{3}$ or $B_{3}^{+}$, contradicting our assumption on $G$. If
$G^{\prime}\in\cal A$ then Lemma 3.4 ensures that $G$ has an edge $f$ such
that $G/f$ is quasi 4-connected. Note that $G/f\not\in\cal A$ (since the
degree of $\bar{f}$ is not 3) and
$G/f\not\in\\{W_{3},W_{4},W_{5},B_{3},B_{3}^{+}\\}$ (since $|G/f|>6$).
Therefore, $H=G/f$ satisfies ($*$). Finally, suppose $G^{\prime}=W_{5}$. Let
$v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}$ be the rim cycle of $W_{5}$ and let $v_{0}$
be the hub. Without lose of generality, let $e=v_{1}v_{3}$. Now we see that
$H=G\backslash v_{0}v_{1}$ (a graph obtained from prism $A_{3}$ by adding an
edge) satisfies ($*$). The proof of the lemma is complete. ∎

Note that Theorem 4.2 holds trivially for graphs with at most six vertices. In
the following we prove that the theorem holds for graphs with seven vertices.

######  Lemma 4.4.

Let $G$ be quasi 4-connected with $|G|=7$. If $G$ is nonplanar then $G$
contains $K$ as a spanning subgraph; if $G$ is planar then $G$ contains $\Pi$
as a spanning subgraph.

Proof. We begin with two well known results on graph minors. (1) If a
3-connected graph is nonplanar then either the graph is isomorphic to $K_{5}$
or the graph contains a $K_{3,3}$ minor. (2) If a graph contains a cubic graph
$Q$ as a minor then the graph contains a subdivision of $Q$ as a subgraph.
From these two results and Lemma 4.3 we immediately obtain: if $G$ is
nonplanar then $G$ contains a subgraph $H$, where $H$ is a subdivision of
$A=K_{3,3}$; if $G$ is planar then $G$ contains a subgraph $H$, where $H$ is a
subdivision of $A=A_{3}$. We choose $H$ with $|H|$ maximized.

We first prove $V(H)=V(G)$. Suppose otherwise. Then $H\cong A$ (meaning that
edges of $A$ are subdivided zero times) and $G$ contains exactly one vertex
$z$ outside $H$. If two neighbors $x,y$ of $z$ are adjacent in $H$ then
replacing edge $xy$ with path $xzy$ would result in a bigger $H$. Hence,
$N_{G}(z)$ must be a stable set of $H$. Since $d_{G}(z)\geq 3$, we must have
$A=K_{3,3}$ and $N_{G}(z)$ has to be a color class of $H$. Now the quasi
4-connectivity of $G$ implies that $G\backslash N_{G}(z)$ contains a vertex
$y$ of degree exceeding 1. It follows that $G\backslash y$ contains a subgraph
$H^{\prime}\cong A$ yet $N_{G}(y)$ is not stable in $H^{\prime}$, which leads
to a larger subdivided $A$ in $G$. This contradiction proves $V(H)=V(G)$.

In the following discussion, let $V(G)=V(H)=\\{v_{1},...,v_{7}\\}$. Let
$v_{1}$ be the unique subdividing vertex in obtaining $H$ and let
$e=v_{1}v_{2}\in G$ be an edge outside $H$. Then $H+e$ is a subgraph of $G$.
In the case $A=K_{3,3}$, up to isomorphism, $H+e$ is unique, which is the
first graph in Figure 4.3. Since $\\{v_{2},v_{4},v_{6}\\}$ does not separate
$v_{3},v_{5}$ from $v_{1},v_{7}$, $G$ must contain an edge $f$ between
$\\{v_{3},v_{5}\\}$ and $\\{v_{1},v_{7}\\}$. By symmetry, there is only one
choice for $f$ and it is easy to see that $H+e+f\cong K$, which settles the
case for nonplanar $G$.

Figure 4.3: $H+v_{1}v_{2}$.

Next we assume $G$ is planar and $A=A_{3}$. If $v_{1}$ subdivides an edge of a
triangle of $A$ then, subject to planarity and up to isomorphism, there are
two choices of $e$. In these two cases we denote $H+e$ by $H_{1}$ and $H_{2}$,
which are the last two graphs shown in Figure 4.3. If $v_{1}$ subdivides an
edge not contained in a triangle of $A$ then, up to isomorphism, there is only
one choice of $e$ and $H+e$ is isomorphic to $H_{2}$. In conclusion, $G$
contains $H_{1}$ or $H_{2}$ as a subgraph. If $H_{1}$ is a subgraph, since
$\\{v_{2},v_{4},v_{5}\\}$ does not separate $v_{1},v_{3}$ from $v_{6},v_{7}$,
$G$ must contain an edge $f$ between $v_{1},v_{3}$ and $v_{6},v_{7}$. By
symmetry and planarity, there is only one choice for $f$ and it is easy to see
that $H_{1}+f\cong\Pi$. Hence, we assume $H_{1}$ is not a subgraph, which
implies that $H_{2}$ is a subgraph and (under the labeling of $H_{2}$)
$v_{1}v_{6},v_{1}v_{7}\not\in G$. Like in the previous cases, by considering
cut $\\{v_{3},v_{4},v_{5}\\}$ we may assume $v_{2}v_{6}\in G$. Then by
considering cut $\\{v_{2},v_{4},v_{6}\\}$ we have $v_{3}v_{7}\in G$, and by
considering cut $\\{v_{2},v_{3},v_{7}\\}$ we also have $v_{4}v_{5}\in G$. Now
we have
$(H_{2}+v_{2}v_{6}+v_{3}v_{7}+v_{4}v_{5})\backslash\\{v_{2}v_{3},v_{6}v_{7}\\}\cong\Pi$,
which completes our proof of the lemma. ∎

Proof Theorem 4.2. By Lemma 4.3, there exists a
$(G,\\{A_{3},A_{3}^{\prime}\\})$-chain of quasi 4-connected graphs
$G_{0},G_{1},...,G_{t}$ such that, fore all $i=1,...,t$, either
$\|G_{i}\|=\|G_{i-1}\|-1$ or $G_{i}=O_{3}(G_{i-1})$. Since $|G_{0}|\geq 7$,
there exists a largest index $k$ with $|G_{k}|\geq 7$. Note that $k<t$, as
$\|G_{t}\|=6$. By the maximality of $k$, we have $|G_{k+1}|<7$ and thus
$G_{k+1}\neq G_{k}\backslash e$. Consequently, $G_{k+1}=G_{k}/e$ or
$G_{k}/e\backslash f$ for some $e,f$. As a result, $|G_{k+1}|=|G_{k}|-1$,
which implies $|G_{k}|=7$. By Lemma 4.4, $G_{k}$ contains either $\Pi$ or $K$
as a spanning subgraph. In other words, there exists a
$(G_{k},\\{\Pi,K\\})$-chain $H_{0},...,H_{s}$ such that each $H_{i}$
($i=1,...,s$) is obtained from $H_{i-1}$ by deleting an edge. Since $\Pi$ and
$K$ are quasi 4-connected, every $H_{i}$ is also quasi 4-connected. Therefore,
$G_{0},...,G_{k},H_{1},...,H_{s}$ is a required chain, which proves the
theorem. ∎

##  5 On 3-connected graphs

In this section we prove the following strengthening of Tutte Theorem. Since
3-connectivity has been extensively studied in the literature, it is possible
to obtain a shorter proof for this result using more powerful tools. However,
we choose to present a more elementary proof, which is not long either.

######  Theorem 5.1.

For every $3$-connected graph $G\not\in\cal W$ there exists a
$(G,W_{4})$-chain $G_{0},G_{1},...,G_{t}$ of $3$-connected graphs such that
$||G_{i}||=||G_{i-1}||-1$ for all $i=1,...,t$.

Proof. Let $G\not\in\cal W$ be 3-connected. We need to find an edge $f$ of $G$
such that at least one of $G\backslash f$ and $G/f$ is either the wheel
$W_{4}$ or a 3-connected non-wheel graph. By Theorem 1.1, we may assume that
$G$ has an edge $e$ such that $G\backslash e$ or $G/e$ is a wheel $W_{n}$ with
$n\neq 4$. Since no graph satisfies $G\backslash e=W_{3}$ or $G/e=W_{3}$, we
may further assume $n\geq 5$. Let $z$ be the hub of $W_{n}$ and let $e=xy$. If
$G\backslash e=W_{n}$ then both $x,y$ are rim vertices. Let $f=xz$. Then
$G\backslash f$ is not a wheel since it has two non-cubic vertices $y$ and
$z$. In addition, $G\backslash f$ is 3-connected since $G$ is 3-connected and
$G\backslash f$ has three independent paths joining $x$ and $z$. Therefore,
$f$ satisfies the requirements. Next, suppose $G/e=W_{n}$. Then $G$ is
obtained from $W_{n}$ by splitting $z$ into $x$ and $y$. Without loss of
generality, let $d_{G}(x)\geq d_{G}(y)$. Then $d_{G}(x)>3$ since $n\geq 5$.
Let $f=uv$ be a rim edge such that $ux,vy\in G$. Then $f$ is not contained in
any triangle and thus $G/f$ is simple. Now we see that $G/f$ is not a wheel
since $\bar{f}$ and $x$ are two non-cubic vertices. In addition, by Lemma 2.4,
$H=G/f$ is 3-connected, as $si(H/e)=W_{n-1}$ is 3-connected. Therefore, $f$
satisfies the requirements. ∎

Acknowledgement: The second author is supported in part by NSF of China under
grant 11961051 and supported in part by Natural Sciences Foundation of Guangxi
Province under grant 2018GXNSFAA050117.

## References

  * [1] Xujin Chen, Guoli Ding, Xingxing Yu, and Wenan Zang, Bonds with parity constraints, Journal of Combinatorial Theory Series B 102 (2012) 588-609.
  * [2] Reinhard Diestel, Graph Theory, Fourth Edition, 2010.
  * [3] Max Fontet, Graphes 4-essentiels, C. R. Acad. Sci. Paris Sér. A-B 287(5) (1978) 289-290.
  * [4] Jim Geelen and Xiangqian Zhou, Generating weakly 4-connected matroids, Journal of Combinatorial Theory, Series B 98 (2008) 538-557.
  * [5] Nicola Martinov, Uncontractable 4-connected graphs, Journal of Graph Theory 6(3) (1982) 343-344.
  * [6] James Oxley, Matroid Theory, Second Edition (2011).
  * [7] Themistocles Politof and A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Mathematics 161 (1996) 217-228.
  * [8] Chengfu Qin and Guoli Ding, A chain theorem for 4-connected graphs, Journal of Combinatorial Theory, Series B 134 (2019) 341-349.
  * [9] W.T. Tutte, A theory of 3-connected graphs, Indagationes Math. 23 (1961) 441-455.


* [252] Andringa S, et al.  Adv. High Energy Phys. 2016:6194250 (2016)
  * [253] Anderson M, et al.  Phys. Rev. D 99:012012 (2019)
  * [254] An F, et al.  J. Phys. G 43:030401 (2016)
  * [255] Djurcic Z, et al. arXiv:1508.07166 [physics.ins-det] (2015)
  * [256] Bellini G, et al.  Phys. Rev. D 82:033006 (2010)
  * [257] Abusleme A, et al. arXiv:2006.11760 [hep-ex] (2020)
  * [258] Cheng JP, et al.  Annual Review of Nuclear and Particle Science 67:231 (2017)
  * [259] Guo Z, et al. arXiv:2007.15925 [physics.ins-det] (2020)
  * [260] Beacom JF, et al.  Chin. Phys. C 41:023002 (2017)
  * [261] Bonventre R, Orebi Gann G.  Eur. Phys. J. C 78:435 (2018)
  * [262] Land B, et al. arXiv:2007.14999 [physics.ins-det] (2020)
  * [263] Seo SH arXiv:1903.05368 [physics.ins-det] (2019)
  * [264] Freedman DZ.  Phys. Rev. D 9:1389 (1974)
  * [265] Drukier A, Stodolsky L :395 (1984)
  * [266] Cabrera B, Krauss LM, Wilczek F.  Phys. Rev. Lett. 55:25 (1985)
  * [267] Akimov D, et al.  Science 357:1123 (2017)
  * [268] Akimov D, et al. arXiv:2003.10630 [nucl-ex] (2020)
  * [269] Dutta B, Strigari LE.  Annual Review of Nuclear and Particle Science 69:137 (2019)
  * [270] Billard J, Strigari LE, Figueroa-Feliciano E.  Phys. Rev. D 91:095023 (2015)
  * [271] Agnese R, et al.  Phys. Rev. D 95:082002 (2017)
  * [272] Strauss R, et al.  Eur. Phys. J. C 77:506 (2017)
  * [273] Strigari LE.  Phys. Rev. D 93:103534 (2016)
  * [274] Dutta B, Liao S, Strigari LE, Walker JW.  Phys. Lett. B 773:242 (2017)
  * [275] Coloma P, Esteban I, Gonzalez-Garcia M, Maltoni M.  JHEP 02:023 (2020), [Addendum: JHEP 12, 071 (2020)]
  * [276] Coloma P, Gonzalez-Garcia M, Maltoni M, Schwetz T.  Phys. Rev. D 96:115007 (2017)
  * [277] Coloma P, et al.  JHEP 04:116 (2017)
  * [278] Denton PB, Gehrlein J arXiv:2008.06062 [hep-ph] (2020)
  * [279] Denton PB, Farzan Y, Shoemaker IM.  JHEP 07:037 (2018)
  * [280] Aprile E, et al. arXiv:2012.02846 [hep-ex] (2020)
  * [281] Cerdeño DG, et al.  JHEP 05:118 (2016), [Erratum: JHEP 09, 048 (2016)]
  * [282] Aalbers J, et al.  JCAP 11:017 (2016)
  * [283] DARWIN Collaboration, et al.  European Physical Journal C 80:1133 (2020)
  * [284] Kostensalo J, Suhonen J, Zuber K.  arXiv e-prints :arXiv:2009.01164 (2020)
  * [285] Newstead JL, Strigari LE, Lang RF.  Phys. Rev. D 99:043006 (2019)
  * [286] Agnes P, et al.  Phys. Rev. D 93:081101 (2016)
  * [287] Cattadori CM.  Journal of Physics: Conference Series 375:042008 (2012)
  * [288] Franco D, et al.  JCAP 08:017 (2016)
  * [289] Haselschwardt S, Lenardo B, Pirinen P, Suhonen J.  Phys. Rev. D 102:072009 (2020)
  * [290] Acciarri R, et al. arXiv:1601.02984 [physics.ins-det] (2016)
  * [291] Kostensalo J, Suhonen J, Zuber K.  Phys. Rev. C 97:034309 (2018)
  * [292] Capozzi F, Li SW, Zhu G, Beacom JF.  Phys. Rev. Lett. 123:131803 (2019)
  * [293] Cerdeño DG, Davis JH, Fairbairn M, Vincent AC.  Journal of Cosmology and Astroparticle Physics 2018:037 (2018)