# Tree Independence Number IV.
Even-hole-free Graphs

Maria Chudnovsky † Princeton University, Princeton, NJ, USA. Supported by NSF-
EPSRC Grant DMS-2120644 and by AFOSR grant FA9550-22-1-0083. Peter Gartland
University of California, Santa Barbara, USA.  Sepehr Hajebi University of
Waterloo, Waterloo, Ontario, Canada. We acknowledge the support of the Natural
Sciences and Engineering Research Council of Canada (NSERC), [funding
reference number RGPIN-2020-03912]. Cette recherche a été financée par le
Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG),
[numéro de référence RGPIN-2020-03912]. This project was funded in part by the
Government of Ontario. This research was conducted while Spirkl was an Alfred
P. Sloan Fellow. Daniel Lokshtanov22footnotemark: 2 Sophie
Spirkl33footnotemark: 3

###### Abstract

We prove that the tree independence number of every even-hole-free graph is at
most polylogarithmic in its number of vertices. More explicitly, we prove that
there exists a constant $c>0$ such that for every integer $n>1$ every
$n$-vertex even-hole-free graph has a tree decomposition where each bag has
stability (independence) number at most $c\log^{10}n$. This implies that the
Maximum Weight Independent Set problem, as well as several other natural
algorithmic problems that are known to be NP-hard in general, can be solved in
quasi-polynomial time if the input graph is even-hole-free.

##  1 Introduction

A graph $G$ even-hole-free if $G$ does not contain a cycle of even length as
an induced subgraph. Here an induced subgraph of a graph $G$ is a graph that
can be obtained from $G$ by deleting vertices (and all edges incident to the
deleted vertices), the length of a cycle (or path) is the number of edges in
it, and a hole in $G$ in an induced subgraph that is a cycle of length at
least four. The class of even-hole-free graphs has attracted much attention
due to its somewhat tractable, yet quite rich structure [17, 20, 46]. In
particular the structure of even-hole-free graphs has some similarities [46]
with the structure of perfect graphs, which by the strong perfect graph
theorem [16] are precisely the graphs that are odd-hole-free and whose
complement is odd-hole-free. In addition to their structure, much effort was
put into designing efficient algorithms for even-hole-free graphs (to solve
problems that are NP-hard in general). This is discussed in the survey [46],
while [1, 12, 19, 38] provide examples of more recent work. We now consider
some of the problems that have received the most attention on even-hole free
graphs.

A vertex set $S$ of a graph $G$ is stable (or independent) if no two vertices
of $S$ have an edge between them. A clique is a set $S$ if vertices such that
every pair of vertices of $S$ has an edge between them. A proper $k$-coloring
of $G$ is a partition of the vertex set of $G$ into (at most) $k$ independent
sets. In the Maximum Weight Independent Set (Maximum Weight Clique) problem,
the input is a graph $G$ and a weight function that assigns to each vertex an
integer weight. The task is to find a stable set (clique) $S$ in $G$ of
maximum weight. In the $k$-Coloring problem, the input is a graph $G$, the
task is to determine whether $G$ has a proper $k$-coloring. Finally, in the
Coloring problem, the input is a graph $G$ and the task determine the minimum
$k$ such that $G$ has a proper $k$-coloring. All of the above mentioned
problems are known to be NP-hard [32, 36] On even-hole-free graphs, Maximum
Weight Clique is known to be polynomial-time solvable [46]. The questions of
whether or not there exist polynomial time algorithms for Maximum Weight
Independent Set and Coloring remain open. This is in stark contrast to perfect
graphs, for which polynomial time algorithms for these problems have been
known since 1981 [34].

This discrepancy is somewhat surprising, to explain why (and to state our main
result) we need to define tree decompositions and treewidth. For a graph
$G=(V(G),E(G))$, a _tree decomposition_ $(T,\chi)$ of $G$ consists of a tree
$T$ and a map $\chi:V(T)\to 2^{V(G)}$ with the following properties:

  * •

For every $v_{1}v_{2}\in E(G)$, there exists $t\in V(T)$ with
$v_{1},v_{2}\in\chi(t)$.

  * •

For every $v\in V(G)$, the subgraph of $T$ induced by $\\{t\in V(T)\mid
v\in\chi(t)\\}$ is non-empty and connected.

The _width_ of a tree decomposition $(T,\chi)$, denoted by
$\operatorname{width}(T,\chi)$, is $\max_{t\in V(T)}|\chi(t)|-1$. The
_treewidth_ of $G$, denoted by $\operatorname{tw}(G)$, is the minimum width of
a tree decomposition of $G$. Bounded treewidth is a useful graph property from
both a structural [41] and an algorithmic [10] perspective. For example
Maximum Weight Independent Set, Maximum Weight Clique, $k$-Coloring (for every
fixed $k$) and a host of other problems are known to admit $O(c^{t}n)$ time
algorithms on graphs of treewidth at most $t$ [21, 28, 31], while Coloring is
known to admit $O(t^{t+O(1)}n)$ time algorithms on graphs of treewidth at most
$t$.

From the perspective of tree decompositions and treewidth, perfect graphs
appear much more intractable than even-hole-free graphs. On one hand there
exist triangle-free (a triangle is a clique on $3$ vertices) perfect graphs
whose treewidth is linear in the number of vertices in the graph: the complete
bipartite graph $K_{t,t}$, consisting of two stable sets $L$ and $R$ of size
$t$ with an edge connecting every vertex in $L$ with every vertex in $R$, is
an example. On the other hand, triangle-free even-hole-free graphs have
constant treewidth [12]. Sintiari and Trotignon [44] give a construction of
arbitrarily large $K_{4}$-free ($K_{t}$ is the clique on $t$ vertices) even-
hole-free graphs whose treewidth is logaritmic in the number of vertices. This
led Sintiari and Trotignon [44] to conjecture that for every $t$ there exists
a constant $c_{t}$ such that every $n$-vertex $K_{t}$-free and even-hole-free
graph has treewidth at most $c_{t}\log n$. This conjecture was very recently
confirmed by Chudnovsky et al. [13]. The logarithmic treewidth bound of
Chudnovsky et al. [13] immediately implies that $k$-Coloring can be solved in
polynomial time for every fixed $k$ on even-hole-free graphs.

An early step of the proof of Chudnovsky et al. [13] is to prove that even-
hole-free graphs admit “dominated balanced separators”. More precisely they
show that there exists a constant $c$ such that every even-hole-free graph
contains a vertex set $S$ of size at most $c$ such that every connected
component of $G-N[S]$ has at most $n/2$ vertices. Here $N[S]$ is the closed
neighborhood of $S$, namely the set of all vertices in $S$ and all vertices
with at least one neighbor in $S$. A fairly direct consequence of this result
(based on an argument of Chudnovsky et al. [15]) is that for every
$\epsilon>0$ there exists a $(1+\epsilon)$-approximation algorithm for Maximum
Weight Independent Set which runs in quasi-polynomial time. Here an algorithm
runs in quasi-polynomial time if the running time is upper bounded by
$2^{O(\log^{c}n)}$ for some constant $c$. Nevertheless, this is fully
consistent with Maximum Weight Independent Set on even-hole-free graphs being
NP-hard, and so the complexity of Maximum Weight Independent Set and Coloring
on even-hole-free graphs remain open.

Our results. We prove a structural result which implies that Maximum Weight
Independent Set, as well as a host of other problems, admit quasi-polynomial
time algorithms on even-hole-free graphs. To state our main result we need one
more notion, that of tree independence number. This is a relatively new width
parameter, defined by Dallard, Milanič and Štorgel [25], in the second of a
series of papers [22, 23, 24, 25, 26] aiming to identify graphs whose large
treewidth can be completely explained by the presence of a large clique. The
tree independence number of a tree decomposition $(T,\chi)$ is the maximum
over all $t\in V(T)$ of the maximum stable set size of the subgraph
$G[\chi(t)]$ of $G$ induced by $\chi(t)$. The tree independence number of a
graph $G$ is the minimum tree independence number of a tree decomposition of
$G$. We are now ready to state our main result.

######  Theorem 1.1.

There exists a constant $c$ such that for every integer $n>1$ every $n$-vertex
even-hole-free graph has tree independence number at most $c\log^{10}n$.

Since the only construction of even-hole-free graphs with large treewidth
known to date is the construction of [44], where all graphs have clique number
at most four and have treewidth logarithmic in the number of vertices, we do
not know if the bound of Theorem 1.1 is asymptotically tight, or whether the
exponent of $\log n$ can be reduced. Dallard et al. [22] gave an algorithm
that takes as input a graph $G$ and integer $k$, runs in time
$2^{O(k^{2})}n^{O(k)}$ and either outputs a tree decomposition of $G$ with
independence number at most $8k$, or determines that the tree-independence
number of $G$ is larger than $k$. Using this algorithm, Theorem 1.1 can be
made constructive in the sense that there exists an algorithm which takes as
input an even-hole-gree graph, runs in time $2^{O(\log^{20}n)}$ and computes a
tree decomposition of $G$ with tree independence $O(\log^{10}n)$.

Theorem 1.1 implies the main result of [13] with a $O(\log^{10}n)$ instead of
logarithmic bound on the treewidth. Indeed, let $G$ be a $K_{t}$-free even-
hole free graph, and let $(T,\chi)$ be the tree decomposition obtained from
Theorem 1.1. We claim that this decomposition has width $O(\log^{10}n)$. This
follows from the fact that every even-hole-free graph on at least $2\alpha t$
vertices either has a clique of size at least $t$ or a stable set of size at
least $\alpha$ [17]. Thus every bag of the decomposition must have size at
most $c\log^{10}n\cdot 2t$.

A number of problems can be solved efficiently when a tree decomposition of
the input graph of low independence number is given as input. This is
discussed in more detail in [14] and [39]. We will not repeat the discussion
here, but only list some of the problems that can be solved in quasi-
polynomial time in the class of even-hole-free graphs as a direct consequence
of Theorem 1.1, the above mentioned approximation algorithm of Dallard et al.
[22], and existing algorithms when a tree decomposition of the input graph of
low independence number (or low width) is given as input.

######  Theorem 1.2.

For every integer $k\geq 0$, the following problems admit quasi-polynomial
time time algorithms on even-hole free graphs:

  * •

Maximum Weight Independent Set,

  * •

Weighted Feedback Vertex Set,

  * •

Weighted Odd cycle transversal,

  * •

Maximum Weight Induced Path,

  * •

Maximum Weight Induced Matching,

  * •

Maximum Weight Induced Subgraph of Treewidth at most $k$,

  * •

$k$-coloring.

Resolving the complexity status of Maximum Weight Independent Set on even-
hole-free graphs has been stated as an open problem a number of times [2, 12,
19, 35, 38], and the complexity of Feedback Vertex Set on even-hole-free
graphs has been posed at least once [45]. Even though Theorem 1.2 does not
fully resolve these open problems, it offers a partial resolution in the
following sense. If an NP-hard problem has a quasi-polynomial-time algorithm
then every problem in NP has a quasi-polynomial-time algorithm. Thus Theorem
1.2 implies that, unless a highly unexpected complexity theoretic collapse
occurs, none of the above problems are NP-hard in even-hole-free graphs. It
remains an intriguing and challenging open problem to design polynomial time
algorithms for the problems in Theorem 1.2 (with the exception of
$k$-coloring, for which a polynomial time algorithm was recently found [13])
on even-hole-free graphs. Polynomial time algorithms for these problems would
require significant new ideas. Indeed, even if the exponent of $\log n$ in
Theorem 1.1 were reduced to 1, the resulting algorithms would still take
quasi-polynomial (rather than polynomial) time.

It is worth noting that Feedback Vertex Set, Maximum Weight Induced Path, and
Maximum Weight Induced Matching are all NP-hard on bipartite graphs, and
therefore on perfect graphs. This partially confirms the intuition that even-
hole-free graphs should be more algorithmically tractable than perfect graphs.

All of the results of Theorem 1.2 (except for $k$-Coloring) can be derived
from the following theorem. The theorem uses Counting Monadic Second Order
Logic (CMSO2), which is a useful formalism to express properties of graphs and
vertex and edge sets [11, 39]. We refer the reader to Lima et al. [39] for an
introduction to CMSO2 logic.

######  Theorem 1.3.

For every integer $\ell$ and CMSO2 formula $\phi$, there exists an algorithm
that takes as input an even-hole-free graph $G$ and a weight function
$w:V(G)\rightarrow\mathbb{N}$, runs in time
$(f(\phi,\ell)n)^{O(\ell\log^{10}n)}$ and outputs a maximum weight vertex
subset $S$ such that $G[S]$ has treewidth at most $\ell$ and
$G[S]\models\phi$.

Theorem 1.3 is obtained from Theorem 1.1 in (exactly) the same way as
Chudnovsky et al. [14] obtain their algorithmic consequences (Theorem 8.2 of
[14]) from their bound on the tree independence number (Theorem 1.2 of [14])
of $3$PC-free graphs. The algorithm for Odd Cycle Transversal in Theorem 1.2
follows from Theorem 1.3 because on even-hole-free graphs, Odd Cycle
Transversal and Feedback Vertex Set are the same problem.

The quasi-polynomial time algorithm of Theorem 1.2 for $k$-Coloring follows
from the fact that $K_{k+1}$ is not $k$-colorable, the $O(k^{t+O(1)}n)$ time
algorithm for $k$-Coloring on graphs of treewidth $t$ [21], and the
$O(\log^{10}n)$ treewidth bound on $K_{t}$-free even-hole free graphs which
follows from Theorem 1.1)

The list of problems in Theorem 1.2 for which Theorem 1.3 implies a quasi-
polynomial-time algorithm is by no means exhaustive. For an example Theorem
1.3 also yields a quasi-polynomial time algorithm to recognize even-hole-free
graphs (since we can encode in CMSO2 that $G[S]$ is a cycle of even length).
We refer the reader to [14] and [39].

Comparison with the Algorithmic Consequences of [13]: It is worth comparing
the algorithmic consequences of Theorem 1.1 with those of the logarithmic
treewidth bound for $K_{t}$-free graphs in [13]. The logarithmic treewidth
bound for $K_{t}$-free even-hole-free graphs in [13] typically leads to
polynomial time algorithms for problems on $K_{t}$-free even-hole-free graphs.
With the exception of $k$-Coloring, for which this leads to a polynomial time
algorithm on even-hole-free graphs, for other problems the results on
$K_{t}$-free even-hole-free graphs only lead to polynomial (or quasi-
polynomial) time approximation schemes on even-hole-free graphs. On the other
hand, Theorem 1.1 readily leads to quasi-polynomial time exact algorithms on
even-hole-free graphs (and hence shows that the considered problems are
unlikely to be NP-hard), but does not appear to give any meaningful polynomial
time algorithms (neither exact nor approximation).

Organization of the paper. In Section 2 we define the notations and basic
definitions used in the paper. In Section 3 we give a brief outline of the
proof of Theorem 1.1. The remainder of the paper concerns the proof of Theorem
1.1.

##  2 Preliminaries

All graphs in this paper are finite and simple and all logarithms are base
$2$. We begin with some standard definitions (see, for example, [13]). Let
$G=(V(G),E(G))$ be a graph. In this paper, we use induced subgraphs and their
vertex sets interchangeably. For a graph $G$ and vertex set $S$, the graph
$G\setminus S$ is the graph obtained from $G$ by deleting all vertices in $S$
and all edges incident to at least one vertex in $S$. The subgraph of $G$
induced by $S$ is denoted by $G[S]$ and defined as
$G[S]=G\setminus(V(G)\setminus S)$. For graphs $G,H$ we say that $G$ contains
$H$ if $H$ is isomorphic to an induced subgraph of $G$. We say that $G$ is
$H$-free if $G$ does not contain $H$. For a set $\mathcal{H}$ of graphs, $G$
is $\mathcal{H}$-free if $G$ is $H$-free for every $H\in\mathcal{H}$.

Let $v\in V(G)$. Let $X\subseteq V(G)$. We denote by $N_{G}(X)$ the set of all
vertices in $V(G)\setminus X$ with at least one neighbor in $X$. We also
define $N_{G}[X]=N_{G}(X)\cup X$. When $X=\\{v\\}$, we write $N_{G}(v)$ for
$N_{G}(\\{v\\})$ and $N_{G}[v]$ for $N_{G}[\\{v\\}]$. If there is no danger of
confusion, we omit the subscript $G$. If $H$ is an induced subgraph of $G$,
then $N_{H}(X)=N(X)\cap H$ and $N_{H}[X]=N_{H}(X)\cup X$. Let $Y\subseteq
V(G)$ be disjoint from $X$. We say $X$ is complete to $Y$ if every vertex in
$X$ is adjacent to every vertex in $Y$ in $G$, and $X$ is _anticomplete_ to
$Y$ if there are no edges between $X$ and $Y$.

A path in a graph is an induced subgraph that is a path. Given a path $P$ with
ends $a,b$, the interior of $P$, denoted by $P^{*}$, is the set
$P\setminus\\{a,b\\}$. The length of a path or a hole is the number of edges
in it. A hole is _even_ if its length is even. A graph is even-hole-free it
contains no even holes.

The stability (or independence) number $\alpha(G)$ of $G$ is the maximum size
of a stable set in $G$. A related parameter, the clique cover number
$\kappa(G)$ of $G$, is the smallest number of cliques whose union equals
$V(G)$.

Next, we define a slight generalization of even-hole-free graphs; we need the
following definitions (see, for example, [13]). A _theta_ is a graph
consisting of three internally vertex-disjoint paths
$P_{1}=a\hbox{-}\cdots\hbox{-}b$, $P_{2}=a\hbox{-}\cdots\hbox{-}b$, and
$P_{3}=a\hbox{-}\cdots\hbox{-}b$, each of length at least 2, such that
$P_{1}^{*},P_{2}^{*},P_{3}^{*}$ are pairwise anticomplete. We call $a$ and $b$
the ends of the theta and $P_{1},P_{2},P_{3}$ the _paths_ of the theta. A
near-prism is a graph consisting of two triangles $\\{a_{1},a_{2},a_{3}\\}$
and $\\{b_{1},b_{2},b_{3}\\}$, and three paths $P_{i}$ from $a_{i}$ to $b_{i}$
for $1\leq i\leq 3$, and such that $P_{i}\cup P_{j}$ is a hole for every
$i,j\in\\{1,2,3\\}$. It follows that $P_{1}^{*},P_{2}^{*},P_{3}^{*}$ are
pairwise disjoint and anticomplete to each other,
$|\\{a_{1},a_{2},a_{3}\\}\cap\\{b_{1},b_{2},b_{3}\\}|\leq 1$, and if
$|\\{a_{1},a_{2},a_{3}\\}\cap\\{b_{1},b_{2},b_{3}\\}|=1$, then two of the
paths have length at least 2. Moreover, the only edges between $P_{i}$ and
$P_{j}$ are $a_{i}a_{j}$ and $b_{i}b_{j}$. A prism is a near-prism whose
triangles are disjoint. A _wheel_ in $G$ is a pair $(H,x)$ where $H$ is a hole
and $x$ is a vertex with at least three neighbors in $H$. The vertex $x$ is
called the center of the wheel $(H,x)$. A wheel $(H,x)$ is even if $x$ has an
even number of neighbors on $H$. Let $\mathcal{C}$ be the class of ($C_{4}$,
theta, prism, even wheel)-free graphs (these are sometimes called
“$C_{4}$-free odd-signable graphs”). Every even-hole-free graph belongs to
$\mathcal{C}$. For every integer $t\geq 1$, let $\mathcal{C}_{t}$ be the class
of all graphs in $\mathcal{C}$ with no clique of size $t$.

A wheel $(H,x)$ is proper if $\alpha(N(x)\cap H)$ is at least three. A pyramid
is a graph consisting of a vertex $a$ and a triangle
$\\{b_{1},b_{2},b_{3}\\}$, and three paths $P_{i}$ from $a$ to $b_{i}$ for
$1\leq i\leq 3$, such that $P_{i}\cup P_{j}$ is a hole for every
$i,j\in\\{1,2,3\\}$. It follows that $P_{1}\setminus a,P_{2}\setminus
a,P_{3}\setminus a$ are pairwise disjoint, and the only edges between them are
of the form $b_{i}b_{j}$. It also follows that at most one of
$P_{1},P_{2},P_{3}$ has length exactly 1. We say that $a$ is the apex of the
pyramid and that $b_{1}b_{2}b_{3}$ is the base of the pyramid.

##  3 Proof Outline

We give here the main ideas of the proof. We will not concern ourselves with
the exponent of $\log n$ in our bound and simply show that the tree
independence number of $G$ is polylogarithmic in $n$. The high level
scaffolding of the proof is quite similar to the proof of [13] that
$K_{t}$-free even-hole-free graphs have logarithmic treewidth. However most of
the individual high level pieces of the proof differ substantially from the
corresponding step in [13] and require significant new ideas.

The proof of [13] that every $K_{t}$-free graph has treewidth $O(\log n)$ goes
as follows: first it is proved that even-hole-free graphs admit “dominated
balanced separators”. In particular there exists a constant $c$ such that
every even-hole-free graph contains a vertex set $S$ of size at most $c$ such
that every connected component of $G-N[S]$ has at most $n/2$ vertices. This
fact is then used to show that, in order to obtain the treewidth bound, it is
sufficient to show that every pair of non-adjacent vertices $a$, $b$ in a
$K_{t}$-free even-hole free graph can be separated from each other by a set of
size at most $c_{t}\log n$ for a constant $c_{t}$ depending only on $t$. The
most technical part of the argument is then to show the existence of such
small $a$-$b$ separators.

The first step of the proof of [13], that even-hole-free graphs admit
dominated balanced separators, does not use the assumption that $G$ is
$K_{t}$-free and hence we can use it here. Using the dominated balanced
separator bound we then show an analog of the second step of [13] tailored to
tree independence number rather than treewidth: we show that in order to
obtain the tree independence number bound, it is sufficient to prove that
every pair of non-adjacent vertices $a$, $b$ in an even-hole-free graph can be
separated from each other by a set with independence number $O(\log
n^{O(1)})$. Here we cannot re-use the proof from [13] because that proof
crucially uses the assumption that $G$ is $K_{t}$-free. However we can
directly apply a similar step from [14]. Thus, “all” that remains is to prove
the following statement:

######  Theorem 3.1.

There exists a constant $c$ with the following property. Let $G$ be an even-
hole-free graph with $|V(G)|=n$, and let $a,b\in V(G)$ be non-adjacent. Then
there is a set $X\subseteq V(G)\setminus\\{a,b\\}$ with $\kappa(X)\leq
c\log^{8}n$ and such that every component of $G\setminus X$ contains at most
one of $a,b$.

In Theorem 3.1, the clique cover number $\kappa$ of the separator $X$ is
bounded rather than the independence number $\alpha$ because that is what
naturally comes out of the proof. Obtaining a separator $X$ with
polylogarithmic independence number would also have been sufficient. Let us
now not worry too much about the exponent $8$ in the statement of Theorem 3.1,
and simply aim for a polylogarithmic bound on $\kappa$.

Towards this goal we employ a recent tool of Korchemna et al. [37], who
provide a “max flow-min cut” like theorem for clique separators. Applying this
theorem to even-hole-free graphs (and using that even-hole-free graphs are
$K_{2,2}$-free and therefore have only polynomially many maximal cliques [30])
we get one of two outcomes. Either we get an $a$-$b$ separator $X$ with a
polylogaritmic upper bound on $\kappa(X)$, this is the desired outcome, or we
get a set of $f$ paths $P_{1},\ldots,P_{f}$ from $a$ to $b$ such that no
clique of $G-\\{a,b\\}$ intersects more than $O(\log n)$ of the paths. Here
$f$ can be chosen to be an arbitrarily large polylogarithmic function of $n$
(and the larger we choose $f$, the worse bound we get on $\kappa(X)$).

Observe that the graph $G^{\prime}$ induced by all of these $a$-$b$ paths
$P_{1},\ldots,P_{f}$ is $K_{t}$-free, where $t=O(\log n)$. Indeed, every
vertex of a clique $K$ in $G^{\prime}$ must be on some $a$-$b$ path (by the
definition of $G^{\prime}$), and no path can contain more than $2$ vertices of
$K$ (since the path is induced), so $K$ must intersect at least $|K|/2$ paths.
It follows that $G^{\prime}$ is $K_{t}$-free where $t=O(\log n)$.

If only the constant $c_{t}$ in the $c_{t}\log n$ bound on the size of an
$a$-$b$ separator from [13] depended polynomially on $t$ we would be done!
Indeed, we could then have chosen $f$ to be so large that
$f\geq(c_{t}\cdot\log n)\cdot\log^{2}n$, and get an $a$-$b$ separator $X$ in
$G^{\prime}$ of size at most $c_{t}\cdot\log n$. But then some vertex of $X$
intersects at least $\log^{2}n$ of the paths, contradicting that no clique
intersects more than $O(\log n)$ of them.

Unfortunately the constant $c_{t}$ in the proof of [13] does not depend
polynomially on $t$, and it does not look like an easy task to improve the
dependence to a polynomial in $t$. However, the argument above works out just
fine even if $c_{t}$ is not a constant but rather a polynomial in $t$ and
$\log n$. Hence, in order to prove Theorem 3.1 it is sufficient to prove that,
for every $K_{t}$-free graph, every pair $a,b$ of vertices can be separated by
a set $X$ of size polynomial in $t$ and $\log n$. This is precisely the
approach that we take, this is the most involved part of our arguments.

#### Separating Two Vertices

We now sketch the main ideas of the proof of Theorem 13.1: that for every
$K_{t}$-free graph every pair $a$ and $b$ of vertices can be separated by a
set $X$ of size polynomial in $t$ and $\log n$. We start by sketching how we
would have liked the proof to work, point to where this approach breaks, and
then outline how the proof actually works.

We wish to separate $a$ from $b$. We will concentrate on the neighborhood
$N(a)$ of $a$. Let $D$ be the component of $G-N[a]$ that contains $b$, we can
safely ignore the vertices in $N(a)\setminus N(D)$ and focus on the vertices
in $N(D)$. As long as $N(D)$ contains a clique that covers at least $0.1\%$ of
$N(D)$ we can add this clique to $X$ since we only can do this step $O(\log
n)$ many times. After this step, “many” (i.e., at least $99\%$) of vertex
triples $x_{1}$, $x_{2}$, $x_{3}$ in $N(a)\cap N(D)$ are stable (this follows
from, e.g., [17]).

For a stable triple $x_{1},x_{2},x_{3}$ let $D^{\prime}$ be an inclusion
minimal connected subset of $D$ that contains neighbors of $x_{1}$, $x_{2}$
and $x_{3}$, and let $H=\\{a,x_{1},x_{2},x_{3}\\}\cup D^{\prime}$. A simple
case analysis shows that $\\{a,x_{1},x_{2},x_{3}\\}\cup D^{\prime}$ is either
a pyramid or a wheel. We show in Section 4 that if $H$ is a pyramid, then
either there is a clique $K$ in $D$ that separates at least two vertices of
$\\{x_{1},x_{2},x_{3}\\}$ from $b$ in $(\\{x_{1},x_{2},x_{3}\\}\cup D)$, or
there is a clique $K$ in $D$ that has an “almost as good” separation effect
(the precise formulation of this “almost as good” effect is cumbersome, and we
skip it here). Additionally there are two exceptional cases for which we are
not able to obtain this outcome: $H$ could grow to a loaded pyramid or an
extended near-prism (see Section 4 for definitions).

Suppose that at least $1\%$ of the stable triples $x_{1},x_{2},x_{3}$ in
$N(a)\cap N(D)$ there is a clique $K_{x_{1},x_{2},x_{3}}$ that separates at
least two of them from $b$ in $(\\{x_{1},x_{2},x_{3}\\}\cup D)$ (or does the
morally equivalent job). One of the main structural insights in this paper is
that in this case we can conclude that there is a single set $K$ in $D$ such
that $\kappa(K)$ is constant and no component of $D-K$ sees more than $99\%$
of $N(D)$. This kind of local-to-global transition is usually very hard to
force when one works with families of graphs defined by forbidden induced
subgraphs. Our arguments here only rely on $G$ being $C_{4}$-free, so we
expect for this technique to be applicable in other contexts in the future.

Whenever we get a $K$ as above we win – we can just add it to our separator
$X$, and again we will only do this $O(\log n)$ many times before $|N(D)|$
drops to $0$ and $a$ is separated from $b$. A similar outcome can be derived
using structural arguments from [17] when $H$ is a pyramid that grows to an
extended near-prism for a sufficiently large proportion of stable triples in
$N(D)$.

The problem with this approach is that it gets stuck whenever $99\%$ of the
stable triples $\\{x_{1},x_{2},x_{3}\\}$ satisfy that $H$ is a wheel or grows
to a loaded pyramid. When this problem occurs a large fraction of the vertices
of $N(D)$ are hubs. We say that a vertex $v$ of $G$ is a hub if $v$ is the
center of a proper wheel, or the “corner” of a loaded pyramid (again, see
Section 4) and we denote by $\operatorname{Hub}(G)$ the set of all hubs of
$G$. We remark that our definition of hubs is not precisely the same as the
definition of hubs in [13], although the role hubs play in [13] and here are
similar. When none of the vertices in $N(a)$ (and therefore $N(D)$) are hubs
an argument quite similar to the one outlined above works, and we are able to
obtain an $a$-$b$ separator $X$ with polylogarithmic $\kappa$. We call this
the “hub-free” case.

The remainder of the proof then consists of reducing the general case to the
hub-free case. The reduction is based on the “central bag” method, developed
in [7] and [6] and also used in [13]. Since $G$ is $C_{4}$-free it follows
that $N(a)\cap N(b)$ is a clique, and we may add $N(a)\cap N(b)$ to $X$ at the
cost of increasing $|X|$ by $t$ (recall that $G$ is $K_{t}$-free). From now on
we assume that $N(a)\cap N(b)$ is empty.

Since every even-hole-free graph has a vertex whose neighborhood is the union
of two cliques, it follows that every induced subgraph of $G$ has average
degree upper bounded by $O(t)$. Thus, the set $\operatorname{Hub}(G)$ contains
a stable set $S_{1}$ of size at least
$\Omega(\frac{|\operatorname{Hub}(G)|}{t})$ such that the degree of each
vertex in $S_{1}$ in $G[\operatorname{Hub}(G)]$ is at most $O(t)$. We show
that for every hub $v$ in a graph in ${\cal C}$, $G-N[v]$ is disconnected.
When $v$ is a wheel center this was already known, for loaded pyramid corners
we prove it in Section 6 (we skip this proof in the overview).

For each $v\in S_{1}$, since $v\notin N(a)\cap N(b)$ there is a component
$D_{v}$ of $G\setminus N[v]$ that contains at least one of $\\{a,b\\}$. We
claim that $N[D_{v}]$ must contain both $\\{a,b\\}$ or we are already done!
Indeed, suppose $N[D_{v}]$ contains $b$ but not $a$. Then a set $X$ that
separates $v$ from $b$ also separates $a$ from $b$, but $v$ only has $O(t)$
hubs in its neighborhood. So adding these $t$ hubs to $X$ leaves us with the
task of separating $v$ from $b$, but now $v$ has no hubs in its neighborhood
and we are in the hub-free case (and therefore done).

Thus, if we are not done yet, then for every vertex $v$ in $S_{1}$ there is a
component $D_{v}$ such that $\\{a,b\\}\subseteq N[D_{v}]$. We define the
central bag to be $\beta=\cap_{v\in S_{1}}(N[D_{v}]\cup\\{v\\})$ (the actual
definition of the central bag is subtly different). Observe that both $a$ and
$b$ are in the central bag $\beta$.

There are now two key observations behind the central bag method. The first
(and easy) one is that no vertex $v\in S_{1}$ can be a hub in $\beta$. Indeed
$v$ cannot be a hub in $N[D_{v}]$ since $N[D_{v}]-N(v)=D_{v}$ is connected,
contradicting that the neighborhood of every hub is a separator. Since
$\beta\subseteq D_{v}$ it follows that $v$ cannot be a hub in $\beta$ either.
When the more nuanced definition is used, the proof is slightly more involved.

This observation means that the number of hubs in $\beta$ is smaller by a
linear fraction than the number of hubs in $G$. Thus, by induction on
$\log(|\operatorname{Hub}(G)|)$, we can find an $a$-$b$ separator $Y$ in the
central bag $\beta$ of polylogarithmic size. If we can grow $Y$ to an $a$-$b$
separator $X$ in $G$ incurring an additive polylogarithmic cost, then the
induction goes through and we are able to upper bound the total size of $X$ by
$(\log n)^{O(1)}$. In particular the depth of the induction is logaritmic in
$n$, so if $|X|$ grows by an additive term of $(\log n)^{O(1)}$ in each
inductive step this is ok, but if $X$ grows by a factor $1.01$ in each step
then $|X|$ ends up being polynomial in $n$.

The second (and more involved) component of the central bag method is to show
that $Y$ can indeed be grown to $X$ as prescribed above. This incurs a cost
which is proportional to (essentially) $|Y\cap S_{1}|$, because for each
vertex $s$ in $|Y\cap S_{1}|$ we add all of its $O(t)$ hub neighbors to $X$
and then separate $s$ from either $a$ or $b$ using the hub-free case.

Unfortunately the inductive step which gives us $Y$ does not give us any
guarantees on the size of $|Y\cap S_{1}|$, so in the worst case $Y\cap S_{1}$
could be almost as big as $Y$ itself. Then the cost of turning $Y$ into a
separator $X$ in $G$ would incur at least a constant multiplicative cost,
which would be too expensive. We therefore apply an additional “pivot” step
where $Y$ is changed so that $|Y\cap S_{1}|$ is small. This pivot step again
relies on the hub-free case as well as a second application of the local-
global transition mentioned above. This concludes the proof outline.

We note that most of the results are proved for the slightly more general
class of graphs $\mathcal{C}$, rather than even-hole-free graphs. However,
Section 7 deals with even-hole-free graphs only. It is very likely that the
proofs there do in fact work in the more general setting, but we did not
verify the details. Theorem 13.2 is another fact we need that has only been
proved for even-hole-free graphs (and not for $C_{4}$-free odd-signable
graphs); once again it is likely to generalize, but we have not checked it
carefully. These are the two reasons for the fact that our main theorem
applies to even-hole-free graphs only.

###  3.1 Organization of the Proof

The pieces of the proof appear in a different order than in the outline.
Specifically each piece is proved before it is used. In Section 4 we prove
Theorem 4.3, which allows us to generate clique separators from pyramids that
do not grow to an extended near-prisms. In Sections 5 and 6 we define hubs and
prove Theorem 6.5, that every for every hub $v$, $N[v]$ separates the graph
(in a particular way). In Section 7 we prove Theorem 7.2 which allows us to
decompose graphs that contain pyramids that do grow to an extended near-
prisms. In Section 8 we prove Theorem 8.3: that if we have sufficiently many
clique separators of the type that are the output of Theorem 4.3, then there
is a bounded $\kappa$ size set whose removal substantially separates the
graph. In Section 9 we prove Theorem 9.1 which shows how to deal with the case
where we have a vertex $a$, and many of the stable triples $x_{1},x_{2},x_{3}$
in the neighborhood of the component $D$ of $G-N(a)$ that contains $b$ are
contained in a pyramid that grows to an extended near-prism. In Section 10 we
handle the hub-free case and prove Theorem 10.1, that if $a$ does not have any
hub neighbors, then $a$ and $b$ can be separated with $O(\log n)$ cliques.
Section 11 contains all of the elements needed for the central bag method,
with the exception of the “pivot” step where the separator $Y$ is changed to
(mostly) avoid $S_{1}$. In Section 12 we prove Theorem 12.1, which does the
aforementioned pivot step. In Section 13 we apply the central bag method,
putting together the results from Sections 10, 11 and 12 to prove Theorem
13.1, that every pair of non-adjacent vertices in a $K_{t}$-free even-hole-
free graph can be separated by $(t\log n)^{O(1)}$ cliques. In Section 14 we
prove Theorem 14, that every pair of non-adjacent vertices in an even-hole-
free graph can be separated by $(\log n)^{O(1)}$ cliques. Finally, in Section
15 we use Theorem 14 to prove Theorem 1.1.

##  4 Jumps on pyramids

The goal of this section is to prove Theorem 4.3, which asserts the existence
of well-structured cutsets that separate the neighbors of the apex of a
pyramid. Theorem 4.3 is then used to produce the “local cutsets” in Theorem
8.3.

We start with some definitions. Let $G\in\mathcal{C}$ and let $\Sigma$ be a
pyramid in $G$ with apex $a$, base $b_{1}b_{2}b_{3}$ and paths
$P_{1},P_{2},P_{3}$. We say that $X\subseteq\Sigma$ is local (in $\Sigma$) if
$X\subseteq P_{i}$ for some $i\in\\{1,2,3\\}$, or
$X\subseteq\\{b_{1},b_{2},b_{3}\\}$. Let $P=p_{1}\hbox{-}\cdots\hbox{-}p_{k}$
be a path with $P\cap\Sigma=\emptyset$. $P$ is a corner path for $b_{1}$ if
$p_{1}$ is adjacent to $b_{2},b_{3}$, $p_{k}$ has a neighbor in
$P_{1}\setminus b_{1}$, and there are no other edges from $\Sigma\setminus
b_{1}$ to $P$. A corner path for $b_{2}$ and $b_{3}$ is defined similarly. We
say that $P$ is a corner path for $\Sigma$ if $P$ is a corner path for
$b_{1}$, $b_{2}$ or $b_{3}$. If $v\in G\setminus\Sigma$, and $v$ is not a
corner path for $\Sigma$, and $N_{\Sigma}(v)$ is not local, we say that $v$ is
major (for $\Sigma$).

A loaded pyramid in a graph $G$ is a pair $\Pi=(\Sigma,P)$ where $\Sigma$ is
pyramid with apex $a$, base $b_{1}b_{2}b_{3}$ and paths $P_{1},P_{2},P_{3}$,
$a$ is adjacent to $b_{2}$ (hence $|P_{2}|=2$), and
$P=p_{1}\hbox{-}\cdots\hbox{-}p_{k}$ is a path such that

  * •

$p_{1}$ is adjacent to $b_{2}$;

  * •

$p_{k}$ has a neighbor in $P_{1}^{*}$;

  * •

$P_{3}$ is anticomplete to $P$ (and in particular $a$ is anticomplete to $P$);

  * •

$b_{2}$ is anticomplete to $P\setminus p_{1}$; and

  * •

$P_{1}\setminus b_{1}$ is anticomplete to $P\setminus p_{k}$.

In this case, we say $b_{2}$ is a loaded pyramid corner, and denote the loaded
pyramid as a pair $(\Pi,b_{2})$. We also use the notation $\Pi$ to denote the
vertex set $P\cup\Sigma$.

Recall that a _wheel_ $(H,x)$ in $G$ is a pair where $H$ is a hole and $x$ is
a vertex with at least three neighbors in $H$; the vertex $x$ is called the
_center_ of the wheel. A wheel $(H,x)$ is proper if $\alpha(N_{H}(x))\geq 3$.
We say that a vertex $v$ of $G$ is a hub if $v$ is a proper wheel center or a
loaded pyramid corner, and we denote by $\operatorname{Hub}(G)$ the set of all
hubs of $G$.

An extended near-prism, defined in [17], is a graph obtained from a near-prism
by adding one extra edge, as follows. Let $P_{1},P_{2},P_{3}$ be as in the
definition of a near-prism, and let $a\in P_{1}^{*}$ and $b\in P_{2}^{*}$; and
add an edge $ab$. (It is important that $a,b$ do not belong to the triangles.)
If the two triangles of the extended near-prism are disjoint, we also call it
an extended prism. We call $ab$ the cross-edge of the extended near-prism (or
of the extended prism). We start with two lemmas:

######  Theorem 4.1.

Let $G\in\mathcal{C}$. Let $\Sigma$ be a pyramid in $G$ with apex $a$, base
$b_{1}b_{2}b_{3}$ and paths $P_{1},P_{2},P_{3}$. Let $p$ be a major vertex for
$\Sigma$. Then one of the following holds:

  1. 1.

$p$ is adjacent to $a$ and at least two of the neighbors of $a$ in $\Sigma$;

  2. 2.

$p$ is adjacent to $a$, and $p$ is a hub;

  3. 3.

$\Sigma\cup p$ is an extended prism whose cross-edge contains $a$; or

  4. 4.

$(\Sigma,p)$ is a loaded pyramid, and so one of $b_{1},b_{2},b_{3}$ is a
loaded pyramid corner.

###### Proof.

We may assume that the last three outcomes of Theorem 4.1 do not hold. First
we prove that $p$ is adjacent to $a$. Suppose not. Assume first that $p$ has a
neighbor in each of $P_{1},P_{2},P_{3}$. Since $p$ is not a corner path for
$\Sigma$ and $N_{\Sigma}(p)$ is not local, it follows that $p$ has neighbors
in the interiors of at least two of $P_{1},P_{2},P_{3}$. Consequently, there
is a theta with ends $a$ and $p$ whose paths are subpaths of
$P_{1},P_{2},P_{3}$, a contradiction. Thus we may assume that $p$ is
anticomplete to at least one of $P_{1},P_{2},P_{3}$, say $p$ is anticomplete
to $P_{3}$.

(1) _If $p$ is non-adjacent to $a$, then for $i=1,2$, we have
$N_{P_{i}}(p)\neq\\{b_{i}\\}$._

Suppose $N_{P_{1}}(p)=\\{b_{1}\\}$. Since $p$ is major, $p$ has a neighbor in
$P_{2}\setminus b_{2}$. Since $p$ is non-adjacent to $a$, and $\Sigma\cup p$
is not a loaded pyramid, it follows that $b_{1}$ is non-adjacent to $a$. But
now we get a theta with ends $b_{1},a$ and paths
$b_{1}\hbox{-}P_{1}\hbox{-}a$, $b_{1}\hbox{-}p\hbox{-}P_{2}\hbox{-}a$ and
$b_{1}\hbox{-}b_{3}\hbox{-}P_{3}\hbox{-}a$, a contradiction. This proves (4).

By (4) and since $p$ is major and we have assumed that $p$ is non-adjacent to
$a$, $p$ has both a neighbor in $P_{1}\setminus b_{1}$, and a neighbor in
$P_{2}\setminus b_{2}$. Let $H$ be the hole formed by $P_{1}$ and $P_{2}$.

(2) _If $p$ is non-adjacent to $a$, then $p$ has exactly three neighbors in
$H$, and two of them are consecutive._

Suppose that $p$ has two non-adjacent neighbors in $P_{1}$. Then there exists
a path $P_{1}^{\prime}$ from $p$ to $a$, and a path $P_{1}^{\prime\prime}$
from $p$ to $b_{1}$, both with interior in $P_{1}$ and such that
$P_{1}^{\prime}\setminus p$ is anticomplete to $P_{1}^{\prime\prime}\setminus
p$. Now we get a theta with ends $p,a$ and paths
$p\hbox{-}P_{1}^{\prime}\hbox{-}a$,
$p\hbox{-}P_{1}^{\prime\prime}\hbox{-}b_{1}\hbox{-}b_{3}\hbox{-}P_{3}\hbox{-}a$
and a path from $p$ to $a$ with interior in $P_{2}\setminus b_{2}$, a
contradiction. This proves that $p$ has either one or two consecutive
neighbors in $P_{1}$, and the same for $P_{2}$. Since $(H,p)$ is not an even
wheel, and $H\cup p$ is not a theta, (4) follows.

We may assume that $N_{P_{1}}(p)=\\{t\\}$, $N_{P_{2}}(p)=\\{q,r\\}$, where
$P_{2}$ traverses $a,q,r,b_{2}$ is this order. By (4), $t\neq b_{1}$. It
follows from (4) that $q$ is adjacent to $r$. Since $\Sigma\cup p$ is not an
extended prism, it follows that $t$ is non-adjacent to $a$. But now there is a
theta with ends $t,a$ and paths $t\hbox{-}P_{1}\hbox{-}a$,
$t\hbox{-}p\hbox{-}q\hbox{-}P_{2}\hbox{-}a$ and
$t\hbox{-}P_{1}\hbox{-}b_{1}\hbox{-}b_{3}\hbox{-}P_{3}\hbox{-}a$, a
contradiction. This proves that $p$ is adjacent to $a$.

To complete to proof of 4.1, assume that $p$ is anticomplete to $N_{P_{1}\cup
P_{2}}(a)$. Since $p$ is major, $p$ has a neighbor in $H\setminus a$. Since
$p\not\in\operatorname{Hub}(G)$ and $H\cup p$ is not a theta, it follows that
$p$ has exactly two neighbors in $H\setminus a$, and they are adjacent. Since
$p$ is not a corner path for $b_{3}$, it follows that
$N_{H}(p)\neq\\{a,b_{1},b_{2}\\}$, and so we may assume that
$N_{H}(p)\subseteq P_{1}$. Since $p$ is major, we deduce that $p$ has a
neighbor in $P_{3}\setminus a$. Let $H^{\prime}$ be the hole $P_{1}\cup
P_{3}$. Since $p\not\in\operatorname{Hub}(G)$, it follows that
$(H^{\prime},p)$ is not a proper wheel. Consequently,
$N_{P_{3}}(p)=\\{a\\}\cup N_{P_{3}}(a)$. But now $(H^{\prime},p)$ is an even
wheel, a contradiction. ∎

######  Theorem 4.2.

Let $G\in\mathcal{C}$. Let $\Sigma$ be a pyramid in $G$ with apex $a$, base
$b_{1}b_{2}b_{3}$ and paths $P_{1},P_{2},P_{3}$. Assume that
$N_{G}(a)\subseteq\Sigma$. Let $P$ be a path in $G\setminus\Sigma$. Then one
of the following holds.

  1. 1.

$N_{\Sigma}(P)$ is local in $\Sigma$;

  2. 2.

$P$ contains a major vertex for $\Sigma$;

  3. 3.

$P$ contains a corner path for $\Sigma$;

  4. 4.

There exist distinct $i,j\in\\{1,2,3\\}$ and a subpath
$Q=q_{1}\hbox{-}\cdots\hbox{-}q_{m}$ of $P$ such that

     * •

$N_{\Sigma}(q_{1})\subseteq P_{i}$;

     * •

$q_{1}$ has a unique neighbor in $P_{i}$ and $N_{P_{i}}(q_{1})=N_{P_{i}}(a)$;

     * •

$N_{\Sigma}(q_{m})\subseteq P_{j}$;

     * •

$q_{m}$ has exactly two neighbors $x,y$ in $P_{j}$; $x$ is adjacent to $y$,
and $a\not\in\\{x,y\\}$; and

     * •

there are no other edges between $\Sigma$ and $Q$;

In particular, $a$ is contained in the cross-edge of an extended prism.

  5. 5.

There is an $i\in\\{1,2,3\\}$ and a subpath
$Q=q_{1}\hbox{-}\cdots\hbox{-}q_{m}$ of $P$ such that $(\Sigma,P)$ is a loaded
pyramid with loaded pyramid corner $b_{i}$.

###### Proof.

Let $P=p_{1}\hbox{-}\cdots\hbox{-}p_{k}$. Suppose for a contradiction that
none of the outcomes hold. We may assume that $N_{\Sigma}(P)$ is not local,
and that $N_{\Sigma}(X)$ is local for every proper subpath $X$ of $P$. Since
no vertex of $P$ is major, and no subpath of $P$ is a corner path, it follows
that $k\geq 2$.

Since $N_{\Sigma}(P)\not\subseteq\\{b_{1},b_{2},b_{3}\\}$, by symmetry, we may
assume that

  * •

$N_{\Sigma}(p_{1})\subseteq P_{1}$ and $p_{1}$ has a neighbor in
$P_{1}\setminus b_{1}$;

  * •

$p_{k}$ has a neighbor in $P_{2}\setminus a$, and either
$N_{\Sigma}(p_{k})\subseteq P_{2}$, or
$N_{\Sigma}(p_{k})\subseteq\\{b_{1},b_{2},b_{3}\\}$; and

  * •

$\Sigma\setminus b_{1}$ is anticomplete to $P^{*}$.

We first show:

(3) _We have $N_{\Sigma}(p_{k})\subseteq P_{2}\cup\\{b_{1}\\}$._

Suppose not. Then $N_{\Sigma}(p_{k})\subseteq\\{b_{1},b_{2},b_{3}\\}$. Since
$p_{k}$ has a neighbor in $P_{2}\setminus a$, it follows that $p_{k}$ is
adjacent to $b_{2}$. Since $P\cup(P_{1}\setminus b_{1})$ contains a path from
$p_{k}$ to $a$, and since $P$ does not contain a corner path for $b_{1}$, it
follows that $p_{k}$ is non-adjacent to $b_{3}$. This proves (4).

(4) _$N_{P_{2}}(p_{k})\neq\\{b_{2}\\}$._

Suppose that $N_{P_{2}}(p_{k})=\\{b_{2}\\}$. By (4) $p_{k}$ is non-adjacent to
$b_{3}$. If $b_{2}$ is non-adjacent to $a$, then there is a theta in $G$ with
ends $b_{2},a$ and paths $P_{2}$, $b_{2}$-$b_{3}$-$P_{3}$-$a$ and
$b_{2}$-$p_{k}$-$P$-$p_{1}$-$P_{1}$-$a$, a contradiction; so $b_{2}$ is
adjacent to $a$. Now since $a$ has no neighbor in $P$, $(\Sigma,P)$ is a
loaded pyramid with base $b_{1}b_{2}b_{3}$, apex $a$, and paths
$P_{1},P_{2},P_{3}$, and the fifth outcome holds, a contradiction. This proves
(4).

(5) _There is no edge from $b_{1}$ to $P\setminus p_{1}$._

Suppose for a contradiction that $b_{1}$ has a neighbor in $P\setminus p_{1}$.
Since $N_{\Sigma}(P\setminus p_{1})$ is local, it follows from (4) that
$N_{\Sigma}(p_{k})\subseteq\\{b_{1},b_{2}\\}$, contrary to (4), and (4)
follows.

By (4), it follows that $\Sigma$ is anticomplete to $P^{*}$ and that
$N_{\Sigma}(p_{k})\subseteq P_{2}$. Traversing $P_{1}$ from $b_{1}$ to $a$,
let $x_{1}$ be the first neighbor of $p_{1}$. Traversing $P_{2}$ from $b_{2}$
to $a$, let $x_{2}$ be the first neighbor of $p_{k}$. Then
$H=p_{1}$-$P$-$p_{k}$-$x_{2}$-$P_{2}$-$b_{2}$-$b_{1}$-$P_{1}$-$x_{1}$-$p_{1}$
is a hole in $G$ (since it contains at least the four distinct vertices
$b_{1},b_{2},p_{1},p_{k}$). For $i=1,2$, let $z_{i}$ be the neighbor of
$x_{i}$ in $P$ (and thus $z_{i}\in\\{p_{1},p_{k}\\}$).

(6) _For $i=1,2$, either there is a vertex $y_{i}$ in $P_{i}$ with $x_{i}$
adjacent to $y_{i}$ and $N(z_{i})\cap P_{i}=\\{x_{i},y_{i}\\}$; or $x_{i}$ is
the only neighbor of $z_{i}$ in $P_{i}$ and $x_{i}$ is adjacent to $a$._

Since $p_{1}$ has a neighbor in $P_{1}\setminus b_{1}$, and since by (4) and
(4) $p_{k}$ has a neighbor in $P_{2}\setminus b_{2}$, it follows that for
$i=1,2$, there is a path from every vertex of $P$ to $a$ with interior in
$(P\cup P_{i})\setminus b_{i}$.

If $x_{i}$ is the only neighbor of $z_{i}$ in $P_{i}$, and $x_{i}$ is non-
adjacent to $a$, then we find a theta with ends $x_{i},a$ in $G$ and paths
$x_{i}$-$P_{i}$-$a$, $x_{i}$-$P_{i}$-$b_{i}$-$b_{3}$-$P_{3}$-$a$, and a path
whose interior is contained in $(P\cup P_{3-i})\setminus b_{3-i}$ given by the
claim of the previous paragraph applied to $z_{3-i}$, a contradiction.

Thus we may assume that $z_{i}$ has two non-adjacent neighbors in $P_{i}$. Let
$y_{i}$ be the neighbor of $z_{i}$ along $P_{i}$ closest to $a$. Since
$y_{i}\neq a$, there is a theta with ends $z_{i},a$ and paths
$z_{i}$-$y_{i}$-$P_{i}$-$a$, $z_{i}$-$x_{i}$-$b_{i}$-$b_{3}$-$P_{3}$-$a$, and
a path whose interior is contained in $(P\cup P_{3-i})\setminus b_{3-i}$ given
by the claim of the first paragraph applied to $z_{3-i}$, a contradiction. Now
(4) follows.

If the first outcome of (4) holds for both $i=1$ and $i=2$, we get a prism
with triangles $x_{1}y_{1}z_{1}$ and $x_{2}y_{2}z_{2}$ and paths
$y_{1}\hbox{-}P_{1}\hbox{-}a\hbox{-}P_{2}\hbox{-}y_{2}$, $P$ and
$x_{1}\hbox{-}P_{1}\hbox{-}b_{1}\hbox{-}b_{2}\hbox{-}P_{2}\hbox{-}x_{2}$, a
contradiction. If the second outcome of (4) holds for both $i=1$ and $i=2$,
then we get a theta with ends $x_{1},x_{2}$ and paths
$x_{1}\hbox{-}P_{1}\hbox{-}a\hbox{-}P_{2}\hbox{-}x_{2}$, $P$ and
$x_{1}\hbox{-}P_{1}\hbox{-}b_{1}\hbox{-}b_{2}\hbox{-}P_{2}\hbox{-}x_{2}$, a
contradiction. Thus we may assume that the first outcome holds for $i=1$ and
the third outcome holds for $i=2$. But now the fourth outcome of Theorem 4.2
holds, a contradiction. ∎

We need an additional definition: given a graph $G$ $x,y,z\in V(G)$, a path
$P$ from $x$ to $y$, and a non-empty set $A\subseteq P$, we define the
_$(P,y)$ -last vertex of $A$_ to be the vertex of $A$ which is closest to $y$
along $P$.

We now prove the main result of this section.

######  Theorem 4.3.

Let $G\in\mathcal{C}$. Let $\Sigma$ be a pyramid in $G$ with apex $a$, base
$b_{1}b_{2}b_{3}$ and paths $P_{1},P_{2},P_{3}$. For each $i$, let $Q_{i}$ be
a subpath of $P_{i}$, with ends $a$ and $x_{i}$, such that all internal
vertices of $Q_{i}$ have degree two in $G$. Let $b\in V(G)\setminus(Q_{1}\cup
Q_{2}\cup Q_{3})$. Assume that

  * •

$N_{G}(a)=N_{\Sigma}(a)$;

  * •

$\\{x_{1},x_{2},x_{3}\\}$ is a stable set;

  * •

$b$ is non-adjacent to $x_{1},x_{2},x_{3}$;

  * •

$a$ does not belong to a cross-edge of an extended near-prism in $G$; and

  * •

$\operatorname{Hub}(G)\cap\\{x_{1},x_{2},x_{3}\\}=\emptyset$.

Let $D=G\setminus(Q_{1}\cup Q_{2}\cup Q_{3})$. Then there is a clique
$K\subseteq D$ and distinct $i,j\in\\{1,2,3\\}$ such that one of the following
holds: (For $i\in\\{1,2,3\\}$ let $D_{i}$ be the union of components of
$D\setminus K$ such that $N(x_{i})\cap D_{i}\neq\emptyset$.)

  1. 1.

$b\not\in K\cup D_{i}\cup D_{j}$; or

  2. 2.

We have $b\not\in N[D_{i}]$. Moreover, there is a set
$D_{j}^{\prime}=D_{j}^{\prime}(x_{1}x_{2}x_{3})$ of vertices such that:

     * •

$D_{j}^{\prime}$ is not a clique;

     * •

$D_{j}^{\prime}$ is complete to $K$;

     * •

There is a vertex $q=q(x_{1}x_{2}x_{3})$ with the following property. Either
$b\in K$ and $q=b$; or there exists $k\in\\{1,2,3\\}\setminus\\{i\\}$ such
that $x_{k}$ is complete to $K\cup D_{j}^{\prime}$ and $q=x_{k}$;

     * •

For every $v\in D_{j}^{\prime}$, there is a path $P$ in $D\cup\\{x_{j}\\}$
from $b$ to $x_{j}$ such that $P\cap N(q)\neq\emptyset$ and the
$(P,x_{j})$-last vertex in $P\cap N(q)$ is $v$; and

     * •

For every path $P$ in $D\cup\\{x_{j}\\}$ from $b$ to $x_{j}$, we have $P\cap
N(q)\neq\emptyset$, and the $(P,x_{j})$-last vertex of $P\cap N(q)$ is
complete to $K$.

###### Proof.

Let $B_{1},C_{1},B_{2},C_{2},B_{3},C_{3}$ be pairwise disjoint subsets of
$G\setminus a$ with the following properties:

  * •

the sets $B_{1},B_{2},B_{3}$ are all pairwise complete to each other;

  * •

the sets $C_{1},C_{2},C_{3}$ are pairwise anticomplete to each other;

  * •

for distinct $i,j\in\\{1,2,3\\}$, the set $B_{i}$ is anticomplete to $C_{j}$:

  * •

for every $i$, every vertex of $B_{i}$ is an end of a path to $x_{i}$ with
interior in $C_{i}$;

  * •

for every $i$, one of the following holds:

    * –

$x_{i}\in C_{i}$ and every vertex of $C_{i}\setminus Q_{i}$ is in the interior
of a path from some vertex of $B_{i}$ to $x_{i}$; or

    * –

$x_{i}=b_{i}$, and $B_{i}=\\{x_{i}\\}$, and $C_{i}=Q_{i}^{*}$.

  * •

For every $i$, we have $b_{i}\in B_{i}$ and
$P_{i}\setminus\\{b_{i},a\\}\subseteq C_{i}$.

Subject to these properties, we choose the sets with
$W=\\{a\\}\cup\bigcup_{i=1}^{3}(B_{i}\cup C_{i})$ maximal.

(7) _Let $D$ be a component of $G\setminus W$. Then either $N(D)\subseteq
B_{1}\cup B_{2}\cup B_{3}$, or there exists $i$ such that $N(D)\subseteq
B_{i}\cup C_{i}$._

Suppose not and let $D$ be a component of $G\setminus W$ violating the
statement. Then there exist $i\in\\{1,2,3\\}$ and a path
$P=p_{1}\hbox{-}\cdots\hbox{-}p_{k}$ in $D$ such that $p_{1}$ has a neighbor
in $C_{i}$ and $p_{k}$ has a neighbor in $W\setminus(B_{i}\cup
C_{i}\cup\\{a\\})$. We may assume that $P$ is chosen with $k$ as small as
possible and that $i=1$. Let $c_{1}\in C_{1}$ be a neighbor of $p_{1}$. Let
$P_{1}^{\prime}$ be a path from $b_{1}^{\prime}\in B_{1}$ to $a$ with interior
in $C_{1}$ and such that $c_{1}\in P_{1}^{\prime}$. Let $c_{2}\in B_{2}\cup
C_{2}\cup B_{3}\cup C_{3}$ be a neighbor of $p_{k}$; choose $c_{2}\not\in
B_{2}\cup B_{3}$ if possible. We may assume that $c_{2}\in B_{2}\cup C_{2}$.
Let $P_{2}^{\prime}$ be a path from $b_{2}^{\prime}\in B_{2}$ to $a$ with
interior in $C_{2}$ and such that $c_{2}\in P_{2}^{\prime}$. Let
$P_{3}^{\prime}=P_{3}$. Now $\Sigma^{\prime}=P_{1}^{\prime}\cup
P_{2}^{\prime}\cup P_{3}^{\prime}\cup\\{a\\}$ is a pyramid with apex $a$ an
base $b_{1}^{\prime}b_{2}^{\prime}b_{3}$. We apply Theorem 4.2 to
$\Sigma^{\prime}$ and $P$. Since $P$ is not local for $\Sigma^{\prime}$ and
$N_{G}(a)=N_{\Sigma}(a)$ and $N_{G}(a)\cap\operatorname{Hub}(G)=\emptyset$
(because each neighbor of $a$ ethre has degree 2 in $G$ or is in
$\\{x_{1},x_{2},x_{3}\\}$), and $a$ is not contained in a cross-edge of an
extended near-prism in $G$, it follows that one of the following holds:

  * •

$P$ contains a major vertex for $\Sigma^{\prime}$; or

  * •

$P$ contains a corner path for $\Sigma^{\prime}$;

Theorem 4.1 implies that $P$ does not contain a major vertex for
$\Sigma^{\prime}$, and therefore $P$ contains a corner path for
$\Sigma^{\prime}$. By the minimality of $k$, it follows that $P$ is a corner
path for $\Sigma^{\prime}$; consequently
$N_{\Sigma^{\prime}\setminus\\{b_{1}^{\prime}\\}}(p_{k})=\\{b_{2}^{\prime},b_{3}\\}$,
$N_{\Sigma^{\prime}\setminus\\{b_{1}^{\prime}\\}}(p_{1})\subseteq B_{1}\cup
C_{1}$, and there are no other edges between $P$ and $\Sigma^{\prime}\setminus
b_{1}^{\prime}$. In particular, $p_{1}$ has a neighbor in $C_{1}$, and so
$x_{1}\in C_{1}$.

We claim that $P$ is anticomplete to $C_{2}\cup C_{3}$ and $P\setminus p_{k}$
is anticomplete to $B_{2}\cup B_{3}$. By the minimality of $k$, it follows
that $P\setminus p_{k}$ is anticomplete to $C_{2}\cup C_{3}\cup B_{2}\cup
B_{3}$. From the choice of $c_{2}$, it follows that $p_{k}$ is anticomplete to
$C_{2}\cup C_{3}$. This proves the claim.

Now let $i\in\\{2,3\\}$ and let $\Sigma^{\prime\prime}$ be obtained for
$\Sigma^{\prime}$ by replacing the path $P_{i}^{\prime}$ by an arbitrary path
from some $b_{i}^{\prime\prime}\in B_{i}$ to $a$ with interior in $C_{i}$.
Then $P$ is not local for $\Sigma^{\prime\prime}$. Applying Theorems 4.2 and
4.1 to $\Sigma^{\prime\prime}$ and $P$, we deduce that $P$ is a corner path
for $\Sigma^{\prime\prime}$. It follows that $p_{k}$ is adjacent to
$b_{i}^{\prime\prime}$. Since $b_{i}^{\prime\prime}$ was chosen arbitrarily,
we conclude that $p_{k}$ is complete to $B_{2}\cup B_{3}$. But now, we can
replace $B_{1}$ by $B_{1}\cup p_{k}$ and $C_{1}$ by $C_{1}\cup(P\setminus
p_{k})$, contradicting the maximality of $W$. This proves (4).

Let $F$ be the union of the components $D$ of $G\setminus W$ with
$N(D)\subseteq B_{1}\cup B_{2}\cup B_{3}$. Let $F_{i}$ be the union of the
components $D$ of $G\setminus(W\cup F)$ such that $N(D)\subseteq B_{i}\cup
C_{i}$. By (4), $G\setminus W=F_{1}\cup F_{2}\cup F_{3}\cup F$ and the sets
$F_{1},F_{2},F_{3},F$ are pairwise disjoint and anticomplete to each other. We
may assume that $b\in B_{3}\cup C_{3}\cup F_{3}\cup F$. If $K=B_{1}\cup B_{2}$
is a clique and $x_{1},x_{2}\not\in B_{1}\cup B_{2}$, then for
$i\in\\{1,2\\}$, we have $D_{i}=(C_{i}\cup F_{i})\setminus Q_{i}$ and outcome
(2)(a) holds. Thus we may assume that either $B_{2}$ is not a clique or
$B_{2}=\\{x_{2}\\}$.

(8) _We may assume that $B_{2}=\\{x_{2}\\}$ or $B_{3}=\\{x_{3}\\}$._

Suppose not; by symmetry, we may assume also that $B_{1}\neq\\{x_{1}\\}$. Then
$B_{2}$ is not a clique. Since $G$ is $C_{4}$-free, it follows that $B_{1}\cup
B_{3}$ is a clique. Let $K=B_{1}\cup B_{3}$. Now $D_{1}=(C_{1}\cup
F_{1})\setminus Q_{1}$ and $D_{2}\subseteq(C_{2}\cup F_{2}\cup B_{2}\cup
F)\setminus Q_{2}$ and $D_{3}=(C_{3}\cup F_{3})\setminus Q_{3}$.

If $b\in C_{3}\cup F_{3}$, then outcome (2)(a) of the theorem holds with $i=1$
and $j=2$, and if $b\in F$, then outcome (2)(a) of the theorem holds with
$i=1$ and $j=3$. Thus we may assume that $b\in B_{3}$. Let $i=1$ and $j=2$.
Then $b$ is anticomplete to $D_{1}$. Since every path from $b$ to $x_{2}$ with
interior in $D$ contains exactly one vertex of $B_{2}$ and exactly one vertex
in $N(b)$, and $B_{2}$ is not a clique, and for every vertex $v$ in $B_{2}$
there is a path from $v$ to $x_{2}$ with interior in $C_{2}$, it follows that
outcome (2)(b) holds with $D_{j}^{\prime}=B_{2}$ and $q=b$. This proves (4).

Since $b$ is non-adjacent to $a$, it follows that if $B_{3}=\\{x_{3}\\}$, then
$C_{3}=Q_{3}^{*}$ and $F_{3}=\emptyset$, and so $b\in F$ and in particular,
$b\in B_{2}\cup C_{2}\cup F_{2}\cup F$; so there is symmetry between $2$ and
$3$ in this case.

Therefore, we may assume that $B_{2}=\\{x_{2}\\}$. Since
$\\{x_{1},x_{2},x_{3}\\}$ is a stable set, it follows that $x_{1},x_{3}\not\in
B_{1}\cup B_{3}$. Since $b$ is non-adjacent to $x_{2}$, it follows that $b\in
C_{3}\cup F_{3}\cup F$.

(9) _$B_{1}\cup B_{3}$ is not a clique._

Suppose that $B_{1}\cup B_{3}$ is a clique, and let $K=B_{1}\cup B_{3}$. Then
$D_{1}=(C_{1}\cup F_{1})\setminus Q_{1}$ and $D_{3}=(C_{3}\cup F_{3})\setminus
Q_{3}$ and $D_{2}\subseteq F$. If $b\in F$, then outcome (2)(a) of the theorem
holds with $i=1$ and $j=3$. If $b\in C_{3}\cup F_{3}$, then outcome (2)(a) of
the theorem holds with $i=1$ and $j=2$. This proves (4).  (10) _$B_{1}$ is a
clique._

Suppose not. It follows that $B_{3}$ is a clique. Let $K=B_{3}$. Then
$D_{3}=(C_{3}\cup F_{3})\setminus Q_{3}$ and $D_{1},D_{2}\subseteq(C_{1}\cup
B_{1}\cup F_{2}\cup F)\setminus(Q_{1}\cup Q_{2})$. If $b\in C_{3}\cup F_{3}$,
then outcome (2)(a) of the theorem holds with $i=1$ and $j=2$. It follows that
$b\in F$. Let $R$ be the component of $F$ containing $b$. Let $M=N(R)\cap
B_{1}$. If $M$ is a clique, then outcome (2)(a) of the theorem holds with
$K=B_{3}\cup M$ and $i=1$ and $j=3$.

It follows that $M$ is not a clique. Now outcome (2)(b) of the theorem holds
with $i=3$ and $j=1$ as well as $K=B_{3}$ and $D_{1}^{\prime}=M$ and
$q=x_{2}$. We show that the last two bullets of (2)(b) hold:

  * •

Let $v\in M$. Let $P$ be a path from $b$ to $v$ in $R\cup\\{v\\}$. Let $Q$ be
a path from $v$ to $x_{1}$ with $Q^{*}\subseteq C_{1}$. Then
$P^{\prime}=b\hbox{-}P\hbox{-}v\hbox{-}Q\hbox{-}x_{1}$ is a path from $b$ to
$x_{1}$ in $D\cup\\{x_{1}\\}$. Then, $v$ is the $(P^{\prime},x_{1})$-last
vertex in $P^{\prime}\cap N(q)$, and the second-to-last bullet of (2)(b)
holds.

  * •

Let $P$ be a path from $b$ to $x_{1}$ in $D\cup\\{x_{1}\\}$. Traversing $P$
from $b$ to $x_{1}$, let $v$ be the last vertex of $P$ which is not in
$C_{1}\cup F_{1}$. It follows that $v\in B_{1}$, and so $v$ is complete to
$K$, and the last bullet holds.

(11) _$B_{3}$ is a clique._

Suppose not. It follows that $B_{1}$ is a clique. Let $K=B_{1}$. Then
$D_{1}=(C_{1}\cup F_{1})\setminus Q_{1}$ and $D_{2},D_{3}\subseteq(C_{3}\cup
B_{3}\cup F_{2}\cup F)\setminus(Q_{2}\cup Q_{3})$. Suppose first that $b\in
F$. Then there is symmetry between $1$ and $3$, and the result follows from
(4). It follows that $b\in F_{3}\cup C_{3}$. Let $R$ be the component of
$(F_{3}\cup C_{3})\setminus Q_{3}$ containing $b$. Then $M=N_{D}(R)\subseteq
B_{3}$. If $M$ is a clique, then outcome (2)(a) holds with $K=B_{1}\cup M$ and
$i=1$ and $j=2$. So we may assume that $M$ is not a clique. Now we let $i=1$,
$j=2$, $q=x_{2}$, and $D_{2}^{\prime}=M$. It follows that outcome (2)(b)
holds. This proves (4).

Together, (4), (4), and (4) yield a contradiction; this concludes the proof. ∎

##  5 Star cutsets from wheels

The following well-known definitions appear, for example, in [7]. A _cutset_
$C\subseteq V(G)$ of $G$ is a set of vertices such that $G\setminus C$ is
disconnected. A star cutset in a graph $G$ is a cutset $S\subseteq V(G)$ such
that either $S=\emptyset$ or for some $x\in S$, $S\subseteq N[x]$.

Let $G$ be a graph and let $X,Y,Z\subseteq V(G)$. We say that $X$ separates
$Y$ from $Z$ if no component of $G\setminus X$ meets both $Y$ and $Z$. Recall
that a _wheel_ $(H,x)$ of $G$ consists of a hole $H$ and a vertex $x$ that has
at least three neighbors in $H$, and a wheel is proper if $\alpha(N(x)\cap
H)\geq 3$. A _sector_ of $(H,x)$ is a path $P$ of $H$ whose ends are distinct
and adjacent to $x$, and such that $x$ is anticomplete to $P^{*}$. A sector
$P$ is a _long sector_ if $P^{*}$ is non-empty. A wheel $(H,x)$ is a
_universal wheel_ if $x$ is complete to $H$. The following result was observed
in [7] based on results of [8, 42, 43] and stated in this form in [13]; it
shows that proper wheels force star cutsets in graphs in $\mathcal{C}$.

######  Theorem 5.1 (Abrishami, Chudnovsky, Vušković [7]; see also [13]).

Let $G\in\mathcal{C}$ and let $(H,v)$ be an proper wheel in $G$. Then there is
no component $D$ of $G\setminus N[v]$ such that $H\subseteq N[D]$.

In particular, we need the following:

######  Theorem 5.2 (Addario-Berry, Chudnovsky, Havet, Reed, Seymour [8], da
Silva, Vušković [42]).

Let $G\in\mathcal{C}$ and let $(H,x)$ be a proper wheel in $G$ that is not a
universal wheel. Let $x_{1}$ and $x_{2}$ be the endpoints of a long sector $Q$
of $(H,x)$. Let $W$ be the set of all vertices $h$ in $H\cap N(x)$ such that
the subpath of $H\setminus\\{x_{1}\\}$ from $x_{2}$ to $h$ contains an even
number of neighbors of $x$, and let $Z=H\setminus(Q\cup N(x))$. Let
$N^{\prime}=N(x)\setminus W$. Then, $N^{\prime}\cup\\{x\\}$ is a cutset of $G$
that separates $Q^{*}$ from $W\cup Z$.

##  6 Star cutsets from loaded pyramids

The main theorem of this section is the following.

######  Theorem 6.1.

Let $G\in\mathcal{C}$. Suppose that $G$ contains a loaded pyramid
$\Pi=(\Sigma,P)$ with $a,b_{1},b_{2},b_{3},P_{1},P_{2},P_{3}$ as in the
definition. Then there is no connected component $D$ of $G\setminus N[b_{2}]$
with $\Pi\subseteq N[D]$.

In order to prove Theorem 6.1, we first prove the following:

######  Theorem 6.2.

Let $G\in\mathcal{C}$. Suppose that $G$ contains a loaded pyramid
$\Pi=(\Sigma,P)$ with $a,b_{1},b_{2},b_{3},P_{1},P_{2},P_{3}$ as in the
definition. Moreover, assume that $D$ is a connected component of $G\setminus
N[b_{2}]$ such that neither $N[D]\cap(\Pi\setminus P_{3})$ nor
$N[D]\cap(P_{3}\setminus\\{a\\})$ is empty. Then one of the following holds.

  * •

We have $N[D]\cap(\Pi\setminus P_{3})=\\{b_{1}\\}$ and
$N[D]\cap(P_{3}\setminus\\{a\\})=\\{b_{3}\\}$; or

  * •

There is a proper wheel $(H,b_{2})$ in $G$ with two long sectors $\Gamma_{1}$
and $\Gamma_{3}$ such that $\Gamma_{1}^{*}$ contains the neighbor of $a$ in
$P_{1}$ and $\Gamma_{3}=P_{3}$.

In order to prove Theorem 6.2, first we need to verify its assertion for two
special types of loaded pyramids, as follows. For a loaded pyramid
$(\Sigma,P)$ in a graph $G$, we say $(\Sigma,P)$ is of type 1 if
$N_{P_{1}}(p_{k})\subseteq N_{P_{1}}[b_{1}]$. We say that $(\Sigma,P)$ is of
type 2 if $b_{1}$ is anticomplete to $P$ and $p_{k}$ has exactly two neighbors
$x,y\in P_{1}$, and $x$ is adjacent to $y$.

######  Theorem 6.3.

Let $G\in\mathcal{C}$. Suppose that $G$ contains a loaded pyramid
$\Pi=(\Sigma,P)$ of type 1 with $a,b_{1},b_{2},b_{3},P_{1},P_{2},P_{3},P$ as
in the definition. Moreover, assume that $D$ is a connected component of
$G\setminus N[b_{2}]$ such that neither $N[D]\cap(\Pi\setminus P_{3})$ nor
$N[D]\cap(P_{3}\setminus\\{a\\})$ is empty. Then one of the following holds.

  * •

We have $N[D]\cap(\Pi\setminus P_{3})=\\{b_{1}\\}$ and
$N[D]\cap(P_{3}\setminus\\{a\\})=\\{b_{3}\\}$; or

  * •

There is a proper wheel $(H,b_{2})$ in $G$ with two long sectors $\Gamma_{1}$
and $\Gamma_{3}$ such that $\Gamma_{1}^{*}$ contains the neighbor of $a$ in
$P_{1}$ and $\Gamma_{3}=P_{3}$.

###### Proof.

Suppose not. Then since the first bullet of Theorem 6.3 does not hold, there
exists a shortest path $Q=q_{1}\hbox{-}\cdots\hbox{-}q_{t}$ in $G\setminus
N[b_{2}]$ with $t\geq 1$ where

  * •

$q_{1}$ has a neighbor in $P_{3}\setminus\\{a\\}$;

  * •

$q_{t}$ has a neighbor in $\Pi\setminus P_{3}$; and

  * •

either $q_{1}$ has a neighbor in $P_{3}^{*}$ or $q_{t}$ has a neighbor in
$P_{1}^{*}\cup P$.

From the minimality of $Q$, it follows that $Q^{*}$ is anticomplete to
$(\Sigma\cup P)\setminus\\{a,b_{1},b_{3}\\}$. Let $c$ be the neighbor of
$b_{1}$ in $P_{1}$. Then $c\neq a$, and since $G$ is $C_{4}$-free, $c$ is non-
adjacent to $a$.

(12) _ $N(q_{1})\cap P_{3}^{*}\neq\emptyset$._

For otherwise we have $N(q_{1})\cap(P_{3}\setminus\\{a\\})=\\{b_{3}\\}$.
Consequently $q_{t}$ has a neighbor in $P_{1}^{*}\cup P$, and so by the
minimality of $Q$, $Q\setminus\\{q_{1}\\}$ is anticomplete to
$P_{3}\setminus\\{a\\}$. Traversing $Q$ starting at $q_{1}$, let $q$ be the
the first vertex with a neighbor in $P^{\prime}=(P_{1}\setminus b_{1})\cup P$,
and traversing the path $P^{\prime}$ starting at $a$, let $x$ be the first
vertex adjacent to $q$. Then
$H=a\hbox{-}P^{\prime}\hbox{-}x\hbox{-}q\hbox{-}Q\hbox{-}q_{1}\hbox{-}b_{3}\hbox{-}P_{3}$
is a hole in $G$. Note that $\\{a,b_{3}\\}\subseteq N(b_{2})\cap
H\subseteq\\{a,b_{3},p_{1}\\}$. Since $H\cup\\{b_{2}\\}$ is not a theta in
$G$, it follows that $N(b_{2})\cap H=\\{a,b_{3},p_{1}\\}$. But then
$(H,b_{2})$ is a wheel in $G$ satisfying the second bullet of Theorem 6.3, a
contradiction. This proves (6).

(13) _ $N(b_{1})\cap(Q\setminus q_{t})=\emptyset$, and $q_{t}$ has a neighbor
in $P_{1}^{*}\cup P$._

Suppose not. Traversing $Q$ starting at $q_{t}$, let $q$ be the last vertex
adjacent to $b_{1}$. Since (6) does not hold, it follows that $q$ has no
neighbor in $P_{1}^{*}\cup P$. Note that by (6),
$q\hbox{-}Q\hbox{-}q_{1}\cup(P_{3}\setminus b_{3})$ is connected, and so
contains an induced path $R$ from $q$ to $a$. But then $P_{1}\cup
R\cup\\{b_{2}\\}$ is a theta with ends $a,b_{1}$ in $G$, which is impossible.
This proves (6).

(14) _ $N(Q)\cap(P\cup\\{b_{1}\\})\neq\emptyset$._ Suppose not. Then $q_{t}$
has a neighbor in $P_{1}\setminus b_{1}$. Traversing $P_{1}\setminus b_{1}$
starting at $a$, let $x$ be the last vertex with a neighbor in $Q$. It follows
that $x\neq a$. By (6) $x$ is adjacent to $q_{t}$ and anticomplete to
$Q\setminus q_{t}$. Traversing $P_{3}$ starting at $a$, let $y$ be the last
vertex adjacent to $q_{1}$; hence $y\neq a$. Then both $H_{1}=(P_{1}\setminus
b_{1})\cup P$ and
$H_{2}=c\hbox{-}P_{1}\hbox{-}x\hbox{-}q_{t}\hbox{-}Q\hbox{-}q_{1}\hbox{-}y\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{2}\hbox{-}p_{1}\hbox{-}P\hbox{-}p_{k}\hbox{-}c$
are holes in $G$. Note that $b_{1}$ has at least two non-adjacent neighbors in
$H_{1}$ and $N(b_{1})\cap H_{2}=(N(b_{1})\cap H_{1})\cup\\{b_{3}\\}$. So one
of $(H_{1},b_{1})$ and $(H_{2},b_{1})$ is an even wheel in $G$, a
contradiction. This proves (6).

(15) _ $N(q_{t})\cap P\neq\emptyset$._

Suppose for a contradiction that $q_{t}$ is anticomplete to $P$. Recall that
by the minimality of $t$, $Q\setminus q_{t}$ is also anticomplete to $P$.
Thus, $Q$ is anticomplete to $P$, and so by (6), we have $N(b_{1})\cap
Q\neq\emptyset$. This, together with (6), implies that $q_{t}$ is adjacent to
$b_{1}$. Since $q_{t}\hbox{-}b_{1}\hbox{-}b_{2}\hbox{-}a\hbox{-}q_{t}$ is not
a $C_{4}$ in $G$, $q_{t}$ is nonadjacent to $a$. Moreover, note that by (6),
it follows that $q_{t}$ has a neighbor in $P_{1}^{*}$. Traversing
$P_{1}\setminus b_{1}$ starting at $c$, let $x$ be the last vertex adjacent to
$q_{t}$. Also, by (6), $(P_{3}\setminus b_{3})\cup Q$ is connected, and so
contains a path $R$ from $q_{t}$ to $a$ (note that $R$ has more than one edge,
as $q_{t}$ is not adjacent to $a$). Now, if $x\neq c$, then we get a theta
with ends $a,q_{t}$ and paths $a\hbox{-}P_{1}\hbox{-}x\hbox{-}q_{t}$, $R$ and
$q_{t}\hbox{-}b_{1}\hbox{-}b_{2}\hbox{-}a$, a contradiction. Therefore, we
have $x=c$. But now we get a theta with ends $c,a$ and paths
$c\hbox{-}P_{1}\hbox{-}a$,
$c\hbox{-}p_{k}\hbox{-}P\hbox{-}p_{1}\hbox{-}b_{2}\hbox{-}a$ and
$c\hbox{-}q_{t}\hbox{-}R\hbox{-}a$, again a contradiction. This proves (6).

In particular, (6) implies that $b_{3}$ is anticomplete to $Q\setminus q_{1}$.
Henceforth, we denote the hole $(P_{1}\setminus b_{1})\cup P$ in $G$ by $K$.
Also, in view of (6), let $i\in\\{1,\dots,k\\}$ be minimum such that $q_{t}$
is adjacent to $p_{i}$. Denote the neighbor of $a$ in $P_{1}$ by $w$. Then
$w\neq c$.

(16) _ $|N(q_{t})\cap K|\geq 2$._

Suppose not. Then $p_{i}$ is the unique neighbor of $q_{t}$ in $K$. By (6),
$(P_{3}\setminus b_{3})\cup Q$ is connected, and so contains a path $R$ from
$q_{t}$ to $a$. But now $K\cup R$ is a theta with ends $a,p_{i}$ in $G$, which
is impossible. This proves (6).

(17) _ $q_{t}$ has a neighbor in $K\setminus(N[a]\cup\\{p_{1}\\})$._

Suppose not. Then $i=1$. Since
$q_{t}\hbox{-}p_{1}\hbox{-}b_{2}\hbox{-}a\hbox{-}q_{t}$ is not a $C_{4}$ in
$G$, it follows that $q_{t}$ is non-adjacent to $a$. Now
$N_{K}(q_{t})=\\{p_{1},w\\}$ and so $K\cup q_{t}$ is a theta, a contradiction.
This proves (6).

In view of (6) there is a path $P^{\prime}$ from $q_{t}$ to $b_{1}$ with
interior in $K\setminus\\{b_{2},a,p_{1},w\\}$. It follows from (6) and the
minimality of $t$ that $q_{t}$ is the only vertex of $P^{\prime*}$ with a
neighbor in $Q\setminus q_{t}$.

(18) _ $N(a)\cap Q=\emptyset$._

Suppose not. By (6), $(P_{3}\setminus a)\cup\\{q_{1}\\}$ is connected, and so
contains an induced path $R$ from $b_{3}$ to $q_{1}$. Now $H_{1}=Q\cup
P^{\prime}\cup R$ and $H_{2}=Q\cup
b_{2}\hbox{-}p_{1}\hbox{-}P\hbox{-}p_{i}\cup R$ are holes in $G$. Also, we
have $N(a)\cap H_{1}=N(a)\cap(Q\cup R)$ and $N(a)\cap H_{2}=(N(a)\cap
H_{1})\cup\\{b_{2}\\}$. If $|N(a)\cap(Q\cup R)|\geq 3$, then either
$(H_{1},a)$ or $(H_{2},a)$ is an even wheel in $G$, which is impossible. Also,
if $|N(a)\cap(Q\cup R)|=1$, then $H_{2}\cup\\{a\\}$ is a theta in $G$, which
is impossible. It follows that $|N(a)\cap(Q\cup R)|=2$. Since
$H_{1}\cup\\{a\\}$ is not a theta in $G$, the two neighbors of $a$ in $H_{1}$
are adjacent and contained in $(Q\cup R)\setminus\\{b_{3}\\}$. But now
$H_{1}\cup\\{a,b_{2}\\}$ is a prism in $G$, which is impossible. This proves
(6).

If $q_{1}$ has exactly one neighbor $x$ in $P_{3}$, then by (6), $x\in
P_{3}^{*}$ and, using (6) we get a theta with ends $x,b_{2}$ and paths
$x\hbox{-}P_{3}\hbox{-}a\hbox{-}b_{2}$,
$x\hbox{-}q_{1}\hbox{-}Q\hbox{-}q_{t}\hbox{-}p_{i}\hbox{-}P\hbox{-}b_{2}$, and
$x\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{2}$, a contradiction. Thus, traversing
$P_{3}$ starting at $b_{3}$, we may assume $y$ and $z$ to be the first and the
last neighbor of $q_{1}$ in $P_{3}$, respectively, and $y\neq z$. If $z$ is
non-adjacent to $y$, using (6) we get a theta with ends $b_{2},q_{1}$ and
paths $q_{1}\hbox{-}z\hbox{-}P_{3}\hbox{-}a\hbox{-}b_{2}$,
$q_{1}\hbox{-}Q\hbox{-}q_{t}\hbox{-}p_{i}\hbox{-}P\hbox{-}b_{2}$, and
$q_{1}\hbox{-}y\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{2}$, a contradiction. So
$z$ and $y$ are adjacent. But now, again using (6), we get a near-prism with
triangles $b_{1}b_{2}b_{3}$ and $q_{1}zy$ and paths
$b_{1}\hbox{-}P^{\prime}\hbox{-}q_{t}\hbox{-}Q\hbox{-}q_{1}$,
$b_{2}\hbox{-}a\hbox{-}P_{3}\hbox{-}z$ and $b_{3}\hbox{-}P_{3}\hbox{-}y$, a
contradiction. ∎

######  Theorem 6.4.

Let $G\in\mathcal{C}$. Suppose that $G$ contains a loaded pyramid
$\Pi=(\Sigma,P)$ of type 2 with $a,b_{1},b_{2},b_{3},P_{1},P_{2},P_{3},P$ as
in the definition. Moreover, assume that $D$ is a connected component of
$G\setminus N[b_{2}]$ such that neither $N[D]\cap(\Pi\setminus P_{3})$ nor
$N[D]\cap(P_{3}\setminus\\{a\\})$ is empty. Then one of the following holds.

  * •

We have $N[D]\cap(\Pi\setminus P_{3})=\\{b_{1}\\}$ and
$N[D]\cap(P_{3}\setminus\\{a\\})=\\{b_{3}\\}$; or

  * •

There is a proper wheel $(H,b_{2})$ in $G$ with two long sectors $\Gamma_{1}$
and $\Gamma_{3}$ such that $\Gamma_{1}^{*}$ contains the neighbor of $a$ in
$P_{1}$ and $\Gamma_{3}=P_{3}$.

###### Proof.

Suppose not. Assume that $P_{1}$ traverses $b_{1},x,y,a$ in this order, where
$x$ and $y$ are the two neighbors of $q_{t}$ in $P_{1}$. Then $b_{1}\neq x$.
Let $P^{\prime}_{1}=b_{1}\hbox{-}P_{1}\hbox{-}x$,
$P^{\prime\prime}_{1}=y\hbox{-}P_{1}\hbox{-}a$. We write
$P=p_{1}\hbox{-}\cdots\hbox{-}p_{k}$ where $p_{1}$ is adjacent to $b_{2}$, and
$p_{k}$ has a neighbor in $P_{1}^{*}$.

Since the first bullet of Theorem 6.4 does not hold, there exists a shortest
path $Q=q_{1}\hbox{-}\cdots\hbox{-}q_{t}$ in $G\setminus N[b_{2}]$ with $t\geq
1$ where

  * •

$q_{1}$ has a neighbor in $P_{3}\setminus\\{a\\}$;

  * •

$q_{t}$ has a neighbor in $\Pi\setminus P_{3}$; and

  * •

either $q_{1}$ has a neighbor in $P_{3}^{*}$ or $q_{t}$ has a neighbor in
$P_{1}^{*}\cup P$.

From the minimality of $Q$, it follows that $Q^{*}$ is anticomplete to
$(\Sigma\cup P)\setminus\\{a,b_{1},b_{3}\\}$. Let $c$ be the neighbor of
$b_{1}$ in $P_{1}$. Then $c\neq a$, and since $G$ is $C_{4}$-free, $c$ is non-
adjacent to $a$.

(19) _$q_{t}$ has a neighbor in $P\cup P_{1}^{\prime}$._

Suppose not. Then $N_{P_{1}}(q_{t})\subseteq P_{1}^{\prime\prime}$, and there
is a path $R$ from $y$ to $b_{3}$ with $R\subseteq P_{1}^{\prime\prime}\cup
Q\cup P_{3}$. Now we get a prism with triangles $p_{k}xy$ and
$b_{1}b_{2}b_{3}$ and paths $P$, $P_{1}^{\prime}$ and $R$, a contradiction.
This proves (6).

(20) _$q_{1}$ has a neighbor in $P_{3}^{*}$._

Suppose not. Then $N_{P_{3}}(q_{1})\subseteq\\{b_{3},a\\}$. Suppose first that
either $a$ has a neighbor in $Q$, or $q_{t}$ has a neighbor in
$(P_{1}\setminus b_{1})\cup(P\setminus p_{1})$. Then there is a path $R$ from
$q_{1}$ to $a$ with $R^{*}\subseteq Q\cup(P_{1}\setminus b_{1})\cup(P\setminus
p_{1})$. Now we get a theta with ends $b_{3},a$ and paths $P_{3}$,
$b_{3}\hbox{-}b_{2}\hbox{-}a$ and $b_{3}\hbox{-}q_{1}\hbox{-}R\hbox{-}a$, a
contradiction.

It follows that $a$ is anticomplete to $Q$, and $N_{P_{1}\cup
P}(q_{t})\subseteq\\{p_{1},b_{1}\\}$. From the choice of $Q$, and since $G$ is
$C_{4}$-free, it follows that $N_{P_{1}\cup P}(q_{t})=\\{p_{1}\\}$. Now
$H=b_{3}\hbox{-}Q\hbox{-}p_{1}\hbox{-}P\hbox{-}y\hbox{-}P_{1}^{\prime\prime}\hbox{-}a\hbox{-}P_{3}\hbox{-}b$
is a hole, and so $(H,b_{2})$ is a proper wheel satisfying the second outcome
of the theorem. This proves (6).

It follows from (6) and the minimality of $t$ that $b_{1}$ is anticomplete to
$Q\setminus q_{t}$. Let $v$ be the neighbor of $q_{1}$ in $P_{3}$ closest to
$b_{3}$. Let $v^{\prime}$ be the neighbor of $q_{1}$ in $P_{3}$ closest to
$a$.

(21) _$q_{t}$ has a neighbor in $P_{1}^{*}\cup P$._

Suppose not. Then $N_{P_{1}\cup P}(q_{t})\subseteq\\{b_{1},a\\}$. By (6) there
is a path $R$ from $q_{t}$ to $a$ with $R^{*}\subseteq Q\cup(P_{3}\setminus
b_{3})$. Now we get a theta with ends $b_{1},a$ and paths $P_{1}$,
$b_{1}\hbox{-}b_{2}\hbox{-}a$ and $b_{1}\hbox{-}q_{t}\hbox{-}R\hbox{-}a$, a
contradiction. This proves (6).

It follows from (6) and the minimality of $t$ that $b_{3}$ is anticomplete to
$Q\setminus q_{1}$.

(22) _$a$ is anticomplete to $Q$._

Suppose not. Let $R_{1}$ be a path from $q_{1}$ to $b_{1}$ with
$R_{1}^{*}\subseteq Q\cup P_{1}^{\prime}\cup P$. If possible, choose $R_{1}$
so that $p_{1}\not\in R_{1}$. Observe that $Q\subseteq R_{1}$ and $a$ is
anticomplete to $R_{1}\setminus Q$. Let $H_{1}$ be the hole
$b_{1}\hbox{-}R_{1}\hbox{-}q_{1}\hbox{-}v\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{1}$.
By (6) there is a path $R_{2}$ from $b_{2}$ to $q_{1}$ with
$R_{2}^{*}\subseteq Q\cup P\cup(P_{1}^{\prime}\setminus b_{1})$. Observe that
$Q\subseteq R_{2}$ and $a$ is anticomplete to $R_{2}\setminus Q$. Let $H_{2}$
be the hole
$b_{2}\hbox{-}R_{2}\hbox{-}q_{1}\hbox{-}v\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{2}$.
Now $N_{H_{2}}(a)=N_{H_{1}}(a)\cup\\{b_{2}\\}$. Since neither of $(H_{1},a)$,
$(H_{2},a)$ is a theta or an even wheel in $G$, it follows that $a$ has
exactly two neighbors $uw$ in $Q$, and $u$ is adjacent to $w$. We may assume
that $Q$ traverses $q_{1},u,w,q_{t}$ in this order. If $p_{1}\not\in R_{1}$,
we get a prism with triangles $auw$ and $b_{1}b_{2}b_{3}$ and paths $ab_{2}$,
$u\hbox{-}Q\hbox{-}q_{1}\hbox{-}v\hbox{-}P_{3}\hbox{-}b_{3}$ and
$w\hbox{-}R_{1}\hbox{-}b_{1}$, a contradiction. This proves that $p_{1}\in
R_{1}$, and therefore $N_{P\cup P_{1}^{\prime}}(q_{t})=\\{p_{1}\\}$. Now let
$H_{3}$ be the hole
$b_{1}\hbox{-}P_{1}^{\prime}\hbox{-}x\hbox{-}p_{k}\hbox{-}P\hbox{-}p_{1}\hbox{-}q_{t}\hbox{-}Q\hbox{-}w\hbox{-}a\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{1}$.
Then $N_{H_{3}}(b_{2})=\\{b_{1},b_{3},p_{1},a\\}$ and so $(H_{3},b_{2})$ is an
even wheel, a contradiction. This proves (6).

(23) _$N(q_{t})\cap(P_{1}\cup P)$ is a clique of size at least 2._ Suppose
not. Since $G$ is $C_{4}$-free, $q_{t}$ is non-adjacent to at least one of
$b_{1}$ and the neighbor $p_{1}$ of $b_{2}$ in $P$. Suppose that there are two
paths $R_{1},R_{2}$ from $q_{t}$ to $a$, both with interior in $P_{1}\cup
P\cup b_{2}$ and such that $R_{1}^{*}$ is anticomplete to $R_{2}^{*}$. Then we
get a theta with ends $q_{t},a$ and paths $R_{1},R_{2}$ and
$q_{t}\hbox{-}Q\hbox{-}v^{\prime}\hbox{-}P_{3}\hbox{-}a$, a contradiction. It
follows that $q_{t}$ has a unique neighbor $w$ in $P_{1}\cup P\cup b_{2}$. By
(6), $w$ is non-adjacent to $a$. Now there are two path $R_{1},R_{2}$ from $w$
to $a$ with interior in $P_{1}\cup P\cup b_{2}$ and such that $R_{1}^{*}$ is
anticomplete to $R_{2}^{*}$, and we get a theta with ends $w,a$ and paths
$R_{1},R_{2}$ and
$w\hbox{-}q_{t}\hbox{-}Q\hbox{-}v^{\prime}\hbox{-}P_{3}\hbox{-}a$, a
contradiction. This proves (6).

If follows from (6) and (6) that
$N_{P_{1}^{\prime\prime}}(q_{t})\subseteq\\{y\\}$.

(24) _$q_{t}$ is adjacent to $y$._ Suppose not. Let $N_{P_{1}\cup
P}(q_{t})=\\{u,w\\}$, and we may assume that $P_{1}^{\prime}\cup P$ traverses
$b_{1},u,w,p_{1}$ in this order. Then there is a prism with triangles
$uwq_{t}$ and $b_{1}b_{2}b_{3}$, two of whose paths have interior in
$P_{1}^{\prime}\cup P$, and the third one is
$q_{t}\hbox{-}Q\hbox{-}q_{1}\hbox{-}v\hbox{-}P_{3}\hbox{-}b_{3}$, a
contradiction. This proves (6).

(25) _$q_{t}$ is non-adjacent to $x$._

Suppose $q_{t}$ is adjacent to $x$. Since we do not get a prism with triangles
$xyq_{t}$ and $b_{1}b_{2}b_{3}$ and paths $x\hbox{-}P_{1}\hbox{-}b_{1}$,
$y\hbox{-}P_{1}\hbox{-}a\hbox{-}b_{2}$ ad
$q_{t}\hbox{-}Q\hbox{-}q_{1}\hbox{-}v\hbox{-}P_{3}\hbox{-}b_{3}$, it follows
that $v=v^{\prime}$ is adjacent to $a$. But now we get a theta with ends
$b_{2},v$ and paths $b_{2}\hbox{-}a\hbox{-}v$,
$b_{2}\hbox{-}p_{1}\hbox{-}P\hbox{-}p_{k}\hbox{-}x\hbox{-}q_{t}\hbox{-}Q\hbox{-}q_{1}\hbox{-}v$
($x$ is omitted if $p_{k}$ is adjacent to $q_{t}$) and
$b_{2}\hbox{-}b_{3}\hbox{-}P_{3}\hbox{-}v$. This proves (6).

By (6), (6), and (6), we deduce that $N_{P\cup P_{1}}(q_{t})=\\{y,p_{k}\\}$.

Suppose that $y$ is non-adjacent to $a$. Then $G$ contains a theta with ends
$a,y$ and paths $P_{1}^{\prime\prime}$,
$y\hbox{-}P_{1}^{\prime}\hbox{-}b_{1}\hbox{-}b_{2}\hbox{-}a$, and
$y\hbox{-}q_{t}\hbox{-}Q\hbox{-}q_{1}\hbox{-}v^{\prime}\hbox{-}P_{3}\hbox{-}a$,
a contradiction. This proves that $y$ is adjacent to $a$. Since $G$ is
$C_{4}$-free, it follows that $p_{k}$ is non-adjacent to $b_{2}$. Now, since
by (6) $v^{\prime}\neq b_{3}$, there is a theta with ends $p_{k},b_{2}$ and
paths $p_{k}\hbox{-}x\hbox{-}P_{1}^{\prime}\hbox{-}b_{1}\hbox{-}b_{2}$,
$p_{k}\hbox{-}P\hbox{-}p_{1}\hbox{-}b_{2}$ and
$p_{k}\hbox{-}q_{t}\hbox{-}Q\hbox{-}q_{1}\hbox{-}v^{\prime}\hbox{-}P_{3}\hbox{-}a\hbox{-}b_{2}$.
∎

Having proved Theorems 6.3 and 6.4, we can give a proof of Theorem 6.2, below.

###### Proof of Theorem 6.2.

Suppose for a contradiction that there exists a loaded pyramid
$\Pi=(\Sigma,P)$ in $G$ with $a,b_{1},b_{2},b_{3},P_{1},P_{2},P_{3},P$ as in
the definition, and a connected component $D$ of $G\setminus N[b_{2}]$ for
which neither $N[D]\cap(\Pi\setminus P_{3})$ nor
$N[D]\cap(P_{3}\setminus\\{a\\})$ is empty, such that neither of the two
bullets of Theorem 6.2 hold. Also, let $a^{\prime}$ be the neighbor of $a$ in
$P_{1}$, and subject to the above properties and $a^{\prime}$ being the
neighbor of $a$ in $P_{1}$, let $|P_{1}|$ be minimal. We claim:

(26) _We have $N(p_{k})\cap P_{1}$ is a clique._

Suppose not. Traversing $P_{1}$ from $b_{1}$ to $a$, let $x$ and $y$ be the
first and the last neighbor of $p_{k}$ in $P_{1}$, respectively. Then $x$ and
$y$ are distinct and non-adjacent, and we have $y\neq a$. If $k=1$, then
$H=b_{1}\hbox{-}P_{1}\hbox{-}x\hbox{-}p_{k}\hbox{-}y\hbox{-}P_{1}\hbox{-}a\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{1}$
is a hole in $G$ and $b_{2}$ has exactly four neighbors in $H$, namely
$a,b_{1},b_{3}$ and $p_{k}$. But then $(H,b_{2})$ is an even wheel in $G$,
which is impossible. So $k>1$ and consequently $b_{2}$ is not adjacent to
$p_{k}$. Now, replacing the path $P_{1}$ in the pyramid $\Sigma$ by the path
$P_{1}^{\prime}=b_{1}\hbox{-}P_{1}\hbox{-}x\hbox{-}p_{k}\hbox{-}y\hbox{-}P_{1}\hbox{-}a$
we obtain a pyramid $\Sigma^{\prime}$ in $G$, where
$\Pi^{\prime}=(\Sigma^{\prime},P\setminus p_{k})$ is a loaded pyramid in $G$
with $|P_{1}^{\prime}|<|P_{1}|$ and $D$ is a connected component of
$G\setminus N[b_{2}]$ for which neither $N[D]\cap(\Pi^{\prime}\setminus
P_{3})$ nor $N[D]\cap(P_{3}\setminus\\{a\\})$ is empty, such that neither of
the two bullets of Theorem 6.2 hold. This violates the choice of $\Pi$, and
hence proves (6).

(27) _The vertex $b_{1}$ is anticomplete to $P$._

Suppose not. Let $i$ be maximum such that $b_{1}$ is adjacent to $p_{i}$.
Also, traversing $P_{1}$ from $b_{1}$ to $a$, let $y$ be the last neighbor of
$p_{k}$ in $P_{1}$. Then we have $y\in P_{1}\setminus\\{a,b_{1}\\}$. If $y$ is
adjacent to $b_{1}$, then $N_{P_{1}}(p_{k})\subseteq N_{P_{1}}(b_{1})$ and
$\Pi$ is a loaded pyramid of type 1, which together with Theorem 6.3 implies
that the one of the two bullets of Theorem 6.2 holds, a contradiction. Thus,
$y$ is not adjacent to $b_{1}$. Suppose that $i=1$. Then
$H=b_{1}\hbox{-}p_{1}\hbox{-}P\hbox{-}y\hbox{-}P_{1}\hbox{-}a\hbox{-}P_{3}\hbox{-}b_{3}\hbox{-}b_{1}$
is a hole in $G$ and $b_{2}$ has exactly four neighbors in $H$, namely
$a,b_{1},b_{3}$ and $p_{1}$. But then $(H,b_{2})$ is an even wheel, which is
impossible. So $i>1$, and consequently $b_{2}$ is not adjacent to $p_{i}$.
Now, replacing the path $P_{1}$ in the pyramid $\Sigma$ by the path
$P_{1}^{\prime}=b_{1}\hbox{-}p_{i}\hbox{-}P\hbox{-}p_{k}\hbox{-}y\hbox{-}P_{1}\hbox{-}a$
we obtain a pyramid $\Sigma^{\prime}$ in $G$, where
$\Pi^{\prime}=(\Sigma^{\prime},p_{1}\hbox{-}P\hbox{-}p_{i-1})$ is a loaded
pyramid in $G$ with $|P_{1}^{\prime}|<|P_{1}|$, and $D$ is a connected
component of $G\setminus N[b_{2}]$ for which neither
$N[D]\cap(\Pi^{\prime}\setminus P_{3})$ nor $N[D]\cap(P_{3}\setminus\\{a\\})$
is empty, such that neither of the two bullets of Theorem 6.2 hold. This
violates the choice of $\Pi$, and hence proves (6).

Now, if $p_{k}$ has exactly one neighbor $x$ in $P_{1}$, then $x\neq b_{1}$
and so by (6), $P_{1}\cup P\cup\\{b_{2}\\}$ is a theta with ends $b_{2},x$ in
$G$, a contradiction. Therefore, by (6), $p_{k}$ has exactly two neighbors in
$P_{1}$, which are adjacent. Also, by (6), $b_{1}$ is anticomplete to $P$, and
in particular $b_{1}$ is not adjacent to $p_{k}$. Therefore, we may assume
that $N(p_{k})\cap P_{1}=\\{x,y\\}\subseteq P_{1}\setminus\\{a,b_{1}\\}$ where
$P_{1}$ traverses $b_{1},x,y,a$ in this order. But now $\Pi$ is loaded pyramid
of type 2, which along with Theorem 6.4 implies that the one of the two bullet
of Theorem 6.2 holds, a contradiction. This completes the proof of Theorem
6.2. ∎

We now prove Theorem 6.1.

###### Proof.

Suppose not, and let $D$ be a component of $G\setminus N[b_{2}]$ such that
$\Pi\subseteq N[D]$. By Theorem 6.2 we deduce that there is a proper wheel
$(H,b_{2})$ in $G$ with two long sectors $\Gamma_{1}$ and $\Gamma_{3}$ such
that $\Gamma_{1}^{*}$ contains the neighbor of $a$ in $P_{1}$ and
$\Gamma_{3}=P_{3}$. But now we get a contradiction to Theorem 5.2. ∎

From Theorem 5.1 and Theorem 6.1 we deduce:

######  Theorem 6.5.

Let $G\in\mathcal{C}$ and let $(H,v)$ be a proper wheel or a loaded pyramid in
$G$. Then there is no component $D$ of $G\setminus N[v]$ such that $H\subseteq
N[D]$.

##  7 Tree strip systems

In this section we summarize results from [17] that allow us to deal with
cross-edges of near-prisms in an even-hole-free graph. Recall that an extended
near-prism is a graph obtained from a near-prism by adding one extra edge, as
follows. Let $P_{1},P_{2},P_{3}$ be as in the definition of a near-prism, and
let $a\in P_{1}^{*}$ and $b\in P_{2}^{*}$; and add an edge $ab$. We call $ab$
the cross-edge of the extended near-prism. Next we explain a theorem from [17]
that describes the structure of graphs with an extended near prism. We start
with several definitions from [17].

Let $T$ be a tree with at least 3 leaves. A leaf of $T$ is a vertex of degree
exactly one, and a leaf-edge is an edge incident with a leaf. Let
$(A^{\prime},B^{\prime})$ be a bipartition of $T$, and assume that for every
$v\in V(T)$, there is at most one component $C$ of $T\setminus v$ such that
$A^{\prime}\cap C=\emptyset$, and at most one such that $B^{\prime}\cap
C=\emptyset$. (Note that every component $C$ of $T\setminus v$ contains a leaf
of $T$ and therefore meets at least one of $A^{\prime},B^{\prime}$.) Since
$|V(T)|\geq 3$, each leaf-edge is incident with only one leaf; let $A$ be the
set of leaf-edges incident with a leaf in $A^{\prime}$, and define $B$
similarly. Let $L(T)$ be the line-graph of $T$, that is the vertex set of
$L(T)$ is the edge set of $T$, and two edges of $T$ are adjacent in $L(T)$ if
they share an end in $T$. Add to $L(T)$ two more vertices $a,b$ and the edge
$ab$, and make $a$ complete to $A$ and $b$ complete to $B$, forming a graph
$H(T)$ with vertex set $E(T)\cup\\{a,b\\}$. We say that $H(T)$ is an extended
tree line-graph, and $ab$ is its cross-edge.

Every extended near-prism is an extended tree line-graph, where the
corresponding tree has four leaves and exactly two vertices of degree three.

A branch-vertex of a tree is a vertex of degree different from two (thus,
leaves are branch-vertices). A branch of a tree $T$ is a path $P$ of $T$ with
distinct ends $u,v$, both branch-vertices, such that every vertex of $P^{*}$
has degree two in $T$. Every edge of $T$ belongs to a unique branch.

Let $T$ be a tree, and let $U$ be the set of branch-vertices of $T$; and make
a new tree $J$ with vertex set $U$ by making $u,v\in U$ adjacent in $J$ if
there is a branch of $T$ with ends $u,v$. We call $J$ the shape of $T$. Thus
$J$ has no vertices of degree two; and $T$ is obtained from $J$ by replacing
each edge by a path of positive length.

Let $A,B,C$ be subsets of $V(G)$, with $A,B\neq\emptyset$ and disjoint from
$C$, and let $S=(A,B,C)$. A rung of $S$, or an $S$-rung, is a path
$p_{1}\hbox{-}\cdots\hbox{-}p_{k}$ of $G[A\cup B\cup C]$ such that $p_{1}\in
A$, $p_{k}\in B$ and $p_{2},\ldots,p_{k-1}\in C$, and if $k>1$ then
$p_{1}\notin B$ and $p_{k}\notin A$. (If $A\cap B\neq\emptyset$, then $k=1$ is
possible.) If every vertex in $A\cup B\cup C$ belongs to an $S$-rung, we call
$S$ a strip.

Let $J$ be a tree with at least three vertices. $M$ is a $J$-strip system in a
graph $G$ consists of:

  * •

for each edge $e=uv$ of $J$, a subset $M_{uv}=M_{vu}=M_{e}$ of $V(G)$; and

  * •

for each $v\in V(J)$, a subset $M_{v}$ of $V(G)$

satisfying the following conditions:

  * •

the sets $M_{e}\;(e\in E(J))$ are pairwise disjoint;

  * •

for each $u\in V(J)$, $M_{u}\subseteq\bigcup_{v\in N_{J}(u)}M_{uv}$;

  * •

for each $uv\in E(J)$, $(M_{uv}\cap M_{u},M_{uv}\cap
M_{v},M_{uv}\setminus(M_{u}\cup M_{v}))$ is a strip;

  * •

if $uv,wx\in E(J)$ with $u,v,w,x$ all distinct, then there are no edges
between $M_{uv}$ and $M_{wx}$;

  * •

if $uv,uw\in E(J)$ with $v\neq w$, then $M_{u}\cap M_{uv}$ is complete to
$M_{u}\cap M_{uw}$, and there are no other edges between $M_{uv}$ and
$M_{uw}$.

A rung of the strip $(M_{uv}\cap M_{u},M_{uv}\cap
M_{v},M_{uv}\setminus(M_{u}\cup M_{v}))$ will be called an $e$-rung or
$uv$-rung. (the dependence on $M$ and $J$ is left implicit, for the sake of
brevity.) Let $V(M)$ denote the union of the sets $M_{e}\;(e\in E(J))$.

Let $J$ be a tree, let $M$ be a $J$-strip system in $G$, and let
$(\alpha,\beta)$ be a partition of the set of leaves of $J$. We say an edge
$ab$ of $G$ is a cross-edge for $M$ with partition $(\alpha,\beta)$ if:

  * •

$J$ has no vertex of degree two, and at least three vertices;

  * •

for every vertex $s\in V(J)$, $s$ has at most one neighbor in $\alpha$, and at
most one in $\beta$;

  * •

$a,b\not\in V(M)$; and

  * •

$a$ is complete to $\bigcup_{u\in\alpha}M_{u}$, and $a$ has no other neighbors
in $V(M)$; $b$ is complete to $\bigcup_{u\in\beta}M_{u}$, and $b$ has no other
neighbors in $V(M)$.

Under these circumstances, a leaf $v\in\alpha$ is called and $a$-leaf, and a
leaf $v\in\beta$ is a $b$-leaf.

Let $M$ be a $J$-strip system in $G$ with cross-edge $ab$ and partition
$(\alpha,\beta)$. We say $X\subseteq V(M)\cup\\{a,b\\}$ is local if either:

  * •

$X\subseteq M_{e}$ for some $e\in E(J)$;

  * •

$X\subseteq M_{u}$ for some $u\in V(J)$; or

  * •

$X$ contains $a$ and not $b$, and $X\setminus\\{a\\}\subseteq M_{u}$ for some
leaf $u\in\alpha$; or $X$ contains $b$ and not $a$, and
$X\setminus\\{a\\}\subseteq M_{u}$ for some leaf $u\in\beta$.

Next we describe two maximizations:

  * •

We start with an even-hole-free graph $G$, and an edge $ab$ of $G$, such that
there is an extended tree line-graph $H(T)$ that is an induced subgraph of
$G$, with cross-edge $ab$. Subject to this we choose $T$ with as many branches
as possible, that is, such that its shape $J$ has $|E(J)|$ maximum.

  * •

Then we choose a $J$-strip system $M$ in $G$ with the same cross-edge $ab$,
with $V(M)$ maximal.

In these circumstances $(J,M)$ is said to be optimal for $ab$.

We will need the following special case of Theorem 4.2 of [17] (here we have
corrected a typo that occurred in the statement in [17]):

######  Theorem 7.1 (Chudnovsky, Seymour [17]).

Let $ab$ be an edge of an even-hole-free graph $G$, and let $(J,M)$ be optimal
for $ab$. Assume that no vertex of $G$ is adjacent to both $a$ and $b$. Then
for every connected induced subgraph $F$ of $G\setminus(M\cup\\{a,b\\})$:

  * •

if not both $a,b$ have neighbors in $V(F)$, then the set of vertices in
$V(M)\cup\\{a,b\\}$ with a neighbor in $V(F)$ is local;

  * •

if both $a,b$ have neighbors in $V(F)$, then there exists a leaf $t$ of $J$
such that every vertex of $V(M)$ with a neighbor in $V(F)$ belongs to $M_{t}$.

Theorem 7.1 assumes that $G$ is even-hole-free, rather than $G\in\mathcal{C}$.
It is likely that the proof works under the more general assumption, we but we
have not verified the details. The last result of this section is a slight
strengthening of Theorem 7.1:

######  Theorem 7.2.

Let $ab$ be an edge of an even-hole-free graph $G$, and let $(J,M)$ be optimal
for $ab$. Let $(\alpha,\beta)$ be the partition such that $ab$ is a cross-edge
for $M$ with partition $(\alpha,\beta)$. Assume that

  * •

$|\beta|\geq 2$;

  * •

no vertex of $G$ is adjacent to both $a$ and $b$;

  * •

$a,b\not\in\operatorname{Hub}(G)$; and

  * •

$G\setminus N[a]$ is connected.

Let $F\subseteq G\setminus(M\cup\\{a,b\\})$ be connected. Then $a$ is
anticomplete to $F$, and the set of vertices in $M\cup\\{b\\}$ with a neighbor
in $F$ is local.

###### Proof.

Let $F$ be a component of $G\setminus(M\cup\\{a,b\\})$; notice that it
suffices to prove Theorem 7.2 for such $F$. If $a$ is anticomplete to $F$, the
result follows from Theorem 7.1. Thus suppose that $a$ has a neighbor in $F$.
By Theorem 7.1 there exists a leaf $t$ of $J$ such that $N(F)\subseteq
M_{t}\cup\\{a,b\\}$. Since $G\setminus N[a]$ is connected, it follows that $t$
is a $b$-leaf and $N(F)\cap M_{t}\neq\emptyset$. Let $P$ be a path from $a$ to
a vertex of $x\in M_{t}$ with $P^{*}\subseteq F$. Let $Q$ be a path of $J$
from $t$ to an $a$-leaf $t^{\prime}$. Concatenating rungs corresponding to
edges of $Q$ in $M$, we obtain a path $R$ from $x$ to a vertex $y\in
M_{t}^{\prime}$. Let $H$ be the hole
$x\hbox{-}R\hbox{-}y\hbox{-}a\hbox{-}P\hbox{-}x$. Since $H\cup b$ is not a
theta, it follows that $b$ has a neighbor in $P^{*}$. Since $(H,b)$ is not a
proper wheel and $N(a)\cap N(b)=\emptyset$, it follows that $b$ has a unique
neighbor $x^{\prime}\in P^{*}$ and $x^{\prime}$ is adjacent to $x$ and non-
adjacent to $a$. Let $t^{\prime\prime}$ be a $b$-leaf in $J$ such that
$t^{\prime\prime}\neq t$, and let $S$ be a shortest path in $J$ from
$t^{\prime\prime}$ to $Q$. Since $t$ is a leaf, it follows that $t\not\in S$.
Concatenating rungs corresponding to edges of $S$ in $M$, we obtain a path $T$
from $x^{\prime\prime}\in M_{t^{\prime\prime}}$ to a vertex with two
(consecutive) neighbors in $R$. But now $H\cup T\cup\\{b\\}$ is a loaded
pyramid with loaded corner $b$ and apex $a$, contrary to the fact that
$b\not\in\operatorname{Hub}(G)$. This proves Theorem 7.2. ∎

##  8 From local to global separators

In this section we prove a theorem that is the heart of the proof of our main
result. Qualitatively, the content of this theorem is the following. We have a
graph $G$ whose vertex set is partitioned into two subsets $D$ and $X$ where
$D$ is connected, and $X=N(D)$. We also have a dustinguished vertex $b\in D$.
We are given a collection of clique cutsets separating individual vertices of
$X$ from $b$ (and with additional properties). The theorem asserts that there
is one cutset, whose clique cover number is bounded from above by an absolute
constant, that separates a positive proportion of the vertices of $X$ from
$b$.

Let us now delve into the details. Let $D$ be graph and let $b\in D$. Our
first goal is to associate to each clique of $D$ a canonical separation. First
we handle cliques that do not contain $b$; in this case the definition is
similar in spirit to other papers in the series. For every clique $K\subseteq
D\setminus b$ let $B(K)$ be the component of $D\setminus K$ with $b\in B(K)$.
Let $C(K)=N(B(K))$ and $A(K)=D\setminus(C(K)\cup B(K))$. We call
$(A(K),C(K),B(K))$ the $b$-canonical separation for $K$.

Now we extend the definition of a $b$-canonical separation to all cliques of
$D$. Thus let $K\subseteq D$ be a clique such that $b\in K$. Let $B(K)$ be the
union of the components $D^{\prime}$ of $D\setminus K$ such that $b\in
N[D^{\prime}]$. Let $C(K)=N(B(K))$ and let $A(K)=D\setminus(B(K)\cup C(K))$.
Note that $(A(K),C(K),B(K))=(A(K\setminus b),C(K\setminus
b)\cup\\{b\\},B(K\setminus b)\setminus\\{b\\})$.

Let $\mathcal{K}$ be the set of all cliques of $D$ with $A(K)$ maximal. Let
$\beta(D,b)=\bigcap_{K\in\mathcal{K}}(B(K)\cup C(K)$). (Some readers may
recognize $\beta(D,b)$ as the “central bag” for a collection of separations
defined in [7].) For every $v\in D\setminus\beta(D,b)$, let $F(v)$ be the
component of $D\setminus\beta(D,b)$ such that $v\in F(v)$. The next two lemmas
describe some of the properties of $\beta(D,b)$.

######  Lemma 8.1.

We have $b\in\beta(D,b)$. For every component $F$ of $D\setminus\beta(D,b)$
there exists $K\in\mathcal{K}$ such that $F\subseteq A(K)$. In particular,
$N(F(v))$ is a clique for every $v\in D\setminus\beta(D,b)$.

###### Proof.

We prove the first assertion of the lemma first.

(28) _$b\in\beta(D,b)$._

Let $K\in\mathcal{K}$. Then $b\in C(K)\cup B(K)$, and therefore (8) follows.

(29) _Let $K_{1},K_{2}\in\mathcal{K}$. Then $C(K_{1})\cap
A(K_{2})=C(K_{2})\cap A(K_{1})=\emptyset$._ Let $(A_{i},C_{i},B_{i})$ be the
canonical separation associated with $K_{i}$. Suppose that there exists $v\in
C_{1}\cap A_{2}$. Then $C_{1}\cap B_{2}=\emptyset$.

First we show that $b\not\in C_{1}\cap C_{2}$. Suppose it is; then $b\in
K_{2}$, and $b$ has a neighbor in $A_{2}$, namely $v$, contrary to the
definition of a canonical separation. This proves that $b\not\in C_{1}\cap
C_{2}$. Since $C_{1}\subseteq C_{2}\cup A_{2}$, and $b\in\beta(D,b)$ by (8),
it follows that $b\not\in C_{1}$. By (8), $b\in B_{1}$; see Figure 1 (left).

Figure 1: Proof of Lemma 8.1.

Since $b\in B_{1}$, and $\\{b\\}\cup B_{2}$ is connected, and $(\\{b\\}\cup
B_{2})\cap C_{1}=\emptyset$, it follows that $B_{2}\subseteq B_{1}$; see
Figure 1 (right). But $C_{2}=N(B_{2})\subseteq B_{1}\cup C_{1}$, and so
$A_{1}\subseteq A_{2}\setminus\\{v\\}$, contrary to the definition of
$\mathcal{K}$. This proves (8).

Now let $F$ be a component of $D\setminus\beta(D,b)$. Let $K\in\mathcal{K}$ be
such that $F\cap A(K)\neq\emptyset$. By (8), $F\cap C(K)=\emptyset$. But now
$F\subseteq A(K)$, as required. Since $N(F)\subseteq N(A(K))\subseteq K$, the
second assertion follows. ∎

######  Lemma 8.2.

If $K$ is a clique cutset in the graph $\beta(D,b)$, then $b\in K$.

###### Proof.

Suppose that $K$ is a clique cutset of $\beta(D,b)$ and $b\not\in K$. Let
$D_{1}$ be the component of $\beta(D,b)\setminus K$, with $b\in D_{1}$, and
let $D_{2}=\beta(D,b)\setminus(K\cup D_{1})$. Since by Lemma 8.1, $N(F)$ is a
clique for every component $F$ of $D\setminus\beta(D,b)$, it follows that $K$
is a clique cutset in $D$ and no component of $D\setminus K$ meets both
$D_{1}$ and $D_{2}$. But then $D_{2}\cap A(K)\neq\emptyset$. It follows that
there exists $K^{\prime}\in\mathcal{K}$ such that $D_{2}\cap
A(K^{\prime})\neq\emptyset$, contrary to the definition of $\beta(D,b)$. ∎

Next we define a breaker in a graph. Let $G$ be a graph. Let $X\subseteq V(G)$
and let $X_{1},X_{2},X_{3}$ be subsets of $X$ such that
$|X_{1}|=|X_{2}|=|X_{3}|$ and $X_{1},X_{2},X_{3}$ are pairwise disjoint and
anticomplete to each other. Write $D=G\setminus X$ and let $b\in D\setminus
N[X]$. Assume that $N(D)=X$.

For $x_{1},x_{2},x_{3}\in X$ let us say that $x_{1}x_{2}x_{3}$ is partitioned
if $x_{i}\in X_{i}$ for every $i\in\\{1,2,3\\}$. For a partitioned triple
$x_{1}x_{2}x_{3}$ we say that it is $b$-separated and $(i,j)$-active if $b$ is
non-adjacent to $x_{1},x_{2},x_{3}$ and there is a clique $K\subseteq D$ such
that one of the following holds (For $i\in\\{1,2,3\\}$, let $D_{i}$ be the
union of components of $D\setminus K$ such that $N(x_{i})\cap
D_{i}\neq\emptyset$.)

  * •

$b\not\in K\cup D_{i}\cup D_{j}$; or

  * •

We have $b\not\in N[D_{i}]$. Moreover, there is a set
$D_{j}^{\prime}=D_{j}^{\prime}(x_{1}x_{2}x_{3})$ of vertices such that:

    * –

$D_{j}^{\prime}$ is not a clique;

    * –

$D_{j}^{\prime}$ is complete to $K$;

    * –

There is a vertex $q=q(x_{1}x_{2}x_{3})$ with the following property. Either
$b\in K$ and $q=b$; or there exists $k\in\\{1,2,3\\}\setminus\\{i\\}$ such
that $x_{k}$ is complete to $K\cup D_{j}^{\prime}$ and $q=x_{k}$;

    * –

For every $v\in D_{j}^{\prime}$, there is a path $P$ in $D\cup\\{x_{j}\\}$
from $b$ to $x_{j}$ such that $P\cap N(q)\neq\emptyset$ and the
$(P,x_{j})$-last vertex in $P\cap N(q)$ is $v$; and

    * –

For every path $P$ in $D\cup\\{x_{j}\\}$ from $b$ to $x_{j}$, we have $P\cap
N(q)\neq\emptyset$, and the $(P,x_{j})$-last vertex of $P\cap N(q)$ is
complete to $K$.

Under these circumstances we say that $K$ is a witness for $x_{1}x_{2}x_{3}$.
We say that $x_{1}x_{2}x_{3}$ is of _type 1_ if the first bullet of (8.2)
holds; otherwise, we say that $x_{1}x_{2}x_{3}$ is of _type 2_. We say an
$(i,j)$-active triple $x_{1}x_{2}x_{3}$ is of _type 2a_ if
$q(x_{1}x_{2}x_{3})=b$; it is of _type 2b_ if $q(x_{1}x_{2}x_{3})=x_{j}$; and
it is of _type 2c_ if $q(x_{1}x_{2}x_{3})\neq b,x_{j}$. A triple is
$b$-separated if it is $b$-separated and $(i,j)$-active for some distinct
$i,j\in\\{1,2,3\\}$. Let $\delta\in(0,1]$. We say that $X$ is a
$(\delta,b)$-breaker in $G$ if there exist at least $\delta|X|^{3}$
partitioned $b$-separated triples.

The main result of this section is the following:

######  Theorem 8.3.

Let $\delta\in(0,1]$ and let $\epsilon\leq\frac{\delta^{2}}{48\times 192}$.
Let $G$ be a $C_{4}$-free graph, and let $X$ be a $(\delta,b)$-breaker in $G$.
Then there exists $S\subseteq D\setminus\\{b\\}$ with
$\kappa(S)\leq(96/\delta)^{2}$ such that the component $D(b)$ of $D\setminus
S$ with $b\in D(b)$ is disjoint from $N(x)$ for at least $\epsilon|X|$
vertices $x\in X$.

###### Proof.

We first show:

$\displaystyle{\left\lceil\frac{96}{\delta}\right\rceil+1\choose 2}$
$\displaystyle=\left(\left\lceil\frac{96}{\delta}\right\rceil\right)\left(\left\lceil\frac{96}{\delta}\right\rceil+1\right)/2$
$\displaystyle\leq(96/\delta+1)(96/\delta+2)/2$
$\displaystyle=(96/\delta)^{2}+3\cdot 96/(2\delta)+1-(96/\delta)^{2}/2$
$\displaystyle\leq(96/\delta)^{2}+3\cdot 96/(2\delta)+1-48\cdot 96/\delta$
$\displaystyle\leq(96/\delta)^{2}.$

Now suppose that the statement is false. For every clique $K\subseteq D$, let
$(A(K),C(K),B(K))$ be the $b$-canonical separation for $K$.

Let $x_{1}x_{2}x_{3}$ be a $b$-separated triple. We fix a witness
$K(x_{1},x_{2},x_{3})$ for $x_{1}x_{2}x_{3}$, where $K(x_{1},x_{2},x_{3})$ is
chosen such that $x_{1}x_{2}x_{3}$ is of type 1 if possible. Let $\mathcal{F}$
be the set of components of $D\setminus\beta(D,b)$. For every $x\in X$, let
$\mathcal{F}(x)$ be the set of elements of $\mathcal{F}$ for which $N(x)\cap
F\neq\emptyset$.

(30) _Let $x_{1}x_{2}x_{3}$ be a $b$-separated triple; write
$K=K(x_{1},x_{2},x_{3})$. Assume that the component $D(b)$ of
$D\setminus(K\setminus b)$ with $b\in D(b)$ is anticomplete to $x_{1}$. Then
$x_{1}$ is anticomplete to $\beta(D,b)\setminus K$. Moreover, let
$F\in\mathcal{F}(x_{1})$. Then either $K\cap F\neq\emptyset$, or
$N(F)\subseteq K$._

Since $\beta(D,b)\subseteq D(b)\cup K$, it follows that $x_{1}$ is
anticomplete to $\beta(D,b)\setminus K$. Next, suppose that $F\cap
K=\emptyset$ and that there is a vertex $p\in N(F)\setminus K$. By Lemma 8.2,
$b\in\beta(D,b)$ and $\beta(D,b)\setminus(K\setminus b)$ is connected. Let $P$
be a path from $p$ to $b$ with $P^{*}\subseteq\beta(D,b)$. Let $Q$ be a path
from $N(x_{1})$ to $p$ with interior in $F$. Then
$R=Q\hbox{-}p\hbox{-}P\hbox{-}p$ is a path from $N(x_{1})$ to $b$ with
$R^{*}\cap K=\emptyset$, a contradiction. This proves (8).

It follows from (8) that:

(31) _If $x_{1}x_{2}x_{3}$ is a $(1,2)$-active triple, then $x_{1}$ is
anticomplete to $\beta(D,b)\setminus K(x_{1},x_{2},x_{3})$. Moreover, if
$x_{1}x_{2}x_{3}$ is of type 1, then $x_{2}$ is anticomplete to
$\beta(D,b)\setminus K(x_{1},x_{2},x_{3})$._

Let $x\in X$. We define the projection of $x$, denoted by
$\operatorname{Proj}(x)$, to be
$N_{\beta(D,b)}(x)\cup\bigcup_{F\in\mathcal{F}(x)}N(F)$. Note that since $b$
is non-adjacent to $x_{1},x_{2},x_{3}$ for $b$-seperated triples
$x_{1}x_{2}x_{3}$, and since $b$ is anticomplete to $A(K)$ for every
$K\in\mathcal{K}$, it follows that $b\not\in\operatorname{Proj}(x)$ whenever
$x$ is in a $b$-separated triple.

(32) _Let $x_{1}x_{2}x_{3}$ be a $(1,2)$-active triple; write
$K=K(x_{1},x_{2},x_{3})$. If $x_{1}x_{2}x_{3}$ is of type 1, then
$\operatorname{Proj}(x_{1})\cup\operatorname{Proj}(x_{2})$ is a clique._

For $i\in\\{1,2\\}$, let $F_{i}=\bigcup_{F\in\mathcal{F}(x_{i})}F$. Suppose
first that $K\cap F_{i}=\emptyset$ for all $i\in\\{1,2\\}$; then by (8)
$N(F_{i})\subseteq K$ for $i\in\\{1,2\\}$. Since by (8),
$N_{\beta(D,b)}(x_{i})\subseteq K$ for $i\in\\{1,2\\}$, (8) holds. Thus we may
assume that there exists $F\in\mathcal{F}(x_{1})$ such that $K\cap
F\neq\emptyset$. Let $F^{\prime}\in(F_{1}\cup F_{2})\setminus F$. Since $K$ is
a clique, it follows that $F^{\prime}\cap K=\emptyset$, and by (8),
$N(F^{\prime})\subseteq K$.

Since $K\cap F\neq\emptyset$, we have that $K\cap\beta(D,b)\subseteq N(F)$,
and so $N(F^{\prime})\subseteq N(F)$. Moreover, by (8), for $i\in\\{1,2\\}$,
we have $N_{\beta(D,b)}(x_{i})\subseteq K$, and so
$N_{\beta(D,b)}(x_{i})\subseteq N(F)$. $N(F)$ is a clique by Lemma 8.1, and
(8) follows.

(33) _Let $x_{1}x_{2}x_{3}$ be a $(1,2)$-active triple which is of type 2;
write $K=K(x_{1},x_{2},x_{3})$. Then $\operatorname{Proj}(x_{1})\subseteq K$._

By (8), we have $N_{\beta(D,b)}(x_{1})\subseteq K$. By (8), we either have
$N(F)\subseteq K$ or $K\cap F\neq\emptyset$ for every
$F\in\mathcal{F}(x_{1})$. If the former holds for all
$F\in\mathcal{F}(x_{1})$, then (8) holds; so we may assume that there exists
$F\in\mathcal{F}(x_{1})$ with $K\cap F\neq\emptyset$. By Lemma 8.1, it follows
that $N(F)$ is a clique $K^{\prime}$. From the definition of $\beta(D,b)$, it
follows that $b\not\in K^{\prime}$. We claim that $K^{\prime}$ is a witness
for $x_{1}x_{2}x_{3}$ that makes $x_{1}x_{2}x_{3}$ be of type 1 (and therefore
contradicts the choice of $K=K(x_{1}x_{2}x_{3})$). Suppose not; let $P$ be a
path from $b$ to $x_{i}$ for some $i\in\\{1,2\\}$ such that $P^{*}\cap
K^{\prime}=\emptyset$. From the definition of a $b$-separated $(1,2)$-active
triple, it follows that $P^{*}\cap(K\cup
D_{2}^{\prime}(x_{1}x_{2}x_{3}))\neq\emptyset$. Since
$D_{2}^{\prime}(x_{1}x_{2}x_{3})$ is complete to $K$, it follows that $(K\cup
D_{2}^{\prime}(x_{1}x_{2}x_{3}))\setminus K^{\prime}\subseteq F$. Therefore,
$P^{*}\cap F\neq\emptyset$. Since $P^{*}\cap N(F)=\emptyset$, it follows that
$P\subseteq N[F]\cup\\{x_{i}\\}$, contrary to the fact that $b\not\in
N[F]\cup\\{x_{i}\\}$. This is a contradiction, and proves (8).

By permuting the indices if necessary, we may assume that
$\frac{\delta}{6}|X|^{3}$ separated triples are $(1,2)$-active. Now, for one
of the four possible types (1, 2a, 2b, 2c), there exist
$\frac{\delta}{24}|X|^{3}$ distinct $(1,2)$-active triples $x_{1}x_{2}x_{3}$
of this type with respect to $K(x_{1}x_{2}x_{3})$. Let $l$ be the first entry
of the list (1, 2a, 2b, 2c) for which this is the case; let us say that a
triple $x_{1}x_{2}x_{3}$ is manageable if it is $(1,2)$-active of type $l$.

Let $Z_{1}\subseteq X_{1}$ be the set of all vertices $y_{1}\in X_{1}$ such
that

$|\\{(y_{2},y_{3})\in X_{2}\times X_{3}:y_{1}y_{2}y_{3}\textnormal{ is a
manageable triple}\\}|\geq\frac{\delta}{48}|X|^{2}.$

(34) _$|Z_{1}|\geq\frac{\delta}{48}|X|$._

Suppose not. Each vertex $y_{1}\in X_{1}\setminus Z_{1}$ is in fewer than
$\frac{\delta}{48}|X|^{2}$ manageable triples. Therefore, the total number of
manageable triples is less than

$|Z_{1}||X|^{2}+|X_{1}\setminus
Z_{1}|\frac{\delta}{48}|X|^{2}<\frac{\delta}{48}|X|^{3}+\frac{\delta}{48}|X|^{3}=\frac{\delta}{24}|X|^{3},$

a contradiction. This proves (8).

Recall that by (8), $\operatorname{Proj}(w)$ is a clique for every $w\in
Z_{1}$. Since $|Z_{1}|>\epsilon|X|$, we have $\alpha(\bigcup_{w\in
Z_{1}}\operatorname{Proj}(w))>\frac{96}{\delta}$.

Let $W_{1}$ be a minimal subset of $Z_{1}$ such that $\alpha(\bigcup_{w\in
W_{1}}\operatorname{Proj}(w))\geq\frac{96}{\delta}$. Then
$\alpha(\bigcup_{w\in
W_{1}}\operatorname{Proj}(w))=\left\lceil\frac{96}{\delta}\right\rceil$. Let
$S=\bigcup_{w\in W_{1}}\operatorname{Proj}(w)$. By a theorem of [47] (using
that the complements of even-hole-free graphs contain no induced two-edge
matching), we have $\kappa(S)\leq{\alpha(S)+1\choose
2}\leq{\left\lceil\frac{96}{\delta}\right\rceil+1\choose 2}$.

Let $J$ be a stable set of size $\left\lceil\frac{96}{\delta}\right\rceil$ in
$S$. For every $j\in J$, let $x(j)\in W_{1}$ be such that
$j\in\operatorname{Proj}(x(j))$. Since $J$ is a stable set, the elements
$x(j)$ are pairwise distinct.

Let $H$ be the bipartite graph with bipartition $(\\{x(j)\\}_{j\in
J},X_{2}\times X_{3})$, such that $x(j)$ is adjacent to $(y_{2},y_{3})\in
X_{2}\times X_{3}$ if $x(j)y_{2}y_{3}$ is a manageable triple.

(35) _There exist distinct $j_{1},j_{2}\in J$ such that $|N_{H}(x(j_{1}))\cap
N_{H}(x(j_{2}))|\geq\frac{\delta^{2}}{48\times 192}|X|^{2}$._

Suppose not. Let $j\in J$. Since $x(j)\in Z_{1}$, it follows that $x(j)$ has
at least $\frac{\delta}{48}|X|^{2}$ neighbors in $H$. For every $j\in J$, let
$M(j)$ be the set of vertices $y\in Y_{2}$ such that $y$ is adjacent to $x(j)$
in $H$, and $y$ is not adjacent in $H$ to any other vertex $x(j^{\prime})$ for
$j^{\prime}\neq j$. Since $|N_{H}(x(j_{1}))\cap
N_{H}(x(j_{2}))|<\frac{\delta^{2}}{48\times 192}|X|^{2}$ for all distinct
$j_{1},j_{2}\in J$, and since each $x(j)$ has at least
$\frac{\delta}{48}|X|^{2}$ neighbors in $H$, it follows that

$|M(j)|>\frac{\delta}{48}|X|^{2}-\left(\left\lceil\frac{96}{\delta}\right\rceil-1\right)\frac{\delta^{2}}{48\times
192}|X|^{2}>\frac{\delta}{96}|X|^{2}$

for each $j\in J$. But now $\bigcup_{j\in
J}|M(j)|>|J|\frac{\delta}{96}|X|^{2}\geq|X|^{2}$, a contradiction. This proves
(8).

Suppose that $l=1$. Let $j_{1},j_{2}$ be as in (8), and let

$Z_{2}=\\{y_{2}:(y_{2},y_{3})\in N_{H}(x(j_{1}))\cap
N_{H}(x(j_{2}))\textnormal{ for some }y_{3}\in X_{3}\\}.$

Then $|Z_{2}|\geq\frac{\delta^{2}}{48\times 192}|X|$. Since
$|Z_{2}|\geq\epsilon|X|$, we deduce that $\kappa(\bigcup_{y\in
Z_{2}}\operatorname{Proj}(y))>{\left\lceil\frac{96}{\delta}\right\rceil+1\choose
2}>4$. Therefore we can choose non-adjacent $k_{1},k_{2}\in(\bigcup_{y\in
Z_{2}}\operatorname{Proj}(y))\setminus(\operatorname{Proj}(x(j_{1}))\cup\operatorname{Proj}(x(j_{2}))).$
For $i\in\\{1,2\\}$, let $y(k_{i})\in Z_{2}$ be such
$k_{i}\in\operatorname{Proj}(y_{i})$. It follows that for every
$p,q\in\\{1,2\\}$ there exists $y_{3}(p,q)\in Y_{3}$ such that
$x(j_{p}),y(k_{q}),y_{3}(p,q)$ is a manageable triple. Now applying (8) to
$x(j_{p})y(k_{q})y_{3}(p,q)$, we deduce that $j_{p}$ is adjacent to $k_{q}$;
consequently $\\{j_{1},j_{2}\\}$ is complete to $\\{k_{1},k_{2}\\}$. But then
$j_{1}\hbox{-}k_{1}\hbox{-}j_{2}\hbox{-}k_{2}\hbox{-}j_{1}$ is a $C_{4}$ in
$G$, a contradiction.

This proves that $l$ is one of 2a, 2b, 2c. Let $j_{1},j_{2}$ be as in (8) and
let $(y_{2},y_{3})\in N_{H}(x(j_{1}))\cap N_{H}(x(j_{2}))$. Note that since
$x(j_{1})y_{2}y_{3}$ and $x(j_{2})y_{2}y_{3}$ are both $(1,2)$-active and of
the same type in 2a, 2b, 2c, we have
$q(x(j_{1})y_{2}y_{3})=q(x(j_{2})y_{2}y_{3})$. Let us define
$q=q(x(j_{1})y_{2}y_{3})$. For $i\in\\{1,2\\}$, let
$K_{i}=K(x(j_{i})y_{2}y_{3})$. By (8) we have
$\operatorname{Proj}(x(j_{1}))\subseteq K_{1}$ and so $j_{1}\in K_{1}$;
likewise, $j_{2}\in K_{2}$.

Let $p_{1},p_{2}\in D_{2}^{\prime}(x(j_{1})y_{2}y_{3})$ be non-adjacent. For
$i\in\\{1,2\\}$, let $P_{i}$ be a path from $b$ to $y_{2}$ in
$D\cup\\{y_{2}\\}$ such that the $(P_{i},y_{2})$-last vertex in $P_{i}\cap
N(q)$ is $p_{i}$. It follows that $p_{1},p_{2}$ are complete to $K_{1},K_{2}$.
But now $j_{1}\hbox{-}p_{1}\hbox{-}j_{2}\hbox{-}p_{2}$ is a $C_{4}$ in $G$, a
contradiction. ∎

##  9 Handling dangerous triples

Let $G$ be a graph, let $a\in G$ and write $X=N(a)$ and $D=G\setminus N[a]$.
Let $X$ be partitioned into three equal-size subsets $X_{1},X_{2},X_{3}$
pairwise anticomplete to each other. We say that the triple $x_{1}x_{2}x_{3}$
with $x_{i}\in X_{i}$ is dangerous with center $x_{2}$ if the edge $ax_{2}$ is
a cross-edge of an extended near-prism in the graph
$D\cup\\{x_{1},x_{2},x_{3},a\\}$.

The goal of this section is to prove that if $G$ contains many dangerous
triples with a fixed center, then we can bypass the main argument of Section
10 and obtain the desired conclusion directly. The details of this are
explained in Section 10.

We need the following definition: Let $G=D\cup X\cup\\{a\\}$ be a graph where
$D$ is connected, $a$ is complete to $X$ and anticomplete to $D$, and
$N(D)=X$. Let $b\in D$. Let us say that $X^{\prime}\subseteq X$ is pure if
there does not exist a hole $H\subseteq D\cup X^{\prime}\cup\\{a\\}$ such that
$a,b\in H$.

######  Theorem 9.1.

Let $\delta\in(0,1]$ and let $\epsilon\leq\frac{1}{8}\delta$. Let $G=D\cup
X\cup\\{a\\}$ be a graph where $D$ is connected, $a$ is complete to $X$ and
anticomplete to $D$, and $N(D)=X$. Assume that
$X\cap\operatorname{Hub}(G)=\emptyset$. Assume that $X$ is partitioned into
three pairwise anticomplete sets $X_{1},X_{2},X_{3}$ of equal size. Suppose
that some $x_{2}\in X_{2}$ is a center of $\delta|X|^{2}$ dangerous triples.
Assume also that there is no clique of size $\epsilon|X|$ in $X$. Let $b\in
D$. Then one of the following holds:

  * •

there exists $S\subseteq D\setminus\\{b\\}$ with $\kappa(S)\leq 4$ such that
the component $D(b)$ of $D\setminus S$ with $b\in D(b)$ is disjoint from
$N(x)$ for at least $\epsilon|X|$ vertices $x\in X$; or

  * •

$X$ is not pure and there exists $X^{\prime}\subseteq X$ with
$|X^{\prime}|\geq\frac{1-4\epsilon}{2}|X|$ such that $X^{\prime}$ is pure.

###### Proof.

Suppose not. Let $x_{2}\in X_{2}$. For $i=1,3$ let $Y_{i}\subseteq X_{i}$ be
the set of all $y\in X_{i}$ such that there exist at least
$\frac{1}{2}\delta|X|$ elements $z\in X_{4-i}$ for which $yx_{2}z$ is a
dangerous triple with center $x_{2}$.

(36) _For $i=1,3$, $|Y_{i}|\geq\frac{1}{2}\delta|X|$._

Suppose that $|Y_{1}|<\frac{1}{2}\delta|X|$. The number of dangerous triples
with center $x_{2}$ and using an element of $Y_{1}$ is at most
$|Y_{1}||X|\leq\frac{1}{2}\delta|X|^{2}$. The number of dangerous triples with
center $x_{2}$ and not using an element of $Y_{1}$ is less than
$|X_{1}\setminus
Y_{1}|\times\frac{1}{2}\delta|X|\leq\frac{1}{2}\delta|X|^{2}$. It follows that
the number of dangerous triples with center $x_{2}$ is less than
$\delta|X|^{2}$, a contradiction. This proves (9).

Let $G^{\prime}=D\cup X_{1}\cup X_{3}\cup\\{a,x_{2}\\}$. Then $ax_{2}$ is a
cross-edge of an extended near-prism in $G^{\prime}$ and no vertex of
$G^{\prime}$ is adjacent to both $a$ and $x_{2}$. Since $N(D)=X$, it follows
from Theorem 6.5 that $a\not\in\operatorname{Hub}(G)$. Applying Theorem 7.2 to
$ax_{2}$ and $G^{\prime}$, we obtain a $J$-strip system $M$ with cross-edge
$ax_{2}$ such that for every connected induced subgraph $F$ of
$G^{\prime}\setminus(M\cup\\{a,x_{2}\\})$, we have that $a$ is anticomplete to
$F$, and the set of vertices in $M\cup\\{x_{2}\\}$ with a neighbor in $F$ is
local.

(37) _For every $x\in X_{1}\cup X_{3}$, there exists an $a$-leaf $t$ such that
$x\in M_{t}$._

Since $X_{1}\cup X_{3}\subseteq N(a)$, Theorem 7.2 implies that $X_{1}\cup
X_{3}\subseteq V(M)$. Now (9) follows from the fact that $ax_{2}$ is a cross-
edge for $M$.

Let $v\in V(J)$. Let $e$ be an edge of $J$ incident with $v$. We say that $e$
is special for $v$ if either $v$ is a leaf, or the set $M_{v}\cap M_{e}$ is
not a clique. Since $G^{\prime}$ is $C_{4}$-free and $M_{v}\cap M_{e}$ is
complete to $M_{v}\cap M_{e^{\prime}}$ for distinct edges $e,e^{\prime}$
incident with $v$, it follows that for every $v\in V(J)$, there is at most one
special edge for $v$.

For $v\in V(J)$, let $F_{v}$ be, the union of components $F$ of
$G^{\prime}\setminus(M\cup\\{a,x_{2}\\})$ such that $N(F)\cap M\subseteq
M_{v}$. For $e\in E(J)$ with ends $u,v$ let $F_{e}$ be the union of components
$F$ of $G^{\prime}\setminus(M\cup\\{a,x_{2}\\})$ such that $N(F)\cap
M\subseteq M_{e}$, and such that $N(F)\not\subseteq M_{u}$ and
$N(F)\not\subseteq M_{v}$. Since $D$ is connected and disjoint from $N(a)$, it
follows that $F_{t}=\emptyset$ for every $a$-leaf $t$.

Let $e=uv$ be an edge of $J$. Define $\mu(e)$ as follows. If $e$ is not
special for either $u$ or $v$, let $\mu(e)=F_{e}\cup M_{e}\setminus(M_{u}\cup
M_{v})$. If $e$ is special for $u$ and not for $v$, let
$\mu(e)=F_{e}\cup(M_{e}\setminus M_{v})\cup F_{u}$. If $e$ is special for $v$
and not for $u$, let $\mu(e)=F_{e}\cup(M_{e}\setminus M_{u})\cup F_{v}$. If
$e$ is special for both $u$ and $v$, let $\mu(e)=M_{e}\cup F_{e}\cup F_{u}\cup
F_{v}$. In all cases let $\nu(e)=\emptyset$. Next, let $v\in V(J)$. If there
is a special edge $e$ for $v$, let $\mu(v)=M_{v}\setminus M_{e}$ and
$\nu(v)=\emptyset$. If no edge is special for $v$, let $\mu(v)=M_{v}$ and
$\nu(v)=F_{v}$. It follows that $\mu(v)$ is a clique for every $v\in V(J)$.
Note that each vertex of $V(G^{\prime})\setminus\\{x_{2},a\\}$ is in at least
one set in $\\{\mu(x),\nu(x)\\}_{x\in V(J)\cup E(J)}$; the only vertices of
$V(G^{\prime})\setminus\\{x_{2},a\\}$ that are in two such sets are vertices
in $M_{u}\cap M_{v}$ where $uv$ is not special for $u$ and not special for
$v$; they are in both $\mu(v)$ and $\mu(u)$.

(38) _If $e$ is an edge of $J$ with ends $u,v$ and $b\in\mu(e)$, then
$|(X_{1}\cup X_{3})\setminus(\mu(e)\cup\mu(v)\cup\mu(u))|\leq\epsilon|X|$._
Suppose $x\in(X_{1}\cup X_{3})\setminus(\mu(e)\cup\mu(v)\cup\mu(u))$. Then
$N(x)\cap\mu(e)=\emptyset$. Since $L=\mu(v)\cup\mu(u)$ separates $\mu(e)$ from
$D\setminus(\mu(e)\cup L)$ in $D$, it follows that the component of
$D\setminus L$ that contains $b$ is disjoint from $N(x)$. Since $\kappa(L)\leq
2$, there are at most $\epsilon|X|$ such vertices $x$, and (9) follows.

(39) _Suppose that $v\in V(J)$ and $b\in\mu(v)$. Let $e=vu\in E(J)$ such that
$b\in M_{e}$. Moreover:_ • _Define_ $L_{1}$ and $C_{1}$ as follows. Let $f=vw$
be a special edge at $v$ if one exists; in this case, let
$L_{1}=\mu(w)\cup\mu(f)$ and $C_{1}=\mu(w)$; otherwise,
$L_{1}=C_{1}=\emptyset$. • _Define_ $L_{2}$ and $C_{2}$ as follows. If $b\in
M_{u}\cap M_{v}$ and there is a special edge $uz$ at $u$ with $z\neq v$, let
$L_{2}=\mu(uz)\cup\mu(z)$ and $C_{2}=\mu(z)$. If $b\in M_{u}\cap M_{v}$ and
there is no special edge at $u$ except possibly $uv$, we let $L_{2}=\nu(u)$
and $C_{2}=\emptyset$. Finally, if $b\not\in M_{u}$, let
$L_{2}=C_{2}=\emptyset$. _Then $|(X_{1}\cup
X_{3})\setminus(\mu(e)\cup\mu(v)\cup L_{1}\cup
L_{2}\cup\mu(u)\cup\nu(v))|\leq\epsilon|X|$._

Suppose that $x\in(X_{1}\cup X_{3})\setminus(\mu(e)\cup\mu(v)\cup L_{1}\cup
L_{2}\cup\mu(u)\cup\nu(v))$. Let $L=((\mu(v)\cup\mu(u)\cup C_{1}\cup
C_{2})\setminus\\{b\\})\cap D$. Then $L$ separates
$(\\{b\\}\cup\mu(e)\cup\nu(v)\cup(L_{1}\setminus C_{1})\cup(L_{2}\setminus
C_{2}))\cap D$ from the rest of $D$, and in particular, from
$D\cap(N(x)\setminus L)$. Since $\kappa(L)\leq 4$, there are at most
$\epsilon|X|$ such vertices $x$, and (9) follows.

(40) _Suppose that $v\in V(J)$ and $b\in\nu(v)$. Then $|(X_{1}\cup
X_{3})\setminus(\mu(v)\cup\nu(v))|\leq\epsilon|X|$._

Suppose that $x\in(X_{1}\cup X_{3})\setminus(\mu(v)\cup\nu(v))$. Then
$N(x)\cap\nu(v)=\emptyset$. Let $L=\mu(v)$. Then $L$ separates $\nu(v)$ from
$D\setminus(\nu(v)\cup\mu(v))$. We deduce that the component of $D\setminus L$
that contains $b$ is disjoint from $N(x)$. Since $\kappa(L)=1$, there are at
most $\epsilon|X|$ such vertices $x$, and (9) follows.

It follows from (9), (9), (9) and (9) that there is an $a$-leaf $t$ with
$N_{J}(t)=\\{t^{\prime}\\}$ such that $b\in\mu(t^{\prime}t)\cup
M_{t^{\prime}}\cup\nu(t^{\prime})$. If $b\in\nu(t^{\prime})$, then by (9) and
(9), it follows that $|X\cap\mu(t^{\prime})|\geq(1-\epsilon)|X|$. But
$\mu(t^{\prime})$ is a clique, and $\epsilon\leq 1/8$, and $X$ contains no
clique of size $\epsilon|X|$, a contradiction. It follows that
$b\in\mu(t^{\prime}t)\cup M_{t^{\prime}}$.

From Theorem 7.2, it follows that:

(41) _If $x\in N(x_{2})\cap M$, then there is a $b$-leaf $q$ such that $x\in
M_{q}\cup F_{q}$._

Next, we show:

(42) _Let $t$ be an $a$-leaf, and let $t^{\prime}$ be the unique neighbor of
$t$ in $J$. Let $Z=\mu(tt^{\prime})\cup\nu(t^{\prime})$. Suppose that
$y_{1}\in X_{1}\cap Z$ and $y_{3}\in X_{3}\cap Z$. Then $y_{1}x_{2}y_{3}$ is
not a dangerous triple._

Suppose not. Then, by the definition of a dangerous triple, there exists a
path $R$ from $y_{1}$ to $y_{3}$ with $x_{2}\in R$ and such that
$R\setminus\\{y_{1},x_{2},y_{3}\\}\subseteq D$. By (9), it follows that there
exist $b$-leaves $q_{1},q_{3}$ such that the neighbor of $x_{2}$ on the
subpath of $R$ from $x_{2}$ to $y_{i}$ is in $M_{q_{i}}\cup F_{q_{i}}$ for
$i\in\\{1,3\\}$. Since $\mu(t^{\prime})$ separates $Z$ from $F_{r}\cup M_{r}$
for all $r\in V(J)\setminus\\{t,t^{\prime}\\}$, it follows that the interiors
of both the paths $y_{1}\hbox{-}R\hbox{-}x_{2}$ and
$x_{2}\hbox{-}R\hbox{-}y_{3}$ meet $\mu(t^{\prime})$, contrary to the fact
that $\mu(t^{\prime})$ is a clique. This proves (9).

(43) _Let $t$ be an $a$-leaf, and let $t^{\prime}$ be the unique neighbor of
$t$ in $J$. Let $t^{\prime\prime}$ be a neighbor of $t$ with
$t^{\prime\prime}\neq t$. Let
$Z=\mu(tt^{\prime})\cup\mu(t^{\prime}t^{\prime\prime})\cup\mu(t^{\prime})\cup\mu(t^{\prime\prime})\cup\nu(t^{\prime})\cup\nu(t^{\prime\prime})$.
Then $|X\cap Z|<(1-\epsilon)|X|.$_

From the definition of a $J$-strip structure with cross-edge $ax_{2}$, it
follows that $t^{\prime\prime}$ is not an $a$-leaf.

Now, since $X$ contains no clique of size $\epsilon|X|$, it follows that
$|X\cap\mu(t^{\prime})\cup\mu(t^{\prime\prime})|\leq 2\epsilon|X|$.
Furthermore, (9) implies that $X\cap\nu(t^{\prime})=\emptyset$,
$X\cap\nu(t^{\prime\prime})=\emptyset$ and
$X\cap\mu(t^{\prime}t^{\prime\prime})=\emptyset$ (as
$t^{\prime\prime},t^{\prime}$ are not $a$-leaves). Therefore, $|(X_{1}\cup
X_{3})\cap\mu(tt^{\prime})|\geq(1-3\epsilon)|X|$. Since
$\epsilon<\frac{1}{8}\delta$, it follows from (9) that there exist $y_{1}\in
Y_{1}\cap(Z\setminus\mu(t^{\prime}))$ and $y_{3}\in
X_{3}\cap(Z\setminus\mu(t^{\prime}))$ such that $y_{1}x_{2}y_{3}$ is a
dangerous triple, contrary to (9). This proves (9).

To finish the proof of Theorem 9.1, we consider three cases. Suppose first
that either:

  * •

$b\in\mu(tt^{\prime})$; or

  * •

$b\in M_{tt^{\prime}}\cap M_{t^{\prime}}$ and no edge is special at
$t^{\prime}$ (except possibly $tt^{\prime}$).

Let $Z=\mu(tt^{\prime})\cup\mu(t^{\prime})$ if $b\in\mu(tt^{\prime})$, and let
$Z=\mu(tt^{\prime})\cup\mu(t^{\prime})\cup\nu(t^{\prime})$ otherwise. By (9)
and (9) and since $\mu(t)=\nu(t)=\emptyset$, it follows that $|X\cap
Z|\geq(1-\epsilon)|X|$. This contradicts (9) (choosing $t^{\prime\prime}$
arbitrarily).

Now suppose that $b\in(M_{t^{\prime}}\cap
M_{tt^{\prime}})\setminus\mu(tt^{\prime})$. We may assume that we are not in
the first case, and so it follows that there is an edge
$t^{\prime}t^{\prime\prime}$ with $t^{\prime\prime}\neq t$ which is special at
$t^{\prime}$. It follows that $t^{\prime\prime}$ is not an $a$-leaf. Let
$Z=\mu(tt^{\prime})\cup\mu(t^{\prime})\cup\mu(t^{\prime}t^{\prime\prime})\cup\mu(t^{\prime\prime})\cup\nu(t^{\prime})$.
By (9) and since $\nu(t)=\mu(t)=\emptyset$, it follows that $|X\cap
Z|\geq(1-\epsilon)|X|$. This contradicts (9).

It follows that $b\in M_{t^{\prime}}\cap M_{t^{\prime}t^{\prime\prime}}$ for
some neighbor $t^{\prime\prime}$ of $t^{\prime}$ with $t^{\prime\prime}\neq
t$. Then $t^{\prime\prime}$ is not an $a$-leaf. Suppose first that either:

  * •

$b\not\in M_{t^{\prime\prime}}$; or

  * •

$b\in M_{t^{\prime\prime}}\cap M_{t^{\prime}}$ and there is no special edge at
$t^{\prime\prime}$ except possibly $t^{\prime\prime}t^{\prime}$.

Let
$Z=\mu(tt^{\prime})\cup\mu(t^{\prime}t^{\prime\prime})\cup\mu(t^{\prime})\cup\mu(t^{\prime\prime})\cup\nu(t^{\prime})\cup\nu(t^{\prime\prime})$.
Using (9) (with $t^{\prime}=v$; $t=w$; $t^{\prime\prime}=u$), we conclude that
$|X\cap Z|\geq(1-\epsilon)|X|$. Again, this contradicts (9).

It follows that $b\in M_{t^{\prime}}\cap M_{t^{\prime\prime}}$, and there is a
special edge $t^{\prime\prime}t^{\prime\prime\prime}$ at $t^{\prime\prime}$
with $t^{\prime\prime\prime}\neq t^{\prime}$. Let
$Z=\mu(tt^{\prime})\cup\mu(t^{\prime}t^{\prime\prime})\cup\mu(t^{\prime})\cup\mu(t^{\prime\prime})\cup\nu(t^{\prime})\cup\nu(t^{\prime\prime})\cup\mu(t^{\prime\prime}t^{\prime\prime\prime})\cup\mu(t^{\prime\prime\prime})$.
Using (9) (with $t^{\prime}=v$; $t=w$; $t^{\prime\prime}=u$;
$t^{\prime\prime\prime}=z$), we conclude that $|X\cap Z|\geq(1-\epsilon)|X|$.
From (9), it follows that
$X\cap(\nu(t^{\prime})\cup\nu(t^{\prime\prime}))=\emptyset$. Since $X$
contains no clique of size at least $\epsilon|X|$, it follows that
$|X\cap(\mu(t^{\prime})\cup\mu(t^{\prime\prime})\cup\mu(t^{\prime\prime\prime}))|<3\epsilon|X|$.
Neither $t^{\prime}$ nor $t^{\prime\prime}$ is a leaf, and so
$X\cap\mu(t^{\prime}t^{\prime\prime})=\emptyset$ by (9).

It follows that
$|X\cap(\mu(tt^{\prime})\cup\mu(t^{\prime\prime}t^{\prime\prime\prime}))|>(1-4\epsilon)|X|$.
If $X\cap\mu(t^{\prime\prime}t^{\prime\prime\prime})=\emptyset$, then as
before, there exist $y_{1}\in\mu(tt^{\prime})\cap Y_{1}$ and
$y_{3}\in\mu(tt^{\prime})\cap Y_{3}$ such that $y_{1}x_{2}y_{3}$ is a
dangerous triple, contrary to (9). So
$X\cap\mu(t^{\prime\prime}t^{\prime\prime\prime})\neq\emptyset$. It follows
that $t^{\prime\prime\prime}$ is an $a$-leaf. There is symmetry (switching
$t,t^{\prime},t^{\prime\prime},t^{\prime\prime\prime}$ with
$t^{\prime\prime\prime},t^{\prime\prime},t^{\prime},t$), and so
$X\cap\mu(tt^{\prime})\neq\emptyset$.

Let $x\in X\cap\mu(tt^{\prime})$ and let $x^{\prime}\in
X\cap\mu(t^{\prime\prime}t^{\prime\prime\prime})$. Then $x\in M_{t}$ and
$x^{\prime}\in M_{t^{\prime\prime\prime}}$ by (9). Let $R$ be a
$tt^{\prime}$-rung containing $x$, and let $R^{\prime}$ be a
$t^{\prime\prime}t^{\prime\prime\prime}$-rung containing $x^{\prime}$. Then
$x\hbox{-}R\hbox{-}b\hbox{-}R^{\prime}\hbox{-}x^{\prime}\hbox{-}a\hbox{-}x$ is
a hole in $D\cup X\cup\\{a\\}$ containing $a$ and $b$, and so $X$ is not pure.

By symmetry, we may assume that
$|X\cap\mu(tt^{\prime})|\geq\frac{1-4\epsilon}{2}|X|$. Write
$X^{\prime}=X\cap\mu(tt^{\prime})$. We claim that $X^{\prime}$ is pure (and so
the second outcome of the theorem holds). Suppose not; let $H$ be a hole
containing $a$ and $b$ with $H\setminus a\subseteq X^{\prime}\cup D$. Then $H$
contains two internally disjoint paths from $b$ to $a$, say $P_{1}$ and
$P_{2}$. Since $Y=M_{t^{\prime}}\cap M_{tt^{\prime}}$ separates $b$ from
$X^{\prime}\setminus Y$ in $D\cup X^{\prime}$, it follows that $P_{1}^{*}$ and
$P_{2}^{*}$ each contain a vertex in $Y$ (and in particular, $tt^{\prime}$ is
special at $t^{\prime}$). Since $\mu(t^{\prime})$ is complete to $Y$, it
follows that $H\cap\mu(t^{\prime})=\\{b\\}$. Consequently, $H\setminus
b\subseteq\mu(tt^{\prime})$. It follows that $R^{\prime}\setminus b$ is
anticomplete to $H\setminus b$. But now $H\cup R^{\prime}$ is a theta in $G$
with ends $a,b$, a contradiction. This concludes the proof. ∎

##  10 Separating a pair of vertices: the hub-free case

In this section we set $\epsilon=\frac{1}{4\times 17^{6}\times 48\times 192}$,
$\gamma=\frac{\epsilon(1-4\epsilon)}{2}$ and $C=96^{2}\times 4\times
17^{6}+4$. The goal of this section is to prove the following:

######  Theorem 10.1.

Let $G\in\mathcal{C}$ with $|V(G)|=n$, and let $a,b\in V(G)$ be non-adjacent.
Assume that $N(a)\cap\operatorname{Hub}(G)=\emptyset$. Then there is a set
$Z\subseteq V(G)\setminus\\{a,b\\}$ with
$\kappa(Z)\leq-C\frac{1}{\log(1-\gamma)}\log n$ and such that every component
of $G\setminus Z$ contains at most one of $a,b$.

We need the following result from [5].

######  Lemma 10.2 (Abrishami, Chudnovsky, Dibek, Vušković [5]).

Let $x_{1},x_{2},x_{3}$ be three distinct vertices of a graph $G$. Assume that
$H$ is a connected induced subgraph of $G\setminus\\{x_{1},x_{2},x_{3}\\}$
such that $V(H)$ contains at least one neighbor of each of $x_{1}$, $x_{2}$,
$x_{3}$, and that $V(H)$ is minimal subject to inclusion. Then, one of the
following holds:

  1. (i)

For some distinct $i,j,k\in\\{1,2,3\\}$, there exists $P$ that is either a
path from $x_{i}$ to $x_{j}$ or a hole containing the edge $x_{i}x_{j}$ such
that

     * •

$V(H)=V(P)\setminus\\{x_{i},x_{j}\\}$; and

     * •

either $x_{k}$ has two non-adjacent neighbors in $H$ or $x_{k}$ has exactly
two neighbors in $H$ and its neighbors in $H$ are adjacent.

  2. (ii)

There exists a vertex $a\in V(H)$ and three paths $P_{1},P_{2},P_{3}$, where
$P_{i}$ is from $a$ to $x_{i}$, such that

     * •

$V(H)=(V(P_{1})\cup V(P_{2})\cup V(P_{3}))\setminus\\{x_{1},x_{2},x_{3}\\}$;

     * •

the sets $V(P_{1})\setminus\\{a\\}$, $V(P_{2})\setminus\\{a\\}$ and
$V(P_{3})\setminus\\{a\\}$ are pairwise disjoint; and

     * •

for distinct $i,j\in\\{1,2,3\\}$, there are no edges between
$V(P_{i})\setminus\\{a\\}$ and $V(P_{j})\setminus\\{a\\}$, except possibly
$x_{i}x_{j}$.

  3. (iii)

There exists a triangle $a_{1}a_{2}a_{3}$ in $H$ and three paths