# Polyhedra without cubic vertices are prism-hamiltonian

Simon Špacapan111 University of Maribor, FME, Smetanova 17, 2000 Maribor,
Slovenia. e-mail: simon.spacapan @um.si.

###### Abstract

The prism over a graph $G$ is the Cartesian product of $G$ with the complete
graph on two vertices. A graph $G$ is prism-hamiltonian if the prism over $G$
is hamiltonian. We prove that every polyhedral graph (i.e. 3-connected planar
graph) of minimum degree at least four is prism-hamiltonian.

Key words: Hamiltonian cycle, circuit graph

AMS subject classification (2010): 05C10, 05C45

##  1 Introduction

The study of hamiltonicity of planar graphs is largely concerned with finding
subclasses of 3-connected planar graphs for which each member of the subclass
is hamiltonian or has some hamiltonian-type property. One such result was
obtained in 1956 by Tutte who proved that all $4$-connected planar graphs are
hamiltonian [21]. Although not every 3-connected planar graph is hamiltonian
it is possible to prove that this class of graphs satisfies (hamiltonian-type)
properties weaker than hamiltonicity. A 2-walk in a graph is a closed spanning
walk that visits every vertex at most twice. Clearly, every hamiltonian graph
has a 2-walk. In [8] Gao and Richter proved that every $3$-connected planar
graph has a 2-walk.

There is an extensive list of non-hamiltonian 3-connected planar graphs with
special properties, such as graphs with small order and size [2], plane
triangulations [15], regular graphs [20, 22], $K_{2,6}$-minor-free graphs [6],
and graphs with few 3-cuts [4]. However some classes of graphs mentioned above
are prism-hamiltonian. For example every plane triangulation is prism-
hamiltonian [3], and every cubic 3-connected graph is prism-hamiltonian
[5],[16]. It is well known that every prism-hamiltonian graph has a 2-walk, so
the result obtained in [3] strengthens the result of Gao and Richter mentioned
above.

Rosenfeld and Barnette [17] conjectured that every 3-connected planar graph is
prism-hamiltonian (see also [11]). This conjecture was recently refuted in
[18] where vertex degrees play a central role in construction of
counterexamples. In particular every counterexample to Rosenfeld-Barnette
conjecture given in [18] has many cubic vertices and two vertices of “high”
degree (linear in order of the graph). In [9] the authors show that there is
an infinite family of 3-connected planar graphs, each of them not prism-
hamiltonian, such that the ratio of cubic vertices tends to 1 when the order
goes to infinity, and maximum degree stays bounded by 36.

Vertex degrees in relation to hamiltonicity properties are discussed already
by Ore in [13] and later by Jackson and Wormald in [10]. Let $\sigma_{k}(G)$
be the minimum sum of vertex degrees of an independent set of $k$ vertices.
Ore showed that $\sigma_{2}(G)\geq n$ implies that $G$ is hamiltonian, and
Jackson and Wormald showed that $\sigma_{3}(G)\geq n$ implies that $G$ has a
2-walk (provided that $G$ is connected). This was strenghtened by Ozeki in
[14] who showed that $\sigma_{3}(G)\geq n$ implies that $G$ is prism-
hamiltonian.

In this paper we prove that every 3-connected planar graph of minimum degree
at least four is prism-hamiltonian. Equivalently, every 3-connected planar
graph which is not prism-hamiltonian must have at least one cubic vertex. In
particular this implies that every regular 3-connected planar graph is prism-
hamiltonian. The class of 3-connected planar graphs of minimum degree at least
four is neither hamiltonian nor traceable (even when restricted to plane
triangulations, or to regular graphs), see [15] and [22]. In this sense prism-
hamiltonicity appears to be the strongest hamiltonian-type property this class
has.

The proof we give in this article builds on results obtained in [8], where a
method of decomposing graphs into plain chains is developed. In [8] the
authors work with circuit graphs (which where originally defined in [1]). A
plane graph is a circuit graph if it is obtained from a 3-connected plane
graph $G$ by deleting all vertices that lie in the exterior of a cycle of $G$.
A cactus is a connected graph $G$ such that every block of $G$ is either a
$K_{2}$ or a cycle, and such that every vertex of $G$ is contained in at most
two blocks of $G$ (the last condition is usually omitted, however for us it
will be crucial, so we include it in the definition). The main result of [8]
is that any circuit graph (and hence also any 3-connected plane graph) has a
spanning cactus as a subgraph. Here we improve this result by proving that any
circuit graph with no internal cubic vertex has a spanning bipartite cactus as
a subgraph. Every cactus has a 2-walk while every bipartite cactus is prism-
hamiltonian. Our result thus implies that circuit graphs with all internal
vertices of degree at least 4 are prism-hamiltonian.

We mention that 3-connected planar graphs of minimum degree at least 4 also
appear in [19] where the author proved that no graph in this class is
hypohamiltonian.

##  2 Preliminaries

We refer to [12] for terminology not defined here. Let $G=(V(G),E(G))$ be a
graph, $x\in V(G)$ and $X\subseteq V(G)$. We say that $x$ is adjacent to $X$,
if $x$ is adjacent to some vertex of $X$. If $u$ and $v$ are adjacent then
$e=uv$ denotes the edge with endvertices $u$ and $v$; the subgraph induced by
$u$ and $v$ is a path denoted by $u,v$. The union of graphs $G=(V(G),E(G))$
and $H=(V(H),E(H))$ is the graph $G\cup H=(V(G)\cup V(H),E(G)\cup E(H))$ and
the intersection of $G$ and $H$ is $G\cap H=(V(G)\cap V(H),E(G)\cap E(H))$.
The graph $G-X$ is obtained from $G$ by deleting all vertices in $X$ and edges
incident to a vertex in $X$. Similarly, for $M\subseteq E(G)$, $G-M$ is the
graph obtained from $G$ by deleting all edges in $M$. If $X=\\{x\\}$ we write
$G-x$ instead of $G-\\{x\\}$.

Let $G$ be a plane graph. Vertices and edges incident to the unbounded face of
$G$ are called external vertices and external edges, respectively. If a vertex
(or an edge) is not an external vertex (or edge), then it is called an
internal vertex (or an internal edge). A path $P$ is an external resp.
internal path of $G$ if all edges of $P$ are external resp. internal edges.

We use $[n]$ to denote the set of positive integers less or equal $n$. A path
of odd/even length is called an odd/even path, respectively. Similarly we
define odd and even faces, based on the parity of their degree.

Recall that every vertex of a cactus $G$ is contained in at most two blocks of
$G$. A vertex of a catus $G$ is good if it is contained in exactly one block
of $G$.

A prism over a graph $G$ is the Cartesian product of $G$ and the complete
graph on two vertices $K_{2}$. The following proposition is given in [7]
(Theorem 2.3.). For the sake of completness we include the proof of it also
here.

###### Proposition 2.1

Every bipartite cactus is prism-hamiltonian.

Proof. We denote $V(K_{2})=\\{a,b\\}$. We use induction to prove the following
stronger statement. Every prism $G\Box K_{2}$ over a bipartite cactus $G$ has
a Hamilton cycle $C$ such that for every good vertex $x$ of $G$, we have
$(x,a)(x,b)\in E(C)$. This is clearly true when $G$ is an even cycle or
$K_{2}$.

Let $G$ be a bipartite cactus and assume that the statement is true for all
bipartite cactuses with fewer vertices than $|V(G)|$. If all vertices of $G$
are good, then $G$ is an even cycle or $K_{2}$. Otherwise, there is a vertex
$u$, which is not a good vertex of $G$. Hence, $u$ is contained in exactly two
blocks of $G$.

Let $G_{1}^{\prime}$ and $G_{2}^{\prime}$ be connected components of $G-x$,
and let $G_{1}=G-G_{2}^{\prime}$ and $G_{2}=G-G_{1}^{\prime}$. Both, $G_{1}$
and $G_{2}$, are bipartite cactuses. Moreover, $x$ is a good vertex in
$G_{i}$, for $i=1,2$. By induction hypothesis there is a Hamilton cycle
$C_{i}$ in $G_{i}$ such that $C_{i}$ uses the edge $e=(x,a)(x,b)$ in $G_{i}$.
The desired Hamilton cycle in $G$ is $(C_{1}\cup C_{2})-e$. Observe that every
good vertex of $G$ is a good vertex of $G_{1}$ or $G_{2}$. It follows that for
every good vertex $x$ of $G$, we have $(x,a)(x,b)\in E(C)$. $\square$

###### Corollary 2.2

Every graph $G$, that has a bipartite cactus $H$ as a spanning subgraph, is
prism-hamiltonian.

If $G$ is plane graph and $H$ is a subgraph of $G$, then $H$ is also a plane
graph and we assume that the embedding of $H$ in the plane is the one given by
$G$.

Let $G$ be a plane graph and $G^{+}$ the graph obtained from $G$ by adding a
vertex to $G$ and making it adjacent to all external vertices of $G$. The
graph $G$ is a circuit graph if $G^{+}$ is 3-connected.

It follows from the definition that any circuit graph is 2-connected, and
hence every face of a circuit graph is bounded by a cycle. If $G$ is a
3-connected plane graph (or if $G$ is a circuit graph) and $C$ is a cycle of
$G$, then the subgraph of $G$ bounded by $C$ is a circuit graph. Observe also
that for any circuit graph $G$ with outer cycle $C$, and any separating set
$S$ of size 2 in $G$, every connected component of $G-S$ intersects $C$.

A graph $G$ is a chain of blocks if the block-cutvertex graph of $G$ is a
path. We denote the blocks and cutvertices of $G$, by

$B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,,$

where $B_{i}$ are blocks for $i\in[n]$, and $b_{i}\in V(B_{i})\cap V(B_{i+1})$
are cutvertices of $G$ for $i\in[n-1]$. A plane graph $G$ is a plane chain of
blocks if it is a chain of blocks

$G=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}$

such that every external vertex of $B_{i},i\in[n]$ is also an external vertex
of $G$. The following lemma is given in [8] (Lemma 3, p. 261).

###### Lemma 2.3

Let $G$ be a circuit graph with outer cycle $C$ and let $x\in V(C)$. Let
$x^{\prime}$ and $x^{\prime\prime}$ be the neighbors of $x$ in $C$. Then

  * (i)

$G-x$ is a plane chain of blocks $B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}$ and
each nontrivial block of $G-x$ is a circuit graph.

  * (ii)

Setting $x^{\prime}=b_{0}$ and $x^{\prime\prime}=b_{n}$, then $B_{i}\cap C$ is
a path in $C$ with endvertices $b_{i-1}$ and $b_{i}$, for every $i\in[n]$.

It follows from the above lemma that for every nontrivial block $B_{i}$ of
$G-x$, with outer cycle $C_{i}$, $C_{i}$ is the union of two
$b_{i-1}b_{i}$-paths $P_{i}$ and $P_{i}^{\prime}$, where $P_{i}$ is an
internal path in $G$ and $P_{i}^{\prime}$ is an external path in $G$.

##  3 The proof of main result

In this section we prove that any circuit graph $G$ such that every internal
vertex of $G$ is of degree at least 4 is prism-hamiltonian.

###### Definition 3.1

Let $G$ be a circuit graph with outer cycle $C$ and let $x,y\in V(C)$. We say
that $G$ is bad with respect to $x$ and $y$ if

  * (i)

$G$ has exactly one bounded odd face $F$

  * (ii)

$x$ and $y$ are incident to $F$

  * (iii)

If $x$ and $y$ are adjacent, then $e=xy$ is an internal edge of $G$.

We say that $G$ is good with respect to $x$ and $y$ if it’s not bad with
respect to $x$ and $y$.

If $G$ is a circuit graph and $G$ is bad with respect to $x$ and $y$, then
there is no hamiltonian cycle $C$ in $G\Box K_{2}$ such that $C$ uses vertical
edges at $x$ and $y$ (edges between the two layers of $G$). For example, an
odd cycle is bad with respect to any two non-adjacent vertices, and hence the
prism over an odd cycle has no hamiltonian cycle that uses vertical edges at
two non-adjacent vertices of this cycle. Conversely, it turns out (and is a
consequence of Theorem 3.19) that for any circuit graph $G$ with all internal
vertices of degree at least 4, and any external vertices $x$ and $y$ of $G$
such that $G$ is good with respect to $x$ and $y$, there is a hamiltonian
cycle in $G\Box K_{2}$ that uses vertical edges at $x$ and $y$.

Note also that a bipartite circuit graph $B$ is good with respect to any two
external vertices of $B$ (this fact we shall use frequently). In order to
simplify the formulation of statements, we also say that complete graphs
$K_{1}$ and $K_{2}$ are good with respect to any of its vertices.

###### Definition 3.2

Let $G=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}$ be a plain chain of blocks such
that each nontrivial block $B_{i}$ is a circuit graph. Let $b_{0}\neq b_{1}$
be an external vertex of $B_{1}$, and $b_{n}\neq b_{n-1}$ be an external
vertex of $B_{n}$. We say that $G$ is a good chain with respect to $b_{0}$ and
$b_{n}$ if $B_{i}$ is good with respect to $b_{i-1}$ and $b_{i}$ for every
$i\in[n]$.

The same definition is used when only one of the two vertices $b_{0}$ and
$b_{n}$ is given, and in this case we say that $G$ is a good chain with
respect to $b_{0}$ or with respect to $b_{n}$. If $G=B_{1}$ has only one block
we say that $G$ is a good chain with respect to any external vertex of $G$.

###### Lemma 3.3

Let $B$ be a bipartite circuit graph with outer cycle $C$ such that all
internal vertices of $B$ are of degree at least 4. Then $B$ has at least 4
external vertices of degree 2.

Proof. Let $C$ be a $k$-cycle, $k\geq 4$. Let ${\mathcal{F}}$ be the set of
faces of $B$, and set $e=|E(B)|,v=|V(B)|$ and $f=|{\mathcal{F}}|$. Since $B$
is bipartite

$2e=\sum_{F\in{\mathcal{F}}}\deg(F)\geq 4(f-1)+k\,.$

We use the Euler’s formula to obtain

$\sum_{x\in V(B)}\deg(x)=2e\leq 4v-k-4\,.$

Since every internal vertex of $B$ is of degree at least 4 we get

$\sum_{x\in V(C)}\deg(x)\leq 3k-4\,.$

Since all vertices of $C$ are of degree at least 2, the claim of the lemma
follows from the pigeonhole principle. $\square$

The following lemma is a well known fact.

###### Lemma 3.4

A plane graph $G$ is bipartite if and only if all bounded faces of $G$ are
even.

###### Lemma 3.5

Let $B$ be a circuit graph with outer cycle $C$ such that all internal
vertices of $B$ are of degree at least 4. Let $x$ and $y$ be any vertices of
$C$, and $Q$ a $xy$-path in $C$. Suppose that all vertices in $V(C)\setminus
V(Q)$ are of degree at least three in $B$. Then $B$ is good with respect to
$x$ and $y$.

Proof. Suppose to the contrary, that $B$ is bad with respect to $x$ and $y$.
Then $x$ and $y$ are incident to odd face $F$ of $B$, and $F$ is the only
bounded odd face of $B$. Moreover, $x$ and $y$ are not adjacent in $C$. It
follows that $B-\\{x,y\\}$ has exactly two components.

Let $H$ be the component of $B-\\{x,y\\}$ that contains a vertex of $Q$. If
$xy\in E(B)$ and $F$ is contained in the exterior of the cycle
$E(Q)\cup\\{xy\\}$ define $H^{\prime}=(B-V(H))-xy$. Otherwise define
$H^{\prime}=B-V(H)$. $H^{\prime}$ is a plain chain of blocks and each
nontrivial block of $H^{\prime}$ is a bipartite circuit graph (by Lemma 3.4),
so assume

$H^{\prime}=D_{1},d_{1},D_{2},\ldots,d_{m-1},D_{m}\,.$

Let $d_{0}=x$ and $d_{m}=y$. If $j\in[m]$ and $u\in
V(D_{j})\setminus\\{d_{j-1},d_{j}\\}$, then $\deg_{D_{j}}(u)>2$. So if $D_{j}$
is nontrivial, then it has at most two vertices of degree 2 in $D_{j}$; since
$D_{j}$ is bipartite this contradicts Lemma 3.3. It follows that all blocks of
$H^{\prime}$ are trivial. If $H^{\prime}$ is $K_{2}$ then $x$ and $y$ are
adjacent in $C$ (a contradiction), otherwise a vertex in $V(C)\setminus V(Q)$
is of degree $\leq 2$ (this contradicts the assumption of the lemma).
$\square$

###### Lemma 3.6

Let $B$ be a circuit graph with outer cycle $C$ such that all internal
vertices of $B$ are of degree at least 4. Let $x\in V(C)$ be any vertex and

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Let $b_{0}\in V(B_{1})$ and $b_{n}\in V(B_{n})$ be the neighbors of $x$ in
$C$. Then for every $i\in[n]$, $B_{i}$ is good with respect to $b_{i-1}$ and
$b_{i}$.

Proof. Let $B_{i}$ be a nontrivial block with outer cycle $C_{i}$, and define
$Q=C\cap B_{i}$. $Q$ is a path in $C_{i}$ with endvertices $b_{i-1}$ and
$b_{i}$, and every vertex in $V(C_{i})\setminus V(Q)$ is of degree more than 2
in $B_{i}$. By Lemma 3.5, $B_{i}$ is good with respect to $b_{i-1}$ and
$b_{i}$. $\square$

###### Lemma 3.7

Let $B$ be a circuit graph with outer cycle $C$ such that all internal
vertices of $B$ are of degree at least 4. Let $x$ and $y$ be any vertices of
$C$ and $Q$ a $xy$-path in $C$ such that all vertices in $V(C)\setminus V(Q)$
are of degree at least three in $B$. If $B-x$ is bipartite, then $|V(B_{i}\cap
Q)|\geq 2$ for every block $B_{i}$ of $B-x$.

Proof. If $V(C)=V(Q)$, the lemma follows from Lemma 2.3. Assume $V(C)\neq
V(Q)$, and let $u\in V(C)\setminus V(Q)$ be the neighbor of $x$. The block
$B_{1}$ of $B-x$ containing $u$ is nontrivial, for otherwise $\deg_{B}(u)=2$.
If $|V(B_{1}\cap Q)|<2$, then $B_{1}$ has at most two vertices of degree two
in $B_{1}$. Therefore, by Lemma 3.3, $B_{1}$ is non-bipartite and hence $B-x$
is non-bipartite. $\square$

###### Lemma 3.8

Let $B$ be a circuit graph with outer cycle $C$ such that all internal
vertices of $B$ are of degree at least 4. Let $x\in V(C)$ be any vertex, and
let

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Then for every $k\in[n-1]$ the graph

$G=B-\bigcup_{i=k+1}^{n}V(B_{i})$

is a good chain with respect to $x$.

Proof. Let $b_{0}\in V(B_{1})$ be the neighbor of $x$ in $C$. Denote the path
$x,b_{0}$ by $B_{0}$.

Case 1: Suppose that $B_{k}$ is trivial.
If $x$ is not adjacent to a vertex in $G-b_{0}$, then $G$ induces a plain
chain of blocks

$B_{0},b_{0},B_{1},\ldots,b_{k-2},B_{k-1}\,$

and, by Lemma 3.6, $B_{i}$ is good with respect to $b_{i-1}$ and $b_{i}$ for
$i\in[k-1]$. Assume therefore that $x$ is adjacent to a vertex in $G-b_{0}$.
Let $\ell\in[k]$ be the maximum number such that $x$ is adjacent to
$B_{\ell}-\\{b_{\ell-1},b_{k}\\}$. Since $B_{k}$ is trivial, $\ell\neq k$. The
graph $H$ induced by $\bigcup_{i=0}^{\ell}V(B_{i})$ is a nontrivial block of
$G$. Moreover, since $H$ is a subgraph of $B$ bounded by a cycle of $B$, $H$
is a circuit graph. Note also that if $x$ and $b_{\ell}$ are incident to a
bounded face $F$ of $H$, then $x$ and $b_{\ell}$ are adjacent, moreover
$xb_{\ell}$ is an external edge of $H$. It follows that $H$ is good with
respect to $x$ and $b_{\ell}$, and therefore

$G=H,b_{\ell},B_{\ell+1},\ldots,b_{k-2},B_{k-1}$

is a good chain with respect to $x$.

Case 2: Suppose that $B_{k}$ is nontrivial.
By Lemma 2.3, $B_{k}-b_{k}$ is a plain chain of blocks, so let

$B_{k}-b_{k}=D_{1},d_{1},D_{2},\ldots,d_{m-1},D_{m}\,.$

Let $C_{k}$ be the outer cycle of $B_{k}$, and $d_{0}\in V(D_{1}),d_{m}\in
V(D_{m})$ be the neighbors of $b_{k}$ in $C_{k}$. Without loss of generality
assume that $b_{k}d_{0}$ is an internal edge of $B$. Note that $D_{1}$ is
nontrivial if $b_{k-1}\neq d_{0}$, for otherwise $\deg_{B}(d_{0})\leq 3$ (this
is a contradiction because $d_{0}$ is an internal vertex of $B$ if
$b_{k-1}\neq d_{0}$).

Suppose that $x$ is adjacent to $D_{1}-\\{b_{k-1},d_{1}\\}$ (it is possible
that $b_{k-1}=d_{1}$). Then $D_{1}$ is nontrivial. Let $j\in[m]$ be such that
$b_{k-1}\in V(D_{j})\setminus\\{d_{j-1}\\}$ and let $H^{\prime}$ be the graph
induced by

$\bigcup_{i=0}^{k-1}V(B_{i})\cup\bigcup_{i=1}^{j}V(D_{i})\,.$

$H^{\prime}$ is bounded by a cylce of $B$, so it is a circuit graph. We shall
prove that $H^{\prime}$ is good with respect to $x$ and $d_{j}$. Suppose that
$x$ and $d_{j}$ are incident to a face $F^{\prime}$ of $H^{\prime}$, and that
$F^{\prime}$ is the only bounded odd face of $H^{\prime}$. Then
$d_{j}=b_{k-1}$, and all bounded faces of $D_{1}$ are even. This contradicts
Lemma 3.3, because $\deg_{D_{1}}(u)>2$ for every $u\in
V(D_{1})\setminus\\{d_{0},d_{1}\\}$. It follows that

$G=H^{\prime},d_{j},D_{j+1},\ldots,d_{m-1},D_{m}\,$

is a good chain with respect to $x$.

Suppose that $x$ is not adjacent to $D_{1}-\\{b_{k-1},d_{1}\\}$. We claim that
$|V(D_{1})\cap V(C)|\geq 2$. To prove the claim suppose the contrary, that
$|V(D_{1})\cap V(C)|<2$. Then $\\{b_{k},d_{1}\\}$ is a separating set in $B$,
and $D_{1}-\\{b_{k},d_{1}\\}$ is a component of $B-\\{b_{k},d_{1}\\}$ disjoint
with $C$. It follows that $B$ is not a circuit graph, a contradiction. This
proves the claim.

Define $\ell$ and $H$ as in Case 1. We claim that

$G=H,b_{\ell},B_{\ell+1},\ldots,B_{k-1},b_{k-1},D_{1},d_{1},\ldots,d_{m-1},D_{m}$

is a good chain with respect to $x$. We have already shown (in Case 1) that
$H$ is good with respect to $x$ and $b_{\ell}$. By Lemma 3.6, $B_{i}$ is good
with respect to $b_{i-1}$ and $b_{i}$ for $i\in[k-1]\setminus[\ell]$, and
$D_{i}$ is good with respect to $d_{i-1}$ and $d_{i}$ for $i\in[m],i\neq 1$.
It remains to prove that $D_{1}$ is good with respect to $b_{k-1}$ and
$d_{1}$. Let $C^{\prime}$ be the outer cycle of $D_{1}$ and let $Q=C\cap
D_{1}$ (or equivalently $Q=C\cap C^{\prime}$). Note that for every vertex
$z\in V(C^{\prime})\setminus V(Q)$, $\deg_{D_{1}}(z)>2$. By Lemma 3.5, $D_{1}$
is good with respect to $b_{k-1}$ and $d_{1}$. $\square$

###### Definition 3.9

Let $B$ be a circuit graph with outer cycle $C$. Let $\\{x,y\\}\subseteq V(C)$
and $\\{u_{1},u_{2}\\}\subseteq V(C)$ be any sets. A set of pairwise disjoint
chains ${\mathcal{C}}=\\{G_{1},\ldots,G_{k}\\}$ is a $(x,y;u_{1},u_{2})$-set
of chains in $B$ if there exists a $xy$-path $P$ in $B$ such that

  * (i)

$V(B)\setminus V(P)\subseteq\bigcup_{i=1}^{k}V(G_{i})$

  * (ii)

For $i\in[k]$, $G_{i}$ intersects $P$ in exactly one vertex $x_{i}$, and
$G_{i}$ is a good chain with respect to $x_{i}$.

  * (iii)

For $j\in[2]$, either $G_{i}$ is a good chain with respect to $u_{j}$ and
$x_{i}$ for some $i\in[k]$, or $u_{j}\notin\bigcup_{i=1}^{k}V(G_{i})$.

A path $P$ that fulfills (i),(ii) and (iii) is called a ${\mathcal{C}}$-path.
The set ${\mathcal{C}}$ is an odd or an even $(x,y;u_{1},u_{2})$-set of chains
if there exits an odd or an even ${\mathcal{C}}$-path, respectively.

We say that a set of pairwise disjoint chains $G_{1},\ldots,G_{k}$ is a
$(x,y;u_{1})$-set of chains if it satisfies (i),(ii) and (iii) for $j=1$.
Moreover, ${\mathcal{C}}$ is a $(x,y)$-set of chains if it satisfies (i) and
(ii) of Definition 3.9.

We also use Definition 3.9 in slightly more general settings in which $B$ is a
plain chain of blocks (and each block is a circuit graph). More precisely, if
$B$ is a plain chain of blocks, $x,y$ are two external vertices of $B$, and
${\mathcal{C}}$ is a set of pairwise disjoint plain chains that satisfy
(i),(ii) and (iii), then ${\mathcal{C}}$ is a $(x,y;u_{1},u_{2})$-set of
chains in $B$.

###### Lemma 3.10

Let $G$ be a bipartite plain chain of blocks

$G=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}$

such that for $i\in[n]$ each nontrivial block $B_{i}$ of $G$ is a circuit
graph with outer cycle $C_{i}$. Suppose that $u,x,y\in V(C_{j}),u\neq b_{j}$,
and that ${\mathcal{C}}$ is a $(x,y;u,b_{j})$-set of chains in $B_{j}$ for
some $j\in[n]$. Then for every $\ell>j$ and any vertex $v\in
V(C_{\ell})\setminus V(C_{\ell-1})$, there is a $(x,y;u,v)$-set of chains in
$\bigcup_{i=j}^{\ell}B_{i}$. Moreover, if $u=b_{j-1}$, then for every
$\ell^{\prime}<j$ and any vertex $v^{\prime}\in V(C_{\ell^{\prime}})\setminus
V(C_{\ell^{\prime}+1})$, there is a $(x,y;v^{\prime},v)$-set of chains in
$\bigcup_{i=\ell^{\prime}}^{\ell}B_{i}$.

Proof. Let $\ell>j$ and $v\in V(C_{\ell})\setminus V(C_{\ell-1})$. Suppose
that ${\mathcal{C}}=\\{G_{1},\ldots,G_{k}\\}$ is a $(x,y;u,b_{j})$-set of
chains in $B_{j}$ and that $P$ is a ${\mathcal{C}}$-path. Then (a) or (b)
occures.

  * (a)

There is a chain $G_{r}\in{\mathcal{C}}$ such that $G_{r}$ is a good chain
with respect to $x_{r}$ and $b_{j}$, where $\\{x_{r}\\}=V(G_{r})\cap V(P)$

  * (b)

$b_{j}\notin\bigcup_{i=1}^{k}V(G_{i})$.

In case (a), $G_{r}^{\prime}=G_{r}\cup\bigcup_{i=j+1}^{\ell}B_{i}$ is a good
chain with respect to $x_{r}$ and $v$, and therefore
${\mathcal{C}^{\prime}}={\mathcal{C}}\cup\\{G_{r}^{\prime}\\}\setminus\\{G_{r}\\}$
is a $(x,y;u,v)$-set of chains in $\bigcup_{i=j}^{\ell}B_{i}$. In case (b),
$G_{0}=\bigcup_{i=j+1}^{\ell}B_{i}$ is a good chain with respect to $b_{j}$
and $v$, and therefore ${\mathcal{C}^{\prime}}=\\{G_{0},\ldots,G_{k}\\}$ is a
$(x,y;u,v)$-set of chains in $\bigcup_{i=j}^{\ell}B_{i}$. In both cases a
${\mathcal{C}^{\prime}}$-path is $P$. The last sentence of the lemma is proved
analogously. $\square$

If we use the notation of the above lemma, we note that a $(x,y;b_{j})$-set of
chains in $B_{j}$ can be extended to a $(x,y)$-set of chains in
$\bigcup_{i=j}^{\ell}B_{i}$ (in fact the construction given in the above proof
works also in this case). Note also that a $(x,y;u,v)$-set of chains in
$\bigcup_{i=j}^{\ell}B_{i}$ exists also under the assumption that $B_{i}$ is
bipartite for $i>j$ (and $G$ may be non-bipartite). In [8] the following
result was proved (Theorem 5, p.262).

###### Theorem 3.11

Let $B$ be a bipartite circuit graph with outer cycle $C$. If $x,y\in V(C)$,
then for any vertex $u\in V(C)$ (not necessarily distinct from $x$ and $y$)
there exists a $(x,y;u)$-set of chains in $B$.

###### Lemma 3.12

Let $B$ be a bipartite circuit graph with outer cycle $C$. Suppose that
$x,y\in V(C)$ and that $Q$ is a $xy$-path in $C$. If every internal vertex of
$B$ is of degree at least 4 and every vertex in $V(C)\setminus V(Q)$ is of
degree at least 3 in $B$, then there exists a $(x,y;x,y)$-set of chains in
$B$.

Proof. By Lemma 2.3, $B-x$ is a plain chain of blocks

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

By Lemma 3.7, $|V(B_{i}\cap Q)|\geq 2$ for $i\in[n]$. We may assume, without
loss of generality, that $y\in V(B_{1})$ and $y\neq b_{1}$. If $B_{1}$ is
nontrivial then $B_{1}-y$ is a plain chain of blocks

$B_{1}-y=D_{1},d_{1},D_{2},\ldots,d_{m-1},D_{m}\,.$

Let $d_{0}\in V(D_{1})$ be the neighbor of $y$ in $Q$, and define
$k=\max\\{i\,|\,D_{i}\cap Q\neq\emptyset\\}$.

Case 1: Suppose that $D_{k}$ intersects $Q$ in exactly one vertex (in this
case $d_{k-1}$). Then $G=\bigcup_{i=k}^{m}D_{i}$ is a good chain with respect
to $d_{k-1}$.

If $D_{i}$ is trivial define $P_{i}=D_{i}$ and ${\mathcal{C}_{i}}=\emptyset$,
for $i\in[k-1]$. If $D_{i}$ is nontrivial then, by Theorem 3.11, there is a
$(d_{i-1},d_{i};d_{i})$-set of chains ${\mathcal{C}_{i}}$ in $D_{i}$, for
$i\in[k-1]$. In this case let $P_{i}$ be a ${\mathcal{C}_{i}}$-path in
$D_{i}$.

If $B_{i}$ is trivial define $R_{i}=B_{i}$ and ${\mathcal{F}_{i}}=\emptyset$,
for $i\in[n],i\neq 1$. If $B_{i}$ is nontrivial then, by Theorem 3.11, there
is a $(b_{i-1},b_{i};b_{i-1})$-set of chains ${\mathcal{F}_{i}}$ in $B_{i}$,
for $i\in[n],i\neq 1$. In this case let $R_{i}$ be a ${\mathcal{F}_{i}}$-path
in $B_{i}$. Let $b_{n}$ be the neighbor of $x$ in $Q$, and let $R_{n+1}$ be
the path $x,b_{n}$. Additionally let $P_{0}$ be the path $y,d_{0}$. Define

$P=\bigcup_{i=0}^{k-1}P_{i}\cup\bigcup_{i=2}^{n+1}R_{i}\,.$

The chain $G$ together with chains ${\mathcal{C}_{i}},i\in[k-1]$ and
${\mathcal{F}_{i}},i\in[n],i\neq 1$ is a $(x,y;x,y)$-set of chains in $B$. If
we call this set of chains ${\mathcal{C}}$, then $P$ is a
${\mathcal{C}}$-path.

Case 2: Suppose that $D_{k}$ intersects $Q$ in more than one vertex. Then, by
Theorem 3.11, there is a $(d_{k-1},b_{1};d_{k})$-set of chains ${\mathcal{H}}$
in $D_{k}$. By Lemma 3.10 (see also the note directly after Lemma 3.10) there
is a $(d_{k-1},b_{1})$-set of chains in $\bigcup_{i=k}^{m}D_{i}$. The rest of
the proof is similar as in Case 1.

If $B_{1}$ is trivial, then $x$ and $y$ are adjacent in $C$ (for otherwise
$\deg_{B}(u)=2$, where $u$ is the neighbor of $x$ in $V(C)\setminus V(Q)$) and
$V(Q)=V(C)$. Define $R_{1}=B_{1}$. In this case
$\bigcup_{i=2}^{n}{\mathcal{F}_{i}}$ is a $(x,y;x,y)$-set of chains in $B$.
The corresponding path is $\bigcup_{i=1}^{n+1}R_{i}.$ $\square$

###### Lemma 3.13

Let $B$ be a bipartite circuit graph with outer cycle $C$. Let
$x,y,u_{1},u_{2}\in V(C)$ be such that $\\{x,y\\}\neq\\{u_{1},u_{2}\\}$. If
every internal vertex of $B$ is of degree at least 4, then there is a
$(x,y;u_{1},u_{2})$-set of chains in $B$.

Proof. Suppose that the claim of the lemma is not true; let $B$ be a
counterexample with minimum number of vertices. It’s easy to verfy the lemma
when $B$ is a 4-cycle, or any even cycle.

By Lemma 2.3, $B-x$ is a plain chain of blocks

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Let $Q$ and $Q^{\prime}$ be the $xy$-paths in $C$. Let $b_{0}\in V(B_{1})$ and
$b_{n}\in V(B_{n})$ be the neighbors of $x$ in $Q$ and $Q^{\prime}$,
respectively. We set $B_{0}=\emptyset$ (to avoid ambiguity in the following
definitions). Let $k\in[n]$ be such that $y\in V(B_{k})\setminus V(B_{k-1})$,
and let $k_{j}\in[n]$ be such that $u_{j}\in V(B_{k_{j}})\setminus
V(B_{k_{j}-1})$ for $j=1,2$ (if $x\in\\{u_{1},u_{2}\\}$ this applies only to
$k_{1}$ and we set $u_{2}=x$). We may assume, without loss of generality, that
$y\neq b_{0}$ (otherwise $y\neq b_{n}$ and we have a similar proof) and that
$k_{1}\leq k_{2}$.

We shall construct a $xy$-path $P$ in $B$. For $i\in[k]$, if $B_{i}$ is
trivial define ${\mathcal{C}_{i}}=\emptyset$ and $P_{i}=B_{i}$. In the sequal
we define ${\mathcal{C}_{i}}$ and $P_{i}$ for nontrivial blocks $B_{i}$.

By minimality of $B$, Lemma 3.13 is true for every nontrivial block $B_{i}$ of
$B-x$ and therefore, for every $i\in[k]$ we can apply the statement of Lemma
3.13 to $B_{i}$.

Denote the outer cycle of $B_{i}$ by $C_{i}$. Since $Q_{i}=B_{i}\cap C$ is a
$b_{i-1}b_{i}$-path in $C_{i}$ and every vertex of $V(C_{i})\setminus
V(Q_{i})$ is of degree at least 3 in $B_{i}$, we can also apply Lemma 3.12 to
$B_{i}$. The following statements are obtained either by an application of
Lemma 3.13 or Lemma 3.12 to $B_{i}$. For $i\in[k-1]$ and $j=1,2$ there exists:

  * (i)

a $(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains in $B_{i}$ (by Lemma 3.12),

  * (ii)

a $(b_{k-1},y;b_{k-1},b_{k})$-set of chains in $B_{k}$ (by minimality of $B$
(i.e. by the statement of Lemma 3.13) if $y\neq b_{k}$, and by Lemma 3.12 if
$y=b_{k}$),

  * (iii)

a $(b_{k_{j}-1},b_{k_{j}};b_{k_{j}-1},u_{j})$-set of chains in $B_{k_{j}}$ (by
minimality of $B$ if $u_{j}\neq b_{k_{j}}$, and by Lemma 3.12 if
$u_{j}=b_{k_{j}}$),

  * (iv)

if $k_{j}=k$ and $u_{j}\neq y$, there is a $(b_{k-1},y;b_{k-1},u_{j})$-set of
chains in $B_{k}$ (by minimality of $B$),

  * (v)

if $k_{j}=k$ and $u_{j}\neq b_{k}$, there is a $(b_{k-1},y;u_{j},b_{k})$-set
of chains in $B_{k}$ (by minimality of $B$),

  * (vi)

if $k_{1}=k_{2}$, there is a $(b_{{k_{1}}-1},b_{k_{1}};u_{1},u_{2})$-set of
chains in $B_{k_{1}}$ (by minimality of $B$),

  * (vii)

if $k_{1}=k_{2}=k$, there is a $(b_{k-1},y;u_{1},u_{2})$-set of chains in
$B_{k}$ (by minimality of $B$).

Since $\\{x,y\\}\neq\\{u_{1},u_{2}\\}$ we may assume, without loss of
generality, that $y\notin\\{u_{1},u_{2}\\}$. Therefore we have the following
possibilities (1) $u_{1},u_{2}\notin V(Q^{\prime})$, (2) $u_{1}\notin
V(Q^{\prime}),u_{2}\notin V(Q)$, (3) $u_{2}=x$ and $u_{1}\notin
V(Q^{\prime})$. All other possibilites are symmetric, and they can be obtained
from one of the above cases by exchanging the roles of $Q$ and $Q^{\prime}$;
for example, $u_{1},u_{2}\notin V(Q^{\prime})$ is symmetric to
$u_{1},u_{2}\notin V(Q)$. Therefore we can also assume that $u_{1}\notin
V(Q^{\prime})$. With this assumption the following cases with regard to
$k,k_{1}$ and $k_{2}$ may appear. Next to each particular case below we also
write which of the above statements we use to prove the existence of a
$(x,y;u_{1},u_{2})$-set of chains in $B$. Later we give detailed arguments.

  * (a)

$k_{1}<k_{2}<k$, we use (i) for $i\in[k-1]\setminus\\{k_{1},k_{2}\\}$, (iii)
for $j\in[2]$, and (ii).

  * (b)

$k_{1}<k_{2}=k$, we use (i) for $i\in[k-1]\setminus\\{k_{1}\\}$, (iii) for
$j=1$, and (iv) for $j=2$.

  * (c)

$k_{1}<k<k_{2}$, we use (i) for $i\in[k-1]\setminus\\{k_{1}\\}$, (iii) for
$j=1$, and (ii).

  * (d)

$k_{1}=k_{2}<k$, we use (i) for $i\in[k-1]\setminus\\{k_{1}\\}$, (vi) for
$j=1$, and (ii).

  * (e)

$k_{1}=k_{2}=k$, we use (i) for $i\in[k-1]$, and (vii).

  * (f)

$k_{1}<k$ and $u_{2}=x$, we use (i) for $i\in[k-1]\setminus\\{k_{1}\\}$, and
(ii).

  * (g)

$k_{1}=k$ and $u_{2}=x$, we use (i) for $i\in[k-1]$, and (v) for $j=1$.

We prove cases (a), (c) and (g) in detail. Cases (b),(d) and (e) are similar
to case (a), and case (f) is similar to case (g), so here we skip details.

Case (a). Suppose that $k_{1}<k_{2}<k$. By (i), there is a
$(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains ${\mathcal{C}_{i}}$ in $B_{i}$,
for $i\in[k-1]\setminus\\{k_{1},k_{2}\\}$. By (iii), there is a
$(b_{k_{j}-1},b_{k_{j}};b_{k_{j}-1},u_{j})$-set of chains
${\mathcal{C}_{k_{j}}}$ in $B_{k_{j}}$ for $j=1,2$. By (ii), there is a
$(b_{k-1},y;b_{k-1},b_{k})$-set of chains ${\mathcal{C}_{k}}$ in $B_{k}$.
Denote by $P_{i}$ a ${\mathcal{C}_{i}}$-path in $B_{i}$, for $i\in[k]$.

By Lemma 3.8, $G_{0}=B-\bigcup_{i=1}^{k}V(B_{i})$ is a good chain with respect
to $x$. Let $P_{0}$ be the path $x,b_{0}$. Define $P=\bigcup_{i=0}^{k}P_{i}$
(and recall that $P_{i}=B_{i}$, if $B_{i}$ is trivial). Then
${\mathcal{C}}=\\{G_{0}\\}\cup\bigcup_{i=1}^{k}{\mathcal{C}_{i}}$ is a
$(x,y;u_{1},u_{2})$-set of chains in $B$.

Case (c). Suppose that $k_{1}<k<k_{2}$. By (i) there is a
$(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains ${\mathcal{C}_{i}}$ in $B_{i}$,
for $i\in[k-1]\setminus\\{k_{1}\\}$. By (iii) there is a
$(b_{k_{1}-1}b_{k_{1}};b_{k_{1}-1},u_{1})$-set of chains
${\mathcal{C}_{k_{1}}}$ in $B_{k_{1}}$. By (ii) there is a
$(b_{k-1},y;b_{k-1},b_{k})$-set of chains ${\mathcal{C}_{k}}$ in $B_{k}$.

Since ${\mathcal{C}}_{k}$ is a $(b_{k-1},y;b_{k-1},b_{k})$-set of chains in
$B_{k}$, by Lemma 3.10 there is a $(b_{k-1},y;b_{k-1},u_{2})$-set of chains
${\mathcal{D}}_{k}$ in $\bigcup_{i=k}^{k_{2}}B_{i}$.

By Lemma 3.8, $G_{1}=B-\bigcup_{i=1}^{k_{2}}V(B_{i})$ is a good chain with
respect to $x$. Then $G_{1}$ together with chains in
${\mathcal{C}_{i}},i\in[k-1]$ and ${\mathcal{D}}_{k}$ forms a
$(x,y;u_{1},u_{2})$-set of chains in $B$ (the corresponding path is
$P=\bigcup_{i=0}^{k}P_{i}$).

Case (g). By (i) there is a $(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains
${\mathcal{C}_{i}}$ in $B_{i}$, for $i\in[k-1]$. Since $u_{1}\notin
V(Q^{\prime})$, by an assumption, we have $u_{1}\neq b_{k}$. By (v), there is
a $(b_{k-1},y;u_{1},b_{k})$-set of chains ${\mathcal{C}_{k}}$ in $B_{k}$. By
Lemma 3.10 there is a $(b_{k-1},y;u_{1})$-set of chains ${\mathcal{F}}_{k}$ in
$\bigcup_{i=k}^{n}B_{i}$.

Let $P_{i}$ be a ${\mathcal{C}_{i}}$-path in $B_{i}$, for $i\in[k]$, and
define $P=\bigcup_{i=0}^{k}P_{i}$. Then chains in
${\mathcal{C}_{i}},i\in[k-1]$ and ${\mathcal{F}}_{k}$ form a
$(x,y;u_{1},x)$-set of chains in $B$, with $P$ being the corresponding path.
$\square$

###### Definition 3.14

Let $B$ be a circuit graph with outer cycle $C$, and let $u_{1},u_{2},u_{3}\in
V(C)$. A set of pairwise disjoint chains
${\mathcal{C}}=\\{G_{1},\ldots,G_{k}\\}$ is a $[u_{1},u_{2},u_{3}]$-set of
chains in $B$ if there exists an even cycle $C^{\prime}$ in $B$ such that

  * (i)

$V(B)\setminus V(C^{\prime})\subseteq\bigcup_{i=1}^{k}V(G_{i})$

  * (ii)

For $i\in[k]$, $G_{i}$ intersects $C^{\prime}$ in exactly one vertex $x_{i}$,
and $G_{i}$ is a good chain with respect to $x_{i}$.

  * (iii)

For $j\in[3]$, either $G_{i}$ is a good chain with respect to $u_{j}$ and
$x_{i}$ for some $i\in[k]$, or $u_{j}\notin\bigcup_{i=1}^{k}V(G_{i})$.

A cycle $C^{\prime}$ that fulfills (i),(ii) and (iii) is called a
${\mathcal{C}}$-cycle.

If ${\mathcal{C}}$ fulfills (i),(ii) and (iii) for $j=1,2$, then
${\mathcal{C}}$ is a $[u_{1},u_{2}]$-set of chains in $B$.

###### Lemma 3.15

Let $B$ be a bipartite circuit graph with outer cycle $C$, and let
$u_{1},u_{2},u_{3}$ be any vertices of $C$. If all internal vertices of $B$
are of degree at least 4, then there exits a $[u_{1},u_{2},u_{3}]$-set of
chains in $B$.

Proof. By Lemma 2.3, $B-u_{3}$ is a plain chain of blocks

$B-u_{3}=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Let $k_{i}\in[n]$ be such that $u_{i}\in V(B_{i})\setminus V(B_{i-1})$ (here
we set $B_{0}=\emptyset$). For $i\in[n]$, define $P_{i}=B_{i}$ and
${\mathcal{C}_{i}}=\emptyset$, if $B_{i}$ is trivial. In the sequal we define
$P_{i}$ and ${\mathcal{C}_{i}}$ for nontrivial blocks $B_{i}$.

Case 1: $k_{1}\neq k_{2}$. By Lemma 3.12 and 3.13 there is

  * (i)

a $(b_{i-1},b_{i};b_{i-1})$-set of chains ${\mathcal{C}_{i}}$ in $B_{i}$, if
$i\notin\\{k_{1},k_{2}\\}$,

  * (ii)

a $(b_{i-1},b_{i};b_{i-1},u_{j})$-set of chains ${\mathcal{C}_{i}}$ in
$B_{i}$, if $i=k_{j}$ for $j=1,2$.

Let $P_{i}$ be the corresponding ${\mathcal{C}_{i}}$-path in $B_{i}$, for
$i\in[n]$. Let $b_{0}\in V(B_{1})$ and $b_{n}\in V(B_{n})$ be the neighbors of
$x$ in $C$ and define $P_{0}=x,b_{0}$ and $P_{n+1}=b_{n},x$. Define
$C^{\prime}=\bigcup_{i=0}^{n+1}P_{i}$ and

${\mathcal{C}}=\bigcup_{i=1}^{n}{\mathcal{C}_{i}}\,.$

Then ${\mathcal{C}}$ is a $[u_{1},u_{2},u_{3}]$-set of chains, and
$C^{\prime}$ is a corresponding ${\mathcal{C}}$-cycle.

Case 2: $k_{1}=k_{2}$. By Lemma 3.12 and 3.13 there is

  * (i)

a $(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains ${\mathcal{C}_{i}}$ in
$B_{i}$, if $i\neq k_{1}$,

  * (ii)

a $(b_{k_{1}-1},b_{k_{1}};u_{1},u_{2})$-set of chains ${\mathcal{C}_{k_{1}}}$
in $B_{k_{1}}$.

The rest of the proof is the same as above. $\square$

###### Lemma 3.16

Let $B$ be a non-bipartite circuit graph with outer cycle $C$. Suppose that
$x,y\in V(C)$ and that $Q$ is a $xy$-path in $C$. If all internal vertices of
$B$ are of degree at least 4, every vertex in $V(C)\setminus V(Q)$ is of
degree at least 3 in $B$, and $B-x$ is bipartite, then for any vertex $u\in
V(C-x)$ there is an odd and an even $(x,y;u)$-set of chains in $B$.

Proof. We claim that for any neighbor $z$ of $x$, there is a $(x,y;u)$-set of
chains ${\mathcal{C}}$ in $B$ such that a ${\mathcal{C}}$-path contains the
edge $xz$. Before we prove the claim let us see how we prove the lemma using
this claim. Since $B$ is non-bipartite and 2-connected, there is an odd cycle
$C^{\prime}$ containing $x$. Let $x_{1}$ and $x_{2}$ be the neigbors of $x$ in
$C^{\prime}$. Let $R$ be the $x_{1}x_{2}$-path in $C^{\prime}$ not containing
$x$. Suppose that $R_{i}$ is a $x_{i}y$-path in $B-x$ for $i=1,2$. Since $B-x$
is bipartite, $R_{1}\cup R_{2}\cup R$ is an even closed walk, and since $R$ is
odd, $R_{1}$ and $R_{2}$ have different parities. It follows that every
$x_{1}y$-path in $B-x$ is odd, and every $x_{2}y$-path in $B-x$ is even (or
vice-versa). Using the above claim and setting $z=x_{1}$ (resp. $z=x_{2}$) we
get an even (resp. an odd) $(x,y;u)$-set of chains in $B$.

In the rest of the proof we prove the claim. Let

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}$

and suppose that $xz\in E(B)$. By Lemma 3.7, $|V(B_{i}\cap Q)|\geq 2$ for
$i\in[n]$, hence we may assume that $y\in V(B_{n})\setminus V(B_{n-1})$. Let
$k_{u},k_{z}\in[n]$ be such that $u\in V(B_{k_{u}})\setminus V(B_{k_{u}+1})$
and $z\in V(B_{k_{z}})\setminus V(B_{k_{z}+1})$ (here we set
$B_{n+1}=\emptyset$). It follows from these definitions that $u\neq b_{k_{u}}$
and $z\neq b_{k_{z}}$.

We shall construct a $(x,y;u)$-set of chains ${\mathcal{C}}$ in $B$, and a
${\mathcal{C}}$-path $P$ in $B$, so that $P$ contains the edge $xz$. We
distinguish several cases with regard to $k_{u}$ and $k_{z}$. In each case we
define $P_{i}=B_{i}$ and ${\mathcal{C}_{i}}=\emptyset$, if $B_{i}$ is trivial
and $i\in[n]$. Now we treat different cases and define $P_{i}$ and
${\mathcal{C}_{i}}$, if $B_{i}$ is nontrivial.

Suppose that $k_{z}<k_{u}<n$. By Lemma 3.12 and Lemma 3.13 there is

  * (i)

a $(z,b_{k_{z}};b_{{k_{z}}-1},b_{k_{z}})$-set of chains in $B_{k_{z}}$, where
$k_{z}\neq k_{u}$

  * (ii)

a $(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains in $B_{i}$, for
$k_{z}<i<n,i\neq k_{u}$

  * (iii)

a $(b_{n-1},y;b_{n-1})$-set of chains in $B_{n}$, where $n\neq k_{u}$

  * (iv)

a $(b_{k_{u}-1},b_{k_{u}};u)$-set of chains in $B_{k_{u}}$.

Let ${\mathcal{C}_{i}}$ be the set of chains in $B_{i}$ (as defined above),
and let $P_{i}$ be a ${\mathcal{C}_{i}}$-path for $i\in[n]\setminus[k_{z}-1]$.
By Lemma 3.8, $G_{0}=B-\bigcup_{i=k_{z}}^{n}V(B_{i})$ is a good chain with
respect to $x$ in $B$ (if $k_{z}=1$ this is irrelevant). Let $P_{0}$ be the
path $x,z$ and define $P=P_{0}\cup\bigcup_{i=k_{z}}^{n}P_{i}$. Then

${\mathcal{C}}=\\{G_{0}\\}\cup\bigcup_{i=k_{z}}^{n}{\mathcal{C}_{i}}$

is a $(x,y;u)$-set of chains in $B$ and $P$ is a ${\mathcal{C}}$-path. If
$k_{z}=k_{u}<n$ we use (ii) and (iii), and instead of (iv) we use

  * (v)

there is a $(z,b_{k_{u}};u)$-set of chains in $B_{k_{u}}$.

The rest of the proof is the same as above. If $k_{z}<k_{u}=n$ we use (i) and
(ii), and instead of (iv) we use

  * (vi)

there is a $(b_{n-1},y;u)$-set of chains in $B_{n}$

and the rest of the proof is (again) the same as above (note that (v) and (vi)
follow from Lemma 3.13).

If $k_{u}<k_{z}<n$ then we use (i),(ii) and (iii). By Lemma 3.10 and (i),
there is a $(z,b_{k_{z}};b_{k_{z}},u)$-set of chains ${\mathcal{F}_{k_{z}}}$
in $\bigcup_{i=k_{u}}^{k_{z}}B_{i}$. By Lemma 3.8,
$G_{1}=B-\bigcup_{i=k_{u}}^{n}V(B_{i})$ is a good chain with respect to $x$ in
$B$. It follows that

${\mathcal{C}}=\\{G_{1}\\}\cup{\mathcal{F}_{k_{z}}}\cup\bigcup_{i=k_{z}+1}^{n}{\mathcal{C}_{i}}$

is a $(x,y;u)$-set of chains in $B$. The path $P$ (as defined above) is a
${\mathcal{C}}$-path. This proves the claim when $k_{z}\neq n$.

Assume now that $k_{z}=n$. If $k_{z}=k_{u}=n$ and $z\neq y$ then, by Lemma
3.13, there is

  * (vii)

a $(z,y;u)$-set of chains ${\mathcal{H}_{n}}$ in $B_{n}$.

By Lemma 3.8, $G_{2}=B-V(B_{n})$ is a good chain with respect to $x$ in $B$.
It follows that ${\mathcal{C}}=\\{G_{2}\\}\cup{\mathcal{H}_{n}}$ is a
$(x,y;u)$-set of chains in $B$, and $P$ (as defined above) is a
${\mathcal{C}}$-path.

If $k_{z}=k_{u}=n$ and $z=y=u$ then $xz$ is an edge of $C$ (recall that $y\neq
b_{n-1}$ and that $y$ is an external vertex of $B$). By Lemma 3.6, $G_{3}=B-y$
is a good chain with respect to $x$. Therefore ${\mathcal{C}}=\\{G_{3}\\}$ is
a $(x,y;u)$-set of chains, where a ${\mathcal{C}}$-path in $B$ is the path
$x,y$. If $z=y\neq u$ then $B_{n}$ is a good chain with respect to $y$ and
$u$, and $G_{2}$ is a good chain with respect to $x$. It follows that
$\\{B_{n},G_{2}\\}$ is a $(x,y;u)$-set of chains in $B$; again a
${\mathcal{C}}$-path in $B$ is the path on two vertices $x,y$. If $z\neq y$

Finally, if $k_{u}<k_{z}=n$ and $z\neq y$ there is

  * (viii)

a $(z,y;b_{n-1})$-set of chains in $B_{n}$.

By Lemma 3.10 and (viii), there is a $(z,y;u)$-set of chains
${\mathcal{I}_{n}}$ in $\bigcup_{i=k_{u}}^{n}B_{i}$. In this case
${\mathcal{C}}=\\{G_{1}\\}\cup{\mathcal{I}_{n}}$ is a $(x,y;u)$-set of chains
in $B$. If $z=y$, then $G_{4}=\bigcup_{i=k_{u}}^{n}B_{i}$ is a good chain with
respect to $u$ and $y$, hence ${\mathcal{C}}=\\{G_{1},G_{4}\\}$ is a
$(x,y;u)$-set of chains in $B$. This proves the claim, and hence also the
lemma. $\square$

###### Theorem 3.17

Let $B$ be a non-bipartite circuit graph with outer cycle $C$, and let $x,y\in
V(C)$. If all internal vertices of $B$ are of degree at least 4, then for any
vertex $u\in V(C)$ there is a $(x,y;u)$-set of chains in $B$. Moreover, if $Q$
is a $xy$-path in $C$ such that every vertex in $V(C)\setminus V(Q)$ is of
degree at least 3 in $B$, then for any vertex $u\in V(Q)$ there is an odd and
an even $(x,y;u)$-set of chains in $B$.

Proof. Suppose the theorem is not true. Let $B$ be a counterexample of minimum
order. We may assume that $u\neq x$ (otherwise $u\neq y$, and the proof is
analogous). By Lemma 2.3, $B-x$ is a plain chain of blocks

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Let $k_{1},k_{2}\in[n]$ be such that $u\in V(B_{k_{1}})\setminus
V(B_{{k_{1}-1}})$ and $y\in V(B_{k_{2}})\setminus V(B_{k_{2}-1})$ (here we set
$B_{0}=\emptyset$). Let $b_{0}\in V(B_{1})$ and $b_{n}\in V(B_{n})$ be the
neighbors of $x$ in $C$. We may assume that $xb_{0}$ is an edge of $Q$ and
$xb_{n}$ is not an edge of $Q$, and that $u\in V(Q)$ (the last sentence of the
theorem assumes $u\in V(Q)$, and for the proof of the first part of the
theorem $u\in V(Q)$ may be assumed without loss of generality). Since $u\in
V(Q)$ we have $k_{1}\leq k_{2}$. We give two constructions. In both
constructions we define $P_{i}=B_{i}$ and ${\mathcal{C}_{i}}=\emptyset$, if
$B_{i}$ is trivial. In the sequal we treat nontrivial blocks $B_{i}$.

Construction A. If $k_{1}<k_{2}$ then, by minimality of $B$ (if $B_{i}$ is
non-bipartite) and by Lemma 3.13 (if $B_{i}$ is bipartite), there is

  * (i)

a $(b_{i-1},b_{i};b_{i})$-set of chains in $B_{i}$, for $i\in[k_{1}-1]$,

  * (ii)

a $(b_{k_{1}-1},b_{k_{1}};u)$-set of chains in $B_{k_{1}}$,

  * (iii)

a $(b_{i-1},b_{i};b_{i-1})$-set of chains in $B_{i}$, for
$i\in[k_{2}-1]\setminus[k_{1}]$,

  * (iv)

a $(b_{k_{2}-1},y;b_{k_{2}-1})$-set of chains in $B_{k_{2}}$,

if $k_{1}=k_{2}$ and $y\neq b_{0}$ there is

  * (v)

a $(b_{k_{2}-1},y;u)$-set of chains in $B_{k_{2}}$.

Note that for $i\in[k_{2}-1]$ every vertex in $V(C_{i})\setminus V(Q_{i})$ is
of degree at least 3 in $B_{i}$, where $C_{i}$ is the outer cycle of $B_{i}$
and $Q_{i}=Q\cap B_{i}$. By minimality of $B$ we may apply the (last)
statement of the theorem to $B_{i}$, if $B_{i}$ is non-bipartite. Hence, if
$B_{i}$ is non-bipartite for some $i\in[k_{2}-1]$, there is an odd and an even
set of chains for (i), (ii) and (iii). Additionally, if $B_{k_{2}}$ is non-
bipartite and $y=b_{k_{2}}$, then there is also an odd and an even set of
chains ${\mathcal{C}_{k_{2}}}$ for (iv) and (v) (by minimality of $B$).

Denote by ${\mathcal{C}_{i}}$ the set of chains in $B_{i}$ defined by (i)-(iv)
if $k_{1}<k_{2}$; and defined by (i) and (v) if $k_{1}=k_{2}$ and $y\neq
b_{0}$. The ${\mathcal{C}_{i}}$-path is denoted by $P_{i}$, for $i\in[k_{2}]$.
Let $P_{0}$ be the path $x,b_{0}$. Define $P=\bigcup_{i=0}^{k_{2}}P_{i}$. By
Lemma 3.8, $G_{1}=B-\bigcup_{i=1}^{k_{2}}B_{i}$ is a good chain with respect
to $x$ in $B$. Hence

${\mathcal{C}}=\\{G_{1}\\}\cup\bigcup_{i=1}^{k_{2}}{\mathcal{C}_{i}}$

is a $(x,y;u)$-set of chains in $B$. The path $P$ is a ${\mathcal{C}}$-path in
$B$. Moreover, if a block $B_{i},i\in[k_{2}-1]$ is non-bipartite, then there
exists an odd and an even set of chains ${\mathcal{C}_{i}}$ in $B_{i}$, and so
${\mathcal{C}}$ is an odd or an even set of chains subject to the choice of
${\mathcal{C}_{i}}$.

If $y=b_{0}$ then $u=y=b_{0}$ (by our assumptions $u\in V(Q)$ and $u\neq x$).
In this case $G_{2}=B-y$ is a good chain with respect to $x$, by Lemma 3.6.
Hence, ${\mathcal{C}}=\\{G_{2}\\}$ is a $(x,y;u)$-set of chains, and $P=x,y$
is the corresponding ${\mathcal{C}}$-path. This proves the first claim of the
theorem; and also the second claim of the theorem if $B_{i}$ is non-bipartite
for some $i\in[k_{2}-1]$, or if $B_{k_{2}}$ is non-bipartite and $y=b_{k_{2}}$
(note that this, in particular, proves the theorem for the case if $y=b_{n}$
and $B-x$ is non-biparite). To finish the proof of the second claim of the
theorem we give construction B, in which we assume that every vertex in
$V(C)\setminus V(Q)$ is of degree at least 3 in $B$. We also assume that
$B_{i}$ is bipartite for $i\in[k_{2}-1]$, and if $y=b_{k_{2}}$ then $B_{i}$ is
bipartite for $i\in[k_{2}]$.

Construction B. If $k_{1}<k_{2}$ and $y\neq b_{k_{2}}$ then, by minimality of
$B$ (if $B_{i}$ is non-bipartite) and by Lemma 3.13 (if $B_{i}$ is bipartite),
there is

  * (vi)

a $(b_{i-1},b_{i};b_{i-1})$-set of chains in $B_{i}$, for
$i\in[n]\setminus[k_{2}]$,

  * (vii)

a $(b_{k_{2}},y;b_{k_{2}-1})$-set of chains in $B_{k_{2}}$,

and if $k_{1}=k_{2}$ and $y\neq b_{k_{2}}$ there is

  * (viii)

a $(b_{k_{2}},y;u)$-set of chains in $B_{k_{2}}$.

Denote by ${\mathcal{C}_{i}}$ the set of chains in $B_{i}$ defined by (vi) and
(vii) if $k_{1}<k_{2}$ and $y\neq b_{k_{2}}$; and defined by (vi) and (viii)
if $k_{1}=k_{2}$ and $y\neq b_{k_{2}}$. The ${\mathcal{C}_{i}}$-paths are
denoted by $P_{i}$, for $i\in[n]\setminus[k_{2}-1]$.

Suppose that $y\neq b_{k_{2}}$ and $k_{1}<k_{2}$. Let $R_{1}$ and $R_{2}$ be
the $yb_{k_{2}}$-paths in $C_{k_{2}}$ (where $C_{k_{2}}$ is the outer cycle of
$B_{k_{2}}$), and assume $b_{k_{2}-1}\in V(R_{1})$. Since every vertex in
$V(C)\setminus V(Q)$ is of degree at least 3 in $B$, we find that every vertex
in $V(C_{k_{2}})\setminus V(R_{1})$ is of degree at least 3 in $B_{k_{2}}$.
Therefore, by minimailty of $B$, if $B_{k_{2}}$ is non-bipartite there is an
odd and an even set of chains ${\mathcal{C}_{k_{2}}}$ for (vii) and (viii).
Moreover, if $B_{i}$ is non-bipartite there exist odd and even sets of chains
${\mathcal{C}_{i}}$ for $i\in[n]\setminus[k_{2}]$, as given by (vi).

If $u\neq b_{k_{1}}$ then, by Lemma 3.10 (see notes directly after Lemma 3.10)
and (vii), there is a $(b_{k_{2}},y;u)$-set of chains ${\mathcal{D}_{k_{2}}}$
in $\bigcup_{i=k_{1}}^{k_{2}}B_{i}$ (recall the assumption that $B_{i}$ is
bipartite for $i\in[k_{2}-1]$). By Lemma 3.8,
$G_{3}=B-\bigcup_{i=k_{1}}^{n}B_{i}$ is a good chain with respect to $x$. Let
$P_{n+1}$ be the path $x,b_{n}$. Define $P=\bigcup_{i=k_{2}}^{n+1}P_{i}$. Then

${\mathcal{C}}=\\{G_{3}\\}\cup{\mathcal{D}_{k_{2}}}\cup\bigcup_{i=k_{2}+1}^{n}{\mathcal{C}_{i}}$

is a $(x,y;u)$-set of chains in $B$. The corresponding ${\mathcal{C}}$-path is
$P$.

If $u=b_{k_{1}}$ the construction of a $(x,y;u)$-set of chains in $B$ is
analogous as in the case $u\neq b_{k_{1}}$ (the only difference is that
${\mathcal{D}_{k_{2}}}$ is a $(b_{k_{2}},y;u)$-set of chains in
$\bigcup_{i=k_{1}+1}^{k_{2}}B_{i}$, and
$G_{3}=B-\bigcup_{i=k_{1}+1}^{n}B_{i}$).

If $y\neq b_{k_{2}}$ and $k_{1}=k_{2}$, we use (vi) and (viii). In this case

${\mathcal{C}}=\\{G_{3}\\}\cup\bigcup_{i=k_{2}}^{n}{\mathcal{C}_{i}}$

is a $(x,y;u)$-set of chains in $B$. If $B_{i}$ is non-bipartite for some
$i\in[n]\setminus[k_{2}-1]$ then we can choose ${\mathcal{C}}_{i}$ so that
${\mathcal{C}}$ is an odd or an even $(x,y;u)$-set of chains in $B$ (in all
cases above). This proves the second claim of the theorem if $y\neq b_{k_{2}}$
and $B_{i}$ is non-bipartite for some $i\in[n]\setminus[k_{2}-1]$.

Suppose now that $y=b_{k_{2}},k_{2}\neq n$ and $u\neq b_{k_{1}}$. If we use
(vi) for $i=k_{2}+1$, we find that ${\mathcal{C}_{k_{2}+1}}$ is a
$(b_{k_{2}},b_{k_{2}+1};b_{k_{2}})$-set of chains in $B_{k_{2}+1}$. Hence, by
Lemma 3.10 (see notes after Lemma 3.10), there is a
$(b_{k_{2}},b_{k_{2}+1};u)$-set of chains ${\mathcal{F}_{k_{2}+1}}$ in
$\bigcup_{i=k_{1}}^{k_{2}+1}B_{i}$ (recall the assumption that $B_{i}$ is
bipartite for $i\in[k_{2}]$ if $y=b_{k_{2}}$). Then

${\mathcal{C}}=\\{G_{3}\\}\cup{\mathcal{F}_{k_{2}+1}}\cup\bigcup_{i=k_{2}+2}^{n}{\mathcal{C}_{i}}$

is a $(x,y;u)$-set of chains in $B$. The corresponding ${\mathcal{C}}$-path is
$P$.

If $y=b_{k_{2}},k_{2}\neq n$ and $u=b_{k_{1}}$, then let
${\mathcal{H}_{k_{2}+1}}$ be a $(b_{k_{2}},b_{k_{2}+1};u)$-set of chains in
$\bigcup_{i=k_{1}+1}^{k_{2}+1}B_{i}$ (it exits by Lemma 3.10) and define
$G_{4}=B-\bigcup_{i=k_{1}+1}^{n}B_{i}$. In this case
${\mathcal{C}}=\\{G_{4}\\}\cup{\mathcal{H}_{k_{2}+1}}\cup\bigcup_{i=k_{2}+2}^{n}{\mathcal{C}_{i}}$
is a $(x,y;u)$-set of chains in $B$.

Observe that, if $B_{i}$ is non-bipartite for some $i\in[n]\setminus[k_{2}]$,
then we can choose $P_{i}$, and hence also $P$, so that ${\mathcal{C}}$ is odd
or even. This proves the second claim of the theorem if $y=b_{k_{2}}$
($k_{2}\neq n$) and $B_{i}$ is non-bipartite for some
$i\in[n]\setminus[k_{2}]$.

The last case to consider is when $B_{i}$ is bipartite for $i\in[n]$. In this
case $B-x$ is bipartite and the theorem follows from Lemma 3.16. $\square$

The proof of the following lemma is similar to the proof of Lemma 3.10 (so we
skip this proof).

###### Lemma 3.18

Let $G$ be a bipartite plain chain of blocks

$G=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Let $u\in V(B_{j})\setminus\\{b_{j-1},b_{j}\\}$ for some
$j\in\\{2,\ldots,n-1\\}$, and suppose that there exits a
$[b_{j-1},b_{j},u]$-set of chains in $B_{j}$. Then for any $v^{\prime}\in
V(B_{1})\setminus V(B_{2})$ and $v^{\prime\prime}\in V(B_{n})\setminus
V(B_{n-1})$, there exists a $[v^{\prime},v^{\prime\prime},u]$-set of chains in
$G$.

###### Theorem 3.19

Let $B$ be a non-bipartite circuit graph with outer cycle $C$. Suppose that
$x,y\in V(C)$ and that $B$ is good with respect to $x$ and $y$. If every
internal vertex of $B$ is of degree at leat 4 and $B$ is not an odd cycle,
then there exists a $[x,y]$-set of chains in $B$.

Proof. By Lemma 2.3, $B-x$ is a plain chain of blocks

$B-x=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n}\,.$

Let $b_{0}\in V(B_{1})$ and $b_{n}\in V(B_{n})$ be the neighbors of $x$ in
$C$. Let $k\in[n]$ be such that $y\in V(B_{k})\setminus V(B_{{k-1}})$ (here we
set $B_{0}=\emptyset$).

Suppose that at least one block $B_{i}$ is non-bipartite. If $B_{i}$ is
trivial, define ${\mathcal{C}_{i}}=\emptyset$ and $P_{i}=B_{i}$. Otherwise, by
Theorem 3.17 and Lemma 3.13 there is

  * (i)

a $(b_{i-1},b_{i};b_{i})$-set of chains in $B_{i}$, for $i\in[k-1]$,

  * (ii)

a $(b_{k-1},b_{k};y)$-set of chains in $B_{k}$,

  * (iii)

a $(b_{i-1},b_{i};b_{i-1})$-set of chains in $B_{i}$ for
$i\in[n]\setminus[k]$.

Denote by ${\mathcal{C}_{i}}$ the set of chains in $B_{i}$ defined by (i),
(ii) and (iii). The ${\mathcal{C}_{i}}$-paths are denoted by $P_{i}$, for
$i\in[n]$. Let $P_{0}=x,b_{0}$ and $P_{n+1}=b_{n},x$, and define
$C^{\prime}=\bigcup_{i=0}^{n+1}P_{i}$. Since $B_{i}$ is non-bipartite for some
$i\in[n]$, there is an odd and an even set of chains ${\mathcal{C}_{i}}$ for
(i),(ii) or (iii). Hence, we can choose ${\mathcal{C}_{i}}$ and $P_{i}$ so
that $C^{\prime}$ is even, and therefore
${\mathcal{C}}=\bigcup_{i=1}^{n}{\mathcal{C}_{i}}$ is a $[x,y]$-set of chains
in $B$.

Suppose that all blocks $B_{i},i\in[n]$ are bipartite. Then all odd faces of
$B$ are incident to $x$. Define $B_{n+1}=P_{n+1}$.

If $y\notin\\{b_{k-1},b_{k}\\}$, then by Lemma 3.15 there exits a
$[b_{k-1},b_{k},y]$-set of chains ${\mathcal{D}_{k}}$ in $B_{k}$. Let
$G=B_{1},b_{1},B_{2},\ldots,b_{n-1},B_{n},b_{n},B_{n+1}\,.$ By Lemma 3.18
there is a $[x,y]$-set of chains in $G$, which is also a $[x,y]$-set of chains
in $B$ (because $G$ is a spanning subgraph of $B$).

Assume now that $y\in\\{b_{k-1},b_{k}\\}$. Suppose that
$y\in\\{b_{0},b_{n}\\}$. We may assume $y=b_{0}$. If a block $B_{i}$ of $G$ is
nontrivial, then by Lemma 3.15, there is a $[b_{i-1},b_{i}]$-set of chains
${\mathcal{F}_{i}}$ in $B_{i}$. Therefore, by Lemma 3.18 there is a
$[x,y]$-set of chains in $G$, which is also a $[x,y]$-set of chains in $B$.
Otherwise all blocks $B_{i},i\in[n+1]$ are trivial. If $C$ is an even cycle,
then $C$ itself is a $[x,y]$-set of chains in $B$. Otherwise $C$ is odd, and
since $B$ is not an odd cycle, $C$ has a chord. Hence $B$ has an even cycle
$C_{0}$ (which goes through $x$). Clearly, $C_{0}$ together with blocks
$B_{i}$ such that $|V(B_{i})\cap V(C_{0})|\leq 1$ forms a $[x,y]$-set of
chains in $B$.

Hence we may assume that $y=b_{k}$ where $k\notin\\{0,n\\}$. Suppose that all
bounded odd faces of $B$ are incident to $y$ (and recall that all bounded odd
faces are incident to $x$). Then there are exactly one or two such faces.
However, if there is exactly one bounded odd face in $B$, and this odd face is
incident to $x$ and $y$, then $xy\in E(C)$ (follows from the fact that $B$ is
good with respect to $x$ and $y$) and so $y\in\\{b_{0},b_{n}\\}$.

Therefore there are exactly two bounded odd faces in $B$ (both adjacent to $x$
and $y$). In this case the cycle $C^{\prime}$(defined above) bounds exactly
two odd faces of $B$ and therefore $C^{\prime}$ is even. Hence,
${\mathcal{C}}$ (defined above) is a $[x,y]$-set of chains in $B$.

We may therefore assume that there is a bounded odd face $F$ of $B$, which is
not incident to $y$, and that $y\notin\\{b_{0},b_{n}\\}$. Let $xx_{1}$ and
$xx_{2}$ be edges incident to $F$. Since $F$ is not incident to $y=b_{k}$ we
may assume, without loss of generality, that
$x_{1},x_{2}\in\bigcup_{i=1}^{k}V(B_{i})$. Since $F$ is an odd face and $G$ is
bipartite, every $x_{1}x$-path in $G$ is odd and every $x_{2}x$-path in $G$ is
even (or vice-versa).

Let $k^{\prime}\in[k]$ be such that $x_{1}\in V(B_{k^{\prime}})\setminus
V(B_{k^{\prime}+1})$. If $B_{k^{\prime}}$ resp. $B_{i}$ is nontrivial, then by
Lemma 3.12 and Lemma 3.13 there is a

  * (iv)

a $(x_{1},b_{k^{\prime}};b_{k^{\prime}-1},b_{k^{\prime}})$-set of chains
${\mathcal{G}_{k^{\prime}}}$ in $B_{k^{\prime}}$,

  * (v)

a $(b_{i-1},b_{i};b_{i-1},b_{i})$-set of chains ${\mathcal{G}_{i}}$ in $B_{i}$
for $i\in[n]\setminus[k^{\prime}]$.

Let $P_{i}$ be the ${\mathcal{G}_{i}}$-path in $B_{i}$ for
$i\in[n]\setminus[k^{\prime}-1]$ (if $B_{i}$ is trivial, define $P_{i}=B_{i}$
and ${\mathcal{G}_{i}}=\emptyset$), and define
$C^{\prime\prime}=\bigcup_{i=k^{\prime}}^{n+1}P_{i}\cup\\{xx_{1}\\}$ (recall
that $P_{n+1}=b_{n},x$). Since every $x_{1}x$-path in $G$ is odd,
$C^{\prime\prime}$ is even. By (iv) and Lemma 3.10, there is a
$(x_{1},b_{k^{\prime}};b_{k^{\prime}})$-set of chains
${\mathcal{H}_{k^{\prime}}}$ in $\bigcup_{i=1}^{k^{\prime}}B_{i}$. Then
${\mathcal{G}}=\bigcup_{i=k^{\prime}+1}^{n}{\mathcal{G}_{i}}\cup{\mathcal{H}_{k^{\prime}}}$
is a $[x,y]$-set of chains in $B$, and $C^{\prime\prime}$ is a
${\mathcal{G}}$-cycle in $B$. $\square$

###### Theorem 3.20

Let $B$ be a circuit graph such that every internal vertex of $B$ is of degree
at least 4. Then $B$ has a spanning bipartite cactus.

Proof. Let $C$ be the outer cycle of $B$. We prove a slightly stronger
statement: if $B$ is a circuit graph such that every internal vertex of $B$ is
of degree at least 4, and $x,y\in V(C)$ are vertices such that $B$ is good
with respect to $x$ and $y$, then $B$ has a spanning bipartite cactus $T$ such
that $x$ and $y$ are contained in exactly one block of $T$.

The proof is by induction on $|V(B)|$. The statement is clealy true if $B$ is
an even cycle. If $B$ is an odd cycle and $B$ is good with respect to $x$ and
$y$ then $x$ and $y$ are adjacent. A spanning $xy$-path in $B$ is a bipartite
spanning cactus in $B$ such that $x$ and $y$ are contained in exactly one
block of this cactus.

If $B$ is not an odd cycle, then by Theorem 3.19 (if $B$ is non-biparitite)
and Lemma 3.15 (if $B$ is bipartite), there is a $[x,y]$-set of chains
${\mathcal{C}}=\\{G_{1},\ldots,G_{k}\\}$ in $B$. Let $C^{\prime}$ be a
${\mathcal{C}}$-cycle. Note that each block $B^{\prime}$ of a chain
$G_{i},i\in[k]$ is good with respect to (both) cutvertices of $G_{i}$
contained in $B^{\prime}$. Moreover, either $x\notin\bigcup_{i=1}^{k}V(G_{i})$
or a chain of ${\mathcal{C}}$ is good with respect to $x$ (a similar fact is
true for $y$). Therefore we can use the induction hypothesis, to obtain a
spanning bipartite cactus $T(B^{\prime})$ in $B^{\prime}$ such that (both)
cutvertices of $G_{i}$ contained in $B^{\prime}$ are contained in exactly one
block of $T(B^{\prime})$. Moreover the block $B_{x}$ that contains $x$ (if
any) has a spanning bipartite cactus $T(B_{x})$ such that $x$ is contained in
exactly one block of $T(B_{x})$ (a similar fact is true for $y$). Let
${\mathcal{B}}$ be the set of all blocks of $G_{i},i\in[k]$ and define
$T=C^{\prime}\cup\bigcup_{B^{\prime}\in{\mathcal{B}}}T(B^{\prime})$. This
gives the required bipartite cactus in $B$. $\square$

Let ${\mathcal{P}}$ be the class of 3-connected planar graphs whose prisms are
not hamiltonian. We end the article with the problem to determine the minimum
ratio of cubic vertices in a graph $G\in{\mathcal{P}}$. Let $V_{3}(G)$ denote
the set of cubic vertices in $G$.

###### Problem 3.21

Determine minimum $\epsilon$ such that there exist arbitrary large graphs
$G\in{\mathcal{P}}$ with $|V_{3}(G)|/|V(G)|<\epsilon$. In particular, can
$\epsilon$ be arbitrary small ?

Acknowledgement: The author thanks Uroš Milutinović for proofreading parts of
the final version of this paper. This work was supported by the Ministry of
Education of Slovenia [grant numbers P1-0297, J1-9109].

## References

  * [1] D.W. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966), 731–736.
  * [2] D. Barnette, E. Jucovič, Hamiltonian circuits on 3-polytopes. J. Comb. Theory 9 (1970), 54–59.
  * [3] D. P. Biebighauser, M. N. Ellingham, Prism-Hamiltonicity of triangulations, J. Graph Theory, 57 (2008), 181–197.
  * [4] G. Brinkmann, C. T. Zamfirescu, Polyhedra with few 3-cuts are hamiltonian, Electron. J. Combin. 26 (2019), no. 1, Paper No. 1.39, 16 pp.
  * [5] R. Čada, T. Kaiser, M. Rosenfeld, Z. Ryjáček, Hamiltonian decompositions of prisms over cubic graphs, Discrete Math. 286 (2004), 45–56.
  * [6] M. N. Ellingham, E. A. Marshall, K. Ozeki, S. Tsuchiya, Hamiltonicity of planar graphs with a forbidden minor, J. Graph Theory 90 (2019), no. 4, 459–483.
  * [7] M. N. Ellingham, P. S. Nowbandegani, S. Shan, Toughness and prism-hamiltonicity of P4-free graphs. Discrete Appl. Math. 284 (2020), 201–206.
  * [8] Z. Gao, R. B. Richter, 2-walks in circuit graphs, J. Comb. Theory Ser. B, 62 (1994), 259–267.
  * [9] D. Ikegami, S. Maezawa, C. T. Zamfirescu, On 3-polytopes with non-Hamiltonian prisms, J. Graph Theory. (2021), 1–9. https://doi.org/10.1002/jgt.22672
  * [10] B. Jackson, N.C. Wormald, k-walks of graphs, Australas. J. Combin. 2 (1990) 135–146.
  * [11] T. Kaiser, D. Král’, M. Rosenfeld, Z. Ryjáček, H.-J. Voss, Hamilton cycles in prisms, J. Graph Theory 56 (2007), 249–269.
  * [12] B. Mohar, C. Thomassen, Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.
  * [13] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
  * [14] K. Ozeki, A degree sum condition for graphs to be prism Hamiltonian, Discrete Math. 309 (2009), no. 13, 4266–4269.
  * [15] K. Ozeki, N. Van Cleemput, C. T. Zamfirescu, Hamiltonian properties of polyhedra with few 3-cuts — a survey. Discrete Math. 341 (2018), no. 9, 2646–2660.
  * [16] P. Paulraja, A characterization of hamiltonian prisms, J. Graph Theory 17 (1993), 161–171.
  * [17] M. Rosenfeld, D. Barnette, Hamiltonian circuits in certain prisms, Discrete Math. 5 (1973), 389–394.
  * [18] S. Špacapan, A counterexample to prism-hamiltonicity of 3-connected planar graphs. J. Combin. Theory Ser. B 146 (2021), 364–371.
  * [19] C. Thomassen. Hypohamiltonian graphs and digraphs, Proc. Internat. Conf. Theory and Appl. of Graphs, Kalamazoo, 1976, LNCS 642, Springer, Berlin (1978) 557–571.
  * [20] W. T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946), 98–101.
  * [21] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956), 99–116.
  * [22] N. Van Cleemput, C. T. Zamfirescu, Regular non-hamiltonian polyhedral graphs. Appl. Math. Comput. 338 (2018), 192–206.


# Hadamard matrices related to the projective planes

Hadi Kharaghani Department of Mathematics and Computer Science, University of
Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada<EMAIL_ADDRESS>Sho Suda
Department of Mathematics, National Defense Academy of Japan, Yokosuka,
Kanagawa 239-8686, Japan<EMAIL_ADDRESS>
###### Abstract

Let $n$ be the order of a (quaternary) Hadamard matrix. It is shown that the
existence of a projective plane of order $n$ is equivalent to the existence of
a balancedly multi-splittable (quaternary) Hadamard matrix of order $n^{2}$.

##  1 Introduction

K. A. Bush [1] was the first to establish a link between projective planes of
even order and specific Hadamard matrices (now called Bush-type) in 1971. H.
J. Ryser [10] found the same connection as an application of factors of design
matrix in 1977. Eric Verheiden [11] showed that the existence of only four
MOLS of size ten would lead to a symmetric Bush-type Hadamard matrix of order
100 in 1981.

Franc C. Bussemaker, Willem Haemers and Ted Spence [2] used an exhaustive
search and found no strongly regular graph with parameters (36,15,6,6) and
chromatic number six or equivalently a symmetric Bush-type Hadamard matrix of
order 36. Many Bush-type Hadamard matrices of order 100 are constructed, but
none is known to be symmetric. The proof of the nonexistence of a symmetric
Bush-type Hadamard matrix of order 100 would be exciting, however, there has
been no attempt at showing it so far. The nonexistence of the projective plane
of order ten was finally established by a long computational method by C. W.
H. Lam et al. in [8, 9].

Balancedly splittable Hadamard matrices were introduced by the authors in 2018
in [7], and it is widely expanded in a recent paper by Jedwab et al. in [4].
It is known [6] that the existence of a Hadamard matrix of order $4n$ would
lead to a balancedly splittable Hadamard matrix of order $64n^{2}$. There is
no balancedly splittable Hadamard matrix of order $4n^{2}$, $n$ odd, see [7].
The case of Hadamard matrices of order $16n^{2}$ remains open, and no
balancedly splittable Hadamard matrix of order $144$ is known.

Concentrating on the order $144$, the authors were led to some exotic classes
of balancedly splittable Hadamard matrices which we have dubbed _balancedly
multi-splittable Hadamard matrices_. There is a balancedly multi-splittable
Hadamard matrix of order $4^{m}$ for every positive integer $m$, and it seems
that these are probably the only Hadamard matrices with this property.

It will be shown that the existence of a projective plane of order $4n$ is
equivalent to the existence of a balancedly multi-splittable Hadamard matrix
of order $16n^{2}$ provided that $4n$ is the order of a Hadamard matrix.

A similar equivalence between the projective plane of order $2n$, $n$ odd, and
balancedly multi-splittable quaternary Hadamard matrices will be presented
too.

The connection between projective planes and Hadamard matrices shown in [1,
10, 11] are all one sided results in which from a projective plane of even
order symmetric Bush-type Hadamard matrices are constructed. The proof of the
nonexistence of a symmetric Bush-type Hadamard matrix of order 100 would be
exciting; however, there has yet to be an attempt at showing it. The fact that
less than half of the assumed nine MOLS are sufficient for their construction
as shown in [11] makes one wonder if there are no symmetric Bush-type Hadamard
matrices of order 100, even though not a single one is found yet.

##  2 Preliminaries

###  2.1 Hadamard matrices

An $n\times n$ matrix $H$ is a Hadamard matrix of order $n$ if its entries are
$1,-1$ and it satisfies $HH^{\top}=I_{n}$, where $I_{n}$ denotes the identity
matrix of order $n$. A Hadamard matrix $H$ of order $n$ is said to be
balancedly splittable if there is an $\ell\times n$ submatrix $H_{1}$ of $H$
such that inner products for any two distinct column vectors of $H_{1}$ take
at most two values. More precisely, there exist integers $a,b$ and the
adjacency matrix $A$ of a graph such that $H_{1}^{\top}H_{1}=\ell
I_{n}+aA+b(J_{n}-A-I_{n})$, where $J_{n}$ denotes the all-ones matrix of order
$n$. In this case we say that $H$ is balancedly splittable with respect
$H_{1}$. Only the special case of $b=-a$ will be used in this note.

The same concept can be extended to orthogonal designs [6]. Here, we adopt the
following definition for quaternary Hadamard matrices. An $n\times n$ matrix
$H$ is a quaternary Hadamard matrix of order $n$ if its entries are $\pm 1,\pm
i$ and it satisfies $HH^{*}=nI_{n}$. A quaternary Hadamard matrix $H$ of order
$n$ is said to be balancedly splittable if there is an $\ell\times n$
submatrix $H_{1}$ of $H$ such that the off-diagonal entries of
$H_{1}^{*}H_{1}$ are in the set

$\\{\varepsilon\alpha,\varepsilon\alpha^{*},\varepsilon\beta,\varepsilon\beta^{*}\mid\varepsilon\in\\{\pm
1,\pm i\\}\\},$

where $\alpha,\beta$ are some complex numbers. In this paper, we restrict to
the case $\alpha=\beta$ and we say that a quaternary Hadamard matrix $H$ of
order $n$ is balancedly splittable if $H_{1}^{*}H_{1}=\ell I+\alpha S$ where
$\alpha$ is some positive real number and $S$ is a $(0,\pm 1,\pm i)$-matrix
with zero diagonal entries and nonzero off-diagonal entries.

###  2.2 Orthogonal arrays

An _orthogonal array_ of strength $t$ and index $\lambda$ is an $N\times k$
matrix over the set $\\{1,\dots,q\\}$ such that in every $N\times t$ subarray,
each $t$-tuple in $S^{t}$ appears $\lambda$ times. We denote this property as
OA${}_{\lambda}(N,k,q,t)$. Note that $N=\lambda q^{t}$ and $(N,k,q,t)$ is the
parameter of the orthogonal array.

For $t=2e$, the following lower bound on $N$ was shown by Rao (see [5, Theorem
2.1]), namely, $N\geq\sum_{i=0}^{e}\binom{k}{i}(q-1)^{i}$. An orthogonal array
with parameters $(N,k,q,2e)$ is said to be complete if the equality holds in
above.

When $t=2$ and $\lambda=1$, the complete orthogonal array has the parameters
OA${}_{1}(q^{2},q+1,q,2)$, and it is known that its existence is equivalent to
that of a projective plane of order $q$. For the construction the orthogonal
version of a projective plane is used in the next section.

The following lemmas will be used later.

######  Lemma 2.1.

Let $A$ be an $N\times k$ matrix over $\\{1,\ldots,q\\}$. Write
$A=\sum_{i=1}^{q}iA_{i}$, where $A_{i}$ ($i\in\\{1,\ldots,q\\}$) are disjoint
$q^{2}\times(q+1)$ $(0,1)$-matrices. Let $D$ be the distance matrix, ie., $D$
is an $N\times N$ matrix whose rows and columns indexed by the rows of $A$
with $(i,j)$-entry defined by the Hamming distance between the $i$-th row and
the $j$-th row of $A$. Then $\sum_{i=1}^{q}A_{i}A_{i}^{\top}=kJ_{N}-D$ holds.

###### Proof.

See the proof of [5, Lemma 2.5 (i)]. ∎

######  Lemma 2.2.

Assume that there exists an orthogonal array $A$ with parameters
$(q^{2},q+1,q,2)$. Write $A=\sum_{i=1}^{q}iA_{i}$, where $A_{i}$
($i\in\\{1,\ldots,q\\}$) are disjoint $q^{2}\times(q+1)$ $(0,1)$-matrices.
Then the matrices $A_{i}$ satisfy

  1. (i)

$\sum_{i=1}^{q}A_{i}A_{i}^{\top}=J_{q^{2}}+qI_{q^{2}}$,

  2. (ii)

$\sum_{i,j=1,i\neq j}^{q}A_{i}A_{j}^{\top}=q(J_{q^{2}}-I_{q^{2}})$.

  3. (iii)

Consider the code $C$ obtained from the rows of $A$. Let
$\\{i_{1},\ldots,i_{s}\\}$ be any $s$-element subset of $\\{1,\ldots,q+1\\}$.
The code $C^{\prime}$ obtained from $C$ by restricting the coordinates on the
set $\\{i_{1},\ldots,i_{s}\\}$ have the Hamming distances $s$ or $s-1$ between
the codewords in $C^{\prime}$.

###### Proof.

The proof for (i) and (ii) are exactly the same as [5, Lemma 2.5].

The assumed orthogonal array is a $2$-design and $1$-distance set with Hamming
distance $q$ in the Hamming association scheme. The case (iii) follows from
the fact that $C$ is a $1$-distance set with Hamming distance $q$. ∎

######  Lemma 2.3.

[3, Theorem 5.14] Let $C$ be an equi-distance code of length $q+1$ over the
symbol set $\\{1,\ldots,q\\}$. Then

$|C|\leq q^{2}$

holds. Equality holds if and only if the matrix whose rows consists of the
codewords of $C$ is an orthogonal array OA${}_{1}(q^{2},q+1,q,2)$.

##  3 Balancedly multi-splittable Hadamard martrices

We consider the following property on a Hadamard matrix. Let $H$ be a Hadamard
matrix of order $4n^{2}$. Assume that $H$ is normalized so that the first
column of $H$ is the all-ones vector. A Hadamard matrix $H$ is said to be
balancedly multi-splittable if there is a block form of
$H=\begin{bmatrix}{\bm{1}}&H_{1}&\cdots&H_{2n+1}\end{bmatrix}$ such that $H$
is balancedly spllitable with respect to a submatrix
$\begin{bmatrix}H_{i_{1}}&\cdots&H_{i_{n}}\end{bmatrix}$ for any $n$-element
subset $\\{i_{1},\ldots,i_{n}\\}$ of $\\{1,2,\ldots,2n+1\\}$.

The main results of this paper are as follows:

######  Theorem 3.1.

Let $n$ be a positive integer. The following are equivalent.

  1. (i)

There exists a balancedly multi-splittable Hadamard matrix of order $16n^{2}$.

  2. (ii)

There exist an OA${}_{1}(16n^{2},4n+1,4n,2)$ and a Hadamard matrix of order
$4n$.

######  Theorem 3.2.

Let $n$ be a positive integer. The following are equivalent.

  1. (i)

There exists a balancedly multi-splittable quaternary Hadamard matrix of order
$4n^{2}$

  2. (ii)

There exist an OA${}_{1}(4n^{2},2n+1,2n,2)$ and a quaternary Hadamard matrix
of order $2n$.

###  3.1 Proof of Theorem 3.1

###### The proof of (i) $\Rightarrow$ (ii).

Assume that there exists a Hadamard matrix $H$ of order $4n$. Write $H$ as

$H=\begin{bmatrix}1&r_{1}\\\ 1&r_{2}\\\ \vdots&\vdots\\\ 1&r_{4n}\\\
\end{bmatrix},$

where $r_{i}$ is a $1\times{(4n-1)}$ matrix for any $i$.

######  Lemma 3.3.

  1. (i)

For any $i$, $r_{i}r_{i}^{\top}={4n-1}$.

  2. (ii)

For any distinct $i,j$, $r_{i}r_{j}^{\top}=-1$.

Assume that there exists an OA$(16n^{2},4n+1,4n,2)$, say $A$, of index $1$
over $\\{1,\ldots,4n\\}$. Write $A=\sum_{i=1}^{4n}iA_{i}$, where the $A_{i}$’s
are disjoint $16n^{2}\times(4n+1)$ $(0,1)$-matrices. We then define the
$16n^{2}\times(16n^{2}-1)$ matrix $D$ by $D=\sum_{i=1}^{4n}A_{i}\otimes r_{i}$
and $\tilde{D}=\begin{bmatrix}{\bm{1}}&D\end{bmatrix}$.

######  Lemma 3.4.

  1. (i)

$DD^{\top}={16n^{2}I_{16n^{2}}-J_{16n^{2}}}$.

  2. (ii)

$\tilde{D}$ is a Hadamard matrix of order $16n^{2}$.

###### Proof.

(i): By Lemma 2.2 and Lemma 3.3,

$\displaystyle DD^{\top}$
$\displaystyle=\sum_{i,j=1}^{4n}A_{i}A_{j}^{\top}\otimes r_{i}r_{j}^{\top}$
$\displaystyle=\sum_{i=1}^{4n}A_{i}A_{i}^{\top}\otimes
r_{i}r_{i}^{\top}+\sum_{i\neq j}A_{i}A_{j}^{\top}\otimes r_{i}r_{j}^{\top}$
$\displaystyle=({4n-1})\sum_{i=1}^{4n}A_{i}A_{i}^{\top}-\sum_{i\neq
j}A_{i}A_{j}^{\top}$ $\displaystyle=({4n-1})J_{16n^{2}}+({4n-1})\cdot
4nI_{16n^{2}}-4n(J_{16n^{2}}-I_{16n^{2}})$
$\displaystyle=16n^{2}I_{16n^{2}}-J_{16n^{2}}.$

(ii) immediately follows from (i). ∎

Let $A^{\prime}$ be a submatrix of $A$ obtained by restricting the columns to
a $2n$ element set. Write $A^{\prime}=\sum_{i=1}^{4n}iA^{\prime}_{i}$, where
$A^{\prime}_{i}$ ($i\in\\{1,\ldots,4n\\}$) are disjoint $16n^{2}\times 2n$
$(0,1)$-matrices.

######  Lemma 3.5.

There exists a symmetric $(0,1)$-matrix $B$ with diagonal entries $0$ such
that

  1. (i)

$\sum_{i=1}^{4n}{A^{\prime}}_{i}{A^{\prime}}_{i}^{\top}=2nJ_{16n^{2}}-(2nB+({2n-1})(J_{16n^{2}}-I_{16n^{2}}-B))$,
and

  2. (ii)

$\sum_{i,j=1,i\neq
j}^{4n}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}=2nB+({2n-1})(J_{16n^{2}}-I_{16n^{2}}-B)$.

###### Proof.

Since the distance matrix of the code of rows of $A^{\prime}$ is
$2nB+({2n-1})(J_{16n^{2}}-I_{16n^{2}}-B)$ with the desired property, the case
(i) follows from Lemma 2.1.

Since $\sum_{i=1}^{4n}{A^{\prime}}_{i}=J_{16n^{2},2n}$, we have
$\sum_{i,j=1}^{4n}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}=(\sum_{i=1}^{4n}{A^{\prime}}_{i})(\sum_{j=1}^{4n}{A^{\prime}}_{j}^{\top})=J_{16n^{2},2n}J_{2n,16n^{2}}=2nJ_{16n^{2}}$.
This with (i) shows (ii). ∎

Now we consider $D^{\prime}=\sum_{i=1}^{4n}{A^{\prime}}_{i}\otimes r_{i}$.
Then, by Lemma 3.5,

$\displaystyle D^{\prime}{D^{\prime}}^{\top}$
$\displaystyle=\sum_{i,j=1}^{4n}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}\otimes
r_{i}r_{j}^{\top}$
$\displaystyle=\sum_{i=1}^{4n}{A^{\prime}}_{i}{A^{\prime}}_{i}^{\top}\otimes
r_{i}r_{i}^{\top}+\sum_{i\neq j}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}\otimes
r_{i}r_{j}^{\top}$
$\displaystyle=({4n-1})\sum_{i=1}^{4n}{A^{\prime}}_{i}{A^{\prime}}_{i}^{\top}-\sum_{i\neq
j}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}$
$\displaystyle=({4n-1})(2nJ_{16n^{2}}-(2nB+({2n-1})(J_{16n^{2}}-I_{16n^{2}}-B))-(2nB+({2n-1})(J_{16n^{2}}-I_{16n^{2}}-B))$
$\displaystyle=({8n^{2}-2n})I_{16n^{2}}+2n(J_{16n^{2}}-I_{16n^{2}}-2B).$

Therefore the Hadamard matrix $D$ is balancedly multi-splittable. ∎

###### The proof of (ii) $\Rightarrow$ (i).

Assume that $H$ is a balancedly multi-splittable Hadamard matrix of order
$16n^{2}$ with respect to the following block form:

$H=\begin{bmatrix}{\bm{1}}&H_{1}&\cdots&H_{{4n+1}}\end{bmatrix},$

where each $H_{i}$ is a $16n^{2}\times{(4n-1)}$ matrix.

######  Lemma 3.6.

For any $i$, $H_{i}H_{i}^{\top}$ is a $({4n-1},-1)$-matrix.

###### Proof.

We show the case $i=1$. Since $H$ is a Hadamard matrix of order $16n^{2}$,
$HH^{\top}=16n^{2}I_{16n^{2}}$, that is,

$J_{16n^{2}}+\sum_{i=1}^{{4n+1}}H_{i}H_{i}^{\top}=16n^{2}I_{16n^{2}}.$

By the assumption of balanced multi-splittabllity, we have that the inner
product of distinct rows of matrices
$\begin{bmatrix}H_{2}&\cdots&H_{{2n+1}}\end{bmatrix}$ or
$\begin{bmatrix}H_{{2n+2}}&\cdots&H_{{4n+1}}\end{bmatrix}$ are $\pm 2n$. Thus,

$\sum_{i=2}^{{2n+1}}H_{i}H_{i}^{\top}={(8n^{2}-2n)}I_{16n^{2}}+2nS,\quad\sum_{i={2n+2}}^{{4n+1}}H_{i}H_{i}^{\top}={(8n^{2}-2n)}I_{16n^{2}}+2nS^{\prime},$

where $S$ and $S^{\prime}$ are $(0,1,-1)$-matrices with diagonal entries $0$
and off-diagonal entries $\pm 1$. Then

$\displaystyle H_{1}H_{1}^{\top}$
$\displaystyle=16n^{2}I_{16n^{2}}-J_{16n^{2}}-({(16n^{2}-4n)}I_{16n^{2}}+2nS+2nS^{\prime})$
$\displaystyle=4nI_{16n^{2}}-J_{16n^{2}}-2n(S+S^{\prime}).$

Since both $S$ and $S^{\prime}$ are $(0,\pm 1)$-matrix, $S+S^{\prime}$ is a
$(0,\pm 2)$-matrix with diagonal entries $0$. However, the off-diagonal
entries of $H_{1}H_{1}^{\top}$ cannot be ${-4n-1}$, $S+S^{\prime}$ is
$(0,-2)$-matrix. Therefore, $H_{1}H_{1}^{\top}$ is a $({4n-1},-1)$-matrix. ∎

For each $i$, consider the matrix
$\tilde{H}_{i}=\begin{bmatrix}{\bm{1}}&H_{i}\end{bmatrix}$. Then, by Lemma
3.6, $\tilde{H}_{i}\tilde{H}_{i}^{\top}$ is a $(4n,0)$-matrix. Since
$\tilde{H}_{i}^{\top}\tilde{H}_{i}=16n^{2}I_{4n}$, the rank of $\tilde{H}_{i}$
is $4n$. Therefore there exist $4n$ rows of $\tilde{H}_{i}$ that correspond to
the rows of a Hadamard matrix $\tilde{K}_{i}$ of order $4n$.

Write $\tilde{K}_{i}=\begin{bmatrix}{\bm{1}}&K_{i}\end{bmatrix}$. Assign a
symbol $j$ to any row in $H_{i}$, which equals the $j$-th row of $K_{i}$. Let
$A$ be the resulting $16n^{2}\times{(4n+1)}$ matrix over the symbol set
$\\{1,\ldots,4n\\}$.

######  Lemma 3.7.

The code $C$ with codewords consisting of the rows of $A$ is an equidistance
code with the number of codewords $16n^{2}$, equidistance $4n$, of length
${4n+1}$.

###### Proof.

It is enough to see the case for the first row and second row. Let the first
and second rows of $H$ be the following forms:

$\displaystyle\begin{bmatrix}1&r_{1,1}&\cdots&r_{1,{4n+1}}\end{bmatrix},$
$\displaystyle\begin{bmatrix}1&r_{2,1}&\cdots&r_{2,{4n+1}}\end{bmatrix}.$

Consider the inner product between them:

$1+\sum_{i=1}^{{4n+1}}r_{1,i}r_{2,i}^{\top}=0.$

By Lemma 3.6, $r_{1,i}r_{2,i}^{\top}\in\\{{4n-1},-1\\}$ for any $i$. Then
there exists $i_{0}$ such that $r_{1,i_{0}}r_{2,i_{0}}^{\top}={4n-1}$ and
$r_{1,i}r_{2,i}^{\top}=-1$ for any $i\neq i_{0}$. Therefore the distance
between the first row and second row is $4n$. ∎

Since the code $C$ attains the upper bound in Lemma 2.3, $A$ is an orthogonal
array OA${}_{1}(16n^{2},{4n+1},4n,2)$. ∎

###  3.2 Proof of Theorem 3.2

###### The proof of (i) $\Rightarrow$ (ii).

Assume that there exists a quaternary Hadamard matrix $H$ of order $2n$. Write
$H$ as

$H=\begin{bmatrix}1&r_{1}\\\ 1&r_{2}\\\ \vdots&\vdots\\\ 1&r_{2n}\\\
\end{bmatrix},$

where $r_{i}$ is a $1\times{(2n-1)}$ matrix for any $i$.

######  Lemma 3.8.

  1. (i)

For any $i$, $r_{i}r_{i}^{*}={2n-1}$.

  2. (ii)

For any distinct $i,j$, $r_{i}r_{j}^{*}=-1$.

Assume that there exists an OA$(4n^{2},{2n+1},2n,2)$, say $A$, of index $1$
over $\\{1,\ldots,2n\\}$. Write $A=\sum_{i=1}^{2n}iA_{i}$, where the $A_{i}$’s
are disjoint $4n^{2}\times{(2n+1)}$ $(0,1)$-matrices. We then define the
$4n^{2}\times{(4n^{2}-1)}$ matrix $D$ by $D=\sum_{i=1}^{2n}A_{i}\otimes r_{i}$
and $\tilde{D}=\begin{bmatrix}{\bm{1}}&D\end{bmatrix}$.

######  Lemma 3.9.

  1. (i)

$DD^{\top}=4n^{2}I_{4n^{2}}-J_{4n^{2}}$.

  2. (ii)

$\tilde{D}$ is a quaternary Hadamard matrix of order $4n^{2}$.

###### Proof.

(i): By Lemma 2.2 and Lemma 3.8,

$\displaystyle DD^{\top}$
$\displaystyle=\sum_{i,j=1}^{2n}A_{i}A_{j}^{\top}\otimes r_{i}r_{j}^{\top}$
$\displaystyle=\sum_{i=1}^{2n}A_{i}A_{i}^{\top}\otimes
r_{i}r_{i}^{\top}+\sum_{i\neq j}A_{i}A_{j}^{\top}\otimes r_{i}r_{j}^{\top}$
$\displaystyle={(2n-1)}\sum_{i=1}^{2n}A_{i}A_{i}^{\top}-\sum_{i\neq
j}A_{i}A_{j}^{\top}$ $\displaystyle={(2n-1)}J_{4n^{2}}+{(2n-1)}\cdot
2nI_{4n^{2}}-2n(J_{4n^{2}}-I_{4n^{2}})$
$\displaystyle=4n^{2}I_{4n^{2}}-J_{4n^{2}}.$

(ii) immediately follows from (i). ∎

Let $A^{\prime}$ be a submatrix of $A$ obtained by restricting the columns to
an $n$ element set. Write $A^{\prime}=\sum_{i=1}^{2n}iA^{\prime}_{i}$, where
$A^{\prime}_{i}$ ($i\in\\{1,\ldots,2n\\}$) are disjoint $4n^{2}\times n$
$(0,1)$-matrices.

######  Lemma 3.10.

There exists a symmetric $(0,1)$-matrix $B$ with diagonal entries $0$ such
that

  1. (i)

$\sum_{i=1}^{2n}{A^{\prime}}_{i}{A^{\prime}}_{i}^{\top}=nJ_{4n^{2}}-(nB+{(n-1)}(J_{4n^{2}}-I_{4n^{2}}-B))$,
and

  2. (ii)

$\sum_{i,j=1,i\neq
j}^{2n}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}=nB+{(n-1)}(J_{4n^{2}}-I_{4n^{2}}-B)$.

###### Proof.

Since the distance matrix of the code of rows of $A^{\prime}$ is
$nB+{(n-1)}(J_{4n^{2}}-I_{4n^{2}}-B)$ with the desired property, the case (i)
follows from Lemma 2.1.

Since $\sum_{i=1}^{2n}{A^{\prime}}_{i}=J_{4n^{2},n}$, we have
$\sum_{i,j=1}^{2n}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}=(\sum_{i=1}^{2n}{A^{\prime}}_{i})(\sum_{j=1}^{2n}{A^{\prime}}_{j}^{\top})=J_{4n^{2},n}J_{n,4n^{2}}=nJ_{4n^{2}}$.
This with (i) shows (ii). ∎

Now we consider $D^{\prime}=\sum_{i=1}^{2n}{A^{\prime}}_{i}\otimes r_{i}$.
Then, by Lemma 3.10,

$\displaystyle D^{\prime}{D^{\prime}}^{\top}$
$\displaystyle=\sum_{i,j=1}^{2n}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}\otimes
r_{i}r_{j}^{\top}$
$\displaystyle=\sum_{i=1}^{2n}{A^{\prime}}_{i}{A^{\prime}}_{i}^{\top}\otimes
r_{i}r_{i}^{\top}+\sum_{i\neq j}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}\otimes
r_{i}r_{j}^{\top}$
$\displaystyle={(2n-1)}\sum_{i=1}^{2n}{A^{\prime}}_{i}{A^{\prime}}_{i}^{\top}-\sum_{i\neq
j}{A^{\prime}}_{i}{A^{\prime}}_{j}^{\top}$
$\displaystyle={(2n-1)}(nJ_{4n^{2}}-(nB+{(n-1)}(J_{4n^{2}}-I_{4n^{2}}-B))-(nB+{(n-1)}(J_{4n^{2}}-I_{4n^{2}}-B))$
$\displaystyle={(2n^{2}-n)}I_{4n^{2}}+n(J_{4n^{2}}-I_{4n^{2}}-2B).$

Therefore the quaternary Hadamard matrix $D$ is balancedly multi-splittable. ∎

###### The proof of (ii) $\Rightarrow$ (i).

Assume that $H$ is a balancedly multi-splittable quaternary Hadamard matrix of
order $4n^{2}$ with respect to the following block form:

$H=\begin{bmatrix}{\bm{1}}&H_{1}&\cdots&H_{{2n+1}}\end{bmatrix},$

where each $H_{i}$ is a $4n^{2}\times{(2n-1)}$ matrix.

######  Lemma 3.11.

For any $i$, $H_{i}H_{i}^{*}$ is a $({2n-1},-1)$-matrix.

###### Proof.

We show the case $i=1$. Since $H$ is a quaternary Hadamard matrix of order
$4n^{2}$, $HH^{*}=4n^{2}I_{4n^{2}}$, that is,

$J_{4n^{2}}+\sum_{i=1}^{{2n+1}}H_{i}H_{i}^{*}=4n^{2}I_{4n^{2}}.$

By the assumption of balanced multi-splittabllity, we have that the inner
product of distinct rows of matrices
$\begin{bmatrix}H_{2}&\cdots&H_{{n+1}}\end{bmatrix}$ or
$\begin{bmatrix}H_{{n+2}}&\cdots&H_{{2n+1}}\end{bmatrix}$ are $\pm 2n,\pm 2i$.
Thus,

$\sum_{i=2}^{{n+1}}H_{i}H_{i}^{*}={(2n^{2}-n)}I_{4n^{2}}+nS,\quad\sum_{i={n+2}}^{{2n+1}}H_{i}H_{i}^{*}={(2n^{2}-n)}I_{4n^{2}}+nS^{\prime},$

where $S$ and $S^{\prime}$ are $(0,\pm 1,\pm i)$-matrix with diagonal entries
$0$ and off-diagonal entries $\pm 1,\pm i$. Then

$\displaystyle H_{1}H_{1}^{*}$
$\displaystyle=4n^{2}I_{4n^{2}}-J_{4n^{2}}-({(4n^{2}-2n)}I_{100}+nS+nS^{\prime})$
$\displaystyle=2nI_{4n^{2}}-J_{4n^{2}}-n(S+S^{\prime}).$

Since both $S$ and $S^{\prime}$ are $(0,\pm 1,\pm i)$-matrix, $S+S^{\prime}$
is a $(0,\pm 2,\pm 2i)$-matrix with diagonal entries $0$. However, the
absolute values of off-diagonal entries of $H_{1}H_{1}^{*}$ cannot exceed
${2n-1}$, $S+S^{\prime}$ is $(0,-2)$-matrix. Therefore, $H_{1}H_{1}^{*}$ is a
$({2n-1},-1)$-matrix. ∎

For each $i$, consider the matrix
$\tilde{H}_{i}=\begin{bmatrix}{\bm{1}}&H_{i}\end{bmatrix}$. Then, by Lemma
3.11, $\tilde{H}_{i}\tilde{H}_{i}^{*}$ is a $(2n,0)$-matrix. Since
$\tilde{H}_{i}^{*}\tilde{H}_{i}=4n^{2}I_{2n}$, the rank of $\tilde{H}_{i}$ is
$2n$.

Therefore there exist $4n$ rows of $\tilde{H}_{i}$ that correspond to the rows
of a Hadamard matrix $\tilde{K}_{i}$ of order $4n$.

Therefore there exist $2n$ rows of $\tilde{H}_{i}$ that correspond to the rows
of a Hadamard matrix $\tilde{K}_{i}$ of order $2n$.

Write $\tilde{K}_{i}=\begin{bmatrix}{\bm{1}}&K_{i}\end{bmatrix}$. Assign a
symbol $j$ to any row in $H_{i}$, which equals the $j$-th row of $K_{i}$. Let
$A$ be the resulting $4n^{2}\times{(2n+1)}$ matrix over the symbol set
$\\{1,\ldots,2n\\}$.

######  Lemma 3.12.

The code $C$ with codewords consisting of the rows of $A$ is an equidistance
code with the number of codewords $4n^{2}$, equidistance $2n$, of length
${2n+1}$.

###### Proof.

It is enough to see the case for the first row and second row. Let the first
and second rows of $H$ be the following forms:

$\displaystyle\begin{bmatrix}1&r_{1,1}&\cdots&r_{1,{2n+1}}\end{bmatrix},$
$\displaystyle\begin{bmatrix}1&r_{2,1}&\cdots&r_{2,{2n+1}}\end{bmatrix}.$

Consider the inner product between them:

$1+\sum_{i=1}^{{2n+1}}r_{1,i}r_{2,i}^{*}=0.$

By Lemma 3.11, $r_{1,i}r_{2,i}^{*}\in\\{{2n-1},-1\\}$ for any $i$. Then there
exists $i_{0}$ such that $r_{1,i_{0}}r_{2,i_{0}}^{*}={2n-1}$ and
$r_{1,i}r_{2,i}^{*}=-1$ for any $i\neq i_{0}$. Therefore the distance between
the first row and second row is $2n$. ∎

Since the code $C$ attains the upper bound in Lemma 2.3, $A$ is an orthogonal
array OA${}_{1}(4n^{2},{2n+1},2n,2)$. ∎

##  4 Example

In this section, we present an example of balancedly multi-splittable Hadamard
matrices following the construction in Theorem 3.1.

######  Example 4.1.

Take an OA${}_{1}(16,5,4,2)$ $A$ and a Hadamard matrix $H$ of order $4$ as:

$\displaystyle A^{\top}$
$\displaystyle=\sum_{i=1}^{4}A_{i}^{\top}=\left[\begin{array}[]{cccccccccccccccc}1&1&1&1&2&2&2&2&3&3&3&3&4&4&4&4\\\
1&2&3&4&1&2&3&4&1&2&3&4&1&2&3&4\\\ 1&2&3&4&2&1&4&3&3&4&1&2&4&3&2&1\\\
1&2&3&4&3&4&1&2&4&3&2&1&2&1&4&3\\\ 1&2&3&4&4&3&2&1&2&1&4&3&3&4&1&2\\\
\end{array}\right],$ $\displaystyle H$
$\displaystyle=\begin{bmatrix}1&r_{1}\\\ 1&r_{2}\\\ 1&r_{3}\\\ 1&r_{4}\\\
\end{bmatrix}=\left[\begin{array}[]{cccc}1&1&1&1\\\ 1&-1&1&-1\\\ 1&1&-1&-1\\\
1&-1&-1&1\\\ \end{array}\right].$

Then the matrix $D$ constructed in Theorem 3.1 is a balancedly multi-
splittable Hadamard amtrix of order $16$:

$\displaystyle D$ $\displaystyle=\sum_{i=1}^{4}A_{i}\otimes r_{i}$
$\displaystyle=\begin{bmatrix}{\bm{1}}&H_{1}&H_{2}&H_{3}&H_{4}&H_{5}\end{bmatrix}$
$\displaystyle=\left[\begin{array}[]{c|ccc|ccc|ccc|ccc|ccc}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\\
1&1&1&1&-1&1&-1&-1&1&-1&-1&1&-1&-1&1&-1\\\
1&1&1&1&1&-1&-1&1&-1&-1&1&-1&-1&1&-1&-1\\\
1&1&1&1&-1&-1&1&-1&-1&1&-1&-1&1&-1&-1&1\\\
1&-1&1&-1&1&1&1&-1&1&-1&1&-1&-1&-1&-1&1\\\
1&-1&1&-1&-1&1&-1&1&1&1&-1&-1&1&1&-1&-1\\\
1&-1&1&-1&1&-1&-1&-1&-1&1&1&1&1&-1&1&-1\\\
1&-1&1&-1&-1&-1&1&1&-1&-1&-1&1&-1&1&1&1\\\
1&1&-1&-1&1&1&1&1&-1&-1&-1&-1&1&-1&1&-1\\\
1&1&-1&-1&-1&1&-1&-1&-1&1&1&-1&-1&1&1&1\\\
1&1&-1&-1&1&-1&-1&1&1&1&-1&1&-1&-1&-1&1\\\
1&1&-1&-1&-1&-1&1&-1&1&-1&1&1&1&1&-1&-1\\\
1&-1&-1&1&1&1&1&-1&-1&1&-1&1&-1&1&-1&-1\\\
1&-1&-1&1&-1&1&-1&1&-1&-1&1&1&1&-1&-1&1\\\
1&-1&-1&1&1&-1&-1&-1&1&-1&-1&-1&1&1&1&1\\\
1&-1&-1&1&-1&-1&1&1&1&1&1&-1&-1&-1&1&-1\\\ \end{array}\right].$

######  Remark 4.2.

There exist no balancedly multi-splittable quaternary Hadamard matrices of
orders 36 and 100.

## Acknowledgments.

Useful conversations with Professor Tayfeh-Rezaie is appreciated. Hadi
Kharaghani is supported by the Natural Sciences and Engineering Research
Council of Canada (NSERC). Sho Suda is supported by JSPS KAKENHI Grant Number
18K03395, 22K03410.

## References

  * [1] K. A. Bush, Unbalanced Hadamard matrices and finite projective planes of even order, J. Combin. Theory Ser. A, 11 (1971), 38–44.
  * [2] F. C. Bussemaker, W. H. Haemers, Edward Spence, The search for pseudo orthogonal Latin squares of order six. Special issue dedicated to Dr. Jaap Seidel on the occasion of his 80th birthday (Oisterwijk, 1999). Des. Codes Cryptogr. 21 (2000), no. 1-3, 77–82.
  * [3] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. 10 (Suppl.) (1973).
  * [4] J. Jedwab, S. Li, S. Simon, Constructions and restrictions for balanced splittable Hadamard matrices, arXiv:2207.03619.
  * [5] H. Kharaghani, T. Pender, S Suda, A family of balanced generalized weighing matrices, Combinatorica, (2022). https://doi.org/10.1007/s00493-021-4774-4
  * [6] H. Kharaghani, T. Pender, S. Suda, Balancedly splittable orthogonal designs and equiangular tight frames, Des. Codes Cryptogr., 89 (2021), 2033–2050.
  * [7] H. Kharaghani, S. Suda, Balancedly splittable Hadamard matrices, Discrete Math., 342 (2019), 546–561.
  * [8] C. W. H. Lam, L. Thiel, S. Swiercz, The nonexistence of finite projective planes of order 10. Canad. J. Math. 41 (1989), no. 6, 1117–1123.
  * [9] C. W. H. Lam, The search for a finite projective plane of order 10, Amer. Math. Monthly 98 (1991), 305–318.
  * [10] H. J. Ryser, The factors of a design matrix, J. Combin. Theory Ser. A, 22 (1977), 181–193.
  * [11] E. Verheiden, Hadamard matrices and projective planes, J. Combin. Theory Ser. A, 32 (1982), 126–131.