# Matching Theory and Barnette’s Conjecture

Maximilian Gorsky – Technische Universität Berlin<EMAIL_ADDRESS>Raphael
Steiner – ETH Zürich<EMAIL_ADDRESS>Sebastian Wiederrecht –
LIRMM, University of Montpellier<EMAIL_ADDRESS>Supported by
an ETH Postdoctoral Fellowship.Supported by the ANR project ESIGMA
(ANR-17-CE23-0010).

###### Abstract

Barnette’s Conjecture claims that all cubic, 3-connected, planar, bipartite
graphs are Hamiltonian. We give a translation of this conjecture into the
matching-theoretic setting. This allows us to relax the requirement of
planarity to give the equivalent conjecture that all cubic, 3-connected,
Pfaffian, bipartite graphs are Hamiltonian.

A graph, other than the path of length three, is a brace if it is bipartite
and any two disjoint edges are part of a perfect matching. Our perspective
allows us to observe that Barnette’s Conjecture can be reduced to cubic,
planar braces. We show a similar reduction to braces for cubic, 3-connected,
bipartite graphs regarding four stronger versions of Hamiltonicity. Note that
in these cases we do not need planarity.

As a practical application of these results, we provide some supplements to a
generation procedure for cubic, 3-connected, planar, bipartite graphs
discovered by Holton et al. [_Hamiltonian Cycles in Cubic 3-Connected
Bipartite Planar Graphs, JCTB, 1985_]. These allow us to check whether a graph
we generated is a brace.

##  1 Introduction

In 1884, Tait conjectured that every cubic, 3-connected, planar graph is
Hamiltonian [Tai84], which Tutte disproved in 1946 [Tut46]. Subsequently,
Tutte conjectured that the result might hold if the graph was cubic,
3-connected, and bipartite [Tut71], which was disproven by Horton [BM76].
Since all known counterexamples to Tait’s conjecture are non-bipartite and all
known counterexamples to Tutte’s conjecture are non-planar, Barnette’s
conjecture from 1969 seems like a sensible compromise. Let $\mathcal{B}$ be
the class of all cubic, 3-connected, planar, bipartite graphs.

######  Conjecture 1.1 (Barnette [Bar69]).

All graphs in $\mathcal{B}$ are Hamiltonian.

This conjecture has received considerable attention and is known to be true
for some subclasses of $\mathcal{B}$, but an approach to the problem in
general continues to be elusive. See Goodey’s [Goo75] paper from 1975 for the
historically most significant example of a partial solution and see the work
of Bagheri et al. [BGFFS21] for a current partial solution which generalises
Goodey’s result. A related conjecture, also due to Barnette, which asserts
that all cubic, 3-connected, planar graphs in which every face has size at
most six, was recently resolved by Kardoš [Kar20]. Many parts of the proof
make heavy use of the constraint on the size of the faces, which leaves us
with no direct way to translate the methods used there. Significant effort has
also been devoted to finding strengthenings of Conjecture 1.1; that is
statements which also concern $\mathcal{B}$, but demand more than a simple
Hamiltonian cycle. For examples of strengthenings see [Her05] for an overview.

Using the perspective of Matching Theory, we formulate a result reducing the
Conjecture 1.1 to a subset of $\mathcal{B}$. In a graph $G$, we call a set of
mutually disjoint edges a _matching_ and we call it a _perfect matching_ if
the unions of the edges in the set contain all vertices of $G$. A connected
graph $G$ with $|V(G)|\geq 2k+2$ is called _$k$ -extendable_ if for every
matching $F\subseteq E(G)$ with $|F|\leq k$ there exists a perfect matching
$M$ with $F\subseteq M$. If $G$ is isomorphic to $C_{4}$ or a bipartite,
2-extendable graph, it is called a _brace_.

######  Lemma 1.2.

Conjecture 1.1 holds if and only if every cubic, planar brace is Hamiltonian.

We show that this result can be derived from a combination of statements from
across the literature (see Section 4). It hints at an extension of the
conjecture to a larger class of graphs. Despite Tutte’s Conjecture on the
matter being false, there is a substantial class of cubic, 3-connected, non-
planar, bipartite graphs which are Hamiltonian if and only if Barnette’s
conjecture holds. We relegate the introduction of the notion of Pfaffian
graphs to Section 4.

######  Theorem 1.3.

Conjecture 1.1 holds if and only if all cubic, 3-connected, Pfaffian,
bipartite graphs are Hamiltonian.

To prove this result, we discuss how Hamiltonian cycles interact with a
certain type of cut central to structural Matching Theory. We call a connected
graph $G$ _matching covered_ if it is 1-extendable. A cut $\partial(X)$ in a
matching covered graph $G$ is called _tight_ if for any perfect matching $M$
of $G$, we have $|\partial(X)\cap M|=1$. We call a tight cut _non-trivial_ if
each side of the cut contains at least two vertices. If we contract one of the
sides of a tight cut into a single vertex, we call the resulting graph a
_tight cut contraction_. By repeatedly searching out non-trivial tight cuts
and repeating this contraction operation, we arrive at a list of graphs which
do not have non-trivial tight cuts. Such graphs are called bricks if they are
non-bipartite and braces otherwise. The procedure we allude to here is called
the _tight cut decomposition_ due to Lovász [Lov87].

Focusing on matching covered graphs might at first seems like a strong
restriction, but the following result by Kőnig implies that all $k$-regular,
bipartite graphs are in fact matching covered.

######  Theorem 1.4 (Kőnig [Kön16]).

For all $k\in\mathds{N}$, the edge set of a $k$-regular, bipartite graph can
be partitioned into $k$ perfect matchings.

######  Corollary 1.5.

Any $k$-regular, connected, bipartite graph is matching covered.

In particular, if we consider a Hamiltonian graph $G$ with an even number of
vertices, then it turns out that all the structure belonging to its
Hamiltonian cycles is contained in the subgraph induced by those edges of $G$
that are contained in a perfect matching. We call this subgraph the _cover
graph_ of $G$.

######  Observation 1.6.

Let $G$ be a Hamiltonian graph with an even number of vertices, then every
Hamiltonian cycle of $G$ can be decomposed into two perfect matchings.

It turns out that many important properties are preserved under taking tight
cut contractions and are thus also preserved for the braces of a matching
covered, bipartite graph. We prove that this is also true for some types of
Hamiltonicity in cubic, 3-connected, bipartite graphs. This is interesting on
its own, but it also contributes to the proof of Theorem 1.3.

By $P_{k}$ we denote a path on $k$ vertices and note that $P_{k}$ has length
$k-1$. We call a graph $G$ with at least $k$ vertices _$P_{k}$ -Hamiltonian_
if any path of length $k-1$ in $G$ is contained in some Hamiltonian cycle of
$G$. Furthermore, we say that a graph $G$ has the $H^{-}$-property,
respectively the $H^{+-}$-property, if for any edge in $G$ there exists a
Hamiltonian cycle in $G$ which avoids said edge, respectively for any two
distinct edges $e$ and $f$ there exists a Hamiltonian cycle containing $e$ and
avoiding $f$.

######  Theorem 1.7.

Let $G$ be a cubic, $3$-connected, bipartite graph. The following hold

  1. i)

If the braces of $G$ are $P_{4}$-Hamiltonian, then $G$ is $P_{4}$-Hamiltonian.

  2. ii)

$G$ has the $H^{-}$-property if and only if the braces of $G$ have the
$H^{-}$-property.

  3. iii)

$G$ is $P_{3}$-Hamiltonian if and only if the braces of $G$ are
$P_{3}$-Hamiltonian.

  4. iv)

$G$ has the $H^{+-}$-property if and only if the braces of $G$ have the
$H^{+-}$-property.

There have also been computational efforts concerning Conjecture 1.1. The
first of which, by Holton et al. [HMM85] in 1985, also introduced an elegant
generation method for the graphs in $\mathcal{B}$ and this is still the method
used in recent efforts (see [BGM21]). To support the relevance of Lemma 1.2 to
the effort of resolving Conjecture 1.1, we provide a short list of amendments
to the generation procedure in Section 5 that allow us to keep track of
whether a graph we have generated is a brace or not. For each generated graph
this requires us to save some more information. This amounts to at most half
the number of vertices of the graph. Using this additional information we can
check in linear time whether the generated graph is a brace. The current state
of the computational effort is that all graphs in $\mathcal{B}$ with at most
90 vertices are Hamiltonian, announced by Brinkmann et al. [BGM21].

More or less separate from the rest of the presentation, we present the
theorem which motivated this project. It is almost trivial to prove, but
hopefully motivates further inquires into the connections between Matching
Theory and the study of Hamiltonicity.

######  Theorem 1.8.

The bricks and braces of the cover graph of a Hamiltonian graph with an even
number of vertices are Hamiltonian.

In Section 2, we start by introducing many of the basic matching-theoretic
concepts needed for our approach, including some more rigorous definitions for
concepts mentioned in this introduction. We then give a short proof of Theorem
1.8 in Section 3. Following this, we get into the core of the article and
tackle cubic, Pfaffian, bipartite graphs in Section 4. This is then followed
by a discussion on the generation of graphs in $\mathcal{B}$ and how to keep
track of their tight cuts in Section 5. In Section 6, we discuss our results
and provide some open questions.

##  2 Preliminaries

All graphs we consider are simple. Since we will mostly deal with bipartite
graphs, we establish that by $G=(A\cup B,E(G))$ we denote a bipartite graph
$G$ with the edge set $E(G)$ and a vertex set $V(G)$, such that $A$ and $B$
are the two colour classes that partition $V(G)$. A graph $G$ is called
_connected_ if all pairs of vertices can be connected by a path and it is
called $k$-connected if for any set $S\subseteq V(G)$ with $|S|\leq k-1$ the
graph $G-S$ remains connected. The _components_ of a graph are its maximal
connected subgraphs. A component containing only one vertex is called
_trivial_.

Given a cycle or path, we will call it _even_ if it contains an even number of
edges and _odd_ otherwise. We call a graph $G$ _$k$ -regular_ if all vertices
in $G$ have degree exactly $k$. If a graph is 3-regular, we also call it
_cubic_. A subgraph $H$ of a graph $G$ is called _spanning_ if it contains all
vertices of $G$. A spanning cycle is commonly called a _Hamiltonian cycle_
111This concept is more appropriately attributed to Kirkman [Kir56], but the
connection to William R. Hamilton is too well-entrenched to be severed now.,
which leads to a graph containing such a cycle being called _Hamiltonian_.

Given a subgraph $H$ of a graph $G$, we call $H$ _conformal_ if $G-H$ contains
a perfect matching and $H$ is called _$M$ -conformal_ if there exists an
$M\in\mathcal{M}(G)$ such that $M$ contains no edges with one endpoint in
$G-H$ and the other in $H$.

A _cut around $X$_ in a graph $G$, for a set $X\subseteq V(G)$, is a set
$\partial_{G}(X)\subseteq E(G)$, such that an edge $uv$ is in
$\partial_{G}(X)$ if and only if it has exactly one endpoint in $X$. We will
drop the index $G$ if the graph is clear from the context. Any set of edges
$F\subseteq E(G)$ is called a _cut_ , if there exists a set of vertices
$X\subseteq V(G)$ such that $F=\partial(X)$. The order of a cut $\partial(X)$
is defined as $|\partial(X)|$. We also set $\overline{X}=V(G)\setminus X$ and
call $X$ and $\overline{X}$ the _shores_ of the cut $\partial(X)$. If $X$ or
$\overline{X}$ only contain one element, we call $\partial(X)$ _trivial_. A
cut $\partial(X)$ with the property that $|\partial(X)\cap M|=1$ for all
perfect matchings $M$ of $G$ is called _tight_. Given a tight cut
$\partial(X)$ in a matching covered graph $G$, we denote the result of
contracting $X$ into a single vertex $c\not\in V(G)$ and deleting all
resulting parallel edges and loops as $G/(X\\!\\!\rightarrow\\!c)$, which is
called a _tight cut contraction_.

######  Lemma 2.1.

If $G$ is a matching covered graph, then the following properties of $G$ are
preserved for its tight cut contractions: planarity, ($1$-)connectivity, and
being bipartite.

###### Proof.

Proving that both planarity and connectivity are preserved through tight cut
contractions is easy using common methods. The proof that being bipartite is
preserved however uses an argument which we will make use of frequently.

Let $G=(A\cup B,E(G))$ be a matching covered, bipartite graph, let
$\partial(X)$ be a tight cut in $G$, and let $M$ be a perfect matching of $G$,
with $ab\in M\cap\partial(X)$. We can assume w.l.o.g. that $a\in X\cap A$ and
note that $ab$ is the only edge of $M$ found in $\partial(X)$, since it is
tight. Thus if $n=|X\cap A|$, only one the vertices from $X\cap A$ is matched
with a vertex in $\overline{X}$ and thus $|X\cap B|=n-1$.

Suppose there exists an edge $uv\in\partial(X)\setminus\\{ab\\}$ with
$u\in(X\cap B)$ and let $M^{\prime}$ be a perfect matching of $G$ such that
$uv\in M^{\prime}$. It is now easy to observe that it is impossible for
$M^{\prime}\cap E(G[X])$ to cover the $n$ vertices in $A$, as only $n-2$
vertices from $B$ can be matched with them. Therefore all endpoints of edges
from $\partial(X)$ which lie in $X$ also lie in $A$. Thus we can colour the
contraction vertex with the colour of the vertices in $B$ if we contract
$\overline{X}$ to construct $G/(\overline{X}\\!\\!\rightarrow\\!c)$. An
analogous argument also works for $G/(X\\!\\!\rightarrow\\!c)$. ∎

From the proof above, we extract the following statement.

######  Lemma 2.2.

Let $G$ be a matching covered, bipartite graph and let $\partial(X)$ be a
tight cut in $G$. All endpoints of the edges in $\partial(X)$ which lie in $X$
belong to the same colour class.

In general, for any graph $G$ with a perfect matching, it suffices to consider
the spanning subgraph of $G$ which contains only those edges which can be
found in some perfect matching of $G$, at least when we are interested in the
matching-theoretic properties of $G$. We call this graph the _cover graph of
$G$_. By repeatedly contracting non-trivial tight cuts in the cover graph of
$G$ and applying the same procedure to the tight cut contractions produced
this way, we perform a _tight cut decomposition_. This results in a collection
of graphs which cannot be decomposed further, and thus have no non-trivial
tight cuts. These graphs are called _braces_ , if they are bipartite, and
_bricks_ , if they are not bipartite. The tight cut decomposition has the
notable property that it always results in the same list of bricks and braces,
no matter in which order the contractions are applied [Lov87]. For our
purposes it will suffice to only consider braces, since we concentrate on
bipartite graphs. There is a more useful characterisation of braces using
extendability, a proof for which can for example be found in [LP09].

######  Theorem 2.3.

A graph is a brace if and only if it is either isomorphic to $C_{4}$ or
$2$-extendable.

We now introduce an operation which can be seen as a reversed tight cut
contraction. Let $G_{1}$ and $G_{2}$ be two matching covered graphs with
specified vertices $u\in V(G_{1})$ and $v\in V(G_{2})$, such that they are
incident to the same number of edges, $V(G_{1})\cap V(G_{2})=\emptyset$, and
there exists a bijection $\varphi:N_{G_{1}}(u)\rightarrow N_{G_{2}}(v)$. We
call $H$ a _splice of $G_{1}$ and $G_{2}$ at $u$ and $v$_, if $H$ is the
result of taking $(G_{1}-u)+(G_{2}-v)$ and adding the edges $\\{xy\mid x\in
N_{G_{1}}(u)\text{ and }\varphi(x)=y\\}$. The cut
$\partial_{H}(V(G_{1})\setminus\\{u\\})$ is called a _splicing cut_.

Since $G_{1}$ and $G_{2}$ are matching covered and the splicing cut $F$
corresponds to two trivial tight cuts, one in $G_{1}$ and the other in
$G_{2}$, it is easy to see that $H$ is again matching covered and in
particular for every edge $e$ in $H$ there exists a perfect matching of $H$
which contains $e$ and exactly one edge in $C$. Additionally, the splice of
two bipartite graphs is again bipartite. Using these observations, a result by
Carvalho et al. [dCLM02] (see Corollary 2.22.) implies the following.

######  Lemma 2.4.

Let $H$ be the splice of $G_{1}$ and $G_{2}$ and let $F$ be the corresponding
splicing cut in $H$. If $H$ is bipartite, then $F$ is tight.

Lastly, let us note two useful properties concerning $k$-extendable graphs.

######  Theorem 2.5 (Plummer [Plu80]).

If $G$ is $k$-extendable for some $k>1$, then it is also $(k-1)$-extendable
and $(k+1)$-connected.

######  Theorem 2.6 (Plummer [Plu86]).

A bipartite graph $G=(A\cup B,E(G))$ is $k$-extendable if and only if for all
distinct $a_{1},\ldots,a_{k}\in A$ and all distinct $b_{1},\ldots,b_{k}\in B$
the graph $G-\\{a_{1},\ldots,a_{k},b_{1},\ldots,b_{k}\\}$ has a perfect
matching.

##  3 A Note on Hamiltonian cycles in general graphs

We first formalise an observation concerning the interaction of tight cuts and
conformal cycles.

######  Lemma 3.1.

Let $G$ be a matching covered graph with a tight cut $\partial(X)$ and a
perfect matching $M$ of $G$. For every $M$-conformal cycle $C$ with
$E(C)\cap\partial(X)\neq\emptyset$, we have $|E(C)\cap\partial(X)|=2$.

###### Proof.

Clearly, since $C$ is a cycle, we have $|E(C)\cap\partial(X)|\geq 2$. We can
assume towards a contradiction that $|E(C)\cap\partial(X)|>2$. Since $C$ is
even, the set $(M\setminus E(C))\cup(E(C)\setminus M)$ is a perfect matching,
which contradicts the tightness of $\partial(X)$. ∎

Though the consequence of this lemma for Hamiltonian graphs is easy to deduce,
to the best of the authors’ knowledge it has gone unstated so far. The
following immediately implies Theorem 1.8.

######  Lemma 3.2.

Any tight cut contraction of a the cover graph of a Hamiltonian graph with an
even number of vertices is Hamiltonian.

###### Proof.

Let $G$ be an even graph, $\partial(X)$ be a tight cut in $G$, and $C$ be a
Hamiltonian cycle in $G$. It is easy to see that $E(C)$ contains two disjoint
perfect matchings $M$ and $M^{\prime}$ of $G$, making $C$ an $M$-conformal
cycle. Using Lemma 3.1, we thus know that $|E(C)\cap\partial(X)|=2$. Set
$G^{\prime}=G/(X\\!\\!\rightarrow\\!c)$ and
$C^{\prime}=C/(X\\!\\!\rightarrow\\!c)$, then clearly $C^{\prime}$ is a
Hamiltonian cycle of $G^{\prime}$. ∎

(a) A non-Hamiltonian graph on 26 vertices.

(b) A $C_{4}$ above and the cube below.

Figure 1: An example of a non-Hamiltonian graph with Hamiltonian braces.

Of course the reverse direction is more interesting to us, since it would
allow us to construct Hamiltonian graphs using splices, but it does not hold
in general. One example for this is the smallest cubic, 2-connected, planar,
bipartite graph not containing a Hamiltonian cycle found by Asano et al.
[ASEH82], which we depict in Figure 1(a) together with the braces found in its
tight cut decomposition in Figure 1(b). Clearly, both braces are Hamiltonian.

##  4 Hamiltonicity in cubic, bipartite, Pfaffian graphs

To prove our main theorem, we will need to discuss tight cuts in cubic,
bipartite graphs a bit more. Both lemmas that follow can be found in Section 7
of [McC00]. The first lemma can be generalised to arbitrary $k$-regular graphs
via a simple application of Menger’s theorem, though the forward direction
only holds when $k$ is odd.

######  Lemma 4.1 (McCuaig [McC00]).

Let $G$ be a cubic, $3$-connected, bipartite graph. A non-trivial cut in $G$
contains three mutually disjoint, pairwise non-adjacent edges if and only if
it is tight.

######  Lemma 4.2 (McCuaig [McC00]).

Let $G$ be a cubic, $3$-connected, bipartite graph with a non-trivial tight
cut $\partial(X)$. Then both ${G/(X\\!\\!\rightarrow\\!c)}$ and
${G/(\overline{X}\\!\\!\rightarrow\\!c)}$ are cubic, $3$-connected, and
bipartite.

The following strengthenings of Conjecture 1.1 will prove central to our
efforts.

######  Theorem 4.3 (Hertel [Her05] (corollary of a result by Kelmans
[Kel86])).

Conjecture 1.1 holds if and only if all graphs in $\mathcal{B}$ have the
$H^{-}$-property.

######  Theorem 4.4 (Hertel [Her05]).

Conjecture 1.1 holds if and only if all graphs in $\mathcal{B}$ are
$P_{4}$-Hamiltonian.

It should be noted that for the cubic, bipartite graphs the $H^{-}$-property
is equivalent to $P_{3}$-Hamiltonicity. We are now ready to prove the first
major lemma of this section.

######  Lemma 4.5.

Let $G$ be a cubic, $3$-connected, bipartite graph, with a non-trivial tight
cut $\partial(X)$, and let $G_{1}={G/(X\\!\\!\rightarrow\\!c)}$ and
$G_{2}={G/(\overline{X}\\!\\!\rightarrow\\!c)}$ be the two tight cut
contractions belonging to $\partial(X)$. The following hold

  1. i)

If $G_{1}$ and $G_{2}$ are $P_{4}$-Hamiltonian, then $G$ is
$P_{4}$-Hamiltonian.

  2. ii)

$G$ has the $H^{-}$-property if and only if $G_{1}$ and $G_{2}$ have the
$H^{-}$-property.

  3. iii)

$G$ is $P_{3}$-Hamiltonian if and only if $G_{1}$ and $G_{2}$ are
$P_{3}$-Hamiltonian.

  4. iv)

$G$ has the $H^{+-}$-property if and only if $G_{1}$ and $G_{2}$ have the
$H^{+-}$-property.

###### Proof.

Let $E_{c}^{i}$ be the set of edges in $G_{i}$ which are incident with $c$.
There are three edges in $\partial(X)$ and these are contracted into three
edges in $E_{c}^{i}$ for each $i\in\\{1,2\\}$. We say that an edge $e\in
E_{c}^{i}$, for $i\in\\{1,2\\}$, _corresponds_ to the edge $f\in\partial(X)$,
if $e\cap f\neq\emptyset$.

Towards the first item, suppose that $G_{1}$ and $G_{2}$ are
$P_{4}$-Hamiltonian. Let $P\subseteq G$ be a path of length three in $G$.
Suppose first that $P\subseteq G_{1}$ and let $H_{1}$ be a Hamiltonian cycle
of $G_{1}$ with $P\subseteq G_{1}$. Let $e,f\in\partial(X)$ be the two edges
in $G$ which correspond to the two edges in $E(H)\cap E_{c}^{1}$ and let
$e^{\prime},f^{\prime}\in E_{c}^{2}$ be the two edges in $G_{2}$ which
correspond to $e$ and $f$ respectively.

Clearly, $e^{\prime}$ and $f^{\prime}$ together form a path of length two and
since $G_{2}$ is $P_{4}$-Hamiltonian, there therefore exists a Hamiltonian
cycle $H_{2}$ in $G_{2}$ which uses both $e^{\prime}$ and $f^{\prime}$. In $G$
we can now find the Hamiltonian cycle $((H_{1}-c)+(H_{2}-c))+\\{e,f\\}$ which
uses $P$. Of course an analogous construction can be carried out if
$P\subseteq G_{2}$.

If $P$ is neither contained in $G_{1}$ nor in $G_{2}$ it must use at least one
edge of $e\in\partial(X)$, with $e_{i}$ being the edge in $G_{i}$
corresponding to $e$, for $i\in\\{1,2\\}$. We note that due to the edges in
$\partial(X)$ being mutually disjoint and pairwise non-adjacent (see Lemma
4.1), $P$ cannot use a second edge of $\partial(X)$. Let us further suppose
that $P$ uses one edge $f_{1}$ of $E(G[\overline{X}])$ and one edge $f_{2}$ of
$E(G[X])$ each. For our construction, we also choose an edge
$g\in\partial(X)\setminus\\{e\\}$ and the corresponding edges $g_{1}$ and
$g_{2}$ in $G_{1}$ and $G_{2}$. Since both $G_{1}$ and $G_{2}$ are
$P_{4}$-Hamiltonian, we can now choose a Hamiltonian cycle $H_{i}$ in $G_{i}$
containing the edges $e_{i}$ and $g_{i}$ for each $i\in\\{1,2\\}$. As in the
previous case, this lets us construct a Hamiltonian cycle
$((H_{1}-c)+(H_{2}-c))+\\{g,e\\}$ for $G$ which uses $P$.

Finally, we need to consider the case in which two of the edges of $P$ lie in
$G_{1}$, or $G_{2}$ respectively. W.l.o.g. we can assume that $|E(P)\cap
E(G_{1})|=2$ and let $e\in\partial(X)\cap E(P)$ again be the edge of the path
which lies in the tight cut, with $e_{i}$ being the edge in $G_{i}$
corresponding to $e$, for $i\in\\{1,2\\}$. We choose a Hamiltonian cycle
$H_{1}$ in $G_{1}$ which uses the three edges in $(E(P)\cap
E(G_{1}))\cup\\{e_{1}\\}$, which form a path. Let $f$ be the edge in $H_{1}$
which is incident with $c$ that is distinct from $e$ and let $f^{\prime}$ be
the corresponding edge in $G$, with $f^{\prime\prime}$ being the edge
corresponding to $f^{\prime}$ in $G_{2}$. This allows us to choose a
Hamiltonian cycle $H_{2}$ in $G_{2}$ which uses the edges $e_{2}$ and
$f^{\prime\prime}$. A Hamiltonian cycle in $G$ which contains $P$ can then be
constructed using the following expression
$((H_{1}-c)+(H_{2}-c))+\\{f^{\prime},e\\}$.

Now we can move on to considering the second point of the statement. For the
forward direction, we assume that $G$ has the $H^{-}$-property. Let $e\in
E(G_{1})$ be an edge and let us first suppose that it is not incident to $c$.
In $G$ there exists a Hamiltonian cycle $H$ that avoids $e$. Clearly,
${H/(X\\!\\!\rightarrow\\!c)}$ is a Hamiltonian cycle of $G_{1}$, which still
avoids $e$. If on the other hand $e\in E(G_{1})$ is incident to $c$, then let
$e^{\prime}\in\partial(X)$ be the corresponding edge in $G$. We can now
proceed exactly as in the previous case. Of course, these arguments also work
for any edge in $E(G_{2})$.

We can now concern ourselves with the backward direction and assume that both
$G_{1}$ and $G_{2}$ have the $H^{-}$-property. Let $e\in E(G)$ be an edge
which does not lie in $\partial(X)$. W.l.o.g. we can assume that $e\in
E(G_{1})$. Let $H_{1}$ be a Hamiltonian cycle in $G_{1}$ which avoids $e$ and
let $f,g\in E(H_{1})$ be the two edges incident with $c$, let
$f^{\prime},g^{\prime}\in\partial(X)$ be the corresponding edges in $G$, and
let $f^{\prime\prime},g^{\prime\prime}\in E(G_{2})$ be the corresponding edges
to $f^{\prime}$ and $g^{\prime}$ in $G_{2}$. We can now choose a Hamiltonian
cycle $H_{2}$ in $G_{2}$ which avoids the edge incident with $c$ which is
neither $f^{\prime\prime}$ nor $g^{\prime\prime}$. Since $G_{2}$ is cubic, by
Lemma 4.2, $H_{2}$ must therefore use $f^{\prime\prime}$ and
$g^{\prime\prime}$, which allows us to build the Hamiltonian cycle
$((H_{1}-c)+(H_{2}-c))+\\{f^{\prime},g^{\prime}\\}$ for $G$.

In the final case, we have $e\in E(G)\cap\partial(X)$. Let
$f,g\in(\partial(X)\setminus\\{e\\})$ be the two remaining edges in
$\partial(X)$ and let $e_{i},f_{i},g_{i}$ be the corresponding edges in
$G_{i}$ for $i\in\\{1,2\\}$. For both $i\in\\{1,2\\}$, we can now choose a
Hamiltonian cycle $H_{i}$ in $G_{i}$ which avoids $e_{i}$ and this allows us
to construct the Hamiltonian cycle $((H_{1}-c)+(H_{2}-c))+\\{f,g\\}$ for $G$
which avoids $e$.

For the third point of the statement, we only need to observe that a cubic,
$3$-connected, bipartite graph is $P_{3}$-Hamiltonian if and only if it has
the $H^{-}$-property. This has been noted in the literature before (see
[Her05]).

For the forward direction of the fourth point, we assume that $G$ has the
$H^{+-}$-property. Let $e,f\in E(G_{1})$ be two distinct edges. We will want
to include $e$ and avoid $f$. Clearly, as in the previous points, we can
simply find an appropriate Hamiltonian cycle in $G$ using $e$, or its
corresponding edge, and avoiding $f$, or its corresponding edge, and then
contract it to fit $G_{1}$. This of course also works for any two edges in
$G_{2}$.

For the backward direction, assume that $G_{1}$ and $G_{2}$ have the
$H^{+-}$-property. Again, we let $e,f\in E(G)$ be two distinct edges and our
goal is to include $e$ and avoid $f$ in a Hamiltonian cycle of $G$. If $e,f$
or their corresponding edges are both found in $G_{1}$ or $G_{2}$
respectively, we can find an appropriate Hamiltonian cycle $H$ in $G_{1}$ or
$G_{2}$ respectively. Then we force a Hamiltonian cycle which does not use the
edge incident to $c$ whose corresponding edge is not found in $H$. This then
allows us to combine these two cycles into a Hamiltonian cycle in $G$ which
uses $e$ and avoids $f$.

If this is not the case, then either $e$ or $f$ are exclusively to one of the
two tight cut contractions. W.l.o.g. let us say that $e$ or its corresponding
edge is found in $G_{1}$ and $f$ or its corresponding edge is found in
$G_{2}$. In this case we choose a Hamiltonian cycle $H_{2}$ in $G_{2}$ which
avoids $f$, or its corresponding edge, and then choose a Hamiltonian cycle
$H_{1}$ in $G_{1}$ which uses $e$, or its corresponding edge, and avoids the
edge in $E_{c}^{1}$ whose corresponding edge is not used in $H_{2}$. This
again allows us to combine $H_{1}$ and $H_{2}$ appropriately. ∎

This result together with Lemma 4.2 implies Theorem 1.7. The $H^{+-}$-property
is relevant to the contents of Section 5, but will not be needed in this
section. We note that for $P_{2}$-Hamiltonicity the proof idea we presented
fails for a statement analogous to those in Lemma 4.5, since we need to be
able to dictate where the Hamiltonian cycle leaves and where it enters. It
also does not work for $P_{5}$-Hamiltonicity or higher, as this involves paths
which can enter and leave the cut $\partial(X)$ in $G$ without being part of a
Hamiltonian cycle themselves. In particular, some of the graphs in
$\mathcal{B}$ are not $P_{5}$-Hamiltonian for this reason (see Figure 2(a)).

(a) A non-$P_{5}$-Hamiltonian graph.

(b) The Heawood graph.

Figure 2: In Figure 2(a), the tight cut, which is comprised of the dashed
lines, stops the highlighted $P_{5}$ from being in a Hamiltonian cycle. The
graph in Figure 2(a) is a member of $\mathcal{B}$.

A graph $G$ is called _Pfaffian_ if it has an orientation of its edges such
that for every perfect matching $M$ of $G$ and every $M$-conformal cycle $C$,
the number of edges in $C$ oriented in the same way is odd, for either
direction of traversal. Pfaffian graphs have a myriad of connections to other
problems, both in mathematics and outside of it (see [McC04] for an excellent
overview). In particular, the following remarkable statement holds.

######  Theorem 4.6 (Kasteleyn [Kas67]).

All planar graphs are Pfaffian.

The problem of characterising Pfaffian graphs ended up being one of the
central, motivating questions in Matching Theory. As with many problems in
matching theory, it can be reduced to bricks and braces.

######  Theorem 4.7 (Vazirani and Yannakakis [VY89]).

A matching covered graph is Pfaffian if and only if its bricks and braces are
Pfaffian.

Characterising Pfaffian bricks remains an open problem, but for braces McCuaig
[McC04], and Robertson, Seymour, and Thomas [RST99] independently resolved
this problem by providing the following answer. Let $G_{1},G_{2},G_{3}$ be
three bipartite graphs, such that their pairwise intersection is a cycle $C$
of length four and we have $V(G_{i})\setminus V(C)\neq\emptyset$ for all
$i\in\\{1,2,3\\}$. Further, let $S\subseteq E(C)$ be some subset of the edges
of $C$. A _trisum of $G_{1},G_{2},G_{3}$ at $C$_ is a graph
$(\bigcup_{i=1}^{3}G_{i})-S$. For later use, we call a trisum _cubic_ if
$S=E(C)$. Note that the cubic trisum of three cubic, bipartite graphs is
itself again cubic.

######  Theorem 4.8 (McCuaig [McC04], Robertson et al. [RST99]).

A brace is Pfaffian if and only if it is the Heawood graph (see Figure 2(b))
or can be constructed from planar braces by repeated use of the trisum
operation.

######  Corollary 4.9.

A cubic brace is Pfaffian if and only if it is the Heawood graph or can be
constructed from cubic, planar braces by repeated use of the cubic trisum
operation.

###### Proof.

If a cubic brace is constructed from cubic, planar braces by repeated use of
the cubic trisum operation, then it is clearly constructed from planar braces
by repeated use of the trisum operation and is thus Pfaffian due to Theorem
4.8. Of course, if we are considering the Heawood graph, there is nothing to
prove.

Now, let us assume to the contrary of the forward direction that $G$ is a
cubic, Pfaffian brace which cannot be constructed by repeated use of the cubic
trisum operation starting from cubic planar braces. We can assume that $G$ is
non-planar, not the Heawood graph, and a minimal counterexample to the
statement.

According to Theorem 4.8, there exist three Pfaffian braces $G_{1}$, $G_{2}$,
and $G_{3}$ whose pairwise intersection is a cycle $C$ of length four, such
that $G$ is the trisum of $G_{1},G_{2},G_{3}$ at $C$. Suppose for some
$i\in\\{1,2,3\\}$ there exists some $v\in V(G_{i}-C)$ which has degree greater
than three in $G_{i}$, then clearly $G$ would contain a vertex with degree
greater than three and thus not be cubic. We can thus make the narrower
supposition that in fact a vertex $u\in V(C)$ has degree greater than three in
$G_{i}$ for some $i\in\\{1,2,3\\}$. However, note that exactly two edges of
$u$ are contained in $E(C)$ and all other edges are kept in the construction
of $G$ and thus $u$ also has degree greater than three in $G$, again
contradicting that it is cubic.

Thus $G_{1},G_{2},G_{3}$ are cubic, Pfaffian braces which, due to the
minimality of $G$, were constructed from cubic, planar braces by repeated
application of the cubic trisum operation. Therefore the only option left is
for $E(G)\cap E(C)$ to be non-empty, but this would again create vertices of
degree greater than three. This lets us conclude that $G$ was indeed
constructed in the way suggested by the statement, which completes our proof.
∎

Let us now briefly observe how a Hamiltonian cycle in a cubic graph interacts
with a $C_{4}$.

######  Observation 4.10.

Let $G$ be a cubic graph that is not isomorphic to $K_{4}$, let $C$ be a cycle
of length four in $G$, and let $H$ be a Hamiltonian cycle in $G$. Then $C\cap
H$ is either isomorphic to $P_{4}$ or to two copies of $P_{2}$.

Using this observation, we can easily deduce the following if the graph is
also $P_{4}$-Hamiltonian.

######  Observation 4.11.

Let $G$ be a cubic, $P_{4}$-Hamiltonian graph that is not isomorphic to
$K_{4}$ and let $C$ be a cycle of length four in $G$. For any path $P\subseteq
C$ of length four, there exists a Hamiltonian cycle $H$ of $G$, such that
$C\cap H=P$. Similarly, for any perfect matching $M$ of $C$, there exists a
Hamiltonian cycle $H$ of $G$, such that $E(C\cap H)=M$.

We can now prove a key lemma that lets us preserve $P_{4}$-Hamiltonicity
through cubic trisums.

######  Lemma 4.12.

Let $G_{1}$, $G_{2}$, and $G_{3}$ be cubic, Pfaffian braces and let $G$ be the
result of a cubic trisum of $G_{1},G_{2},G_{3}$ at $C$. If $G_{1}$, $G_{2}$,
and $G_{3}$ are $P_{4}$-Hamiltonian, then $G$ is $P_{4}$-Hamiltonian.

###### Proof.

Let $P$ be a path of length three in $G$. Suppose $P\subset G_{1}$ and let
$H_{1}$ be a Hamiltonian cycle of $G_{1}$ with $P\subset H_{1}$, which exists
thanks to the $P_{4}$-Hamiltonicity of $G_{1}$. We note that due to
Observation 4.10, the non-trivial components of $H_{1}-E(C)$ must be paths of
even length ending on two vertices which are adjacent on $C$. Furthermore, we
let $V(C)=\\{u_{0},u_{1},u_{2},u_{3}\\}$, such that
$E(C)=\\{\\{u_{i},u_{j}\\}\mid i\in\\{0,1,2,3\\}\text{ and }i+1\equiv
j\pmod{4}\\}$.

First, we consider the case in which $H_{1}-E(C)$ contains a single non-
trivial component $Q$. Note that $Q$ is a path which must have all vertices in
$V(G_{1})\setminus V(C)$ as its internal vertices. W.l.o.g. we can assume that
$u_{0}$ and $u_{1}$ are the endpoints of $Q$.

Now, let us make use of Observation 4.11. We let $H_{2}$ be a Hamiltonian
cycle of $G_{2}$ with $E(H_{2})\cap E(C)=\\{u_{0}u_{1},u_{2}u_{3}\\}$, and let
$H_{3}$ be a Hamiltonian cycle of $G_{3}$ with $E(H_{3})\cap
E(C)=\\{u_{3}u_{0},u_{0}u_{1},u_{1}u_{2}\\}$. Let $R_{1}$ be the component of
$H_{2}-\\{u_{0}u_{3},u_{1}u_{2}\\}$ that is a path with the endpoints $u_{1}$
and $u_{2}$, and let $R_{2}$ be the other component of
$H_{2}-\\{u_{0}u_{3},u_{1}u_{2}\\}$. Further, let $R_{3}$ be the non-trivial
component of $H_{3}-\\{u_{3}u_{0},u_{0}u_{1},u_{1}u_{2}\\}$, which means it
has the endpoints $u_{2}$ and $u_{3}$. It is now easy to see that
$Q+R_{1}+R_{3}+R_{2}$ is a Hamiltonian cycle of $G$.

Similarly, if $H_{1}-E(C)$ contains two non-trivial components, we can choose
two Hamiltonian cycles in $G_{2}$ and $G_{3}$ to complete these two paths into
a Hamiltonian cycle of $G$. We can of course proceed analogously if $P$ is
entirely contained in $G_{2}$ or $G_{3}$.

Let us therefore assume that $P\subset G$, but $P\not\subset G_{i}$, for any
$i\in\\{1,2,3\\}$. We note that, since $G$ is cubic, there must therefore
exist exactly one $j\in[3]$ with $E(P)\cap E(G_{j})=\emptyset$. W.l.o.g. we
assume that $j=3$ and further, we can also assume that $|E(G_{1})\cap E(P)|=1$
and $|E(G_{2})\cap E(P)|=2$. Since $P$ runs through one of the vertices in
$V(C)$, where we performed the cubic 4-sum, we also know that $|P\cap V(C)|=1$
and we can assume that $u_{0}\in V(P)$.

In $G_{2}$, we choose a Hamiltonian cycle $H_{2}$ with $P\cap G_{2}\subset
H_{2}$ such that $u_{0}u_{1}\in E(H_{2})$. Note that this immediately implies
$u_{2}u_{3}\in E(H_{2})$. Suppose now that $u_{1}u_{2}\in E(H_{2})$. (We know
that $u_{0}u_{3}\not\in E(H_{2})$, since $H_{2}$ enters $C$ through an edge
outside of $C$ at $u_{0}$.) Let $v_{1}$ be the neighbour of $u_{1}$ in $G_{1}$
which is not on $C$. Inside of $G_{1}$, we choose a Hamiltonian cycle $H_{1}$
using $u_{0}u_{1}$, $u_{1}v_{1}$, and the lone edge in $E(P)\cap E(G_{1})$.
Note that $H_{1}$ must then also use the edge $u_{2}u_{3}$, but cannot use
$u_{0}u_{3}$ or $u_{1}u_{2}$, since $G_{1}$ is cubic. We can now choose a
Hamiltonian cycle $H_{3}$ in $G_{3}$ which uses all edges of $C$ except for
$u_{1}u_{2}$. We can now piece together a Hamiltonian cycle for $G$ which
contains $P$ as in the previous cases.

If on the other hand we have $u_{1}u_{2}\not\in E(H_{2})$, we choose a
Hamiltonian cycle $H_{1}$ in $G_{1}$ which uses $u_{0}u_{3}$, $u_{3}u_{2}$,
and the sole edge in $E(P)\cap E(G_{1})$. For $H_{1}$, we observe that this
implies $u_{2}u_{1}\in E(H_{1})$, since $G_{1}$ is cubic. Finally, we then
choose a Hamiltonian cycle $H_{3}$ for $G_{3}$ which uses all edges of $C$
except for $u_{2}u_{3}$. As in all previous cases, this allows us to construct
a Hamiltonian cycle for $G$ which uses $P$, concluding our proof. ∎

Before we prove our main theorem, we note that while the fact that it suffices
to consider braces for Conjecture 1.1 is a novel statement in the literal
sense, a quick trip through the literature yields a proof of Lemma 1.2
independent of our approach. Kelmans proved the following in 1986. We call a
graph _cyclically $k$-connected_, for $k\in\mathds{N}$, if for any cut $F$ of
order less than $k$, at most one component of $G-F$ contains a cycle.

######  Theorem 4.13 (Kelmans [Kel86]).

Conjecture 1.1 holds if and only if every cyclically $4$-connected graph in
$\mathcal{B}$ is Hamiltonian.

The interested reader may find it easier to get an overview of the work of
Kelmans on Conjecture 1.1 in an article by Alt et al. [APSW16] in which
translations of his results along with sketches for their proofs are provided.
The next result was proven as part of a larger project on $n$-extendability.

######  Theorem 4.14 (Holton and Plummer [HP91]).

Let $k\in\mathds{N}$ be a positive integer and let $G$ be a $(k+1)$-regular,
$(k+1)$-connected, bipartite graph. Then if $G$ is at least cyclically
$k^{2}$-connected, $G$ is also $k$-extendable.

######  Corollary 4.15.

If $G$ is a cubic, $3$-connected, bipartite graph, then $G$ is cyclically
4-connected if and only if $G$ is a brace.

###### Proof.

With $k=2$, Theorem 4.14 covers one direction. For the other, let $G$ be a
brace. By definition, $G$ cannot have a non-trivial tight cut and thus, using
Lemma 4.1 and the $3$-connectivity of the graph, we conclude that $G$
possesses no non-trivial cuts of order 3 or less. Hence $G$ is cyclically
$4$-connected. ∎

Thus, as a corollary of Theorem 4.14, we know that Conjecture 1.1 holds if and
only if every brace in $\mathcal{B}$ is Hamiltonian, which was claimed in the
introduction as Lemma 1.2. This leads us into the proof of our main theorem.

######  Theorem 4.16.

The following statements are equivalent:

  1. i)

All graphs in $\mathcal{B}$ are Hamiltonian.

  2. ii)

All braces in $\mathcal{B}$ are Hamiltonian.

  3. iii)

All braces in $\mathcal{B}$ are $P_{4}$-Hamiltonian.

  4. iv)

All cubic, Pfaffian braces are $P_{4}$-Hamiltonian.

  5. v)

All cubic, 3-connected, Pfaffian, bipartite graphs are $P_{4}$-Hamiltonian.

  6. vi)

All cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.

###### Proof.

The equivalence of (i) and (ii) can be taken from Lemma 1.2. That (i) implies
(iii) is a consequence of Theorem 4.4. To have (iii) imply (iv), we need to
use Lemma 4.12 and Corollary 4.9. (We note that the Heawood graph is also
$P_{4}$-Hamiltonian.) Since the first point of Theorem 1.7 allows us to infer
the $P_{4}$-Hamiltonicity of a set of cubic, bipartite, matching covered
graphs from their braces, we also know that (iv) implies (v). The implication
from (v) to (vi) is trivial and (vi) to (i) is implied by Theorem 4.6. ∎

We conclude this section by giving a reversed version of Lemma 4.12. However,
in this direction we only ask for Hamiltonicity. This might prove useful
should Conjecture 1.1 fail, or if there exists a way to show that non-planar,
cubic, Pfaffian braces are Hamiltonian.

For this purpose, we first note that there exists an earlier characterisation
of Pfaffian bipartite graphs. Since this characterisation did not yield a
polynomial time algorithm for recognising Pfaffian bipartite graphs, the
search continued, but for our purposes it will prove quite useful. A
_bisubdivision_ of a graph $H$ is the result of replacing the edges of $H$
with pairwise disjoint paths of odd length (possibly just $P_{2}$).

######  Theorem 4.17 (Little [Lit75]).

A bipartite graph with a perfect matching is Pfaffian if and only if it does
not contain a bisubdivision of $K_{3,3}$ as a conformal subgraph.

We will also need a method for finding these subgraphs. Let $C$ be a cycle of
length four in a brace $G$ with $V(C)=\\{a,b,c,d\\}$ and
$\\{a,c\\},\\{b,d\\}\not\in E(C)$. We call a pair of paths $L$ and $R$—with
$L$ having the endpoints $a$ and $c$, and $R$ having the endpoints $b$ and
$d$—a _conformal cross over $C$_ if $C+L+R$ is a conformal subgraph of $G$.

######  Lemma 4.18 (Giannopoulou and Wiederrecht [GW21]).

Let $G$ be a brace and let $C$ be a cycle of length four in $G$. There is a
conformal cross over $C$ if and only if $C$ is contained in a conformal
bisubdivision of $K_{3,3}$.

And with this, we turn to the proof of the lemma promised above.

######  Lemma 4.19.

Let $G_{1}$, $G_{2}$, and $G_{3}$ be Pfaffian braces, and let $G$ be cubic and
the result of a cubic trisum of $G_{1},G_{2},G_{3}$ at $C$. If $G$ is
Hamiltonian, then $G_{1}$, $G_{2}$, and $G_{3}$ are Hamiltonian.

###### Proof.

It is easy to observe that the fact that $G$ is cubic implies that $G_{1}$,
$G_{2}$, and $G_{3}$ will also be cubic. Now, let $H$ be a Hamiltonian cycle
in $G$. We will prove that we can construct a Hamiltonian cycle for $G_{1}$.
The construction for $G_{2}$ and $G_{3}$ can then be performed analogously.
Since $H$ is a Hamiltonian cycle, $H_{1}=G[V(G_{1})]\cap H$ consists of either
one or two non-trivial components, each of which is a path with both endpoints
in $V(C)$, such that $H_{1}-V(C)$ is a spanning subgraph of $G_{1}-V(C)$.

Suppose $P$ is the sole non-trivial component of $H_{1}$, where $v,w\in V(C)$
are the endpoints of $P$, such that $e=\\{v,w\\}\in E(C)$, then $(P+C)-e$ is a
Hamiltonian cycle in $G_{1}$. Similarly, if $H_{1}$ consists of two paths
$P_{1},P_{2}$, each with endpoints $v_{i},w_{i}\in V(C)$, such that
$e_{i}=\\{v_{i},w_{i}\\}\in E(C)$ for both $i\in\\{1,2\\}$, then
$(P_{1}+P_{2}+C)-\\{e_{1},e_{2}\\}$ is a Hamiltonian cycle in $G_{1}$.

On the other hand, we claim that it is impossible for $H_{1}$ to consist of
two paths $P$ and $Q$, such that each path has endpoints which are non-
adjacent in $C$. Note that therefore $P$ and $Q$ are paths of even length, as
they have endpoints of the same colour. Let $M$ be a perfect matching of $G$
such that $M\subset E(H)$. Due to their even length, both $P$ and $Q$
respectively have exactly one edge $e_{P}$, respectively $e_{Q}$, from $M$
which covers one of its endpoints, but is not actually an edge in $E(P)$,
respectively in $E(Q)$. In particular, the points of $e_{P}$ and $e_{Q}$ which
lie on $C$ are necessarily adjacent on $C$. Let $\\{x,y\\}=E(C)\cap(e_{P}\cup
e_{Q})$ and note that $(E(H_{1})\cap M)\cup\\{xy\\}$ is a perfect matching of
$G_{1}$ and in particular of $H_{1}+C$. Thus $H_{1}+C$ contains a conformal
cross over $C$, meaning $C$ is contained in a conformal bisubdivision of
$K_{3,3}$ in $G_{1}$, according to Lemma 4.18. By Theorem 4.17, $G_{1}$ can
therefore not be Pfaffian, contradicting our assumption. Therefore our claim
at the beginning of the paragraph is valid.

We are left with one more case in which $H_{1}$ has only one non-trivial
component $P$, whose endpoints are not adjacent on $C$. But in this situation,
there must exists a path $Q$, whose endpoints are the two vertices in
$V(C)\setminus V(P)$, which either spans $G_{2}-V(P)$ or $G_{3}-V(P)$.
W.l.o.g. we suppose that $Q\subseteq G_{2}-V(P)$. Note that in $G_{3}$ there
exists a perfect matching $M$ for which $C$ is conformal, since $G_{3}$ is
2-extendable. If we now consider that $(P+Q)-C$ is a spanning subgraph of
$(G_{1}+G_{2})-C$, it is easy to see that $P$ and $Q$ are again paths of even
length and form a conformal cross over $C$ in $G+E(C)$, with $M\setminus E(C)$
being a matching which covers the part of $G_{3}$ not involved in the cross.
As in the previous case, Lemma 4.18 and Theorem 4.17 tell us that $G+E(C)$ is
not Pfaffian. However, according to Theorem 4.8, the graph $G+E(C)$ should in
fact be Pfaffian, as it can be constructed via a trisum from three Pfaffian
braces. ∎

##  5 Generating cubic, planar braces

It is nice to know that it suffices to look at braces to resolve Conjecture
1.1, but that is of limited use if one does not know how to characterise these
graphs in a useful way. For this purpose, we discuss how the generation
procedure for members of $\mathcal{B}$ presented by Holton, Manvel, and McKay
[HMM85] can be amended such that we can track which of the generated graphs
are braces. This removes the burden of checking whether the non-braces
produced are Hamiltonian.

$\Rightarrow$

(a) The cube-expansion.

$x$$y$$u$$v$ $\Rightarrow$
$x$$y$$x^{\prime}$$y^{\prime}$$u$$v$$u^{\prime}$$v^{\prime}$

(b) The $C_{4}$-expansion.

Figure 3: The two operations needed to construct all graphs in $\mathcal{B}$
starting from the cube. The cube expansion can be used independent of the
colours of the vertices involved.

The generation process requires two operations pictured in Figure 3(a) and
Figure 3(b). We will call the operation used on a single vertex a _cube-
expansion_ and the operation used on a pair of edges a _$C_{4}$ -expansion_.
We will need a more rigorous definition of the $C_{4}$-expansion than the
intuition given by the illustration.

Let $G=(A\cup B,E(G))\in\mathcal{B}$ be a matching covered, planar, bipartite
graph and let $uv,xy\in E(G)$, with $u,y\in A$ and $v,x\in B$, such that
$u,v,x,y$ lie on a common facial cycle $C$ and $(C-uv)-xy$ consists of two odd
paths. We call $H$ a _$C_{4}$ -expansion (in $G$) at $uv$ and $xy$_ if

  * •

$V(H)=A^{\prime}\cup B^{\prime}$, where
$A^{\prime}=A\cup\\{v^{\prime},x^{\prime}\\}$ and
$B^{\prime}=B\cup\\{u^{\prime},y^{\prime}\\}$,

  * •

$E(H)=(E(G)\setminus\\{uv,xy\\})\cup\\{uu^{\prime},vv^{\prime},xx^{\prime},yy^{\prime},u^{\prime}v^{\prime},x^{\prime}y^{\prime},u^{\prime}x^{\prime},v^{\prime}y^{\prime}\\}$.

We can in fact remove the requirements that $G$ is planar and along with it,
that the cycle $C$ is facial, and still get a useful operation. In this case
we call $H$ a _general $C_{4}$-expansion_.

We note that the requirements on the parity of the paths of $(C-uv)-xy$
require $u,v,x,y$ to be distinct from each other. If we start with the cube,
it turns out that cube- and $C_{4}$-expansions suffice to construct the
entirety of $\mathcal{B}$.

######  Theorem 5.1 (Holton et al. [HMM85] (see Theorem 4)).

A graph is cubic, 3-connected, planar, and bipartite if and only if it can be
constructed from the cube by repeated applications of the cube- and
$C_{4}$-expansion.

We observe that the cube-expansion creates a cut consisting of three mutually
disjoint, pairwise non-adjacent edges and thus a tight cut, by Lemma 4.1. One
side of the tight cut created by the cube-expansion contracts into the cube,
justifying its name. It is not hard to prove that the cube-expansion preserves
being cubic, $3$-connected, planar, bipartite, and Hamiltonian. However, in
the published literature concerning Conjecture 1.1, it seems to be the only
known expansion—or rather reduction applied in reverse—which allows us to keep
both the structural properties of a graph relevant to Conjecture 1.1 and also
preserve its Hamiltonicity, strengthened or otherwise. In particular, the
sticking point for all other operations tends to be that they reduce
connectivity.

The fact that the cube-expansion behaves more nicely can be attributed to the
fact that it is special case of a splice of two graphs in $\mathcal{B}$ which
preserves planarity. In fact, if we consider the splice of any two graphs in
$\mathcal{B}$, we can easily show that this graph remains 3-connected,
bipartite, and cubic. According to Lemma 4.1, the splicing cut is therefore
tight. Thus the cube-expansion is simply a special case of a splice preserving
planarity.

In contrast to the cube-expansion, the $C_{4}$-expansion is only known to
preserve the structural properties of a graph in $\mathcal{B}$. We add to the
list of properties it is known to preserve by showing that it also interacts
nicely with 1- and 2-extendability. In fact, this is true for a much more
general class of graphs than $\mathcal{B}$.

######  Lemma 5.2.

Let $H$ be a general $C_{4}$-expansion of a matching covered, bipartite graph
$G$, then $H$ is matching covered and if $G$ is $2$-extendable, then $H$ is
also $2$-extendable.

###### Proof.

For this proof we will use the names given to the vertices involved in the
$C_{4}$-expansion in Figure 3(b). To start with, let us briefly discuss how we
can extend a perfect matching $M$ of $G$ to a perfect matching of $H$. If
$uv\in M$, then we can remove $uv$ from $M$ and add $uu^{\prime},vv^{\prime}$,
and we can proceed analogously if $xy\in M$. Should $uv\not\in M$, we instead
add $u^{\prime}v^{\prime}$, and again proceed analogously if $xy\not\in M$. In
the following, we will call the above steps _adjusting $M$_.

Let us first prove that $H$ is matching covered and let $f\in E(H)$ be an
arbitrary edge. If $f\in E(G)$ as well, we can choose a perfect matching $M$
of $G$ containing $f$, which must exist as $G$ is matching covered. No matter
what exactly is contained in $M\cap\\{uv,xy\\}$, it is easy to extend this to
a perfect matching of $H$ by adjusting $M$.

Suppose instead that
$f\in\\{uu^{\prime},xx^{\prime},vv^{\prime},yy^{\prime}\\}$ and w.l.o.g. that
in fact $f=uu^{\prime}$. Then we can choose a perfect matching $M$ of $G$
containing $uv$ and once more adjust $M$ to construct a perfect matching of
$H$. If instead $f\in\\{u^{\prime}v^{\prime},x^{\prime}y^{\prime}\\}$, we can
assume w.l.o.g. that $f=u^{\prime}v^{\prime}$. Now we can match $u$ in $G$ to
a vertex in $N_{H}(u)\setminus\\{v\\}$ inside of a perfect matching $M$ of $G$
and by adjusting $M$, we get a perfect matching of $H$ which uses
$u^{\prime}v^{\prime}$.

Lastly, if $f\in\\{v^{\prime}y^{\prime},x^{\prime}u^{\prime}\\}$, we can
assume w.l.o.g. that $f=v^{\prime}y^{\prime}$ and take a perfect matching $M$
of $(G-u)-x$, which must exist according to Theorem 2.6. We have $M\subseteq
E(H)$ and only $u,u^{\prime},v^{\prime},y^{\prime},x,x^{\prime}$ remain
unmatched, allowing us the add the edges
$uu^{\prime},v^{\prime}y^{\prime},xx^{\prime}$ to $M$ to complete a perfect
matching of $M$ containing $v^{\prime}y^{\prime}$.

Next, let us assume that $G$ is a brace and let $F\subseteq E(H)$ be a
matching containing two edges. There are three cases to consider.

Suppose that $F\subseteq E(G)$, then there exists a perfect matching $M$ of
$G$ with $F\subseteq M$ and we can again adjust $M$. If we instead have
$|F\cap E(G)|=1$, we will choose a perfect matching of $M$ containing the edge
$ab\in F\cap E(G)$ and have the freedom to fix another edge of $G$ which must
be contained. We will give a short list of the options (up to symmetry), under
the assumption that $a,b\not\in\\{u,v,x,y\\}$ and explain how we can change
$M$ to get a perfect matching for $H$.

  * •

$uu^{\prime}\in F$: Demand $ab,uv\in M$ and adjust $M$.

  * •

$u^{\prime}v^{\prime}\in F$: Demand $ab,uu^{\prime\prime}\in M$, for some
$u^{\prime\prime}\in N_{H}(u)\setminus\\{u^{\prime}\\}$, and adjust $M$.

  * •

$u^{\prime}x^{\prime}\in F$: Use Theorem 2.6 to get a perfect matching
matching $M^{\prime}$ of $G-\\{a,b,v,y\\}$ and extend this to a perfect
matching $M^{\prime}\cup\\{ab,u^{\prime}x^{\prime},vv^{\prime},yy^{\prime}\\}$
of $H$.

Now suppose that $|\\{a,b\\}\cap\\{u,v,x,y\\}|=1$. We assume w.l.o.g. that
$a=u$. Again we list the resulting cases (up to symmetry) and how to modify
$M$. Note that $uu^{\prime}\not\in F$.

  * •

$v^{\prime}y^{\prime}\in F$: Choose a $y^{\prime\prime}\in
N_{G}(y)\setminus\\{b,x\\}$, which must exist since $G$ is $3$-connected by
Theorem 2.5 and thus every vertex in $G$ has at least degree three. We can now
demand that $ab,yy^{\prime\prime}\in M$ and thus $uv,xy\not\in M$, which
allows us to construct the perfect matching
$M\cup\\{u^{\prime}x^{\prime},v^{\prime}y^{\prime}\\}$ of $H$. Clearly, this
construction resolves all cases in which
$|F\cap\\{u^{\prime}v^{\prime},v^{\prime}y^{\prime},y^{\prime}x^{\prime},x^{\prime}u^{\prime}\\}|=1$,
since the $C_{4}$ created by the $C_{4}$-expansion is conformal for the
matching we constructed.

  * •

$vv^{\prime}\in F$: We can reuse the construction presented for the case
$u^{\prime}x^{\prime}\in F$ in the previous list. This can also be used if
$yy^{\prime}\in F$.

  * •

$xx^{\prime}\in F$: Demand $ab,xy\in M$, which also means $uv\not\in M$, and
adjust $M$.

Suppose that $|\\{a,b\\}\cap\\{u,v,x,y\\}|=2$. In this case, we can assume
w.l.o.g. that $ab=ux$ and therefore know that $uu^{\prime},xx^{\prime}\not\in
F$. Thus to find matchings containing $ab$ and an edge of
$\\{u^{\prime}v^{\prime},v^{\prime}y^{\prime},y^{\prime}x^{\prime},x^{\prime}u^{\prime}\\}$,
it suffices to demand that $ab\in M$ (see the first item of the previous
list). If $vv^{\prime}\in F$ (or analogously $yy^{\prime}\in F$), we can find
a perfect matching $M$ of $G-\\{u,v,x,y\\}$ using Theorem 2.6 and construct
the perfect matching
$M\cup\\{ux,u^{\prime}x^{\prime},vv^{\prime},yy^{\prime}\\}$ of $H$.

In the third and final case, we have $F\subseteq(E(H)\setminus E(G))$ and this
creates three subcases up to symmetry: $uu^{\prime}\in F$,
$u^{\prime}v^{\prime}\in F$, and $u^{\prime}x^{\prime}\in F$. In the first, if
$F\cap\\{vv^{\prime},xx^{\prime},yy^{\prime}\\}\neq\emptyset$, we can choose a
perfect matching $M$ of $G$ with $uv,xy$ and adjust $M$. If we have
$x^{\prime}y^{\prime}\in F$, we choose a perfect matching $M$ with
$uv,xx^{\prime\prime}\in M$, where $x^{\prime\prime}\in
N_{G}(x)\setminus\\{x^{\prime}\\}$ and adjust $M$. Should
$v^{\prime}y^{\prime}\in F$, we can just take a perfect matching $M$ of
$(G-u)-x$ and construct the perfect matching
$M\cup\\{uu^{\prime},v^{\prime}y^{\prime},xx^{\prime}\\}$ for $H$. This covers
all possibilities, since $uu^{\prime}\in F$ implies that
$u^{\prime}v^{\prime},u^{\prime}x^{\prime}\not\in F$.

For the second subcase, we know that
$uu^{\prime},u^{\prime}x^{\prime},vv^{\prime},v^{\prime}y^{\prime}\not\in F$,
since $u^{\prime}v^{\prime}\in F$. If $xx^{\prime}\in F$, or $yy^{\prime}\in
F$, we are again in the first subcase and if $x^{\prime}y^{\prime}\in F$, we
can simply take a perfect matching of $G$ avoiding both $uv$ and $xy$ and then
expand it with the edges $u^{\prime}v^{\prime},x^{\prime}y^{\prime}$. The only
part of the third subcase that does not fall into the first subcase can then
be solved analogously to the second subcase. This concludes our proof. ∎

Figure 4: An example of a brace in $\mathcal{B}$. If the $C_{4}$-expansion at
the red edges is reversed, we get a graph in $\mathcal{B}$ with three laminar
tight cuts, marked with dashed lines. Should we use a cube expansion at the
blue vertex, we gain a tight cut that cannot be disrupted by the
$C_{4}$-expansion at the top of the graph.

At this point, we note that it is entirely possible to use several cube-
expansions on a graph in $\mathcal{B}$ and then apply a single
$C_{4}$-expansion to build a brace. This then begs the question of how and
when a $C_{4}$-expansion destroys tight cuts. Some intuition on this is given
in Figure 4, where we see that a large number of tight cuts can be disrupted
if a $C_{4}$-expansion touches both shores of those tight cuts, but the
$C_{4}$-expansion does not destroy tight cuts for which it takes place
entirely on one of the shores.

For the remainder of this section, we will work towards formalising this
intuition. We observe that the two edges used for the $C_{4}$-expansion cannot
be part of the same tight cut.

######  Lemma 5.3.

Let $G$ be a cubic, bipartite graph and let $H$ be a $C_{4}$-expansion of $G$
at $uv$ and $xy$. No tight cut in $G$ can contain both $uv$ and $xy$.

###### Proof.

Once more, we will use the names provided by Figure 3(b) in this proof.

Suppose that there exists a tight cut $\partial(X)$ with
$uv,xy\in\partial(X)$. Note that according to Lemma 2.2, we can assume
w.l.o.g. that $u,y\in X$. Let $C$ be the cycle on which $u,v,x,y$ lie
together. Note that $E(C)\cap\partial(X)$ must be even and
$|E(C)\cap\partial(X)|\geq 2$. Thanks to Lemma 4.1, we also know that
$|\partial(X)|=3$ and we can therefore conclude that
$E(C)\cap\partial(X)=\\{uv,xy\\}$. Thus, if $P$ and $Q$ are the two path
components of $(C-uv)-xy$, then $P$ and $Q$ lie in distinct components of
$G-\partial(X)$. W.l.o.g. we can assume that $u,y\in V(P)$ and in particular
this means that $u$ and $y$ are the endpoints of $P$, which makes $P$ a path
of even length, contradicting the requirements set for the application of the
$C_{4}$-expansion at $uv$ and $xy$. Thus no tight cut of $G$ can contain both
$uv$ and $xy$. ∎

Two cuts $\partial(X)$ and $\partial(Y)$ are called _laminar_ if $X\subseteq
Y$ or $Y\subseteq X$. As Lovász [Lov87] proves, the results of a tight cut
decomposition are independent of which tight cuts are chosen and the order in
which they are contracted. Thus it is common to consider a maximal family of
pairwise laminar tight cuts which translate into maximal families of pairwise
laminar tight cuts for the two tight cut contractions resulting from any
member of the original family. This informs the way in which we state the main
theorem of this section.

######  Theorem 5.4.

Let $G=(A\cup B,E(G))\in\mathcal{B}$ and let $\mathcal{F}$ be an inclusion-
wise maximal family of non-trivial, pairwise laminar tight cuts in $G$. If $H$
is a $C_{4}$-expansion of $G$ at $uv$ and $xy$, then the following is an
inclusion-wise maximal family of non-trivial, pairwise laminar tight cuts in
$H$, up to the renaming of at most four edges in $H$:

$\mathcal{F}^{\prime}:=\\{\partial_{G}(X)\mid\partial_{G}(X)\in\mathcal{F}\text{
and }|\\{u,v,x,y\\}\cap X|\neq 2\\}.$

###### Proof.

Let $C\subseteq G$ be the facial cycle containing $uv$ and $xy$ and let
$E^{\prime}=E(H)\setminus E(G)$, which are the edges added as part of the
$C_{4}$-expansion. We will again use the names provided by Figure 3(b) during
this proof. To set up the rest of our arguments, we partition $\mathcal{F}$
into three sets:

  * •

$\mathcal{F}_{1}:=\\{\partial_{G}(X)\in\mathcal{F}\mid|\\{u,v,x,y\\}\cap
X|\in\\{0,4\\}\\}$,

  * •

$\mathcal{F}_{2}:=\\{\partial_{G}(X)\in\mathcal{F}\mid|\\{u,v,x,y\\}\cap
X|\in\\{1,3\\}\\}$, and

  * •

$\mathcal{F}_{3}:=\mathcal{F}\setminus(\mathcal{F}_{1}\cup\mathcal{F}_{2})=\\{\partial_{G}(X)\in\mathcal{F}\mid|\\{u,v,x,y\\}\cap
X|=2\\}$.

We will start by proving that the cuts in $\mathcal{F}_{1}\cup\mathcal{F}_{2}$
can be translated into tight cuts in $H$. Let $\partial_{G}(X)$ be a cut in
$\mathcal{F}_{1}$ and let $M$ be a perfect matching of $G$, with
$ab\in(M\cap\partial(X))$. It is easy to observe that $\partial_{G}(X)\cap
E^{\prime}=\emptyset$ in this case. Therefore $\partial_{G}(X)$ remains a cut
in $H$ and we can assume w.l.o.g. that $|\\{u,v,x,y\\}\cap X|=0$. Furthermore,
we can assume that $X$ contains all endpoints of the edges of
$\partial_{G}(X)$ which lie in $A$, according to Lemma 2.2. From this
circumstance it is evident that $\partial_{G}(X)$ is also tight in $H$, as
$G[X]\subseteq H$ and we must match exactly one vertex from $A\cap X$ with a
vertex outside of $X$ to find a perfect matching of $H$. Thus
$\mathcal{F}_{1}$ is a family of non-trivial, laminar tight cuts in $H$.

Next, we consider a cut $\partial_{G}(Y)\in\mathcal{F}_{2}$. W.l.o.g. we
assume that $u\in Y$ and $v,x,y\in\overline{Y}$. To separate $u$ from $v$ in
$G$, we must have $uv\in\partial_{G}(Y)$, which also means that
$xy\not\in\partial_{G}(Y)$ according to Lemma 5.3. We claim that
$(\partial_{G}(Y)\setminus\\{uv\\})\cup\\{uu^{\prime}\\}$ is a tight cut in
$H$. This can be shown using an argument analogous to the one used in the case
from the previous paragraph, as we again have $G[Y]\subseteq H$. This is the
situation which requires the renaming of an edge, if we truly wanted to
translate the tight cuts of $G$ into $H$. Note that $|\mathcal{F}_{2}|\leq 4$,
since we only have four vertices which can be exclusive to a shore. This
justifies our bound on the number of edges that need to be renamed.

We will now consider $\mathcal{F}_{3}$, or more explicitly, we will prove that
all tight cuts in $H$ must be related to the cuts in
$\mathcal{F}_{1}\cup\mathcal{F}_{2}$. For this discussion, we can assume
$\mathcal{F}_{1}\cup\mathcal{F}_{2}$ to be empty, or equivalently, we can
consider $G$ and $H$ to be the results of contracting all tight cuts in
$\mathcal{F}_{1}\cup\mathcal{F}_{2}$ and renaming vertices appropriately, i.e.
if we contract a shore from a cut of $\mathcal{F}_{2}$ which contained only
$u$, but not $v$, $x$, or $y$, then we rename the contraction vertex to $u$.
Since the family of tight cuts in $\mathcal{F}$ is laminar, any tight cuts we
find in this reduced version of the graphs can also be found if we do not
contract $\mathcal{F}_{1}\cup\mathcal{F}_{2}$, up to some relabelling of edges
incident to $u,v,x,y$. Note that even if we had to contract tight cuts to
arrive in this simplified case, we know that according to Lemma 4.2 our graphs
are still found in $\mathcal{B}$. We claim that under these assumptions $H$ is
a brace.

Suppose towards a contradiction that $\partial_{H}(Z)$ is a non-trivial tight
cut in $H$ and note that since $H\in\mathcal{B}$, according to Lemma 4.1, the
cut $\partial_{H}(Z)$ is a set of three mutually disjoint, pairwise non-
adjacent edges. If $|\\{u,v,x,y\\}\cap Z|\in\\{0,1,3,4\\}$ then
$\partial_{H}(Z)$ corresponds to a tight cut in
$\mathcal{F}_{1}\cup\mathcal{F}_{2}$, which we assumed to be empty. Thus
$|\\{u,v,x,y\\}\cap Z|=2$ and therefore some edges from $E^{\prime}$ must be
part of $\partial_{H}(Z)$.

We distinguish three cases, the first being that $u$ and $v$ lie on the same
shore of $\partial_{H}(Z)$. Clearly, $\partial_{H}(Z)$ must involve some edges
in $E^{\prime}$. However, due to the restrictions Lemma 2.2 places on the
colours of the endpoints of these edges, we would in fact need at least three
edges from $E^{\prime}$ to separate $\\{u,v\\}$ and $\\{x,y\\}$ in
$H-\partial_{H}(Z)$. Furthermore, due to our limited choices, these edges
cannot be mutually disjoint, contradicting Lemma 4.1. Thus we can go on to
assuming that $u$ and $v$, and respectively $x$ and $y$, lie on different
shores with respect to $\partial_{H}(Z)$.

If $u$ and $x$ lie on the same shore, then $\partial_{H}(Z)$ must again
involve at least two edges of $E^{\prime}$ whilst also respecting the
constraints provided by Lemma 2.2. Again, this is not possible if we choose
only two such edges from $E^{\prime}$ and any three suitable edges are not
mutually disjoint, again contradicting Lemma 4.1.

We move on to assuming that $u$ and $y$ lie on the same shore of the tight cut
$\partial_{H}(Z)$. Using the arguments above, especially those based on Lemma
2.2, we can deduce that $uu^{\prime},yy^{\prime}\in\partial_{H}(Z)$, leaving
us with one edge $e\in\partial_{H}(Z)\cap E(G)$. This implies
$\partial_{H}(Z)=\\{uv,xy,e\\}$ is tight in $G$, which directly contradicts
Lemma 5.3. ∎

We observe that this theorem also solidifies the intuition that any tight cut
in a graph in $\mathcal{B}$ was initially introduced by a cube-expansion. This
idea together with Theorem 5.4 suggests the following amendments to the
generation procedure for $\mathcal{B}$.

  * •

Associate with each generated graph $G$ a family $\mathcal{F}_{G}$, which
contains an inclusion-wise maximal family of non-trivial tight cuts in $G$.
(As we will see, we do not have to check these properties.)

  * •

If we use a cube-expansion on a vertex $v$ in a graph $G$ to generate $H$, we
add the tight cut created by this operation into $\mathcal{F}_{G}$. Any edges
of cuts in $\mathcal{F}_{G}$ incident to $v$, are then renamed appropriately.
The result of this is $\mathcal{F}_{H}$. Note that the new tight cut is
guaranteed to be laminar to the others, since we expanded a single vertex.

  * •

Whenever we use a $C_{4}$-expansion in a graph $G$ at $uv$ and $xy$ to
generate $H$, we again rename the edges in cuts of $\mathcal{F}_{G}$ which
involve $uv$ or $xy$. Furthermore, we remove any cuts $\partial_{G}(X)$ from
$\mathcal{F}_{G}$ with $|\\{u,v,x,y\\}\cap X|\neq 2$. The result of this is
$\mathcal{F}_{H}$, which is an inclusion-wise maximal family of non-trivial
tight cuts in $G$ according to Theorem 5.4. Of course if
$\mathcal{F}_{G}=\emptyset$, then $\mathcal{F}_{H}=\emptyset$. The family
$\mathcal{F}_{H}$ can be constructed in linear time (see Lemma 5.6).

If we generate the graphs in $\mathcal{B}$ in this way, we only have to check
the Hamiltonicity of a graph $G\in\mathcal{B}$ if $\mathcal{F}_{G}=\emptyset$,
which means that it is a brace. This drives up the space-requirements of the
procedure somewhat, but the time saved by not checking graphs with tight cuts
for their Hamiltonicity should make up for this fact, at least for small
numbers of vertices. For some pairs of graphs, this also makes it easier to
check whether they are isomorphic, since for two isomorphic graphs $G$ and
$G^{\prime}$, we must have $|\mathcal{F}_{G}|=|\mathcal{F}_{G^{\prime}}|$.

In this context it seems pertinent to ask just how many tight cuts we might
find and thus have to save in addition to the graph. We give a sharp upper
bound to this.

######  Lemma 5.5.

Let $G\in\mathcal{B}$, with $|V(G)|=n$ and let $\mathcal{F}$ be an inclusion-
wise maximal family of non-trivial, pairwise laminar tight cuts, then
$|\mathcal{F}|\leq\frac{n-8}{6}$. This bound is sharp.

###### Proof.

We note that all graphs in $\mathcal{B}$ have at least eight vertices and thus
$0\leq\frac{n-8}{6}$, which verifies the bound for all braces in
$\mathcal{B}$. Assume that $G$ is a smallest counterexample to the statement
of the lemma and observe that $G$ is therefore not a brace. We note that in
any maximal family of non-trivial, pairwise laminar tight cuts, we can always
find a cut $\partial(X)$, such that $X\subseteq Y$, for all
$\partial(Y)\in\mathcal{F}$. Thus
$G_{1}=G/(\overline{X}\\!\\!\rightarrow\\!c)$ is a brace, since any tight cut
in $G_{1}$ would translate into a tight cut in $G$ missing from $\mathcal{F}$,
which was assumed to be maximal. Furthermore, $G_{1}\in\mathcal{B}$ by Lemma
4.2 and $\mathcal{F}^{\prime}=\mathcal{F}\setminus\\{\partial(X)\\}$ is an
inclusion-wise maximal family of non-trivial, pairwise laminar tight cuts in
$G_{2}=G/(X\\!\\!\rightarrow\\!c)$, up to some renaming of edges.

We note that the smallest brace in $\mathcal{B}$ has eight vertices. Hence,
$|X|\geq 7$ and we have $|V(G_{2})|\leq n-6$, since we retained the
contraction vertex $c$. This can then be combined to yield

$|\mathcal{F}|=|\mathcal{F}^{\prime}|+1\leq\frac{n-14}{6}+1=\frac{n-8}{6},$

which contradicts $G$ being a smallest counterexample, as this entails
$|\mathcal{F}|>\frac{n-8}{6}$.

An example of a graph with a tight cut which meets this bound can be
constructed by applying a single cube-expansion to the cube. ∎

If we save every tight cut as a set of three edges, we thus need additional
space for each generated graph adding up to at most half the number of its
vertices. Let us now argue that we can compute $\mathcal{F}_{H}$ from
$\mathcal{F}_{G}$ in linear time if we performed a $C_{4}$-expansion, under
the assumption that $\mathcal{F}_{G}$ was saved in a way that lets us directly
link the edges in the graphs with the edges in the cuts contained in
$\mathcal{F}_{G}$. This could for example be realised by labelling the edges
of $G$.

######  Lemma 5.6.

Let $G\in\mathcal{B}$ and let $\mathcal{F}_{G}$ be an inclusion-wise maximal
family of non-trivial, pairwise laminar tight cuts in $G$. If $H$ is a
$C_{4}$-expansion of $G$ at $uv$ and $xy$, then an inclusion-wise maximal
family $\mathcal{F}_{H}$ of non-trivial, pairwise laminar tight cuts in $H$
can be constructed from $\mathcal{F}_{G}$ in linear time.

###### Proof.

We first make some observations on the structure of the graph, which we can
then use to simplify our computation. Let $\partial_{G}(X)\in\mathcal{F}_{G}$
be such that $|\\{u,v,x,y\\}\cap X|=2$ and recall that according to Theorem
5.4 these are the tight cuts we must identify and remove to construct
$\mathcal{F}_{H}$.

We claim that $\partial_{G}(X)$ cannot separate $u$ and $v$. Suppose that this
is not true. This requires that $uv\in\partial_{G}(X)$. Now, independent of
whether $u$ and $x$, or $u$ and $y$ lie on the same shore, we must also have
$xy\in\partial_{G}(X)$, which contradicts Lemma 5.3. Thus our claim holds and
$\partial_{G}(X)$ must separate $u,v$ and $x,y$ in $G$. In fact, as a
consequence of this claim, we know that we must remove a cut from
$\mathcal{F}_{G}$ if and only if it separates $u,v$ and $x,y$ in $G$. Let us
call such a cut _removable_. We further remark that for any removable cut
$\partial_{G}(X)$, we therefore have
$\partial_{G}(X)\cap\\{uv,xy\\}=\emptyset$.

Next, let us consider a path $P\subseteq G$ with the endpoints $u$ and $x$,
which must exist since $G$ is connected. We now analyse how $P$ interacts with
some arbitrary $\partial_{G}(Y)\in\mathcal{F}_{G}$. W.l.o.g. we assume that
$u\in Y$. The graph $P-\partial_{G}(Y)$ is composed of components
$P_{0},\ldots,P_{t}$ that are paths, which we can name such that $u\in
V(P_{0})$, $x\in V(P_{t})$, and the paths appear in increasing order when we
traverse $P$ from $u$ to $x$. It is now easy to see that $P_{i}\subseteq
G[Y]$, for an $i\in\\{0,\ldots,t\\}$, if and only if $i$ is even. Therefore
$\partial_{G}(Y)$ is removable if and only if $t$ is odd, which is equivalent
to $|E(P)\cap\partial_{G}(Y)|$ being even.

Let us turn to constructing $\mathcal{F}_{H}$. We assume that an edge $e\in
E(G)$ has the label $\ell_{Z}$ if $e\in\partial(Z)\in\mathcal{F}_{G}$. A path
$P$ with endpoints $u$ and $x$ can be found in linear time using a breadth
first search. We can then count the occurrences of all labels, noting the
results separately for each label. If any specific label occurs an odd number
of times, we delete this label from all edges of the graph, which can again be
done by traversing the graph once after we have determined which labels have
to be deleted. After performing the $C_{4}$-expansion and the requisite
renaming of edges mentioned in Theorem 5.4, which can be performed in constant
time, the labels which are left form $\mathcal{F}_{H}$. If necessary
$\mathcal{F}_{H}$ can be constructed explicitly by traversing $H$ once more,
again adding a linear effort. ∎

While the above arguments take care of the generation of braces in
$\mathcal{B}$, the procedure used in [HMM85] to check the Hamiltonicity of the
generated graphs involves checking the $H^{+-}$-property for small graphs in
$\mathcal{B}$. For larger graphs, we can then find certain configurations that
allow us to reduce to the smaller graphs we have generated. The
$H^{+-}$-property can then be used to confirm that the larger graphs are
Hamiltonian, though the actual $H^{+-}$-property cannot be preserved. We
illustrate this with the following result.

######  Theorem 5.7 (Brinkmann et al. [BGM21]).

Let $G\in\mathcal{B}$, with $|V(G)|=n$, then

  1. i)

$n\leq 90$ implies that $G$ is Hamiltonian,

  2. ii)

$n\leq 78$ implies that $G$ is $P_{2}$-Hamiltonian, and

  3. iii)

$n\leq 66$ implies that $G$ has the $H^{+-}$-property.

The first and second item are implied by the third through the use of several
results from [HMM85]. Lemma 4.5 tells us that we can preserve the
$H^{+-}$-property through tight cuts. In particular, combining the above
theorem and Lemma 4.5 tells us that, if $G\in\mathcal{B}$ is a graph whose
braces each have 66 vertices or less, then $G$ has the $H^{+-}$-property. Thus
our amendments to the generation procedure can be adapted in a straight-
forward fashion to checking the $H^{+-}$-property.

Finally, we want to mention that using Lemma 4.1, our results can be rephrased
such that any tight cut is replaced with a cut of order three consisting of
mutually disjoint, pairwise non-adjacent edges, if we are only concerned with
cubic, 3-connected, bipartite graphs. This basically translates everything
into the language of cyclically 4-connected graphs, in line with Corollary
4.15. Whilst this might make some of the statements more intuitive for the
reader, we are not sure if a straightforward translation of the proofs exist.

##  6 Discussion

We mentioned splices briefly in Section 3 and said that reversed versions of
Theorem 1.8 let us construct new Hamiltonian graphs. This can in fact be done
with Lemma 4.2 and, though the lemma does not concern tight cuts, Lemma 4.12
can be used similarly. In particular, the $K_{3,3}$ and the Heawood graph are
$P_{3}$\- and $P_{4}$-Hamiltonian, and have the $H^{-}$\- and the
$H^{+-}$-property. Additionally, Theorem 5.7 provides us with a large class of
small cubic braces with the $H^{-}$\- and the $H^{+-}$-property. Thus we can
generate a large class containing both planar and non-planar, cubic, bipartite
graphs with strong Hamiltonicity properties by repeatedly using splices.

In Section 4, we both mention a reduction of Conjecture 1.1 to braces and then
provide what is essentially a relaxation of planarity for the conjecture. With
this reformulated conjecture, we can again attempt to relax or strengthen
certain properties. Let us start with planar, cubic braces, which are
3-connected by Theorem 2.5. Using Euler’s formula, it is fairly easy to prove
that a planar, bipartite graph cannot have minimum degree four. Thus we cannot
demand 4-connectivity. We cannot drop planarity either, as the Georges-Kelmans
graph $GK$, discovered by Georges [Geo89] and Kelmans [Kel86][Kel88]
independently, is a brace, as the authors verified by hand. Thus the only
option left is to drop regularity, leading us to the following question.

######  Question 6.1.

Is every planar brace Hamiltonian?

Concerning non-Pfaffian graphs, it is fairly easy to find a conformal
bisubdivision of the $K_{3,3}$ in $GK$, but we did not check whether all
counterexamples to Tutte’s conjecture are Pfaffian. If any of them are, then
this would disprove Conjecture 1.1 via the sixth item of Theorem 4.16. Whilst
investigating non-planar braces, the following question comes naturally in the
vein of the main subject of [BGM21] and $GK$ already gives an upper bound of
$50$.

######  Question 6.2.

What is the least number of vertices of a non-planar, non-Hamiltonian brace?

One of the key lemmas for proving Theorem 4.16 was Lemma 4.5. Missing from the
items there are both $P_{2}$-Hamiltonicity and Hamiltonicity itself. If we
have a $P_{2}$-Hamiltonian, cubic, $3$-connected, bipartite graph, then it is
easy to show, using the methods we presented, that all of its tight cut
contractions will also be $P_{2}$-Hamiltonian and for Hamiltonicity this fact
is stated in Theorem 1.8. One might wonder if the other direction holds for
either property.

This however can be disproven by considering the first graph presented by
Horton [BM76] as a counterexample to Tutte’s conjecture. First we note that
this graph can be constructed by taking a $K_{3,3}$ and splicing a copy of the
graph in Figure 5(a) into each of the three vertices of one of its colour
classes. Each of these splices creates a tight cut. The fact that the Horton
graph can be constructed this way confirms that it is not Pfaffian according
to Theorem 4.7 and Theorem 4.17, since the $K_{3,3}$ is one of its braces. We
have already noted that the $K_{3,3}$ has several strong Hamiltonicity
properties. Unsurprisingly, it is also $P_{2}$-Hamiltonian. This is also true
for the graph in Figure 5(a), which also happens to be non-Pfaffian. Thus if
two tight cut contractions of a given cubic, $3$-connected, bipartite graph
$G$ are ($P_{2}$-)Hamiltonian, the graph $G$ itself may still be non-
Hamiltonian.

(a) A brace $B$ of the Horton graph.

(b) A Hamiltonian cycle in $B$.

(c) Another Hamiltonian cycle in $B$.

(d) A conformal bisubdivision of $K_{3,3}$ in $B$.

Figure 5: The two Hamiltonian cycles given for $B$ should help to confirm that
$B$ is $P_{2}$-Hamiltonian. Due to the symmetry in $B$, the cycle in Figure
5(c) can be shifted such that all edges not covered by the cycle in Figure
5(b) can be found in a Hamiltonian cycle of this type in $B$. The
bisubdivision of $K_{3,3}$ in Figure 5(d) confirms that $B$ is not Pfaffian.

In contrast to this, we are unsure whether the first point of Lemma 4.5 can be
reversed. This is somewhat surprising, since for the other Hamiltonicity
properties we considered, this direction was actually the easier one to prove.

######  Question 6.3.

Let $G$ be a $P_{4}$-Hamiltonian, $3$-connected, cubic, bipartite graph, with
a non-trivial tight cut $\partial(X)$, and let $G_{1}$ and $G_{2}$ be the two
tight cut contractions belonging to $\partial(X)$. Are $G_{1}$ and $G_{2}$
also $P_{4}$-Hamiltonian?

Regarding our suggestions for the generation procedure for $\mathcal{B}$, one
might ask why we cannot just check each generated graph and see whether it is
a brace. This is indeed possible. A polynomial time algorithm for determining
the extendability of a bipartite graph was first given by Lakhal and Litzler
[LL98] and an improvement to a runtime in $\mathcal{O}(mn)$, which is in
$\mathcal{O}(n^{2})$ for cubic graphs, was then provided by Zhang and Zhang
[ZZ06]. Of course, we could also just check whether the generated graph is
cyclically 4-connected, but the known algorithms (see [DKKP04] and [LL09]) do
not improve on a quadratic runtime. Either way, unless space is scarce and we
have much more processor time to burn, it seems like checking whether a
generated graph is a brace in this way would not be advisable, though it might
still improve on simply generating all graphs and checking Hamiltonicity
indiscriminately.

Acknowledgements. We want to thank Tom Fowler for providing us with an
unpublished manuscript [Fow00], in which he tackles the task of finding more
reductions for Barnette’s Conjecture. This ended up informing the discussion
on known reductions in Section 5.

Additionally, we want to thank an anonymous reviewer for spotting an error in
the original bound of Lemma 5.5, pointing us to the Horton graph as an example
of a non-Hamiltonian graph with ($P_{2}$-)Hamiltonian braces, and providing
several smaller remarks which improved the paper.

## References

  * [APSW16] Helmut Alt, Michael S Payne, Jens M Schmidt, and David R Wood.  Thoughts on Barnette’s Conjecture.  Australasian Journal of Combinatorics, 64(2):354–365, 2016\.
  * [ASEH82] Takao Asano, Nobuji Saito, Geoffrey Exoo, and Frank Harary.  The smallest 2-connected cubic bipartite planar nonhamiltonian graph.  Discrete Mathematics, 38(1):1–6, 1982.
  * [Bar69] David W Barnette.  Conjecture 5.  Recent Progress in Combinatorics (W. T. Tutte, ed.), 343, 1969.
  * [BGFFS21] Behrooz Bagheri Gh, Tomas Feder, Herbert Fleischner, and Carlos Subi.  Hamiltonian Cycles in Planar Cubic Graphs with Facial 2-Factors, and a New Partial Solution of Barnette’s Conjecture.  Journal of Graph Theory, 96(2):269–288, 2021.
  * [BGM21] Gunnar Brinkmann, Jan Goedgebeur, and Brendan McKay.  The Minimality of the Georges-Kelmans Graph.  Sep 2021.  URL: http://dx.doi.org/10.1090/mcom/3701, doi:10.1090/mcom/3701.
  * [BM76] John A Bondy and Uppaluri S R Murty.  Graph Theory with Applications, volume 290.  Macmillan London, 1976.
  * [dCLM02] Marcelo H de Carvalho, Cláudio L Lucchesi, and Uppaluri SR Murty.  On a Conjecture of Lovász Concerning Bricks: I. The Characteristic of a Matching Covered Graph.  Journal of Combinatorial Theory, Series B, 85(1):94–136, 2002.
  * [DKKP04] Zdeněk Dvořák, Jan Kára, Daniel Kral, and Ondřej Pangrác.  An Algorithm for Cyclic Edge Connectivity of Cubic Graphs.  In Scandinavian Workshop on Algorithm Theory, pages 236–247. Springer, 2004.
  * [Fow00] Tom Fowler.  Reducible Configurations for the Barnette Conjecture.  Unpublished Manuscript, August, 2000.
  * [Geo89] John P Georges.  Non-Hamiltonian Bicubic Graphs.  Journal of Combinatorial Theory, Series B, 46(1):121–124, 1989\.
  * [Goo75] Paul R Goodey.  Hamiltonian Circuits in Polytopes with Even Sided Faces.  Israel Journal of Mathematics, 22(1):52–56, 1975.
  * [GW21] Archontia C Giannopoulou and Sebastian Wiederrecht.  Two disjoint alternating paths in bipartite graphs.  2021\.  arXiv:2110.02013.
  * [Her05] Alexander Hertel.  A Survey & Strengthening of Barnette’s Conjecture.  Technical report, University of Toronto, 2005.  URL: http://www.cs.toronto.edu/~ahertel/WebPageFiles/Papers/StrengtheningBarnette’sConjecture10.pdf.
  * [HMM85] Derek A Holton, Bennet Manvel, and Brendan D McKay.  Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs.  Journal of Combinatorial Theory, Series B, 38:279–297, 1985.
  * [HP91] Derek A Holton and Micheal D Plummer.  Matching Extension and Connectivity in Graphs II.  Graph Theory, Combinatorics, and Applications, 2:651–665, 1991.
  * [Kar20] František Kardoš.  A Computer-Assisted Proof of the Barnette–Goodey Conjecture: Not Only Fullerene Graphs Are Hamiltonian.  SIAM Journal on Discrete Mathematics, 34(1):62–100, 2020.
  * [Kas67] Pieter Kasteleyn.  Graph Theory and Crystal Physics.  Graph Theory and Theoretical Physics, pages 43–110, 1967.
  * [Kel86] Alexander K Kelmans.  Konstruktsii Kubicheskih Dvudolnyh 3-Svyaznyh Bez Gamiltonovyh Tsiklov.  Sb. Tr. VNII Sistem. Issled, 10:64–72, 1986.
  * [Kel88] Alexander K Kelmans.  Cubic Bipartite Cyclic 4-Connected Graphs without Hamiltonian Circuits.  Russian Mathematical Surveys, 43(3):205, 1988.
  * [Kir56] Thomas Kirkman.  On the Representation of Polyhedra.  Philosophical Transactions of the Royal Society, 146:413–418, 1856\.
  * [Kön16] Dénes König.  Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.  Mathematische Annalen, 77(4):453–465, 1916.
  * [Lit75] Charles HC Little.  A Characterization of Convertible (0, 1)-Matrices.  Journal of Combinatorial Theory, Series B, 18(3):187–208, 1975\.
  * [LL98] Jamel Lakhal and Luc Litzler.  A Polynomial Algorithm for the Extendability Problem in Bipartite Graphs.  Information processing letters, 65(1):11–16, 1998.
  * [LL09] Yunting Lu and Xin Lu.  An Efficient Algorithm for Cyclic Edge Connectivity of Planar Graphs.  In 2009 Asia-Pacific Conference on Information Processing, volume 2, pages 193–195. IEEE, 2009.
  * [Lov87] László Lovász.  Matching Structure and the Matching Lattice.  Journal of Combinatorial Theory, Series B, 43(2):187–222, 1987\.
  * [LP09] László Lovász and Michael D. Plummer.  Matching Theory, volume 367.  American Mathematical Soc., 2009.
  * [McC00] William McCuaig.  Even Dicycles.  Journal of Graph Theory, 35(1):46–68, 2000.
  * [McC04] William McCuaig.  Pólya’s Permanent Problem.  Electronic Journal of Combinatorics, pages R79–R79, 2004.
  * [Plu80] Michael D. Plummer.  On $n$-Extendable Graphs.  Discrete Mathematics, 31(2):201–210, 1980.
  * [Plu86] Michael D. Plummer.  Matching Extension in Bipartite Graphs.  Congr. Numer, 54:245–258, 1986.
  * [RST99] Neil Robertson, Paul D Seymour, and Robin Thomas.  Permanents, Pfaffian Orientations, and Even Directed Circuits.  Annals of Mathematics, pages 929–975, 1999.
  * [Tai84] Peter G Tait.  Listing’s Topologie.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 17(103):30–46, 1884.
  * [Tut46] William T Tutte.  On Hamiltonian Circuits.  Journal of the London Mathematical Society, 1(2):98–101, 1946.
  * [Tut71] William T Tutte.  On the 2-Factors of Bicubic Graphs.  Discrete Mathematics, 1(2):203–208, 1971.
  * [VY89] Vijay V Vazirani and Milhalis Yannakakis.  Pfaffian Orientations, 0–1 Permanents, and Even Cycles in Directed Graphs.  Discrete Applied Mathematics, 25(1-2):179–190, 1989.
  * [ZZ06] Fuji Zhang and Heping Zhang.  Construction for Bicritical Graphs and k-Extendable Bipartite Graphs.  Discrete Mathematics, 306(13):1415–1423, 2006.