# Unavoidable induced subgraphs in graphs with complete bipartite induced
minors

Maria Chudnovsky  Princeton University, Princeton, NJ 08544, USA  Meike Hatzel
National Institute of Informatics, Tokyo, Japan  Tuukka Korhonen  University
of Bergen, Norway  Nicolas Trotignon  Univ Lyon, EnsL, CNRS, LIP, F-69342,
Lyon Cedex 07, France  Sebastian Wiederrecht  Discrete Mathematics Group,
Institute for Basic Science, Daejeon, South Korea

###### Abstract

We prove that if a graph contains the complete bipartite graph $K_{134,12}$ as
an induced minor, then it contains a cycle of length at most 12 or a theta as
an induced subgraph. With a longer and more technical proof, we prove that if
a graph contains $K_{3,4}$ as an induced minor, then it contains a triangle or
a theta as an induced subgraph. Here, a _theta_ is a graph made of three
internally vertex-disjoint chordless paths $P_{1}=a\dots b$, $P_{2}=a\dots b$,
$P_{3}=a\dots b$, each of length at least two, such that no edges exist
between the paths except the three edges incident to $a$ and the three edges
incident to $b$.

A consequence is that excluding a grid and a complete bipartite graph as
induced minors is not enough to guarantee a bounded tree-independence number,
or even that the treewidth is bounded by a function of the size of the maximum
clique, because the existence of graphs with large treewidth that contain no
triangles or thetas as induced subgraphs is already known (the so-called
layered wheels).

##  1 Introduction

Graphs in this paper are finite and simple. A graph $H$ is an _induced
subgraph_ of a graph $G$ if $H$ can be obtained from $G$ be repeatedly
deleting vertices. It is an _induced minor_ of $G$ if $H$ can be obtained from
$G$ be repeatedly deleting vertices and contracting edges. It is a _minor_ of
$G$ if $H$ can be obtained from $G$ be repeatedly deleting vertices, deleting
edges and contracting edges. We denote by $K_{t}$ the complete graph on $t$
vertices and by $K_{a,b}$ the complete bipartite graph with sides of size $a$
and $b$. The $(k\times k)$-grid is the graph whose vertices are the pairs
$(i,j)$ of integers such that $1\leq i,j\leq k$ and where $(i,j)$ is adjacent
to $(i^{\prime},j^{\prime})$ if and only if $|i-i^{\prime}|+|j-j^{\prime}|=1$.

The tree-independence number was introduced in [3]. It is defined via tree-
decompositions similarly to treewidth, except that the number associated to
each bag of a tree-decomposition is the maximum size of an independent set of
the graph induced by the bag, instead of its number of vertices (we omit the
full definition for the sake of brevity). It attracted some attention lately,
in particular because for each class of graphs with bounded tree-independence
number, there exists polynomial time algorithms for maximum independent set
and other related problems [3, 5, 6, 11].

The celebrated grid minor theorem of Robertson and Seymour [7] states that
there exists a function $f\colon\mathds{N}\rightarrow\mathds{N}$ so that any
graph with treewidth at least $f(k)$ contains a $(k\times k)$-grid as a minor.
The motivation for our work is the quest for a similar theorem with “tree-
independence number” instead of “treewidth”.

Here, the natural containment relation should be “induced minor” instead of
“minor”, since the tree-independence number is monotone under taking induced
minors but not under taking minors. The list of unavoidable graphs arising
from a large tree-independence number should contain at least large grids and
large complete bipartite graphs, which are known to have unbounded
independence-tree number. Our main result is that this list is not complete.
Indeed, we prove that a construction called _layered wheel_ , first defined in
[8], contains no $(5\times 5)$-grid and no $K_{3,4}$ as an induced minor,
while having arbitrarily large tree-independence number.

### Outline of the proof

We do not need to define layered wheels, which is good since the definition is
a bit long. We just need some of their properties and some preliminary
definitions to state them. A _theta_ is a graph made of three internally
vertex-disjoint chordless paths $P_{1}=a\dots b$, $P_{2}=a\dots b$,
$P_{3}=a\dots b$, each of length at least two, such that no edges exist
between the paths except the three edges incident to $a$ and the three edges
incident to $b$. A graph is _theta-free_ if it does contain a theta as an
induced subgraph, and more generally, a graph is _$H$ -free_ whenever it does
not contain $H$ (when $H$ is a graph) or any graph in $H$ (when $H$ is a class
of graphs, such as thetas) as an induced subgraph. The only property of
layered wheels that we need is the following theorem that states their
existence.

######  Theorem 1.1 (see [8]).

For all integers $t\geq 1$ and $k\geq 3$, there exists a theta-free graph of
girth $k$ that contains $K_{t}$ as a minor.

Since containing $K_{t}$ as a minor implies having treewidth at least $t$,
layered wheels provide theta-free graphs of arbitrarily large girth and
treewidth. Their tree-independence number is also arbitrarily large, since the
treewidth of a triangle-free graph with tree-independence number at most $t$
is at most $R(3,t+1)-2$ where $R(a,b)$ denotes the classical Ramsey number,
see [3]. To fulfill our goal, it therefore remains to prove that layered
wheels do not contain large grids or complete bipartite graphs as induced
minors. As far as we can see, this is non-trivial because even if layered
wheels are precisely defined, checking directly that they do not contain some
$(k\times k)$-grid or $K_{r,s}$ as an induced minor seems to be tedious, at
least according to our several attempts. An indication of this is that some
layered wheels do contain $K_{3,3}$ as an induced minor, which is not obvious,
see Fig. 1 (this figure is meaningful only with the precise definition of a
layered wheel).

Figure 1: A $K_{3,3}$ induced minor in a layered wheel.

Our approach is therefore less direct: we study what induced subgraphs are
forced by the presence of a large grid or complete bipartite graph as an
induced minor as we explain now.

### Complete bipartite graphs

The list of induced subgraphs forced by the presence of $K_{2,3}$ as an
induced minor is already known and not very difficult to obtain, see [4]. But
this is not enough for our purpose since containing $K_{2,3}$ as an induced
minor does not imply anything we can use. By a short argument, we first prove
the following.

######  Theorem 1.2.

If a graph $G$ contains $K_{134,12}$ as an induced minor, then $G$ contains a
cycle of length at most 12 or a theta as an induced subgraph.

The advantage of Theorem 1.2 is its short proof. But its statement is far from
being optimal, as shown by the following, that we obtain by a more careful
structural study.

######  Theorem 1.3.

If a graph $G$ contains $K_{3,4}$ as an induced minor, then $G$ contains a
triangle or a theta as an induced subgraph.

Once Theorem 1.2 (or 1.3) is proved, checking that layered wheels contain no
$K_{134,12}$ (or no $K_{3,4}$) as an induced minor becomes trivial since by
Theorem 1.1, they do not contain short cycles and thetas as induced subgraphs.
Our results therefore avoid some tedious checking, but we also believe that
they are of independent interest.

Note that Theorem 1.3 is best possible in several ways. First, thetas need to
be excluded because the subdivisions of $K_{3,4}$ provide triangle-free graphs
that obviously contain $K_{3,4}$ as an induced minor. Triangles must be
excluded because of line graphs of subdivisions of $K_{3,4}$. A less obvious
construction is represented in Fig. 2, showing that $K_{3,4}$ cannot be
replaced by $K_{3,3}$ in Theorem 1.3.

Figure 2: A (triangle, theta)-free graph containing $K_{3,3}$ as an induced
minor

In fact, we prove a more general result than Theorem 1.3. Before stating it,
we need some definitions.

A _prism_ is a graph made of three vertex-disjoint chordless paths
$P_{1}=a_{1}\dots b_{1}$, $P_{2}=a_{2}\dots b_{2}$, $P_{3}=a_{3}\dots b_{3}$,
such that $\\{a_{1},a_{2},a_{3}\\}$ and $\\{b_{1},b_{2},b_{3}\\}$ are
triangles and no edges exist between the paths except those of the two
triangles and either:

  * •

$P_{1}$, $P_{2}$ and $P_{3}$ all have length at least 1, or

  * •

one of $P_{1},P_{2}$, $P_{3}$ has length 0 and each of the other two has
length at least 2.

Note that allowing a path of length zero in prisms (for instance if
$a_{1}=b_{1}$) is not standard, but natural in our context. A prism with a
path of length zero is sometimes referred to as a _line wheel_ , but we do not
use this terminology here.

Figure 3: The different $3$-path configurations.

A _pyramid_ is a graph made of three chordless paths $P_{1}=a\dots b_{1}$,
$P_{2}=a\dots b_{2}$, $P_{3}=a\dots b_{3}$, each of length at least one, and
two of them with length at least two, vertex-disjoint except at $a$, and such
that $\\{b_{1},b_{2},b_{3}\\}$ is a triangle and no edges exist between the
paths except those of the triangle and the three edges incident to $a$.

A _hole_ in a graph is a chordless cycle of length at least 4. A graph that is
either a theta, a prism or a pyramid is called a _3-paths configuration_ , or
_3PC_ for short. Observe that a graph $G$ is a 3PC if and only if there exist
three pairwise internally vertex disjoint paths $P_{1}$, $P_{2}$, $P_{3}$ such
that $V(G)=V(P_{1})\cup V(P_{2})\cup V(P_{3})$ and for every $i\neq
j\in\\{1,2,3\\}$, $V(P_{i})\cup V(P_{j})$ induces a hole.

######  Theorem 1.4.

If a graph $G$ contains $K_{3,4}$ as an induced minor, then $G$ contains a
3-path configuration as an induced subgraph.

Theorem 1.4 clearly implies Theorem 1.3 because a 3PC that is not a theta
contains a triangle. Proving Theorem 1.4 is just slightly longer than Theorem
1.3, but is also interesting in its own right for the following reason. A hole
is _even_ if it has an even number of vertices. Computing the maximum
independent set of an even-hole-free graph in polynomial time is a well known
open question. Hence, understanding the tree-independence number of even-hole-
free graphs would be interesting. Moreover, Theorem 1.4 implies directly the
existence of even-hole-free graphs of large tree-independence number that
contain no large grids and no $K_{3,4}$ as induced minors. Indeed, [8] not
only provides the layered wheels that we already mentioned, but a variant,
called _even-hole-free layered wheels_ , whose existence is stated in the next
theorem.

######  Theorem 1.5 (see [8]).

For all integers $t\geq 1$, there exists a ($K_{4}$, even hole, 3PC)-free
graph that contains $K_{t}$ as a minor.

So, the simple counter-part of the Robertson and Seymour grid theorem, that
would state that graphs with large tree-independence number should contain a
large grid or a large complete bipartite graph as an induced minor is false,
even when we restrict ourselves to even-hole-free graphs. Even-hole-free
layered wheels provide a counter-example (note that being $K_{4}$-free ensures
that the high treewidth implies a high tree-independence number, see [3]).

Theorem 1.4 is best possible in some sense since we cannot get rid of thetas
in the statement, which are needed because of subdivisions of $K_{3,4}$ that
are easily seen to contain thetas. Also prisms are needed because the line
graph of a theta is a prism, so line graphs of subdivisions of $K_{3,4}$
contain prisms. Observe that we have to allow a path of length zero in a prism
because of the graph depicted in Fig. 4 that contains $K_{3,4}$ as an induced
minor while the only 3PC in it is a prism with a path of length zero. Maybe
pyramids are are not needed in the statement, but we need them in the proof
for reasons that we now explain.

Figure 4: $K_{3,4}$ as an induced minor while all 3PC’s are prisms with a path
of length zero

The proof of Theorem 1.4 relies on a precise description of how $K_{3,3}$ can
be contained as an induced minor in a 3PC-free graph, see Lemma 5.2. The
description is too long to be stated in the introduction, but Fig. 5 provides
representations of the different possible situations.

Figure 5: $K_{3,3}$ as an induced minor in 3PC-free graphs

Observe that excluding pyramids is necessary in Lemma 5.2, because of the
graph presented in Fig. 6, that contains $K_{3,3}$ as induced minor, while the
only 3PC in it is a pyramid.

Figure 6: $K_{3,3}$ as an induced minor in a (theta, prism)-free graph

### Grids

Grids are easier to handle than complete bipartite graphs as shown by the next
lemma whose proof is less involved than the proofs of Theorems 1.2, 1.3 or
1.4. We do not know if a $(4\times 4)$-grid as an induced minor is enough to
guarantee the presence of a 3PC as an induced subgraph.

######  Lemma 1.6.

If a graph $G$ contains a $(5\times 5)$-grid as an induced minor, then $G$
contains a 3-path configuration as an induced subgraph.

Checking that layered wheels (and their even-hole-free variant) contain no
$(5\times 5)$-grid as an induced minor is then easy by Theorem 1.1 and Theorem
1.5.

### Outline of the paper

In Section 2, we prove some technical lemmas about how a connected induced
subgraph of some graph $G$ sees the rest of $G$. These lemmas are more or less
known already. We reprove them for the sake of completeness and because we
could not find them with the precise statement that we need. Note that they
are needed for all the other results. In Section 3, we prove Lemma 1.6. In
Section 4, we prove Theorem 1.2. In Section 5, we prove Theorem 1.4. We
conclude the paper by Section 6 that presents several open questions.

### Notation

Let $G$ be a graph and $X$ and $Y$ be disjoint sets of vertices of $G$. We say
that $X$ is _complete_ to $Y$ if every vertex of $X$ is adjacent to every
vertex of $Y$, $X$ is _anticomplete_ to $Y$ if every no vertex of $X$ is
adjacent to a vertex of $Y$. We say that $X$ _sees_ $Y$ if there exist $x\in
X$ and $y\in Y$ such that $xy\in E(G)$. Note that the empty set is complete
(and anticomplete) to every set of vertices of $G$.

By _path_ we mean a sequence of vertices $p_{1}\dots p_{k}$ such that for all
$1\leq i<j\leq k$, $p_{i}p_{j}\in E(G)$ if and only if $j=i+1$. Therefore,
what we call _path_ for the sake of brevity is sometimes referred to as
_chordless path_ or _induced path_ in a more standard notation. We use the
notation $aPb$ to denote the subpath of $P$ from $a$ to $b$ (possibly $a=b$
since a path may consist of a single vertex).

When we deal with a theta with two vertices of degree 3 $u$ and $v$, we say
that the theta is _from $u$ to $v$_. We use similar terminology for prisms and
pyramids that are, respectively, from a triangle to a triangle and from a
vertex to a triangle.

To avoid too heavy notation, we allow some abuse. Typically, we do not
distinguish between a set of vertices in graph $G$ and the subgraph of $G$
that it induces. For instance, when $P$ is a path and $v$ is a vertex in a
graph $G$, we denote by $P\setminus v$ either $V(P)\setminus\\{v\\}$ or
$G[V(P)\setminus\\{v\\}]$. Also, we may say that a set of vertices $C$ of $G$
is _connected_ when the correct statement should be that $G[C]$ is connected.
We hope that this improves the readability without causing any confusion.

##  2 Types

Figure 7: We illustrate the three types and a degenerate case in which type
path and type claw overlap. For the three types we by way of example
illustrate how $X$ is not connected to anything in $A$ but $x$. For the
degenerate it is depicted that $Y$ and $Z$ are not connected to anything in
$A$ but the vertex $y=z$.

Let $A$, $X$, $Y$ and $Z$ be four disjoint sets of vertices in a graph $G$. We
distinguish three different types the set $A$ can have, see Fig. 7 for an
illustration.

We say that $A$ is of _type path centered at $Y$_ with respect to $X$, $Y$ and
$Z$ if there exists a path $P=x\dots z$ in $A$ such that $x$ sees $X$, $z$
sees $Z$, $P$ sees $Y$, $P\setminus x$ is anticomplete to $X$ and $P\setminus
z$ is anticomplete to $Z$.

Similarly we define $A$ being of _type path centered at $X$_ and being of
_type path centered at $Z$_. We say that $A$ is of _type path_ with respect to
$X$, $Y$ and $Z$ if it is of type path centered at either $X$, $Y$ or $Z$.
Additionally, if $A$ is of type path centered at a set $W$, we call $W$ a
_center for $A$_.

Observe that when $A$ is of type path centered at $Y$ and a unique vertex of
$P$ sees $Y$, and moreover this vertex is $x$, then $A$ is also centered at
$X$. In particular, if $x=z$, then $A$ is centered at $X$, $Y$ and $Z$.

We say that $A$ is of _type claw_ with respect to $X$, $Y$ and $Z$ if there
exists in $A$ a vertex $a$ and three paths $P=a\dots x$, $Q=a\dots y$ and
$R=a\dots z$ such that $V(P)\cap V(Q)\cap V(R)=\\{a\\}$, $P\setminus a$,
$Q\setminus a$ and $R\setminus a$ are pairwise anticomplete, $x$ sees $X$, $y$
sees $Y$, $z$ sees $Z$, $(P\cup Q\cup R)\setminus x$ is anticomplete to $X$,
$(P\cup Q\cup R)\setminus y$ is anticomplete to $Y$ and $(P\cup Q\cup
R)\setminus z$ is anticomplete to $Z$.

Observe that possibly $a=x$, $a=y$ or $a=z$ (in fact, possibly two or three of
these equalities hold). Observe that if $a=x$, then $A$ is not only of type
claw, but also of type path centered at $X$, this case is additionally
depicted in Fig. 7.

We say that $A$ is of _type triangle_ with respect to $X$, $Y$ and $Z$ if
there exists in $A$ three vertex-disjoint paths $P=x\dots x^{\prime}$,
$Q=y\dots y^{\prime}$ and $R=z\dots z^{\prime}$ such that the only edges
between $P$, $Q$ and $R$ are $xy$, $yz$ and $yz$, $x^{\prime}$ sees $X$,
$y^{\prime}$ sees $Y$, $z^{\prime}$ sees $Z$, $(P\cup Q\cup R)\setminus x$ is
anticomplete to $X$, $(P\cup Q\cup R)\setminus y$ is anticomplete to $Y$ and
$(P\cup Q\cup R)\setminus z$ is anticomplete to $Z$.

Observe that each of $P$, $Q$ and $R$ is possibly of length 0.

######  Lemma 2.1.

Let $G$ be a graph and $A$, $X$, $Y$ and $Z$ be disjoint sets of vertices of
$G$. If $A$ is connected and $A$ sees $X$, $Y$ and $Z$, then $A$ is of type
path, of type claw, or of type triangle with respect to $X$, $Y$ and $Z$.

###### Proof.

Suppose that $A$ is not of type path. Let $P=x\dots z$ be a path in $A$ such
that $x$ sees $X$, $z$ sees $Z$, $P\setminus x$ is anticomplete to $X$ and
$P\setminus z$ is anticomplete to $Z$. Note that such a path exists (consider
for instance a shortest path from the vertices that see $X$ to the vertices
that see $Z$). Since $A$ is not of type path centered at $Y$, $P$ is
anticomplete to $Y$. Let $Q=y\dots y^{\prime}$ be path in $A$ disjoint from
$P$ and such that $y$ sees $Y$, $y^{\prime}$ sees $P$, $Q\setminus y$ is
anticomplete to $Y$ and $Q\setminus y^{\prime}$ is anticomplete to $P$. Note
again that such a path exists (consider for instance a shortest path from the
vertices that see $Y$ to the vertices that see $P$). We suppose that $P$ and
$Q$ are chosen subject to the minimality of $V(P)\cup V(Q)$.

Let $a$ be the neighbor of $y^{\prime}$ in $P$ closest to $x$ along $P$ and
$a^{\prime}$ be the neighbor of $y^{\prime}$ in $P$ closest to $z$ along $P$
(possibly $a=a^{\prime}$ or $aa^{\prime}\in E(G)$).

If $Q$ sees both $X$ and $Z$, then consider vertex $u$ in $Q$ such that $yQu$
sees both $X$ and $Z$, and choose $u$ closest to $y$ along $Q$. The path $yQu$
shows that $A$ is of type path (centered at $X$ or $Z$, possibly both,
possibly also centered at $Y$ if $u=y$), a contradiction. Hence, we may assume
up to symmetry that $Q$ is anticomplete to $Z$. If $Q$ sees $X$, then the path
$yQy^{\prime}a^{\prime}Pz$ shows that $A$ is of type path centered at $X$, a
contradiction. Hence, $Q$ is anticomplete to $X$ and $Z$.

If $a\neq a^{\prime}$ and $aa^{\prime}\notin E(G)$, then consider the path
$P^{\prime}=xPay^{\prime}a^{\prime}Pz$. If $y=y^{\prime}$, then because of
$P^{\prime}$, $A$ is of type path centered at $Y$, a contradiction. So, $y\neq
y^{\prime}$ and the paths $P^{\prime}$ and $Q\setminus y^{\prime}$ contradict
the minimality of $V(P)\cup V(Q)$.

Hence $a=a^{\prime}$ or $aa^{\prime}\in E(G)$. If $a=a^{\prime}$, then the
three paths $aPx$, $ay^{\prime}Qy$ and $aPz$ show that $A$ is of type claw
with respect to $X$, $Y$ and $Z$. If $aa^{\prime}\in E(G)$, then the three
paths $aPx$, $Q$ and $a^{\prime}Pz$ show that $A$ is of type triangle with
respect to $X$, $Y$ and $Z$. ∎

The next lemma is implicitly about the presence of $K_{2,3}$ as an induced
minor in a graph. In [4], it is proved along similar lines that a graph
contains $K_{2,3}$ as an induced minor if and only if it contains some
configuration from a restricted list as an induced subgraph (the so-called
thetas, pyramids, long prisms and broken wheels, not worth defining here).

######  Lemma 2.2.

Let $G$ be a 3PC-free graph and $A$, $B$, $X$, $Y$ and $Z$ be disjoint
connected subsets of $V(G)$. If $X$, $Y$ and $Z$ are pairwise anticomplete,
$A$ and $B$ are anticomplete to each other, and each of $A$ and $B$ sees each
of $X$, $Y$ and $Z$, then $A$ and $B$ are of type path with respect to $X$,
$Y$ and $Z$.

###### Proof.

Suppose for a contradiction that $A$ (the argument for $B$ is the same by
symmetry) is not of type path with respect to $X$, $Y$ and $Z$. Hence, by
Lemma 2.1, $A$ we may consider the two cases below.

Case 1: $A$ is of type claw (and not of type path). So, there exists a vertex
$a\in A$ and three paths $P=a\dots x$, $Q=a\dots y$ and $R=a\dots z$ like in
the definition of type claw. Moreover, $a\neq x$, $a\neq y$ and $a\neq z$ for
otherwise, $A$ would be of type path.

If $B$ is of type claw, then there exist a vertex $b\in B$ and three paths
$P^{\prime}=b\dots x^{\prime}$, $Q^{\prime}=b\dots y^{\prime}$ and $R=b\dots
z^{\prime}$ like in the definition of type claw. Consider a shortest path
$P^{\prime\prime}$ from $x$ to $x^{\prime}$ with interior in $X$, and let
$Q^{\prime\prime}=y\dots y^{\prime}$ and $R^{\prime\prime}=z\dots z^{\prime}$
be defined similarly through $Y$ and $Z$. The nine paths $P$, $Q$, $R$,
$P^{\prime}$, $Q^{\prime}$, $R^{\prime}$, $P^{\prime\prime}$,
$Q^{\prime\prime}$ and $R^{\prime\prime}$ form a theta from $a$ to $b$, a
contradiction.

If $B$ is of type triangle, a similar contradiction is found because of the
existence of a pyramid in $G$.

So $B$ is not of type claw or triangle. By Lemma 2.1, $B$ is of type path, and
up to symmetry we suppose that it is centered at $Y$. Let
$P^{\prime}=x^{\prime}\dots z^{\prime}$ be a path like in the definition of
type path. Consider a shortest path $P^{\prime\prime}$ from $x$ to
$x^{\prime}$ with interior in $X$, and let $R^{\prime\prime}=z\dots
z^{\prime}$ be defined similarly through $Z$. Let $Q^{\prime\prime}=b\dots
b^{\prime}$ be a shortest path in $Y$ such that $by\in E(G)$ and $b^{\prime}$
sees $P^{\prime}$. Let $a^{\prime}$ be the neighbor of $b^{\prime}$ in
$P^{\prime}$ closest to $x^{\prime}$ along $P^{\prime}$. Let
$a^{\prime\prime}$ be the neighbor of $b^{\prime}$ in $P^{\prime}$ closest to
$z^{\prime}$ along $P^{\prime}$. If $a^{\prime}=a^{\prime\prime}$, then $B$ is
of type claw, a contradiction. If $a^{\prime}a^{\prime\prime}\in E(G)$, then
the seven paths $P$, $Q$, $R$, $P^{\prime}$, $P^{\prime\prime}$,
$Q^{\prime\prime}$ and $R^{\prime\prime}$ form a pyramid from $a$ to
$b^{\prime}a^{\prime}a^{\prime\prime}$, a contradiction. Hence $a\neq
a^{\prime}$ and $aa^{\prime}\notin E(G)$. So the paths $P$, $Q$, $R$,
$x^{\prime}P^{\prime}a^{\prime}$, $a^{\prime\prime}P^{\prime}z^{\prime}$,
$P^{\prime\prime}$, $Q^{\prime\prime}$ and $R^{\prime\prime}$ form a theta
from $a$ to $b^{\prime}$, a contradiction.

Case 2: $A$ is of type triangle.

The proof is almost the same as in Case 1, so we just sketch it. If $B$ is of
type claw, then $G$ contains a pyramid. If $B$ is of type triangle, then $G$
contains a prism. And if $B$ is of type path, then $G$ contains a prism or a
pyramid. ∎

Let $G$ and $H$ be two graphs. An _induced minor model_ of $H$ in $G$ is a
collection of pairwise disjoint sets $\\{X_{v}\\}_{v\in V(H)},$ called the
_branch sets_ of the model, such that

  * •

$X_{v}\subseteq V(G)$ for all $v\in V(H),$

  * •

$X_{v}$ induces a connected subgraph of $G$ for every $v\in V(H),$ and

  * •

$X_{u}$ sees $X_{v}$ (in $G$) if and only if $uv\in E(H)$.

It is well known and easy to check that $G$ contains a graph isomorphic to $H$
as an induced minor if and only if there exists an induced minor model of $H$
in $G$. We identify an induced minor model $\\{X_{v}\\}_{v\in V(H)}$ of $H$ in
$G$ with the graph $H^{\prime}\coloneqq G[\bigcup_{v\in V(H)}X_{v}]$. Please
note that the definition of the branch sets is not uniquely determined by
$H^{\prime}.$

An induced minor model $H^{\prime}\subseteq G$ of $H$ is _minimal_ if
$H^{\prime}\setminus a$ does not contain an induced minor isomorphic to $H$
for all $a\in V(H^{\prime}).$

We denote by $K^{*}_{2,3}$ the graph obtained from $K_{2,3}$ by subdividing
every edge once, i.e., $K^{*}_{2,3}$ is the graph with two degree-3 vertices
and three paths of length four between them.

######  Lemma 2.3.

If a graph contains $K^{*}_{2,3}$ as an induced minor, then it contains a 3PC.

###### Proof.

Suppose for a contradiction that a 3PC-free graph $G$ contains $H=K^{*}_{2,3}$
as an induced minor. Denote by $a$ and $b$ the degree-3 vertices and let
$ap_{1}p_{2}p_{3}b$, $aq_{1}q_{2}q_{3}b$ and $ar_{1}r_{2}r_{3}b$ be the three
paths of $H$. Consider a minimal induced minor model $\\{X_{v}\\}_{v\in V(H)}$
of $H$ in $G$. For all $v\in V(H)\setminus\\{a,b\\}$, $v$ has two neighbors
$u$ and $w$ in $H$ and by minimality, $X_{v}$ is a path $P=v^{\prime}\dots
v^{\prime\prime}$ such that $v^{\prime}$ see $X_{u}$, $v^{\prime\prime}$ sees
$X_{w}$, $P\setminus v^{\prime}$ is anticomplete to $X_{u}$ and $P\setminus
v^{\prime\prime}$ is anticomplete to $X_{w}$. It follows that if we set
$A=X_{a}\cup X_{p_{1}}\cup X_{p_{2}}\cup X_{q_{1}}\cup X_{q_{2}}\cup
X_{r_{1}}\cup X_{r_{2}}$, $X=X_{p_{3}}$, $Y=X_{q_{3}}$, $Z=X_{r_{3}}$ and
$B=X_{b}$, $A$ cannot be of type path with respect to $X$, $Y$ and $Z$.
Indeed, since $X_{p_{1}}\cup X_{p_{2}}$, $X_{q_{1}}\cup X_{q_{2}}$ and
$X_{r_{1}}\cup X_{r_{2}}$ all induce paths of length at least 1 in $G$, $A$
cannot contain a path with vertices seeing $X$, $Y$ and $Z$. Hence, $A$, $B$,
$X$, $Y$ and $Z$ contradict Lemma 2.2. ∎

##  3 Proof of Lemma 1.6

We here prove Lemma 1.6 that we restate.

See 1.6

###### Proof.

If a graph contains a $(5\times 5)$-grid as an induced minor, then it contains
$K_{2,3}^{*}$ as an induced minor, because the $(5\times 5)$-grid contains
$K_{2,3}^{*}$ as an induced subgraph. The result therefore follows from Lemma
2.3. ∎

##  4 Proof of Theorem 1.2

######  Lemma 4.1.

Let $G$ and $H$ be graphs and $\\{X_{v}\\}_{v\in V(H)}$ a minimal induced
minor model of $H$ in $G$. For every $v\in V(H)$, the graph $G[X_{v}]$ does
not contain cycles longer than the degree of $v$.

###### Proof.

First, for every neighbor $u$ of $v$ in $H$, let us mark a single vertex in
$X_{v}$ that is adjacent to a vertex in $X_{u}$. If there exists a connected
induced proper subgraph of $G[X_{v}]$ that contains all of the marked
vertices, we contradict the minimality of the induced minor model.

Suppose that $G[X_{v}]$ contains a cycle of length longer than the degree of
$v$, and let $C\subseteq X_{v}$ be the vertices of this cycle. We say that a
vertex $w\in C$ is _necessary_ if either $w$ is marked or there exists a
connected component $Y$ of $G[X_{v}\setminus C]$ that contains a marked vertex
and whose only neighbor in $C$ is the vertex $w$. Because $|C|$ is larger than
the number of marked vertices, there exists a vertex in $C$ that is not
necessary, let $w\in C$ be such a vertex. We remove from $X_{v}$ the vertex
$w$ and every component of $G[X_{v}\setminus C]$ whose only neighbor in $C$ is
$w$. All of the remaining vertices in $X_{v}$ are still connected to
$C\setminus\\{w\\}$ and contain all of the marked vertices, so we get a
connected induced proper subgraph of $G[X_{v}]$ that contains all of the
marked vertices, which is a contradiction. ∎

Lemma 4.1 is useful for asserting that $G[X_{v}]$ is a tree, which in turn is
useful for obtaining degree-1 vertices in $G[X_{v}]$. We make use of degree-1
vertices with the following lemma.

######  Lemma 4.2.

Let $\\{X_{v}\\}_{v\in V(H)}$ be a minimal induced minor model of a graph $H$
in a graph $G$, and let $v\in V(H)$. For every vertex $w\in X_{v}$ whose
degree is one in $G[X_{v}]$, there exists $u\in V(H)\setminus\\{v\\}$ so that
$w$ is the only neighbor of $X_{u}$ in $X_{v}$.

###### Proof.

Otherwise, we could remove $w$ from $X_{v}$ and contradict the minimality of
$\\{X_{v}\\}_{v\in V(H)}$. ∎

We say that such a branch set $X_{u}$ is _private_ to the vertex $w$. We may
now prove Theorem 1.2 which we restate below.

See 1.2

###### Proof.

Let $p=12$ and $t=2\binom{p}{2}+2=134$. Let $G$ be a graph with girth at least
$p+1$, and let $\\{X_{v}\\}_{v\in V(K_{t,p})}$ be a minimal induced minor
model of $K_{t,p}$ in $G$. We denote the branch sets corresponding to vertices
of $K_{t,p}$ on the side with $t$ vertices by $A_{1},\ldots,A_{t}$ and on the
other side by $B_{1},\ldots,B_{p}$. Note that $G$ is triangle-free.

First suppose that there are two branch sets $A_{i}$, $A_{j}$ of size
$|A_{i}|,|A_{j}|\leq 2$. In this case, there must be a vertex $v\in A_{i}$
that is adjacent to at least $p/2$ different branch sets on the other side,
and a vertex $u\in A_{j}$ that is adjacent to at least $p/4=3$ different
branch sets on the other side that $v$ is also adjacent to. Fix three
different branch sets $B_{a}$, $B_{b}$, $B_{c}$ that both $v$ and $u$ are
adjacent to. Now, by selecting in each branch set $B_{a}$, $B_{b}$, $B_{c}$ a
shortest path from a neighbor of $v$ to a neighbor of $u$, we obtain a theta
from $u$ to $v$.

We may therefore assume that at least $t-1$ of the branch sets
$A_{1},\ldots,A_{t}$ contain at least three vertices. By Lemma 4.1 and because
$G$ has girth at least $p+1$, for all branch sets $A_{1},\ldots,A_{t}$ the
induced subgraph $G[A_{i}]$ is a tree, and for all such sets with $|A_{i}|\geq
3$, the tree must have two non-adjacent leaves $v$ and $u$. By Lemma 4.2, both
$v$ and $u$ have a private branch set on the other side, so we can label each
branch set $A_{i}$ with $|A_{i}|\geq 3$ with an unordered pair
$\\{B_{j},B_{k}\\}$ so that $B_{j}$ is private to $v$ and $B_{k}$ is private
to $u$.

Now, because $t-1=2\binom{p}{2}+1$, there must exist three branch sets
$A_{a}$, $A_{b}$, and $A_{c}$ that are labeled with the same pair
$\\{B_{j},B_{k}\\}$. By contracting both $B_{j}$ and $B_{k}$ into a single
vertex and taking the paths in $A_{a}$, $A_{b}$, and $A_{c}$ between the
corresponding leaves, we obtain $K^{*}_{2,3}$ as an induced minor. By Lemma
2.3, $G$ must contain a theta since the theta is the only triangle-free 3PC. ∎

##  5 Proof of Theorem 1.4

We start with an improvement of Lemma 2.2.

######  Lemma 5.1.

Let $G$ be a 3PC-free graph and $k\geq 2$ be an integer. Suppose that $X$,
$Y$, $Z$ and $A_{1}$, …, $A_{k}$ are disjoint connected subsets of $V(G)$,
$X$, $Y$ and $Z$ are pairwise anticomplete, $A_{1}$, …, $A_{k}$ are pairwise
anticomplete, and for every $i\in\\{1,\dots,k\\}$, $A_{i}$ sees $X$, $Y$ and
$Z$.

Then the $A_{i}$’s are all of type path with respect to $X$, $Y$ and $Z$ and
furthermore, one of $X$, $Y$ and $Z$ is a center for all of them.

###### Proof.

By Lemma 2.2 applied to $A=A_{i}$, $B=A_{j}$ for some $j\neq i$ and $X$, $Y$
and $Z$, we see that all $A_{i}$’s are of type path with respect to $X$, $Y$
and $Z$. It remains to prove that they all share a common center.

We denote by $\tau(A_{i})$ the sets of all elements $U\in\\{X,Y,Z\\}$ such
that $A_{i}$ is centered at $U$. Note that for all $i\in\\{1,\dots,k\\}$,
$\tau(A_{i})$ is nonempty. It is enough to prove that for all
$i,j\in\\{1,\dots,k\\}$, either $\tau(A_{i})\subseteq\tau(A_{j})$ or
$\tau(A_{j})\subseteq\tau(A_{i})$. Indeed, this implies that the sets
$\tau(A_{i})$ are linearly ordered by the inclusion, so that
$\cap_{i\in\\{1,\dots,k\\}}\tau(A_{i})$ is non-empty and contains the common
center that we are looking for.

So suppose for a contradiction that $A=A_{i}$ and $B=A_{j}$ are such that
$\tau(A_{i})$ and $\tau(A_{j})$ are inclusion-wise incomparable. So, up to
symmetry, $A$ is centered at $X$ and not at $Y$ while $B$ is centered at $Y$
and not at $X$.

Since $A$ is centered at $X$, there exists $P=u\dots u^{\prime}$ in $A$ such
that $u$ sees $Y$, $u^{\prime}$ sees $Z$, $P$ sees $X$, $P\setminus u$ is
anticomplete to $Y$ and $P\setminus u^{\prime}$ is anticomplete to $Z$. Since
$B$ is centered at $Y$, there exists $Q=v\dots v^{\prime}$ in $B$ such that
$v$ sees $X$, $v^{\prime}$ sees $Z$, $Q$ sees $Y$, $Q\setminus v$ is
anticomplete to $X$ and $Q\setminus v^{\prime}$ is anticomplete to $Z$.

Let $R=z\dots z^{\prime}$ be a shortest path in $Z$ such that $u^{\prime}z\in
E(G)$ and $z^{\prime}v^{\prime}\in E(G)$. Let $S=y\dots y^{\prime}$ be a
shortest path in $Y$ such that $y$ sees $Q$ and $y^{\prime}u\in E(G)$. Let
$T=x\dots x^{\prime}$ be a shortest path in $X$ such that $x$ sees $P$ and
$x^{\prime}v\in E(G)$. Observe that each of $P$, $Q$, $R$, $S$ and $T$ can be
of length 0.

Let $a$ be the neighbor of $x$ in $P$ closest to $u$ along $P$. Let
$a^{\prime}$ be the neighbor of $x$ in $P$ closest to $u^{\prime}$ along $P$.
Let $b$ be the neighbor of $y$ in $Q$ closest to $v$ along $Q$. Let
$b^{\prime}$ be the neighbor of $y$ in $Q$ closest to $v^{\prime}$ along $Q$.
See Figure 8.

Figure 8: Paths $P$, $Q$, $R$, $S$ and $T$ in the proof of Lemma 5.1

Suppose first that $a=a^{\prime}$. Observe that $a=a^{\prime}\neq u$ for
otherwise $A$ would be centered at $Y$, contrary to our assumption. Hence,
$ay\notin E(G)$. If $b=b^{\prime}$, then $P$, $Q$, $R$, $S$ and $T$ form a
theta from $a$ to $b$, so $b\neq b^{\prime}$. If $bb^{\prime}\in E(G)$, then
$P$, $Q$, $R$, $S$ and $T$ form a pyramid from $a$ to $ybb^{\prime}$. If
$bb^{\prime}\notin E(G)$, then $P$, $vQb$, $b^{\prime}Qv^{\prime}$, $R$, $S$
and $T$ form a theta from $a$ to $y$ (because $ay\notin E(G)$ as already
noted). Hence $a\neq a^{\prime}$, and symmetrically we can prove that $b\neq
b^{\prime}$.

Suppose now $aa^{\prime}\in E(G)$. If $bb^{\prime}\in E(G)$, then $P$, $Q$,
$R$, $S$ and $T$ form a prism from $xaa^{\prime}$ to $ybb^{\prime}$. If
$bb^{\prime}\notin E(G)$, then $P$, $vQb$, $b^{\prime}Qv^{\prime}$, $R$, $S$
and $T$ form a pyramid from $y$ to $xaa^{\prime}$. Hence $aa^{\prime}\notin
E(G)$, and symmetrically we can prove that $bb^{\prime}\notin E(G)$.

We are left with the case where $a\neq a^{\prime}$, $aa^{\prime}\notin E(G)$,
$b\neq b^{\prime}$ and $bb^{\prime}\notin E(G)$. Then $uPa$,
$a^{\prime}Pu^{\prime}$, $vQb$, $b^{\prime}Qv^{\prime}$, $R$, $S$ and $T$ form
a theta from $x$ to $y$. ∎

The following lemma describes what happens when $K_{3,3}$ is an induced minor
of some 3PC-free graph. It is worth noting that it has a true converse that we
do not need to state formally. More precisely, if in any graph six paths $A$,
$B$, $C$, $P$, $Q$ and $R$ satisfy all the properties described in Lemma 5.2,
then they form a model for a $K_{3,3}$ induced minor, and moreover the graph
that they induce can be checked to be 3PC-free, see Fig. 5.

Note that the statement of Lemma 5.2 is not completely symmetric. Namely, $A$,
$B$ and $C$ are assumed to be minimal while $X$, $Y$ and $Z$ are not. This
yields a slightly stronger statement which is needed for the application in
the proof of Theorem 1.4.

######  Lemma 5.2.

Let $G$ be a 3PC-free graph and $A$, $B$, $C$, $X$, $Y$ and $Z$ be connected
disjoint subsets of $V(G)$ such that $X$, $Y$ and $Z$ are pairwise
anticomplete, $A$, $B$ and $C$ are pairwise anticomplete and each of $A$, $B$
and $C$ sees each of $X$, $Y$ and $Z$. Suppose that no connected proper subset
of $A$ (resp. $B$ and $C$) sees each of $X$, $Y$ and $Z$. Then, there exist
six vertex-disjoint paths $A^{\prime}=a\dots a^{\prime}$, $B^{\prime}=b\dots
b^{\prime}$, $C^{\prime}=c\dots c^{\prime}$, $P=p\dots p^{\prime}$, $Q=q\dots
q^{\prime}$ and $R=r\dots r^{\prime}$ in $G$ such that:

  * •

Each of $A^{\prime}$, $B^{\prime}$ and $C^{\prime}$ _is equal to_ exactly one
of $A$, $B$ or $C$.

  * •

Each of $X$, $Y$ and $Z$ _contains_ exactly one of $P$, $Q$ or $R$.

  * •

$H=aA^{\prime}a^{\prime}rRr^{\prime}c^{\prime}C^{\prime}cp^{\prime}Ppa$ is a
hole.

  * •

$B^{\prime}\setminus b$ (resp. $B^{\prime}\setminus b^{\prime}$, $Q\setminus
q$, $Q\setminus q^{\prime}$) is anticomplete to $P$ (resp. $R$, $A^{\prime}$,
$C^{\prime}$).

  * •

$B^{\prime}$ and $Q$ both have length at most 1 (so they each contain at most
two vertices).

  * •

$b$ (resp. $b^{\prime}$, $q$, $q^{\prime}$) has at least three neighbors in
$P$ (resp. $R$, $A^{\prime}$, $C^{\prime}$). In particular, each of $P$, $R$,
$A^{\prime}$ and $C^{\prime}$ contains at least three vertices.

  * •

$B^{\prime}$ is complete to $Q$, or $G[B^{\prime}\cup Q]$ has four vertices
and five edges.

###### Proof.

By Lemma 5.1, $A$, $B$ and $C$ are of type path with respect to $X$, $Y$ and
$Z$, centered at some $Y^{\prime}\in\\{X,Y,Z\\}$. By Lemma 5.1, $X$, $Y$ and
$Z$ are of type path with respect to $A$, $B$ and $C$, centered at some
$B^{\prime}\in\\{A,B,C\\}$. We let $X^{\prime}$, $Z^{\prime}$, $A^{\prime}$
and $C^{\prime}$ be such that
$\\{A^{\prime},B^{\prime},C^{\prime}\\}=\\{A,B,C\\}$ and
$\\{X^{\prime},Y^{\prime},Z^{\prime}\\}=\\{X,Y,Z\\}$.

So, $A^{\prime}$ contains some path that sees $X^{\prime}$, $Y^{\prime}$ and
$Z^{\prime}$ as in the definition of type path centered at $Y^{\prime}$, but
by the assumption about the minimality of $A$, $B$ or $C$, we see that this
path is in fact $A^{\prime}$ itself. So $A^{\prime}$ is equal to exactly one
of $A$, $B$ or $C$. The arguments works also with $B$ and $C$, so that
$A^{\prime}=a\dots a^{\prime}$, $B^{\prime}=b\dots b^{\prime}$,
$C^{\prime}=c\dots c^{\prime}$, each of $a$, $b$ and $c$ sees $X^{\prime}$,
each of $a^{\prime}$, $b^{\prime}$ and $c^{\prime}$ sees $Z^{\prime}$, each of
$A^{\prime}$, $B^{\prime}$ and $C^{\prime}$ sees $Y^{\prime}$, each of
$A^{\prime}\setminus a$, $B^{\prime}\setminus b$ and $C^{\prime}\setminus c$
is anticomplete to $X^{\prime}$ and each of $A^{\prime}\setminus a^{\prime}$,
$B^{\prime}\setminus b^{\prime}$ is and $C^{\prime}\setminus c^{\prime}$ is
anticomplete to $Z^{\prime}$.

Also $X^{\prime}$ contains a path $P=p\dots p^{\prime}$ such that $p$ sees
$A^{\prime}$, $p^{\prime}$ sees $C^{\prime}$, $P\setminus p$ is anticomplete
to $A^{\prime}$, $P\setminus p^{\prime}$ is anticomplete to $C^{\prime}$ and
$P$ sees $B^{\prime}$. Note that we cannot claim that $X^{\prime}=P$, since we
made no assumption about the minimality of $X$. But since $A^{\prime}\setminus
a$ is anticomplete to $X^{\prime}$ and $P\setminus p$ is anticomplete to
$A^{\prime}$, the only possible edge between $P$ and $A^{\prime}$ is $pa$.
Similarly, $p^{\prime}c$ is the only edge between $P$ and $C^{\prime}$.
Moreover, $P$ sees $B^{\prime}$, and since $B\setminus b$ is anticomplete to
$X^{\prime}$, we know that $b$ sees $P$ (and not only $X^{\prime}$).

Similarly, $Z^{\prime}$ contains a path $R=r\dots r^{\prime}$ with
$ra^{\prime}\in E(G)$, $r^{\prime}c^{\prime}\in E(G)$, $R\setminus r$ is
anticomplete to $A^{\prime}$, $R\setminus r^{\prime}$ is anticomplete to
$C^{\prime}$ and such that $b^{\prime}$ sees $R$. Observe that $A^{\prime}$,
$P$, $C^{\prime}$ and $R$ form a hole $H$.

Also $Y^{\prime}$ is of type path with respect to $A$, $B$ and $C$ and
centered at $B^{\prime}$. So, $Y^{\prime}$ contains a path $Q=q\dots
q^{\prime}$ such that $q$ sees $A^{\prime}$, $q^{\prime}$ sees $C^{\prime}$,
$Q\setminus q$ is anticomplete to $A^{\prime}$, $Q\setminus q^{\prime}$ is
anticomplete to $C^{\prime}$ and $Q$ sees $B^{\prime}$.

Let $\alpha$ be the neighbor of $q$ in $A^{\prime}$ closest to $a$ along
$A^{\prime}$. Let $\alpha^{\prime}$ be the neighbor of $q$ in $A^{\prime}$
closest to $a^{\prime}$ along $A$. Let $\beta$ be the neighbor of $b$ in $P$
closest to $p$ along $P$. Let $\beta^{\prime}$ be the neighbor of $b$ in $P$
closest to $p^{\prime}$ along $P$. Let $\gamma$ be the neighbor of
$q^{\prime}$ in $C^{\prime}$ closest to $c$ along $C^{\prime}$. Let
$\gamma^{\prime}$ be the neighbor of $q^{\prime}$ in $C^{\prime}$ closest to
$c^{\prime}$ along $C^{\prime}$. Let $\delta$ be the neighbor of $b^{\prime}$
in $R$ closest to $r$ along $R$. Let $\delta^{\prime}$ be the neighbor of
$b^{\prime}$ in $R$ closest to $r^{\prime}$ along $R$. See Fig. 9.

Figure 9: Paths $A^{\prime}$, $B^{\prime}$, $C^{\prime}$, $P$, $Q$ and $R$ in
the proof of Lemma 5.2

Suppose that $B^{\prime}$ has length at least 2. Then $B$ and $H$ contains a
theta, a prism or a pyramid, namely from $\beta$ (if $\beta=\beta^{\prime}$)
or $b\beta\beta^{\prime}$ (if $\beta\beta^{\prime}\in E(G)$) or $b$
(otherwise), to $\delta$ (if $\delta=\delta^{\prime}$) or
$b^{\prime}\delta\delta^{\prime}$ (if $\delta\delta^{\prime}\in E(G)$) or
$b^{\prime}$ (otherwise). Hence $B^{\prime}$ has length at most 1, meaning
that either $b=b^{\prime}$ or $bb^{\prime}\in E(G)$. Similarly, $Q$ has length
at most 1 and $q=q^{\prime}$ or $qq^{\prime}\in E(G)$.

Suppose that $\beta=\beta^{\prime}$. Then $b=b^{\prime}$ for otherwise $B$ and
$H$ contain a theta (if $\delta=\delta^{\prime}$), or a pyramid from $\beta$
to $b^{\prime}\delta\delta^{\prime}$ (if $\delta\delta^{\prime}\in E(G)$), or
a theta from $\beta$ to $b^{\prime}$ (otherwise). Since $B^{\prime}$ sees $Q$,
$b$ has a neighbor in $Q$. If $b$ has a unique neighbor in $Q$, say $q$ up to
symmetry (so either $q=q^{\prime}$, or $q\neq q^{\prime}$ and
$bq^{\prime}\notin E(G)$), then the three paths $\beta bq$, $\beta
PpaA^{\prime}\alpha q$ and $\beta Pp^{\prime}cC^{\prime}\gamma q^{\prime}q$
form a theta from $\beta$ to $q$. So, $b$ has two neighbors in $Q$. Hence, the
three paths $\beta b$, $\beta PpaA^{\prime}\alpha q$ and $\beta
Pp^{\prime}cC^{\prime}\gamma q^{\prime}$ form a pyramid from $\beta$ to
$bqq^{\prime}$. We proved that $\beta\neq\beta^{\prime}$.

Suppose that $\beta\beta^{\prime}\in E(G)$. Then $b=b^{\prime}$ for otherwise
$B$ and $H$ contains a pyramid from $\delta$ to $b\beta\beta^{\prime}$ (if
$\delta=\delta^{\prime}$), a prism from $b\beta\beta^{\prime}$ to
$b^{\prime}\delta\delta^{\prime}$ (if $\delta\delta^{\prime}\in E(G)$) or a
pyramid from $b^{\prime}$ to $b\beta\beta^{\prime}$ (otherwise). Since
$B^{\prime}$ sees $Q$, $b$ has a neighbor in $Q$. If $b$ has a unique neighbor
in $Q$, say $q$ up to symmetry (so either $q=q^{\prime}$, or $q\neq
q^{\prime}$ and $bq^{\prime}\notin E(G)$), then the three paths $qb$, $q\alpha
A^{\prime}apP\beta$ and $qq^{\prime}\gamma
C^{\prime}cp^{\prime}P\beta^{\prime}$ form a pyramid from $q$ to
$b\beta\beta^{\prime}$. So, $b$ has two neighbors in $Q$. Hence, the three
paths $b$, $q\alpha A^{\prime}apP\beta$ and $q^{\prime}\gamma
C^{\prime}cp^{\prime}P\beta^{\prime}$ form a prism from $bqq^{\prime}$ to
$b\beta\beta^{\prime}$. We proved that $\beta\beta^{\prime}\notin E(G)$. This
implies that $b$ has at least three neighbors in $P$ for otherwise $H$ and $b$
would form a theta from $\beta$ to $\beta^{\prime}$.

We proved $b$ has at least three neighbors in $P$. By a symmetric argument, we
can prove that $b^{\prime}$ (resp. $q$, $q^{\prime}$) has at least three
neighbors in $R$ (resp. $A^{\prime}$, $C^{\prime}$). It remains to prove that
$B^{\prime}$ is complete to $Q$, or $B^{\prime}\cup Q$ induces a graph with
four vertices and five edges. So suppose that $B^{\prime}$ is not complete to
$Q$.

Since $B^{\prime}$ sees $Q$ and $B^{\prime}$ is not complete to $Q$, there is
at least one edge and at least one non-edge with ends in $B$ and $Q$. So,
there must be a vertex, either in $B$ or $Q$, that is incident to such an edge
and such a non-edge. Up to symmetry, we assume that this vertex is $b$ and
$bq\in E(G)$ (so $bq^{\prime}\notin E(G)$ and $q\neq q^{\prime}$). If
$b=b^{\prime}$, or if $b\neq b^{\prime}$ and $G[B^{\prime}\cup Q]$ has only
three edges (namely $bb^{\prime}$, $qq^{\prime}$ and $bq$), then
$bqq^{\prime}$, $b\beta^{\prime}Pp^{\prime}cC^{\prime}\gamma q^{\prime}$ and
$bb^{\prime}\delta^{\prime}Rr^{\prime}c^{\prime}C^{\prime}\gamma^{\prime}q^{\prime}$
form a theta from $b$ to $q^{\prime}$. We proved that $b\neq b^{\prime}$ and
$G[B^{\prime}\cup Q]$ has at least four edges. So, $G[B^{\prime}\cup Q]$ has
four vertices and it remains to prove that it has exactly five edges. So
suppose for a contradiction that $G[B^{\prime}\cup Q]$ has exactly four edges.

If $b^{\prime}q^{\prime}\in E(G)$ (and therefore $b^{\prime}q\notin E(G)$),
then $bqq^{\prime}$, $bb^{\prime}q^{\prime}$ and
$b\beta^{\prime}Pp^{\prime}cC^{\prime}\gamma q^{\prime}$ form a theta from $b$
to $q^{\prime}$. If $b^{\prime}q\in E(G)$ (and therefore
$b^{\prime}q^{\prime}\notin E(G)$), then $q^{\prime}q$, $q^{\prime}\gamma
C^{\prime}cp^{\prime}P\beta^{\prime}b$ and
$q^{\prime}\gamma^{\prime}C^{\prime}c^{\prime}r^{\prime}R\delta^{\prime}b^{\prime}$
form a pyramid from $q^{\prime}$ to $bb^{\prime}q$. ∎

######  Lemma 5.3.

Let $G$ be a 3PC-free graph and $A$, $B$, $C$, $X$, $Y$ and $Z$ be connected
disjoint subsets of $V(G)$ such that $X$, $Y$ and $Z$ are pairwise
anticomplete, $A$, $B$ and $C$ are pairwise anticomplete, and each of $A$, $B$
and $C$ sees each of $X$, $Y$ and $Z$. Suppose that no connected proper subset
of $A$ (resp. $B$ and $C$) sees each of $X$, $Y$ and $Z$. Then exactly one of
$A$, $B$ and $C$ contains at most 2 vertices.

###### Proof.

Follows directly from Lemma 5.2. ∎

We may now prove Theorem 1.4 that we restate.

See 1.4

###### Proof.

Suppose for a contradiction that a 3PC-free graph $G$ contains $K_{3,4}$ has
an induced minor. So, $G$ contains seven disjoint connected sets $X$, $Y$,
$Z$, $A$, $B$, $C$ and $D$ such that $X$, $Y$ and $Z$ are pairwise
anticomplete, $A$, $B$, $C$ and $D$ are pairwise anticomplete, and each of
$X$, $Y$ and $Z$ sees each of $A$, $B$, $C$ and $D$. We suppose that these
sets are chosen subject to the minimality of $A\cup B\cup C\cup D$. It follows
that no proper connected subset of $A$ (resp. $B$, $C$, $D$) sees $X$, $Y$ and
$Z$ (note that it is important here that no assumption is made about the
minimality of $X$, $Y$ and $Z$).

By Lemma 5.3 applied to $A$, $B$, $C$, $X$, $Y$ and $Z$, exactly one of $A$,
$B$ and $C$ has size at most 2, say $|A|\leq 2$, $|B|>2$ and $|C|>2$. Hence,
by Lemma 5.3 applied to $B$, $C$, $D$, $X$, $Y$ and $Z$, we have $|D|\leq 2$.
Hence, $A$, $B$, $D$, $X$, $Y$ and $Z$ contradict Lemma 5.3. ∎

##  6 Open questions

We need pyramids in Theorem 1.4 only for the sake of the precise description
of Lemma 5.2, see Fig. 6. We therefore wonder whether pyramids in Theorem 1.4
are really needed. More precisely, we do not know whether a (theta,
prism)-free graph that contains $K_{3,4}$ as an induced minor exists.

A _wheel_ is a graph made of a hole called the _rim_ together with a vertex
called the _center_ that has at least three neighbors on the rim. It is _even_
if the center has an even number of neighbors in the rim. It is well known
(and easy to check) that even-hole-free graphs contain no prisms, no thetas
and no even wheels as induced subgraphs, since each of these configurations
implies the presence of an even hole. Conversely, many theorems about even-
hole-free graphs suggest that (theta, prism, even wheel)-free graphs, that are
called _odd signable graphs_ , capture the essentials structural properties of
even-hole-free graphs, see [9, 10]. We believe that the following is true.

######  Conjecture 6.1.

If $G$ is an odd signable graph (in particular if $G$ is an even-hole-free
graph), then $G$ does not contain $K_{3,3}$ as an induced minor.

Observe that we do not know whether the even-hole-free layered wheels contain
$K_{3,3}$ as an induced minor. 6.1 would prove that they do not. We also
propose the following.

######  Conjecture 6.2.

If $G$ contains $K_{6}$ as a minor, then $G$ contains a triangle (as a
subgraph) or $G$ contains $K_{3,3}$ as an induced minor.

In [1], it is proved that triangle-free odd-signable graphs (in particular
(triangle, even-hole)-free graphs) have treewidth at most 5 and therefore do
not contain $K_{6}$ as a minor. So, provided that 6.1 is true, 6.2 is just a
more precise statement.

Here are some remarks about 6.2. It is false with a $K_{5}$ assumption instead
of a $K_{6}$ assumption, see Fig. 10 where an (even hole, triangle)-free graph
with a $K_{5}$ minor, first discovered in [2], is represented. It is false
with a “$K_{3,4}$ as an induced minor or triangle” conclusion because of the
layered wheels. Provided that 6.1 is true, it is false with a “$K_{3,3}$ as an
induced minor or 3PC as an induced subgraph” conclusion, or with a “$K_{3,3}$
as an induced minor or $K_{4}$ as subgraph” conclusion, because of the even-
hole-free layered wheels that are pyramid-free and $K_{4}$-free by Theorem
1.5. 6.2 would therefore provide a statement that is best possible in many
ways.

Figure 10: A $K_{5}$ minor in an (even hole, triangle)-free graph. To see even
hole-freeness first note that no even hole can contain a fat red edge.

It might be interesting to study the implications of a $K_{3,3}-e$ induced
minor in an even-hole free graph, where $K_{3,3}-e$ is the graph obtained from
$K_{3,3}$ by removing one edge. In Fig. 11, an even-hole-free graph that
contains $K_{3,3}-e$ as an induced minor is represented, and we observe that
this graph plays an important role in the structural study of even-hole-free
graphs, see [9]. In Fig. 12, another example of a graph that contains
$K_{3,3}-e$ as an induced minor is represented, and we observe that this graph
contains an even wheel.

Figure 11: A $K_{3,3}-e$ induced minor in an (even hole, triangle)-free graph
Figure 12: A $K_{3,3}-e$ induced minor in a graph without triangles and
without thetas.

More generally, we believe that studying implications between different
containment relations for different kinds of graphs might have more
applications. For instance, this approach is used in [4] to design a
polynomial time algorithm that decides whether an input graph contains
$K_{2,3}$ as an induced minor. We wonder what is the complexity of detecting
$K_{3,3}$ as an induced minor.

##  7 Acknowledgement

We are grateful to Marthe Bonamy, Sepehr Hajebi, Martin Milanič, Sophie Spirkl
and Kristina Vušković for helpful discussions.

Maria Chudnovsky is supported by NSF-EPSRC Grant DMS-2120644 and by AFOSR
grant FA9550-22-1-0083.

Tuukka Korhonen is supported by the Research Council of Norway via the project
BWCA (grant no. 314528).

Nicolas Trotignon is partially supported by the French National Research
Agency under research grant ANR DIGRAPHS ANR-19-CE48-0013-01 and the LABEX
MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program
Investissements d’Avenir (ANR-11-IDEX-0007) operated by the French National
Research Agency (ANR).

Sebastian Wiederrecht is supported by the Institute for Basic Science
(IBS-R029-C1).

Part of this research was conducted during two Graph Theory Workshops at the
McGill University Bellairs Research Institute, and we express our gratitude to
the institute and to the organizers of the workshop.

Part of this work was done when Nicolas Trotignon visited Maria Chudnovsky at
Princeton University with generous support of the H2020-MSCA-RISE project
CoSP- GA No. 823748.

## References

  * [1] Kathie Cameron, Murilo V. G. da Silva, Shenwei Huang, and Kristina Vušković.  Structure and algorithms for (cap, even hole)-free graphs.  Discrete Mathematics, 341(2):463–473, 2018.
  * [2] Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković.  Triangle-free graphs that are signable without even holes.  Journal of Graph Theory, 34(3):204–220, 2000.
  * [3] Clément Dallard, Martin Milanič, and Kenny Storgel.  Treewidth versus clique number. II. Tree-independence number.  Journal of Combinatorial Theory, Series B, 164:404–442, 2024\.
  * [4] Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, and Nicolas Trotignon.  Detecting $K_{2,3}$ as an induced minor.  arXiv:2402.08332, 2024.
  * [5] Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanic.  Computing tree decompositions with small independence number.  arXiv:2207.09993, 2022.
  * [6] Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, and Kenny Storgel Pawel Rzazewski.  Tree decompositions meet induced matchings: beyond max weight independent set.  arXiv:2402.15834, 2024.
  * [7] Neil Robertson and Paul Seymour.  Graph minors. V. Excluding a planar graph.  Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986\.
  * [8] Ni Luh Dewi Sintiari and Nicolas Trotignon.  (Theta, triangle)-free and (even hole, K${}_{\mbox{4}}$)-free graphs - Part 1: Layered wheels.  Journal of Graph Theory, 97(4):475–509, 2021.
  * [9] Kristina Vušković.  Even-hole-free graphs: a survey.  Applicable Analysis and Discrete Mathematics, 10(2):219–240, 2010\.
  * [10] Kristina Vušković.  The world of hereditary graph classes viewed through Truemper configurations.  In S. Gerke S.R. Blackburn and M. Wildon, editors, Surveys in Combinatorics, London Mathematical Society Lecture Note Series, volume 409, pages 265–325. Cambridge University Press, 2013.
  * [11] Nikola Yolov.  Minor-matching hypertree width.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 219–233. SIAM, 2018.