# Graphs with polynomially many minimal separators

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković

► To cite this version:

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, et al. Graphs with polynomially many minimal separators. Journal of Combinatorial Theory, Series B, 2022, 152, pp.248-280. 10.1016/j.jctb.2021.10.003. hal-04046989

HAL Id: hal-04046989

https://hal.science/hal-04046989v1

Submitted on 12 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Graphs with polynomially many minimal separators

Tara Abrishami¹

Maria Chudnovsky¹, *

Cemil Dibek¹, *

Stéphan Thomassé², †

Nicolas Trotignon², †

Kristina Vušković³, ‡

¹Princeton University, Princeton, NJ 08544

²Univ Lyon, EnsL, UCBL, CNRS, LIP, F-69342, LYON Cedex 07, France

³School of Computing, University of Leeds, UK

## Abstract

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

**Keywords:** Minimal separator, induced subgraph, theta, pyramid, prism, turtle.

## 1 Introduction

All graphs in this paper are finite and simple. Let $G = (V, E)$ be a graph. A set $C \subseteq V(G)$ is a minimal separator of $G$ if there are two distinct connected components $L, R$ of $G \setminus C$ such that $N(L) = N(R) = C$. A class $\mathcal{G}$ of graphs is said to have the polynomial separator property if there exists a constant $c$ such that every graph $G \in \mathcal{G}$ has at most $|V(G)|^c$ minimal separators.

The polynomial separator property has proven to be a desirable property due to its connection with potential maximal cliques and the maximum weight treewidth $k$ induced subgraph problem. Given a graph $G$, a nonnegative weight function on $V(G)$, and an integer $k$, the MAXIMUM WEIGHT TREEWIDTH $k$ INDUCED SUBGRAPH problem (MWTkISG) asks for a maximum-weight induced subgraph of $G$ of treewidth less than $k$. The MAXIMUM WEIGHT INDEPENDENT SET problem (MWIS), which asks for an independent set of $G$ with maximum weight, and the FEEDBACK VERTEX SET problem (FVS), which asks for a minimum-size set $X \subseteq V(G)$ such that $G \setminus X$ is a forest, are special cases of MWTkISG when $k=1$ and $k=2$, respectively. Recently, significant progress

<footnote>*Supported by NSF Grant DMS-1763817. This material is based upon work supported by, or in part by, the U.S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-16-1-0404.</footnote>

<footnote>†Partially supported by 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), and by the French National Research Agency under research grant ANR DIGRAPHS ANR-19-CE48-0013-01.</footnote>

<footnote>‡Partially supported by EPSRC grant EP/N0196660/1.</footnote>
was made regarding the complexity of MWIS in various graph classes using potential maximal cliques, originally developed by Bouchitté and Todinca [5,6]. A milestone result with this approach was obtained in 2014 by Lokshtanov, Vatshelle, and Villanger [11], who designed a polynomial-time algorithm for MWIS in $P_5$-free graphs. Later, using the same framework, Grzesik et al. [10] provided a polynomial-time algorithm for MWIS in $P_6$-free graphs. More recently, Abrishami et al. [1] extended the framework of potential maximal cliques to MWTkISG, and gave a polynomial-time algorithm for MWIS in graphs with no induced cycle of length five or greater, and for FVS in $P_5$-free graphs.

Given an integer $k$, it is known that MWTkISG can be solved in polynomial time for graphs that have polynomially many potential maximal cliques. Minimal separators are closely related to potential maximal cliques: it was shown in [6] that a graph has polynomially many potential maximal cliques if and only if it has polynomially many minimal separators. Consequently, MWTkISG is polynomial-time solvable in any class of graphs that has the polynomial separator property. It is therefore interesting to find classes of graphs where the number of minimal separators is bounded by a polynomial. We now define four graphs of interest to us (see also Figure 1):

* A **theta** is a graph $G$ consisting of two nonadjacent vertices $a, b$ and three paths $P_1, P_2, P_3$, each from $a$ to $b$, and otherwise vertex-disjoint, such that for $1 \le i < j \le 3$, $V(P_i) \cup V(P_j)$ induces a hole in $G$. In particular, each of $P_1, P_2, P_3$ has at least two edges. We say that $G$ is a theta between $a$ and $b$.

* A **pyramid** is a graph $G$ consisting of a vertex $a$ and a triangle $\{b_1, b_2, b_3\}$, and three paths $P_1, P_2, P_3$, such that: $P_i$ is between $a$ and $b_i$ for $i = 1, 2, 3$; for $1 \le i < j \le 3$, $P_i, P_j$ are vertex-disjoint except for $a$ and $V(P_i) \cup V(P_j)$ induces a hole in $G$; and in particular at most one of $P_1, P_2, P_3$ has only one edge. We say that $G$ is a pyramid from $a$ to $b_1b_2b_3$.

* A **prism** is a graph $G$ consisting of two vertex-disjoint triangles $\{a_1, a_2, a_3\}$, $\{b_1, b_2, b_3\}$, and three paths $P_1, P_2, P_3$, pairwise vertex-disjoint, where each $P_i$ has ends $a_i, b_i$, and for $1 \le i < j \le 3$, $V(P_i) \cup V(P_j)$ induces a hole in $G$. In particular, each of $P_1, P_2, P_3$ has at least one edge. We say $G$ is a prism between $a_1a_2a_3$ and $b_1b_2b_3$.

* A **turtle** is a graph $G$ consisting of two vertex-disjoint paths $P_1, P_2$ and two adjacent vertices $x, y \in V(G) \setminus (V(P_1) \cup V(P_2))$ such that for $i = 1, 2$, $P_i$ is from $a_i$ to $b_i$, $a_1$ is adjacent to $a_2$, $b_1$ is adjacent to $b_2$, $V(P_1) \cup V(P_2)$ induces a hole in $G$, $x$ has at least three neighbors in $P_1$ and no neighbors in $P_2$, and $y$ has at least three neighbors in $P_2$ and no neighbors in $P_1$. We say that $G$ is an *xy-turtle* where we call $x$ and $y$ the centers of $G$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Theta, pyramid, prism, and turtle</figcaption></figure>

Thetas, pyramids, prisms, and turtles are interesting because they provide examples of graphs with exponentially many minimal separators. Specifically, we have the following examples of graphs with exponentially many minimal separators (see also Figure 2).

* A $k$-theta is a graph $G$ with vertex set $V(G) = \{a, a_1, \dots, a_k, b, b_1, \dots, b_k\}$, and its set of edges consists of the pairs of the following form: $aa_i, bb_i$, and $a_ib_i$ for $1 \le i \le k$.
* A k-pyramid is a graph $G$ with vertex set $V(G) = \{a, a_1, \dots, a_k, b_1, \dots, b_k\}$, and its set of edges consists of the pairs of the following form: $aa_i$ and $a_ib_i$ for $1 \le i \le k$, and $b_ib_j$ for $1 \le i < j \le k$.

* A k-prism is a graph $G$ consisting of two cliques of size $k$ and a $k$-edge matching between them. More precisely, $V(G) = \{a_1, \dots, a_k, b_1, \dots, b_k\}$, each of the sets $\{a_1, \dots, a_k\}$ and $\{b_1, \dots, b_k\}$ is a clique, and $a_ib_i \in E(G)$ for $1 \le i \le k$, and there are no other edges in $G$.

* A k-turtle is a graph $G$ with two non-adjacent vertices $a, b \in V(G)$, two paths $P_1$ and $P_2$ from $a$ to $b$, vertex-disjoint except for $a$ and $b$, such that $V(P_1) \cup V(P_2)$ induces a hole $H$ in $G$. Also, for $1 \le i \le k$, $x_i, y_i \in V(G) \setminus V(H)$ such that $x_iy_i \in E(G)$, and $x_i$ has at least three neighbors in $P_1$ and no neighbors in $P_2$, and $y_i$ has at least three neighbors in $P_2$ and no neighbors in $P_1$. Furthermore, the neighbors of $x_i$'s in $P_1$ and the neighbors of $y_i$'s in $P_2$ are nested along $P_1$ and $P_2$ as shown in Figure 2. Specifically, the neighbors of $x_i$ in $P_1$ are between $a$ and the neighbors of $x_j$ in $P_1$ for all $1 \le i < j \le k$ and the neighbors of $y_i$ in $P_2$ are between $a$ and the neighbors of $y_j$ in $P_2$ for all $1 \le i < j \le k$.

<figure><img src="image_3.png" /><figcaption>Figure 2: k-theta, k-pyramid, k-prism, k-turtle, and k-ladder</figcaption></figure>

There are other examples of graphs with exponentially many minimal separators, such as the $k$-ladder shown in Figure 2. The $k$-ladder also contains a pyramid. In view of these examples, it is natural to ask whether excluding theta, pyramid, prism, and turtle in a graph is enough to obtain a polynomial number of minimal separators. This was conjectured in [7]:

**Conjecture 1.1** ([7]). There is a polynomial $P$ such that every graph $G$ that contains no theta, pyramid, prism, or turtle has at most $P(|V(G)|)$ minimal separators.

Here we prove Conjecture 1.1. Let $C$ be the class of (theta, pyramid, prism, turtle)-free graphs. We prove that the graphs in $C$ have polynomially many minimal separators. Note that in view of the results in [3], listing the minimal separators of a graph can be done in polynomial time in the size of the graph and the number of its minimal separators. Our proof that the graphs in $C$ have polynomially many minimal separators is algorithmic in nature, so we include a polynomial-time algorithm here to construct minimal separators of graphs in $C$ for completeness.

**Theorem 1.2.** Let $G \in C$. One can construct a set $S$ of size at most $|V(G)|^{18}$ in polynomial time such that $S$ is the set of all minimal separators of $G$.

Since the graphs in Figure 2 have exponentially many minimal separators, Theorem 1.2 is in a sense the best possible. Moreover, as explained above, given an integer $k$, Theorem 1.2 implies that MWTKISG can be solved in polynomial time for graphs in $C$. To be more precise, let $n, m, p, s$ denote, respectively, the number of vertices, the number of edges, the number of potential maximal
cliques, and the number of minimal separators of a graph $G$. It is proved in [3] that computing the minimal separators of $G$ can be done in time $O(n^3s)$. In [6], it is proved that $p \le O(ns^2 + ns + 1)$ and that the potential maximal cliques of $G$ can be listed in time $O(n^2ms^2)$. In [1], it is proved that given the list of potential maximal cliques of $G$ and an integer $k$, if $p$ is polynomial in $n$, then MWTkISG can be solved in time $n^{O(k)}$. By Theorem 1.2, for a graph $G \in \mathcal{C}$, we have $s \le O(n^{18})$, and so $p \le O(n^{37})$. Therefore, MWTkISG can be solved in time $n^{O(k)}$ in $\mathcal{C}$. Using results from [11], a better complexity for MWIS can be achieved. In [11], based on [9], it is proved that, given the list of potential maximal cliques, MWIS can be solved in time $O(n^5mp)$ in any graph. Therefore, MWIS can be solved in time $O(n^{44})$ in $\mathcal{C}$.

It is easy to observe that every prism, theta, and turtle contains an even hole. Therefore, the following is an immediate corollary of Theorem 1.2.

**Corollary 1.3.** *The class of (pyramid, even hole)-free graphs has the polynomial separator property.*

In [7], a better bound than the one given in Theorem 1.2 is achieved for (pyramid, even hole)-free graphs. In particular, Corollary 1.3 implies that MWTkISG and MWIS can be solved in (pyramid, even hole)-free graphs in polynomial time. A *cap* is a cycle of length at least five with exactly one chord and that chord creates a triangle with the cycle. Since every pyramid contains a cap, Corollary 1.3 generalizes a result of [8] where it is shown that MWIS can be solved in (cap, even hole)-free graphs in polynomial time.

We conjecture a stronger version of Theorem 1.2. For an integer $k \ge 3$, a graph $G$ is called a $k$- creature if it is given as follows: $V(G) = A \cup B \cup \{x_1, \dots, x_k\} \cup \{y_1, \dots, y_k\}$ such that

(i) $G[A]$ and $G[B]$ are connected, and $A$ is anticomplete to $B$,

(ii) for $i = 1, \dots, k$, $x_iy_i \in E(G)$, $x_i$ has a neighbor in $A$ and is anticomplete to $B$, $y_i$ has a neighbor in $B$ and is anticomplete to $A$, and

(iii) for $1 \le i, j \le k$ with $i \ne j$, $x_iy_j \notin E(G)$.

We observe that if $G$ is a $k$- creature, then $G$ contains a theta, pyramid, prism, or turtle; see Lemma 4.1 for details. We conjecture the following:

**Conjecture 1.4.** *There exists $f: \mathbb{N} \to \mathbb{N}$ such that if no induced subgraph of $G$ is a $k$- creature, then $G$ has at most $|V(G)|^{f(k)}$ minimal separators.*

Observe that even if Conjecture 1.4 is true, it does not provide a full characterization of classes with the polynomial separator property. For example, for every integer $k \ge 1$, let $T_k$ be a $k$- turtle such that the two paths $P_1$ and $P_2$ both have length $2^{2^k}$. Let $\mathcal{D}$ be the class of graphs formed by all induced subgraphs of the graphs $T_k$, $k \ge 1$. Observe that $T_k$ has $2^k$ minimal separators, which is polynomial in $|V(T_k)|$ since $|V(T_k)| \ge 2^{2^k}$, and so $\mathcal{D}$ has the polynomial separator property. However, $\mathcal{D}$ contains $k$-creatures with $k$ arbitrarily large.

We prove a weaker version of Conjecture 1.4. The proof can also be found in [7]. We say that a graph $G$ is an *immature $k$- creature* if $V(G)$ can be partitioned into two sets $X = \{x_1, \dots, x_k\}$ and $Y = \{y_1, \dots, y_k\}$ such that the only edges between $X$ and $Y$ are the edges $x_iy_i$ for $i = 1, \dots, k$. The edges among vertices of $X$ and vertices of $Y$ are unrestricted.

**Theorem 1.5.** Let $k \ge 1$ be an integer and let $G$ be a graph on $n$ vertices such that no induced subgraph of $G$ is an immature $k$- creature. Then, $G$ has at most $O(n^{2k-2})$ minimal separators that can be enumerated in time $O(n^{2k})$.

*Proof.* Let $a$ and $b$ be two non-adjacent vertices in $G$. Let $C$ be a minimal separator that separates $a$ and $b$. Let $A$ and $B$ be the components of $G \setminus C$ that contain $a$ and $b$, respectively. By the minimality
of $C$, every vertex in $C$ has a neighbor in $A$. It is therefore well-defined to consider an inclusion-wise minimal subset $X_A$ of $A$ such that $C \subseteq N(X_A)$. For every $x \in X_A$, there exists a vertex $c \in C$ such that $xc \in E(G)$ and no other vertex of $X_A$ is adjacent to $c$, for otherwise, $X_A \setminus \{x\}$ would contradict the minimality of $X_A$. It follows that $G[X_A \cup C]$ contains an immature $|X_A|$- creature, and so $|X_A| < k$. We define a similar set $X_B \subseteq B$, and we observe that $C = N(X_A) \cap N(X_B)$.

Now, the following algorithm enumerates all minimal separators of $G$: for every pair of sets $X_A, X_B$ with $|X_A|, |X_B| < k$, compute $C = N(X_A) \cap N(X_B)$ and check whether $C$ is a minimal separator. Since $\binom{n}{i} \le n^i$, we have $\binom{n}{0} + \cdots + \binom{n}{k-1} \le kn^{k-1}$. Therefore, the algorithm enumerates at most $O(n^{2k-2})$ minimal separators in time $O(n^{2k})$. $\square$

We note that there exist graphs in $C$ of arbitrarily large cliquewidth. In [2], examples of even-hole-free graphs of arbitrarily large cliquewidth are presented. Those graphs are also diamond-free and they have no clique separators. (A *diamond* is the graph with vertex set $\{a, b, c, d\}$ with all possible edges except $ab$.) However, they are not in $C$ because they contain pyramids. In [7], a procedure to obtain graphs in $C$ with unbounded cliquewidth by modifying graphs defined in [2] is explained in detail. Moreover, those graphs contain arbitrarily large immature $k$-creatures, and so the main result of the current paper is not a corollary of Theorem 1.5.

The rest of the paper is devoted to the proof of Theorem 1.2. In Section 2, we prove a useful theorem about star cutsets of graphs in $C$. In Section 3, we describe the structure of proper separators of graphs in $C$. In Section 4, we construct a list of all minimal separators of graphs in $C$ and prove Theorem 1.2.

## Definitions

Let $G = (V, E)$ be a graph. For $X \subseteq V(G)$, $G[X]$ denotes the induced subgraph of $G$ with vertex set $X$ and $G \setminus X$ denotes the induced subgraph of $G$ with vertex set $V(G) \setminus X$. We use induced subgraphs and their vertex sets interchangeably throughout the paper. We say that $G$ contains a graph $H$ if $G$ has an induced subgraph isomorphic to $H$. A graph $G$ is $H$-free if it does not contain $H$. When $\mathcal{H}$ is a set of graphs, we say that $G$ is $\mathcal{H}$-free if $G$ is $H$-free for every $H \in \mathcal{H}$. For a graph $H$, we say that a set $X \subseteq V(G)$ is an $H$ in $G$ if $G[X]$ is isomorphic to $H$.

Let $X \subseteq V(G)$. The *neighborhood* of $X$ in $G$, denoted by $N(X)$, is the set of all vertices in $V(G) \setminus X$ with a neighbor in $X$. The *closed neighborhood* of $X$ in $G$, denoted $N[X]$, is given by $N[X] = N(X) \cup X$. For $u \in V(G)$, $N(u) = N(\{u\})$ and $N[u] = N[\{u\}]$. For $u \in V(G) \setminus X$, $N_X(u) = N(u) \cap 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$, and $X$ is *anticomplete* to $Y$ if every vertex in $X$ is non-adjacent to every vertex in $Y$. Note that the empty set is complete and anticomplete to every $X \subseteq V(G)$. We say that a vertex $v$ is *complete* (anticomplete) to $X \subseteq V(G)$ if $\{v\}$ is complete (anticomplete) to $X$, and an edge $e = uv$ is *complete* (anticomplete) to $X$ if $\{u, v\}$ is complete (anticomplete) to $X$.

A *clique* in $G$ is a set of pairwise adjacent vertices, and an *independent set* is a set of pairwise non-adjacent vertices. A *triangle* is a clique of size three. A *path* in $G$ is an induced subgraph isomorphic to a graph $P$ with $k+1$ vertices $p_0, p_1, \dots, p_k$ and with $E(P) = \{p_i p_{i+1} : i \in \{0, \dots, k-1\}\}$. We write $P = p_0-p_1-\dots-p_k$ to denote a path with vertices $p_0, p_1, \dots, p_k$ in order. We say that $P$ is a path from $p_0$ to $p_k$. For a set $Y \subseteq V(G)$, if $P \setminus \{p_0, p_k\} \subseteq Y$, we say that $P$ is a path from $p_0$ to $p_k$ through $Y$. The *length* of a path $P$ is the number of edges in $P$. A path is *odd* if its length is odd, and *even* otherwise. If $a, b \in P$, we denote by $aPb$ the subpath of $P$ from $a$ to $b$. For a path $P$ with ends $a, b$, the *interior* of $P$, denoted $P^*$, is the set $V(P) \setminus \{a, b\}$. For an integer $k \ge 4$, a
hole of length $k$ in $G$ is an induced subgraph isomorphic to the $k$-vertex cycle $C_k$. A hole is odd if its length is odd, and even if its length is even.

If $X, Y, Z \subseteq V(G)$ are such that $X \cap Z = \emptyset$, we say that the path $P = p_0\dots p_k$ is a path from $X$ to $Z$ through $Y$ if $p_0 \in X$, $V(P) \setminus \{p_0\} \subseteq Y$, $V(P) \setminus \{p_k\}$ is anticomplete to $Z$, and $p_k$ has a neighbor in $Z$. When $X = \{p_0\}$, we say that $P$ is a path from $p_0$ to $Z$ through $Y$. Note that $P$ is disjoint from $Z$, and possibly $P = p_0$ (when $p_0$ is a vertex from $X$ with neighbors in $Z$). A path from $X$ to $Z$ through $Y$, when it exists, can be computed in time $O(|V(G)|^2)$ as follows. In $G[X \cup Y \cup Z]$, compute a shortest path $q_0\dots q_k$ from $X$ to $Z$ by a breadth-first search (that also terminates when no such path exists). Then, the path $q_0\dots q_{k-1}$ is from $X$ to $Z$ through $Y$. Observe that this algorithm detects when no path from $X$ to $Z$ through $Y$ exists (when no connected component of $G[X \cup Y \cup Z]$ contains vertices of both $X$ and $Z$).

## 2 Star cutsets in (theta, pyramid, prism, turtle)-free graphs

Let $G$ be a graph and $H$ a hole in $G$. A minor vertex for $H$ is a vertex $u \in G \setminus H$ such that $u$ has neighbors in $H$ and $N_H(u)$ is contained in a three-vertex path. A vertex $v \in G \setminus H$ is a major vertex for $H$ if $v$ has neighbors in $H$ and $v$ is not minor. A set $X \subseteq V(G)$ is a star cutset of $G$ if $G \setminus X$ is not connected, and there exists $x \in X$ such that $x$ is complete to $X \setminus x$. We call $x$ the center of the star cutset $X$. The goal of this section is to prove that major vertices for holes of graphs $G \in C$ are the centers of star cutsets of $G$. The following two lemmas describe major and minor vertices.

**Lemma 2.1.** Let $G \in C$. Every major vertex $u$ for a hole $H$ of $G$ has at least four neighbors in $H$ or has exactly three neighbors in $H$ that are pairwise non-adjacent.

*Proof.* Let $u$ be a major vertex for a hole $H$. Suppose $u$ has exactly two neighbors in $H$. The neighbors of $u$ are non-adjacent, because they are not contained in a three-vertex path. Thus, $H \cup \{u\}$ forms a theta between the neighbors of $u$ in $H$, a contradiction. If $u$ has exactly three neighbors in $H$, they are pairwise non-adjacent, otherwise $H \cup \{u\}$ forms a pyramid. $\square$

**Lemma 2.2.** Let $G \in C$. Then, every minor vertex $u$ for a hole $H$ of $G$ satisfies one of the following:

* $u$ has a unique neighbor in $H$ (we say that $u$ is a pendant of $H$)

* $u$ has two adjacent neighbors in $H$ (we say that $u$ is a cap of $H$)

* $u$ has three neighbors in $H$ which induce a path $xyz$ (we say that $u$ is a clone of $y$ in $H$)

*Proof.* Since $u$ is minor, $N_H(u)$ is contained in a three-vertex path. Therefore, the only possibility not listed above is that $u$ has two non-adjacent neighbors in $H$, in which case $H \cup \{u\}$ is a theta. $\square$

Suppose $H$ is a hole of a graph $G$ and $u$ is a clone of $y$ in $H$. We denote by $H_{u\setminus y}$ the hole of $G$ induced by $(V(H) \setminus \{y\}) \cup \{u\}$. Note that $y$ is a clone of $u$ in $H_{u\setminus y}$.

**Lemma 2.3.** Let $H$ be a hole in a graph $G \in C$, let $v$ be a major vertex for $H$, let $u$ be a clone of $y$ in $H$, and suppose $uv \in E(G)$. If $yv \notin E(G)$, then $u$ and $v$ have a common neighbor in $H$.

*Proof.* Let $N_H(u) = \{x, y, z\}$. Suppose $uv \in E(G)$ and $yv \notin E(G)$. Because $v$ is major, by Lemma 2.1, $v$ has at least three neighbors in $H$. If $v$ is anticomplete to $\{x, z\}$, then $H \cup \{u, v\}$ is a uv-turtle in $G$, a contradiction. Therefore, $v$ is adjacent to at least one of $x, z$, and so $u$ and $v$ have a common neighbor in $H$. $\square$

Let $u \in G \setminus H$ be a vertex with at least two neighbors in $H$. A $u$-sector is a path $P = u' \dots u''$ such that $P \subseteq H$, $u'$ and $u''$ are neighbors of $u$, and $P^*$ is anticomplete to $u$.
**Lemma 2.4.** Let $u$ and $v$ be two non-adjacent major vertices for a hole $H$ of a graph $G \in \mathcal{C}$. Let $P = u'...u''$ be a $u$-sector of $H$. Then one of the following holds:

(i) $P$ contains at most one neighbor of $v$, and if it has one, it is either $u'$ or $u''$,

(ii) $u'u'' \in E(G)$ and $v$ is adjacent to both $u'$ and $u''$,

(iii) $P$ contains at least 3 neighbors of $v$,

(iv) $H \cup \{u, v\}$ is a cube (see Figure 3).

<figure><img src="image_4.png" /><figcaption>Figure 3: The cube graph</figcaption></figure>

*Proof.* Let $R = H \setminus P$, let $x$ be the neighbor of $u'$ in $R$, and let $y$ be the neighbor of $u''$ in $R$. First, suppose that $P$ contains exactly two neighbors of $v$. We may assume that $u'u'' \notin E(G)$, otherwise outcome (ii) holds. Let the neighbors of $v$ in $P$ be given by $v', v''$. Then, $G$ contains a theta between $v'$ and $v''$ in $P \cup \{u, v\}$ unless $v'v'' \in E(G)$, so $v'v'' \in E(G)$. Since either $v' \neq u'$, $u''$ or $v'' \neq u'$, $u''$, we may assume that $v' \neq u'$, $u''$ and $v'$ is between $u'$ and $v''$ in $P$ (possibly $v'' = u''$). If both $u$ and $v$ have neighbors in $R^*$, then $G$ contains a pyramid from $u$ to $vv'v''$ via paths through $u'$, $u''$, and $R^*$, so at least one of $u, v$ has no neighbors in $R^*$. By Lemma 2.1, either $N_H(u) = \{x, u', u'', y\}$ or $N_H(v) = \{x, v', v'', y\}$. Since $v$ is major, $v$ has a neighbor in $R \setminus y$. Let $v'''$ be the neighbor of $v$ in $R \setminus y$ closest to $x$. If $ux \in E(G)$, then $G$ contains a prism from $uxu'$ to $v''vv'$ through the paths $u-u''-P-v'$, $u'-P-v'$, and $x-R-v'''-v$, so $ux \notin E(G)$ and thus $N_H(v) = \{x, v', v'', y\}$. Now, $G$ contains a pyramid from $u'$ to $vv'v''$ via the paths $u'-x-v$, $u'-u-u''-P-v''$, and $u'-P-v'$, a contradiction.

Now, suppose $P$ contains exactly one neighbor $v'$ of $v$. We may assume that $v' \neq u'$, $u''$, otherwise outcome (i) holds. If $u$ and $v$ both have neighbors in $R^*$, then $G$ contains a theta between $u$ and $v'$ through $u'$, $u''$, and $R^* \cup \{v\}$, so at least one of $u, v$ has no neighbors in $R^*$. By Lemma 2.1, either $N_H(u) = \{x, u', u'', y\}$ or $N_H(v) = \{x, v', y\}$. Since $v$ is major, $v$ has a neighbor in $R \setminus y$. Let $v''$ be the neighbor of $v$ in $R$ closest to $x$. If $ux \in E(G)$, then $G$ contains a pyramid from $v'$ to $u'ux$ through the paths $v'-P-u'$, $v'-v-v''-R-x$, and $v'-P-u''-u$, so $ux \notin E(G)$. By symmetry, $uy \notin E(G)$. It follows that $N_H(v) = \{x, v', y\}$. Because $u$ is major, $u$ has a neighbor in $R^*$. Let $u'''$ be the neighbor of $u$ in $R^*$ closest to $y$. Then $G$ contains a theta between $u$ and $y$ through the paths $u-u''-y$, $u-u'-x-v-y$, and $u-u'''-R-y$, unless $xu''' \in E(G)$. Similarly, $G$ contains a theta between $u$ and $x$ unless $yu''' \in E(G)$. If $u'v' \notin E(G)$, then $G$ contains a theta between $u'$ and $v'$ through the paths $u'-P-v'$, $u'-x-v-v'$, and $u'-u-u''-P-v'$, so $v'u' \in E(G)$. Similarly, $v'u'' \in E(G)$. Now, $H \cup \{u, v\}$ is a cube, and so outcome (iv) holds. This completes the proof. $\square$

Let $H$ be a hole in a graph $G$ and let $u, v \in V(G) \setminus V(H)$. We say that $u$ and $v$ are *nested* with respect to $H$ if there exist distinct $a, b \in V(H)$ such that one *ab-path* of $H$ contains all the neighbors of $u$ and the other *ab-path* of $H$ contains all the neighbors of $v$. Note that pendants, caps, and vertices of $G \setminus H$ with no neighbor in $H$ are nested with all other vertices of $G \setminus H$. The vertices $u$ and $v$ are *strictly nested* with respect to $H$ if $u$ and $v$ are nested with respect to $H$ and $N_H(u) \cap N_H(v) = \emptyset$.

**Lemma 2.5.** Let $H$ be a hole in a graph $G \in \mathcal{C}$, let $u$ and $v$ be major or clones for $H$ such that $u$ and $v$ are nested, and suppose $uv \in E(G)$. Then, $u$ and $v$ have a common neighbor in $H$.
*Proof.* Since $u$ and $v$ are major or clones, $u$ and $v$ have at least three neighbors in $H$. If $u$ and $v$ have no common neighbors in $H$, then $H \cup \{u, v\}$ is a uv-turtle in $G$, a contradiction. $\square$

Two vertices $u$ and $v$ not in $H$ that are not nested with respect to $H$ are said to cross. The following lemmas characterize the behavior of vertices that cross.

**Lemma 2.6.** Let $H$ be a hole in a graph $G \in \mathcal{C}$ and let $u$ and $v$ be two vertices not in $H$ that cross. Then, one of the following holds:

(i) $H$ contains four distinct vertices $u', v', u'', v''$ that appear in this order along $H$ such that $u', u'' \in N_H(u)$ and $v', v'' \in N_H(v)$,

(ii) $N_H(u) = N_H(v)$, $N_H(u)$ is an independent set, $|N_H(u)| = 3$, and $uv \in E(G)$,

(iii) $N_H(u) = N_H(v)$, both $u$ and $v$ are clones in $H$, and $uv \in E(G)$.

*Proof.* Since $u$ and $v$ are not nested, $u$ and $v$ are major or clones for $H$. Suppose $u$ and $v$ are both clones. Since $u$ and $v$ cross, it follows that either $u$ and $v$ are clones of adjacent vertices, so outcome (i) holds, or $u$ and $v$ are clones of the same vertex. Let $u$ and $v$ both be clones of $y$ and let $N_H(u) = N_H(v) = \{x, y, z\}$. Then, $G$ contains a theta between $x$ and $z$ in $H_{u \setminus y} \cup \{v\}$ unless $uv \in E(G)$, so outcome (iii) holds. Now, suppose $u$ is a clone of $y$ and $v$ is major. Because $u$ and $v$ cross, $vy \in E(G)$, and because $v$ is major, $v$ has at least one neighbor in $V(H) \setminus N_H(u)$. Therefore, outcome (i) holds. Finally, suppose $u$ and $v$ are both major. Assume that $u$ has a neighbor $x$ in $H$ such that $vx \notin E(G)$. Then, $x$ is contained in a $v$-sector $P = v'...v''$ of $H$. Because $u$ and $v$ cross, $u$ has a neighbor in $H \setminus P$, so outcome (i) holds. Therefore, we may assume that $N_H(u) = N_H(v)$. If $|N_H(u)| > 3$, outcome (i) holds, so $|N_H(u)| = 3$. Because $u$ is major and $|N_H(u)| = 3$, it follows from Lemma 2.1 that $N_H(u)$ is an independent set. Let $N_H(u) = \{x, y, z\}$. Then, $G$ contains a theta between $x$ and $y$ in $(H \setminus \{z\}) \cup \{u, v\}$ unless $uv \in E(G)$, so outcome (ii) holds. $\square$

Let $H = h_1-h_2-\dots-h_k-h_1$ be a hole in a graph $G \in \mathcal{C}$ and let $u, v \in V(G) \setminus V(H)$ be two non-adjacent major vertices for $H$. The following lemma shows that if $u$ and $v$ cross, then $H \cup \{u, v\}$ is a major non-adjacent cross (MNC) configuration. We describe MNC configurations as follows (see also Figure 4).

* MNC configuration (1): $k=4$, and $\{u, v\}$ are complete to $H$.

* MNC configuration (2): $k=5$, and $\{u, v\}$ are complete to $H$.

* MNC configuration (3): $k=6$, $N_H(u) = \{h_1, h_3, h_5\}$, and $N_H(v) = \{h_2, h_4, h_6\}$.

* MNC configuration (4): $\{u, v\}$ is complete to $\{h_1, h_2, h_3, h_4\}$, $v$ has no other neighbors in $H$, and $u$ has at least one other neighbor in $H$.

Let $3 < i < k-1$. Let $H_1$ be the path from $h_1$ to $h_{i+1}$ in $H \setminus \{h_2\}$ and let $H_2$ be the path from $h_2$ to $h_i$ in $H \setminus \{h_1\}$.

* MNC configuration (5): $\{u, v\}$ is complete to $\{h_1, h_2, h_i, h_{i+1}\}$, $u$ and $v$ both have other neighbors in $H$, $N_H(u) \subseteq H_1 \cup \{h_2, h_i\}$, and $N_H(v) \subseteq H_2 \cup \{h_1, h_{i+1}\}$.

* MNC configuration (6): $\{u, v\}$ is complete to $\{h_1, h_2, h_i, h_{i+1}\}$, $v$ has no other neighbors in $H$, and $u$ has neighbors both in $H_1^*$ and $H_2^*$.

* MNC configuration (7): $\{u, v\}$ is complete to $\{h_1, h_2, h_i\}$, $u$ and $v$ both have other neighbors in $H$, $N_H(u) \subseteq H_1 \cup \{h_2, h_i\}$, and $N_H(v) \subseteq H_2 \cup \{h_1\}$.

* MNC configuration (8): $\{u, v\}$ is complete to $\{h_1, h_2\}$, $u$ and $v$ both have other neighbors in $H$, $N_H(u) \subseteq H_1 \cup \{h_2\}$, and $N_H(v) \subseteq H_2 \cup \{h_1\}$.
<figure><img src="image_5.png" /><figcaption>Figure 4: MNC configurations (dashed lines represent possible edges)</figcaption></figure>

**Lemma 2.7.** Let $H$ be a hole in a graph $G \in \mathcal{C}$ and suppose that $u$ and $v$ are two major vertices for $H$. If $uv \in E(G)$, then either $u$ and $v$ cross or $u$ and $v$ have a common neighbor in $H$. If $u$ and $v$ cross, then either $uv \in E(G)$ or $G$ contains an MNC configuration.

*Proof.* The first statement follows from Lemma 2.5. It remains to prove the second statement. Assume that $u$ and $v$ cross and $uv \notin E(G)$. Let $H = h_1\dots h_k h_1^{-1}$.

(1) No three common neighbors of $u$ and $v$ in $H$ form an independent set.

If $u$ and $v$ have three common neighbors $x, y, z \in V(H)$ such that $\{x, y, z\}$ is an independent set, then $\{u, v, x, y, z\}$ is a theta in $G$ between $u$ and $v$, a contradiction. This proves (1).

(2) Suppose there exist $i, j \in \{1, \dots, k\}$ with $j > i$ such that $h_i h_j \notin E(G)$, $\{u, v\}$ is complete to $\{h_i, h_j\}$, and there are no common neighbors of $u$ and $v$ in $P = h_{j+1}-h_{j+2}-\dots-h_{i-1}$. Then, $u$ and $v$ do not both have neighbors in $P$.

If both $u$ and $v$ have neighbors in $P^*$, then $G$ contains a theta between $u$ and $v$, through $h_i$, $h_j$, and $P^*$. Therefore, we may assume that $h_{j+1}$ is adjacent to $u$. If $v$ has a neighbor in $P^*$, let $v'$ be the neighbor of $v$ in $P^*$ closest to $h_{j+2}$. Then, $G$ contains a pyramid from $v$ to $uh_j h_{j+1}$ through the paths $v-h_j$, $v-h_i-u$, and $v-v'-P-h_{j+1}$, a contradiction. Therefore, we may assume that $N_P(v) = \{h_{i-1}\}$. Then, $G$ contains a prism from $uh_j h_{j+1}$ to $h_i v h_{i-1}$ through the paths $u-h_i$, $h_j-v$, and $h_{j+1}-P-h_{i-1}$, a contradiction. This proves (2).

Let $N = N_H(u) \cap N_H(v)$.

(3) We may assume that $R = H[N]$ is a subpath of $H$ of length at most one.

If $N = V(H)$, then by (1), $H \cup \{u, v\}$ is MNC configuration (1) or (2). So, we may assume that $N \neq V(H)$. Suppose first that $R$ is a subpath of $H$ of length greater than one. By (1), $R$ is of length at most three. If it is of length two, then by (2), one of $u, v$ is a clone, a contradiction. Suppose $R$ is of length three, say $R = h_i h_{i+1} h_{i+2} h_{i+3}$. Then, by (2), at most one of $u, v$ has a neighbor in $H \setminus R$. If one of $u, v$ has a neighbor in $H \setminus R$, then $H \cup \{u, v\}$ is MNC configuration (4), otherwise $G$ contains a theta between $h_i$ and $h_{i+3}$ through $u, v$, and $H \setminus R$.

Next, suppose that $R$ is not a subpath of $H$. By (1), it follows that $R$ is the disjoint union of two subpaths $Q_1, Q_2$ of $H$ of length at most one. Let $Q_1 = h_1\dots h_i$ and $Q_2 = h_{i+1}\dots h_{i+2}$. where $k > t \ge s \ge i+2$, $i \le 2$, and $t \le s+1$. By (2), we may assume that $v$ has no neighbors in $h_{t+1}-h_{t+2}-\dots-h_k$, and that not both $u$ and $v$ have neighbors in $h_{i+1}-\dots-h_{s-1}$. Since $u$ and $v$ cross, at least one of $Q_1$ and $Q_2$ has length one, so we may assume $i=2$.
Note that at least one of $u$ and $v$ has a neighbor in $h_{t+1}-\dots-h_k$, otherwise $G$ contains a theta between $h_1$ and $h_t$ through $H \setminus \{h_2, h_s\}$, $u$, and $v$. Similarly, at least one of $u$ and $v$ has a neighbor in $h_{i+1}-\dots-h_{s-1}$. It follows that if $t = s+1$, then $G$ contains MNC configuration (5) or (6), and if $t = s$, then $G$ contains MNC configuration (7). This proves (3).

(4) We may assume that $N = \emptyset$.

We may assume that $H \cup \{u, v\}$ is not a cube (MNC configuration (3)) or MNC configuration (8). By (3), we may assume that $R = h_1$ or $R = h_1h_2$. Let $i=1$ if $R = h_1$, and $i=2$ if $R = h_1h_2$. We claim that we may assume that $H \setminus R$ contains three distinct vertices $u', v', u''$ such that $h_i, u', v', u'', h_1$ appear in this order and $u', u'' \in N_H(u)$, $v' \in N_H(v)$. If $i=2$, then this follows from the assumption that $G$ does not contain MNC configuration (8), and if $i=1$, it follows from Lemma 2.6. Let $u', v', u''$ be chosen such that the path from $u'$ to $u''$ in $H \setminus R$ is a $u$-sector. Let $H_a$ be the path from $h_i$ to $v'$ in $H \setminus \{u''\}$, let $H_b$ be the path from $h_1$ to $v'$ in $H \setminus \{u'\}$, and let $H_u$ be the path from $u'$ to $u''$ in $H \setminus R$. Since $H_a$ contains a $v$-sector that contains $u'$, it follows from Lemma 2.4 that there are at least three neighbors of $u$ in $H_a$, and so there at least two neighbors of $u$ in $H_a^*$. Since $H_u$ is a $u$-sector, there is a neighbor of $u$ in $H_a^*$ between $h_i$ and $u'$. Similarly, there are at least three neighbors of $u$ in $H_b$, and so at least two neighbors of $u$ in $H_b^*$. Since $H_u$ is a $u$-sector, there is a neighbor of $u$ in $H_b^*$ between $h_1$ and $u''$. Finally, since $H_u$ is a $u$-sector that contains $v'$, there are at least three neighbors of $v$ in $H_u^*$. Let $v_1$ be the neighbor of $v$ in $H_u^*$ closest to $u'$, and let $v_2$ be the neighbor of $v$ in $H_u^*$ closest to $u''$. Then, $G$ contains a theta from $u$ to $v$, through $u-h_1-v$, $u-u'-H_u-v_1-v$, and $u-u''-H_u-v_2-v$. This proves (4).

It follows from Lemma 2.6 and (4) that $H$ contains four distinct vertices $u', v', u'', v''$ that appear in that order along $H$, such that $u', u'' \in N_H(u)$ and $v', v'' \in N_H(v)$. By (4), $u$ and $v$ have no common neighbors in $H$, and so every neighbor of $u$ in $H$ is in the interior of a $v$-sector and every neighbor of $v$ in $H$ is in the interior of a $u$-sector. Let $u', v', u'', v''$ be chosen so that $P = u' \dots u''$ is a $u$-sector and $Q = v' \dots v''$ is a $v$-sector. We may assume that $H \cup \{u, v\}$ is not a cube (i.e. MNC configuration (3)). Because $v'$ is in $P^*$, it follows from Lemma 2.4 that there are at least three neighbors of $v$ in $P^*$. Since there are no neighbors of $v$ in $Q^*$, we may assume that $v_1, v_2$ are neighbors of $v$ in $P^*$ between $u'$ and $v'$ in that order. Similarly, there are at least three neighbors of $u$ in $Q^*$. Since there are no neighbors of $u$ in $P^*$, we may assume that $u_1, u_2$ are neighbors of $u$ in $Q^*$ between $u''$ and $v''$ in that order. Finally, because $v''$ is in the interior of a $u$-sector and $Q = v' \dots v''$ is a $v$-sector, there is another neighbor of $v$ between $v''$ and $u'$. Then, $G$ contains a theta between $u$ and $v$ through the paths $u-u_2-Q-v''-v$, $u-u''-Q-v'-v$, and $u-u'-P-v_1-v$, a contradiction. $\square$

**Lemma 2.8.** Let $H$ be a hole of length greater than six in a graph $G \in \mathcal{C}$ and suppose $u$ and $v$ are non-adjacent vertices of $G \setminus H$ that cross. Then, $H$ contains a $\{u, v\}$-complete edge.

*Proof.* Since $u$ and $v$ cross, $u$ and $v$ are major or clones. If $u$ and $v$ are both major, it follows from Lemma 2.7 that $H \cup \{u, v\}$ is MNC configuration (4), (5), (6), (7), or (8), so $H$ contains a $\{u, v\}$-complete edge. Now, suppose $u$ is a clone of $y$ in $H$ and $N_H(u) = \{x, y, z\}$. Because $u$ and $v$ cross, it follows that $vy \in E(G)$. We may assume that $xv, zv \notin E(G)$ since otherwise $H$ contains a $\{u, v\}$-complete edge. Note that $x-u-z$ is a subpath of $H_{u\setminus y}$ that contains all the neighbors of $y$ in $H_{u\setminus y}$ and no neighbors of $v$. If $v$ has at least three neighbors in $H_{u\setminus y}$, then $G$ contains a $vy$-turtle. So $v$ has two neighbors in $H_{u\setminus y}$, say $v_1$ and $v_2$, and hence three neighbors in $H$. By Lemma 2.1 applied to $H$ and $v$, $v_1v_2 \notin E(G)$. But then $H_{u\setminus y}$ and $v$ form a theta, a contradiction. $\square$

The following lemma describes the behavior of paths whose endpoints are nested with respect to $H$ and whose internal vertices are anticomplete to $H$.
**Lemma 2.9.** Let $H$ be a hole in a graph $G \in \mathcal{C}$ and let $P = u\dots v$ be a path of length at least 1, vertex-disjoint from $H$, such that $u$ and $v$ have neighbors in $H$ and are nested with respect to $H$, and no internal vertex of $P$ has a neighbor in $H$. Then, $u$ and $v$ have a common neighbor in $H$, or $u$ and $v$ are both pendants of $H$ with adjacent neighbors in $H$. In particular, if $u$ and $v$ are strictly nested with respect to $H$, then $u$ and $v$ are both pendants of $H$ with adjacent neighbors in $H$.

*Proof.* We may assume that $u$ and $v$ do not have a common neighbor in $H$. If $u$ (resp. $v$) has at least two neighbors in $H$, then let $u'$ and $u''$ (resp. $v'$ and $v''$) be the endpoints of the $u$-sector (resp. $v$-sector) that contains all neighbors of $v$ (resp. $u$) in $H$, and otherwise let $u' = u''$ (resp. $v' = v''$) be its unique neighbor in $H$. Without loss of generality, $u', v', v'', u''$ appear in this order along $H$. If $u$ and $v$ both have two non-adjacent neighbors in $H$ (and so by Lemma 2.1 and Lemma 2.2, $u$ and $v$ each has at least three neighbors in $H$) and $uv \in E(G)$, then $H \cup \{u, v\}$ is a $uv$-turtle, a contradiction. If $u$ and $v$ both have two non-adjacent neighbors in $H$ and $uv \notin E(G)$, then $G$ contains a theta between $u$ and $v$ through the paths $u-u'-H \setminus \{u''\}, v''\}-v'-v$, $u-u''-H \setminus \{u'\}, v'\}-v''-v$, and $u-P-v$, a contradiction. If $u$ has two non-adjacent neighbors in $H$ and $v$ is a cap, then $G$ contains a pyramid from $u$ to $vv'v''$ through $u-P-v$, $u-u'-H \setminus \{u''\}-v'$, and $u-u''-H \setminus \{u'\}-v''$, a contradiction. If $u$ has two non-adjacent neighbors in $H$ and $v$ is a pendant, then $G$ contains a theta between $u$ and $v'$ through $u-u'-H \setminus \{u''\}-v$, $u-P-v-v'$, and $u-u''-H \setminus \{u'\}-v'$, a contradiction. Thus, neither $u$ nor $v$ has two non-adjacent neighbors in $H$.

If $u$ and $v$ are both caps, then $H \cup P$ is a prism between $uu'u''$ and $vv'v''$, a contradiction. If $u$ is a cap and $v$ is a pendant, then $H \cup P$ is a pyramid from $v'$ to $uu'u''$. If $u$ and $v$ are both pendants, then $H \cup P$ is a theta between $u'$ and $v'$, unless $u'v'$ is an edge. $\square$

Let $G \in \mathcal{C}$, let $H$ be a hole in $G$, and let $w$ be a major vertex for $H$. A path $N \subseteq H$ is an *extended neighborhood* of $w$ in $H$ if there exists a $w$-sector $Q = x\dots y$ such that $N = Q \cup (\{x', y'\} \cap N_H(w))$, where $x'$ and $y'$ are the neighbors of $x$ and $y$ in $H \setminus Q$, respectively. Two vertices $a, b \in H$ are *distant* in $H$ with respect to $w$ if $a, b$ are not contained in an extended neighborhood of $w$ in $H$. Note that if a vertex $v \in H$ is not adjacent to $w$, then $v$ is in exactly one extended neighborhood of $w$ in $H$.

Suppose $H$ is a hole in a graph $G \in \mathcal{C}$ and $u$ is a major vertex for $H$. The vertex $u$ is called a *hub* if $N_H(u) = \{x, y, z, w\}$ where the vertices $x, y, z, w$ appear in that order in $H$, $xy, zw \in E(G)$, and $xw, zy \notin E(G)$.

**Lemma 2.10.** Let $G \in \mathcal{C}$, let $H$ be a hole in $G$ of length greater than six, and let $w$ be a major vertex for $H$. Let $p \in V(G) \setminus V(H)$ be such that $pw \notin E(G)$. Then, either $N_H(p)$ is contained in an extended neighborhood of $w$ in $H$ or $H \cup \{p, w\}$ is MNC configuration (6).

*Proof.* If $p$ and $w$ are nested, then $N_H(p)$ is contained in an extended neighborhood of $w$ in $H$, so we may assume that $p$ and $w$ cross. It follows that $p$ is either a clone or a major vertex for $H$. If $p$ is a clone, then it follows from Lemma 2.8 that $N_H(p)$ is contained in an extended neighborhood of $w$. Now, suppose $p$ is major. By Lemma 2.7, it follows that $H \cup \{w, p\}$ is MNC configuration (4), (5), (6), (7), or (8), and therefore either $N_H(p)$ is contained in an extended neighborhood of $w$ in $H$, or $H \cup \{w, p\}$ is MNC configuration (6). $\square$

Let $G \in \mathcal{C}$, let $H$ be a hole in $G$, and let $w$ be a major vertex for $H$. We say that a path $P = p_1\dots p_k$ is $(H, w)$-significant if there exist $a, b \in V(H)$ such that $a \in N_H(p_1) \setminus N_H(w)$, $b \in N_H(p_k)$, and $a$ and $b$ are distant in $H$ with respect to $w$.

**Lemma 2.11.** Let $G \in \mathcal{C}$, let $H$ be a hole in $G$ of length greater than six, and let $w$ be a major vertex for $H$ such that either $w$ is not a hub or every major vertex for $H$ is a hub. Let $P = p_1\dots p_k$ be $(H, w)$-significant with $a, b \in V(H)$ as in the definition of a significant path. Let $Q = x\dots y$
be the w-sector containing a. Suppose w is anticomplete to {$p_1, p_k$} and $p_1, p_k \notin H$. Then, $p_k$ is
anticomplete to $Q^*$.

**Proof.** Since $p_1$ has a neighbor in the interior of a w-sector, $H \cup \{w, p_1\}$ is not MNC configuration (6). By Lemma 2.10, it follows that $N_H(p_1)$ is contained in an extended neighborhood of $w$. Note that, by definition, a w-sector of length greater than one is contained in exactly one extended neighborhood of $w$. Let $\bar{Q}$ be the extended neighborhood of $w$ containing $Q$, and suppose for sake of contradiction that $p_k$ has a neighbor in $Q^*$. Since $p_k$ has a neighbor in the interior of a w-sector, $H \cup \{w, p_k\}$ is not MNC configuration (6), so by Lemma 2.10, $N_H(p_k)$ is contained in an extended neighborhood of $w$. Because $p_1$ has a neighbor $a$ in $Q^*$, it follows that $N_H(p_1) \subseteq \bar{Q}$. Similarly, because $p_k$ has a neighbor in $Q^*$, it follows that $N_H(p_k) \subseteq \bar{Q}$. Then, $a$ and $b$ are contained in an extended neighborhood of $w$, a contradiction. $\square$

**Lemma 2.12.** Let $G \in \mathcal{C}$, let $H$ be a hole in $G$ of length greater than six, and let $w$ be a major vertex for $H$ such that either $w$ is not a hub or every major vertex for $H$ is a hub. Let $P = p_1 - \dots - p_k$ be $(H, w)$-significant with $a, b \in V(H)$ as in the definition of a significant path. Assume that $P^*$ is anticomplete to $H$, $w$ is anticomplete to $\{p_1, p_k\}$, and $p_1, p_k \notin H$. Then, $p_1$ and $p_k$ have a common neighbor in $H$.

**Proof.** Assume for a contradiction that $p_1$ and $p_k$ do not have a common neighbor in $H$. In particular, $p_1 \neq p_k$. Suppose that $p_1$ and $p_k$ are nested. Then, they are strictly nested. By Lemma 2.9, $p_1$ and $p_k$ are pendants of $H$ with adjacent neighbors in $H$. It follows that $a$ and $b$ are adjacent, contradicting that $a$ and $b$ are distant in $H$ with respect to $w$. Therefore, $p_1$ and $p_k$ cross, and hence they are clone or major for $H$. Since $p_1$ and $p_k$ cross and they do not have a common neighbor in $H$, it follows that $p_1$ and $p_k$ are both major. If $w$ and $p_1$ are nested, then by Lemma 2.11, $p_1$ and $p_k$ are nested. Hence, $w$ and $p_1$ cross. By Lemma 2.8, $H$ contains a $\{w, p_1\}$-complete edge. Let $Q = x \dots y$ be the w-sector containing $a$. Let $x'$ and $y'$ be the neighbors of $x$ and $y$ in $H \setminus Q$, respectively. Since $p_1$ has a neighbor in the interior of a w-sector, $H \cup \{w, p_1\}$ is not MNC configuration (6). By Lemma 2.10, it follows that $N_H(p_1) \subseteq Q \cup (\{x', y'\} \cap N_H(w))$, and by Lemma 2.11, it follows that $N_H(p_k) \subseteq H \setminus Q^*$. Up to symmetry, suppose $\{w, p_1\}$ is complete to $\{x, x'\}$. Since $p_1$ and $p_k$ cross and $p_1$ and $p_k$ have no common neighbor in $H$, $p_1y', p_ky \in E(G)$ and $p_1y, p_ky' \notin E(G)$. Also, $p_k$ has another neighbor in $H \setminus (Q \cup \{x', y'\})$ and in particular, $x'y' \notin E(G)$. Because $p_1y' \in E(G)$, it follows that $wy' \in E(G)$. Let $p'$ be the neighbor of $p_1$ in $Q^*$ closest to $y$. Then, $G$ contains a pyramid from $p_1$ to $wyy'$ through $p_1-y', p_1-x'-w$, and $p_1-p'-Q-y$, a contradiction. $\square$

We can now prove the main result of this section.

**Theorem 2.13.** Let $G \in \mathcal{C}$, let $H$ be a hole in $G$ of length greater than six, and let $w$ be a major vertex for $H$ such that either $w$ is not a hub or every major vertex for $H$ is a hub. Let $P = p_1 - \dots - p_k$ be $(H, w)$-significant. Then, $w$ has a neighbor in $P$.

**Proof.** We may assume that no subpath of $P$ is $(H, w)$-significant. Suppose that $w$ is anticomplete to $P$. Let $a, b \in V(H)$ be as in the definition of a significant path, i.e., $a \in N_H(p_1) \setminus N_H(w)$, $b \in N_H(p_k)$, and $a$ and $b$ are distant in $H$ with respect to $w$. Let $Q = x \dots y$ be the w-sector containing $a$, and let $x'$ and $y'$ be the neighbors of $x$ and $y$ in $H \setminus Q$, respectively. Possibly $x' = b$ (resp. $y' = b$), in which case $w$ is not adjacent to $x'$ (resp. $y'$) since $a$ and $b$ are distant in $H$ with respect to $w$.

Suppose that $k = 1$. Since $a$ and $b$ are distant in $H$, $p_1 \notin V(H)$. So, by Lemma 2.11 and Lemma 2.2, $p_1$ is major but not a hub. It follows that $w$ is not a hub. But this contradicts Lemma 2.10. Therefore, $k > 1$.
(1) *P* is disjoint from *H*.

Suppose that $p_i \in P$ is in $H$. Since no subpath of $P$ is $(H, w)$-significant, it follows that $a$ and $p_i$ are not distant in $H$ with respect to $w$. Then, either $p_i \in Q^*$ or $p_i w \in E(G)$. Since $w$ is anticomplete to $P$, $p_i w \notin E(G)$, so $p_i \in Q^*$. Note that since $p_i \in Q^*$ and $b \notin Q$, $i < n$. Then, $p_{i+1}...-p_k$ is $(H, w)$-significant, a contradiction. This proves (1).

(2) Either $N_H(P^*) \subseteq \{x\} \cup (N_H(w) \cap \{x'\})$ or $N_H(P^*) \subseteq \{y\} \cup (N_H(w) \cap \{y'\})$.

No vertex $p_i \in P \setminus \{p_1\}$ can have a neighbor in $Q^*$, otherwise $p_i...-p_k$ is $(H, w)$-significant. Similarly, no vertex $p_i \in P \setminus \{p_k\}$ can be adjacent to a vertex $v$ such that $a$ and $v$ are distant in $H$ with respect to $w$, otherwise $p_1...-p_i$ is $(H, w)$-significant. It follows that $N_H(P^*) \subseteq \{x, y\} \cup (\{x', y'\} \cap N_H(w))$.

Consider a vertex $p_i \in P^*$ such that $p_i$ has neighbors in $H$. Suppose $p_i$ is not a cap or a pendant, so by Lemmas 2.1 and 2.2, $N_H(p_i) = \{x, y, x', y'\}$. Then, since $Q = x...a...y$ is a $w$-sector and $p_i x, p_i y \in E(G)$, by Lemma 2.4 it follows that $xy \in E(G)$, a contradiction. Therefore, $p_i$ is a cap or a pendant for every $p_i \in P^*$ that has a neighbor in $H$.

Now, assume that there exist $p_i, p_j \in P^*$ such that $N_H(p_i) \subseteq \{x\} \cup (N_H(w) \cap \{x'\})$ and $N_H(p_j) \subseteq \{y\} \cup (N_H(w) \cap \{y'\})$. Consider the shortest path $R$ from $\{x\} \cup (N_H(w) \cap \{x'\})$ to $\{y\} \cup (N_H(w) \cap \{y'\})$ through $P^*$. By Lemma 2.9, the endpoints of $R^*$ have a common neighbor in $H$ or are pendants of $H$ with adjacent neighbors, a contradiction since $b \in H \setminus (Q \cup (\{x', y'\} \cap N_H(w)))$. This proves (2).

In view of (2), we assume from now on that $N_H(P^*) \subseteq \{x\} \cup (N_H(w) \cap \{x'\})$. Let $H_x$ and $H_y$ be the paths in $H$ from $a$ to $b$ through $x$ and $y$, respectively. Since $p_1$ has a neighbor in the interior of a $w$-sector, $H \cup \{w, p_1\}$ is not MNC configuration (6). By Lemma 2.10, it follows that $N_H(p_1) \subseteq Q \cup (\{x', y'\} \cap N_H(w))$, and by Lemma 2.11, it follows that $N_H(p_k) \subseteq H \setminus Q^*$. Therefore, if $p_1$ and $p_k$ have a common neighbor $v$ in $H_y$, then $v \in \{y, y'\}$. Let $r_1 = r_s = v$ if $p_1$ and $p_k$ have a common neighbor $v$ in $H_y$. Otherwise, let $r_1$ be the neighbor of $p_1$ in $H_y$ that is furthest from $a$, and let $r_s$ be the neighbor of $p_k$ in $H_y$ that is furthest from $b$. Let $R = r_1...r_s$ be the path from $r_1$ to $r_s$ through $H_y$. Note that $r_1$ is between $a$ and $r_s$ unless $r_1 = y'$ and $r_s = y$, in which case $p_k y', p_1 y \notin E(G)$. It follows that $P \cup R$ is a hole when $P$ has length at least two.

(3) $w$ has a neighbor in $R \cap \{y, y'\}$.

Because $N_H(p_1) \subseteq Q \cup (\{x', y'\} \cap N_H(w))$, it follows that $N_{H_y}(p_1) \subseteq Q \cup (\{y'\} \cap N_H(w))$. If $r_1 \neq y'$, then $y \in R$ and $wy \in E(G)$, so $w$ has a neighbor in $R \cap \{y, y'\}$. If $r_1 = y'$, then $p_1 y' \in E(G)$, so $wy' \in E(G)$, and $w$ has a neighbor in $R \cap \{y, y'\}$. This proves (3).

(4) If $P \cup R$ is a hole, then $x$ is anticomplete to $P \cup R$.

Let $J$ be the hole given by $P \cup R$. We prove a number of subclaims.

(4.1) $x' \notin J$.

Suppose $x' \in J$. Then $x' = r_s = b$, and so $x'$ is non-adjacent to $w$, since otherwise $a$ and $b$ are not distant in $H$ with respect to $w$. By Lemma 2.9 applied to $J$ and the path $x-w$, it follows that $w$ and $x$ are strictly nested with respect to the hole $J$, and so $x$ and $w$ are both pendants of $J$ with adjacent neighbors in $J$. Let $N_J(w) = \{x''\}$, then $x''$ is the neighbor of $x'$ in $H \setminus x$. Since $w$ has a unique neighbor in $J$, it follows from (3) that $x'' \in \{y, y'\}$. If $x'' = y'$, then $H = y-Q-x-x'-x''-y$ and $N_H(w) = \{x, y, y'\}$, so $H \cup \{w\}$ is a pyramid, a contradiction. So $x'' = y$. But now $H = y-Q-x-x'-y$ and $N_H(y) = \{x, y\}$, so $H \cup \{w\}$ is a theta, a contradiction. This proves (4.1).

(4.2) If $w$ is a hub, then $p_1$ is anticomplete to $\{x', y'\}$.

Suppose $w$ is a hub and $p_1$ is adjacent to $y'$ (the argument is similar if $p_1$ is adjacent to $x'$). Since $p_1$ is adjacent to $a$ and to $y'$, we deduce that $p_1$ is either a clone of $y$ or $p_1$ is major for $H$. Since $w$ is a hub, it follows that if $p_1$ is major for $H$, then $p_1$ is a hub for $H$. In both cases, $N_H(p_1) \setminus Q = \{y'\}$.
Then, $G$ contains a pyramid from $y'$ to $xx'w$ through the paths $y'-w, y'-p_1-Q-x$, and the path from $y'$ to $x'$ with interior in $H \setminus Q$, a contradiction. This proves (4.2).

Suppose that $x$ has a neighbor in $J$. Since, by (4.1), $x' \notin J$, it follows that $x$ is anticomplete to $R$, so $x$ has a neighbor in $P$. We apply Lemma 2.9 to $J$ and the path $x-w$. Since $w$ is anticomplete to $P$, we have that $x$ and $w$ have no common neighbor in $J$. Consequently, $w$ and $x$ are strictly nested with respect to $J$, and so $x$ and $w$ are both pendants of $J$ with adjacent neighbors in $J$. Since $x$ is anticomplete to $R$, and $w$ is anticomplete to $P$, there are two possibilities:

1. $N_J(x) = \{p_k\}$, $N_J(w) = \{r_s\}$, or

2. $N_J(x) = \{p_1\}$, $N_J(w) = \{r_1\}$.

Suppose the former holds. By (3), $r_s \subseteq \{y, y'\} \cap N(w)$. If $p_k$ is adjacent to $y$ (so $r_s = y$), then $G$ contains a theta between $x$ and $r_s$ given by the paths $x-w-r_s, x-p_k-r_s$ and $x-Q-r_s$, a contradiction. It follows that $p_k$ is non-adjacent to $y$, and so $r_s = y'$. Then, $G$ contains a pyramid from $x$ to $yy'w$ through the paths $x-w, x-p_k-r_s$ and $x-Q-y$, a contradiction. This proves that the former case does not hold, and therefore the latter holds.

By (3), $r_1 \in \{y, y'\}$. If $r_1 = y$, let $r'_1 = y'$, and if $r_1 = y'$ let $r'_1$ be the neighbor of $r_1$ in $H \setminus \{y\}$. Let $M$ be the subpath of $H \setminus \{a\}$ from $r'_1$ to $x'$. Suppose that both $w$ and $p_k$ have neighbors in $M^*$. Then there is a path $M'$ from $w$ to $p_k$ with $M' \subseteq M^*$. Now, $G$ contains a theta between $p_1$ and $w$ through the paths $p_1-r_1-w, p_1-x-w$ and $p_1-P-p_k-M'-w$, a contradiction. This proves that either $p_k$ or $w$ is anticomplete to $M^*$.

(4.3) $w$ has no neighbor in $M^*$.

Suppose that $w$ has a neighbor in $M^*$. Then, $p_k$ is anticomplete to $M^*$. Since $w$ has a neighbor in $M^*$, and $N_R(w) = \{r_1\}$, it follows that $r_s \neq x'$ and $r_s$ is non-adjacent to $x'$. Consequently, $r_s \in \{y, y', r'_1\}$. Since $r_1 \in \{y, y'\} \cap N(w)$ and $a$ and $b$ are distant in $H$ with respect to $w$, it follows that either $b = r'_1$, or $b = x'$ and $x'$ is non-adjacent to $w$. Also, since $w$ has a unique neighbor in $J$, it holds that if $r_s = y$ then $r_1 = y$.

Suppose $x'$ has a neighbor in $P \setminus p_1$. Then, there is a path $P'$ from $x'$ to $p_k$ with interior in $P^*$. It follows from the minimality of $k$ that $P'$ is not $(H, w)$-significant. If $x'$ is non-adjacent to $w$, then $x'$ and $r_s$ are distant in $H$ with respect to $w$ since $w$ has a neighbor in $M^*$, and so $P'$ is $(H, w)$-significant, a contradiction. It follows that $x'$ is adjacent to $w$, and so $x' \neq b$ and $b = r'_1$. Suppose $r'_1 \in R$. Then, $w$ is non-adjacent to $r'_1$ since $N_R(w) = \{r_1\}$. Now, we get a contradiction applying Lemma 2.9 to the path $x'-w$ and the hole $J$. This implies that $r'_1 \notin R$, and so $r_1 = r_s$. (Indeed, if $r_1 \neq r_s$, then $r_1 = y, r_s = y', p_k y \notin E(G), wy' \notin E(G), r'_1 = b = y'$, and hence the path $x'-w$ and the hole $J$ contradict Lemma 2.9.) Since $J$ is a hole, we have $k > 2$. Again, by Lemma 2.9 applied to the path $x'-w$ and the hole $J$, it follows that $x'$ is a pendant for $J$, and $N_J(x') = p_k$. But now $G$ contains a pyramid from $r_1$ to $xx'w$ with paths $r_1-p_1-x, r_1-w$ and $r_1-p_k-x'$, a contradiction. This proves that $x'$ is anticomplete to $P \setminus p_1$.

Since $N_H(P^*) \subseteq \{x\} \cup (N_H(w) \cap \{x'\})$, $x'$ is anticomplete to $P \setminus p_1$, and $p_k$ is anticomplete to $M^*$, it follows that $P \setminus p_1$ is anticomplete to $M \setminus r'_1$. Since $x'$ is non-adjacent to $p_k$, it follows that $b = r'_1$. Since $k > 1$ and by minimality of $k$, we deduce that $p_1$ is non-adjacent to $r'_1$. If $r'_1 \in R$, then $G$ contains a theta between $p_1$ and $r'_1$ through the paths $p_1-r_1-r'_1, p_1-x-H_x-r'_1$ (possibly shortcutting through the edge $p_1x'$), and $p_1-P-p_k-r'_1$, a contradiction. This proves that $r'_1 \notin R$, and so $r_s \in \{y, r_1\}$. Since $N_J(x) = \{p_1\}$, $x'$ is anticomplete to $P \setminus \{p_1\}$, and $N_H(P^*) \subseteq \{x, x'\}$, it follows that $P^*$ is anticomplete to $H$. By Lemma 2.12, $p_1$ and $p_k$ have a common neighbor in $H$. It follows that either $r_1 = r_s = y$ or $r_1 = r_s = y'$. Since $P \cup R$ is a hole, it follows that $k > 2$. But now $G$ contains a pyramid from $p_1$ to $r_1 r'_1 p_k$ through the paths $p_1-r_1, p_1-P-p_k$, and $p_1-x-H_x-r'_1$ (possibly shortcutting through $p_1 x'$). This proves (4.3).
(4.4) *w* is a hub for *H*.

If *w* has no neighbor in *M* \ {x', y'}, then by Lemma 2.1, *w* is a hub for *H*. Suppose *w* has a neighbor in *M* \ {x', y'}. Since, by (4.3), *w* is anticomplete to *M*\*, it follows that the only neighbor of *w* in *M* \ {x', y'} is *r*'_1*. Thus, *r*'_1 ≠ *y*', and so *r*₁ = *y*'. Since *r*₁ = *y*' (and thus *p*₁ is adjacent to *y*'), it follows that *w* is adjacent to *y*'. Since *N*<sub>*J*</sub>(*w*) = {*r*₁}, it holds that *r*₁ = *r*<sub>s</sub> = *y*', and since *J* is a hole, *P* has length at least two. If *w* is non-adjacent to *x*', then *p*₁ is non-adjacent to *x*' (as *N*<sub>*H*</sub>(*p*₁) ⊆ *Q* ∪ ({*x*', *y*'} ∩ *N*<sub>*H*</sub>(*w*)) and hence *G* contains a pyramid from *x* to *y*'<sub>1</sub>*w* through *x*-p<sub>1</sub>-*y*', *x*-w, and *x*-x'<sub>-</sub>*M*<sup>-</sup>*r*'_1', a contradiction. Therefore, *w* is adjacent to *x*'. Suppose that the only neighbor of *p*<sub>*k*</sub> in *M* is *r*'_1'. Then, *G* contains a pyramid from *p*₁ to *p*<sub>*k*</sub>r<sub>1</sub>r'_1 through p<sub>1</sub>-r<sub>1</sub>, p<sub>1</sub>-P-p<sub>*k*</sub> (recall that *P* has length at least two), and p<sub>1</sub>-x-x'<sub>-</sub>*H*<sub>*x*</sub>-r'_1 (possibly shortcutting through the edge p<sub>1</sub>-x'), a contradiction. So *p*<sub>*k*</sub> has a neighbor in *M* different from *r*'_1'. Let *b*′ be the neighbor of *p*<sub>*k*</sub> in *M* closest to *x*'. Now, *G* contains a pyramid from *y*' to xx'*w* through *y*'-w, *y*'-p<sub>1</sub>-*x*, and *y*'-p<sub>*k*</sub>-b'<sub>-</sub>*M*-x', a contradiction. This proves (4.4).

It follows that w is a hub and N_H(w) = {x, x', y, y'}. Consequently, by (4.2), p_1 is anticomplete to {x', y'}, and so N_H(p_1) ⊆ Q. Since r_1 ∈ {y, y'} and p_1 is non-adjacent to y', we deduce that r_1 = y. Since N_J(w) = {r_1}, it follows that y' ∉ R, and so r_s = y. Since (H \ {y'}) ∪ {w, p_k} is not a pyramid, it follows that p_k is not a clone of y'. Since a and b are distant in H with respect to w, it follows that b ∈ H \ (Q ∪ {x', y'}). Since p_k is adjacent to y and to b, it holds that p_k is a major vertex for H, and so p_k is a hub by the assumption of the theorem. Consequently, p_k is adjacent to y', and p_k is non-adjacent to x. Since P ∪ R is a hole and r_1 = r_s, it follows that k > 2. But now G contains a pyramid from y to wxx' given by paths y-w, y-p_1-x and y-p_k-H_x-x'. This proves that x is anticomplete to J and completes the proof of (4).

(5) If $x'$ is not anticomplete to $P \setminus p_k$, then $p_1 x \in E(G)$.

Assume $x'$ has a neighbor in $P \setminus p_k$, but $p_1 x \notin E(G)$. By our assumption, $N_H(P^*) \subseteq \{x\} \cup (N_H(w) \cap \{x'\})$, and by Lemma 2.10, $N_H(p_1) \subseteq Q \cup (\{x', y'\} \cap N_H(w))$. Hence, $wx' \in E(G)$. Let $z$ be the neighbor of $x'$ in $P$ closest to $p_1$. Note that if $z \neq p_1$, then $P$ is of length at least two, so $P \cup R$ is a hole and by (4), $x$ is anticomplete to $P$. In particular, $x$ is anticomplete to $p_1$-P-z. Consider the triangle given by $wxx'$. If $N_Q(p_1) = a$, then $G$ contains a pyramid from $a$ to $wxx'$ through a-Q-y-w, a-Q-x, and a-P-z-x', a contradiction. Suppose $p_1$ has two non-adjacent neighbors in $Q$ and let $q$ and $q'$ be the neighbors of $p_1$ in $Q$ closest to $x$ and $y$, respectively. Then, $G$ contains a pyramid from $p_1$ to $wxx'$ through $p_1-q'-Q-y-w$, $p_1-q$-Q-x, and $p_1$-P-z-x', a contradiction. Finally, suppose $p_1$ has exactly two adjacent neighbors in $Q$ and let $N_H(p_1) = \{q, q'\}$, where $q$ is between $x$ and $q'$ in $Q$. Then, $G$ contains a prism between $p_1qq'$ and $x'xw$ through $p_1$-P-z-x', $q$-Q-x, and $q'$-Q-y-w, a contradiction. This proves (5).

(6) If $P \cup R$ is a hole, then $\{x, x'\}$ is anticomplete to $P \setminus p_k$. In particular, $N_H(P^*) = \emptyset$.

Suppose $P \cup R$ is a hole. By (4), $x$ is anticomplete to $P$. If $x'$ has neighbors in $P \setminus p_k$, then, by (5), $p_1 x \in E(G)$, contradicting that $x$ is anticomplete to $P$. This proves the first assertion. Next, suppose that $N_H(P^*) \neq \emptyset$. Then, $P^* \neq \emptyset$, and so $P \cup R$ is a hole. Now, by the first assertion, $\{x, x'\}$ is anticomplete to $P \setminus p_k$. But $N_H(P^*) \subseteq \{x, x'\}$, a contradiction. This proves (6).

By (6), $N_H(P^*) = \emptyset$, and so the symmetry between $x$ and $y$ is restored. Let $T = N_H(p_1) \cap N_H(p_k)$. By Lemma 2.12, $T \neq \emptyset$. Because $N_H(p_1) \subseteq Q \cup \{x', y'\}$ and $N_H(p_k) \subseteq H \setminus Q^*$, it follows that $T \subseteq \{x, x', y, y'\}$. Suppose first that one of $T \cap \{x, x'\}$ and $T \cap \{y, y'\}$ is empty. We may assume up to symmetry that $T \subseteq \{x, x'\}$. Because $p_1$ and $p_k$ do not have a common neighbor in $\{y, y'\}$, it follows that $P \cup R$ is a hole. Then, by (6), $\{x, x'\}$ is anticomplete to $p_1$, a contradiction. Therefore, we may assume that $T \cap \{x, x'\} \neq \emptyset$ and $T \cap \{y, y'\} \neq \emptyset$. By Lemma 2.4 and since $p_k$ is anticomplete $Q^*$, it follows that $p_k$ is adjacent to at most one of $x$ and $y$, and so not both $x$ and
y are in T. Suppose that $x'$ and $y$ are both in T. Then, $w$ has three neighbors in the hole given by $x'-x-Q-y-p_k-x'$ and $w$ is not a clone or a major vertex for this hole, contradicting Lemmas 2.1 and 2.2. This proves that not both $x'$ and $y$ are in T. By symmetry, not both $y$ and $x'$ are in T. It follows that $T = \{x', y'\}$. Because $p_1$ and $w$ are major and non-adjacent, and $p_1$ is adjacent to $x'$ and $y'$, it follows by Lemma 2.7 that $H \cup \{p_1, w\}$ is MNC configuration (5). Therefore, $p_1$ is adjacent to $x$ and $y$. Since $T = \{x', y'\}$, it follows that $\{x, y\}$ is anticomplete to $V(P) \setminus \{p_1\}$. Further, because $p_1$ is not a hub, it follows that $w$ is not a hub, so $w$ has neighbors in $H \setminus (Q \cup \{x', y'\})$. Note also that $b \in H \setminus (Q \cup \{x', y'\})$. Then, $G$ contains a theta between $p_1$ and $w$, through $x, y$, and $P \cup (H \setminus (Q \cup \{x', y'\}))$, a contradiction. □

Let $H = h_1-h_2-\dots-h_k-h_1$ be a hole in a graph $G \in \mathcal{C}$ and let $v \in V(G)$. We say that $v$ is a gem-center if $k \ge 5$ and $N_H(v) = \{h_1, h_2, h_3, h_4\}$.

**Corollary 2.14.** Let $G \in \mathcal{C}$ and let $H$ be a hole in $G$ of length greater than six. Let $w$ be a major vertex for $H$ such that $w$ is not complete to $H$, $w$ is not a gem-center, and either $w$ is not a hub or every major vertex for $H$ is a hub. Then, $w$ is the center of a star cutset in $G$.

*Proof.* Let $u \in H$ such that $uw \notin E(G)$. We claim that there exists a vertex $v \in H$ such that $u$ and $v$ are distant in $H$ with respect to $w$. Suppose otherwise. Let $Q$ be the $w$-sector containing $u$ and let $\bar{Q}$ be the extended neighborhood of $w$ containing $Q$. It follows that $\bar{Q} = H$, so $N_H(w)$ is contained in a subpath of $H$ of length at most three. Since $w$ is major, it follows that $N_H(w)$ is a subpath of $H$ of length exactly three, so $w$ is a gem-center, a contradiction. Let $v \in H$ be such that $u$ and $v$ are distant in $H$ with respect to $w$. It follows from Theorem 2.13 that $w$ has a neighbor in the interior of every path from $u$ to $v$. Therefore, $u$ and $v$ are in different components of $G \setminus (N[w] \setminus v)$, so $w$ is the center of a star cutset in $G$. □

# 3 Structure of proper separators

In this section, we consider minimal separators of graphs in $\mathcal{C}$. We start with the following result concerning minimal separators that are cliques.

**Lemma 3.1 (|4|).** For every graph $G$, there are at most $\mathcal{O}(|V(G)|)$ minimal clique separators of $G$ and they can be enumerated in time $\mathcal{O}(|V(G)||E(G)|)$.

A separator in a graph is proper if it is minimal and not a clique. By Lemma 3.1, we restrict our attention here to proper separators. Our goal is to prove that graphs in $\mathcal{C}$ have polynomially many proper separators.

Let $C$ be a minimal separator of a graph $G$. A connected component $D$ of $G \setminus C$ is a full component for $C$ if every vertex of $C$ has a neighbor in $D$, i.e., $N(D) = C$. Recall that there are at least two full components for every minimal separator. The next lemma, while not necessary for our results, is a convenient observation about full components for proper separators of graphs in $\mathcal{C}$.

**Lemma 3.2.** If $C$ is a proper separator of a graph $G \in \mathcal{C}$, then there are exactly two full components for $C$.

*Proof.* Let $c_1c_2$ be a non-edge in $C$, and suppose that there are three full components for $C$. Then, $G$ contains a path from $c_1$ to $c_2$ through each of the three full components, and so $G$ contains a theta between $c_1$ and $c_2$, a contradiction. □
For the rest of this section, we let $C$ be a proper separator of a graph $G \in \mathcal{C}$, and we denote by $L$ and $R$ the two full components for $C$. Let $H$ be a hole with $V(H) \cap V(C) = \{c_1, c_2\}$, and let $H_L$ and $H_R$ be the two paths of $H$ between $c_1$ and $c_2$. We say that $H$ is a $(C, c_1, c_2)$-hole if $H_L^* \subseteq L$ and $H_R^* \subseteq R$. A vertex $v \in V(G)$ is $(c_1, c_2)$-heavy with respect to $H$ if $v$ is major for $H$ and $c_1, c_2$ are distant in $H$ with respect to $v$. Note that if $v \in V(G)$ is $(c_1, c_2)$-heavy with respect to $H$, then $v$ has a neighbor in $H_L^*$ and a neighbor in $H_R^*$, and therefore $v \in C$. The frame of $H$ is given by $F(H) = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2)$, where $\ell_1$ is the neighbor of $c_1$ in $H_L$, $\ell'_1$ is the neighbor of $\ell_1$ in $H_L^*$ if $\ell_1 \neq \ell_2$, and otherwise $\ell'_1 = \ell_1 = \ell_2$. We define similarly $\ell_2, \ell'_2, r_1, r'_1, r_2, r'_2$. We denote by $V(F)$ the vertices of $F$. We call $F$ a $(C, c_1, c_2)$-frame if $F$ is the frame of a $(C, c_1, c_2)$-hole. A hole $H$ is an $F$-hole if $H$ is a $(C, c_1, c_2)$-hole with frame $F$.

**Lemma 3.3.** Let $H$ be a $(C, c_1, c_2)$-hole with frame $F = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2)$. Assume that $v \in V(G) \setminus V(H)$ has a neighbor both in $H_L^* \setminus \{\ell_1, \ell_2\}$ and in $H_R^* \setminus \{r_1, r_2\}$. Then, $v$ is $(c_1, c_2)$-heavy with respect to $H$.

*Proof.* Suppose that $v$ is not $(c_1, c_2)$-heavy with respect to $H$. Then, $c_1$ and $c_2$ are in an extended neighborhood $\overline{Q}$ of $v$. Let $\overline{Q} = Q \cup (N_H(v) \cap \{x', y'\})$, where $Q = x \dots y$ is a $v$-sector, and $x'$ and $y'$ are the neighbors of $x$ and $y$ in $H \setminus Q^*$, respectively. Then, $c_1$ and $c_2$ are either in $V(Q)$ or have a neighbor in $V(Q)$. Since $v$ has a neighbor in $H_L^* \setminus \{\ell_1, \ell_2\}$, it follows that $H_L^* \setminus V(Q) \neq \emptyset$. Similarly, $H_R^* \setminus V(Q) \neq \emptyset$.

Suppose first that $c_1$ is not adjacent to $v$. Let $S$ be the $v$-sector of $H$ that contains $c_1$. Since $c_1v \notin E(G)$ and $c_1 \in \overline{Q}$, it follows that $S = Q$. Since $c_2 \in \overline{Q}$, either $v$ has no neighbor in $H_L^* \setminus \{\ell_1, \ell_2\}$ or $v$ has no neighbor in $H_R^* \setminus \{r_1, r_2\}$, a contradiction. Thus, $c_1v \in E(G)$, and similarly $c_2v \in E(G)$. But then, since $c_1, c_2 \in \overline{Q}$, either $H_L^* \setminus V(Q) = \emptyset$ or $H_R^* \setminus V(Q) = \emptyset$, a contradiction. $\square$

The potential of a $(C, c_1, c_2)$-hole $H$ is the total number of $(c_1, c_2)$-heavy vertices with respect to $H$. The following lemma shows that the potential of a $(C, c_1, c_2)$-hole only depends on its frame.

**Lemma 3.4.** Let $H_1$ and $H_2$ be $(C, c_1, c_2)$-holes with the same frame, given by $F(H_1) = F(H_2) = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2)$. Then, $v \in V(G)$ is $(c_1, c_2)$-heavy with respect to $H_1$ if and only if $v$ is $(c_1, c_2)$-heavy with respect to $H_2$. In particular, the potential of $H_1$ and the potential of $H_2$ are equal.

*Proof.* Suppose $v \in V(G)$ is $(c_1, c_2)$-heavy with respect to $H_1$ and not with respect to $H_2$.

(1) If $v$ has no neighbor in $H_{2L}^* \setminus \{\ell_1, \ell_2\}$, then $N(v) \cap H_{1L}^* \subseteq \{\ell_1, \ell_2\}$. Similarly, if $v$ has no neighbor in $H_{2R}^* \setminus \{r_1, r_2\}$, then $N(v) \cap H_{1R}^* \subseteq \{r_1, r_2\}$.

By symmetry, it suffices to prove the first statement. So assume that $v$ has no neighbor in $H_{2L}^* \setminus \{\ell_1, \ell_2\}$. We may assume that $\ell_1, \ell'_1, \ell_2, \ell'_2$ are all distinct, since otherwise the result clearly holds. In particular, $H_1$ and $H_2$ are both of length greater than six.

Since $v$ is $(c_1, c_2)$-heavy with respect to $H_1$, $v$ has a neighbor in both $H_{1L}^*$ and $H_{1R}^*$. Suppose $v$ is anticomplete to $\{\ell_1, \ell_2\}$. Then, there exists a path $P = p_1 - \dots - p_k$ in $(H_1 \setminus \{\ell_1, \ell_2\}) \cup \{v\}$ such that $P \cap H_2 = \emptyset$, $p_1$ has a neighbor in $H_{2L}^*$, $p_k$ has a neighbor in $H_{2R}$, and $P^*$ is anticomplete to $H_2$. Note that $v \in P$ and $p_1 \in L$ (i.e. $p_1 \neq v$), so $P$ is of length at least 1. But then $P$ and $H_2$ contradict Lemma 2.9. So $v$ is not anticomplete to $\{\ell_1, \ell_2\}$. Thus, we may assume that $v$ is adjacent to $\ell_1$. Let $Q$ be the $v$-sector of $H_1$ that contains $\ell'_1$. Then, $\ell_1 \in V(Q)$. Since $c_1$ and $c_2$ are distant in $H_1$ with respect to $v$, it follows that $v$ is a major vertex for $H_1$. We claim that $v$ is not a hub for $H_1$. Suppose $v$ is a hub for $H_1$. Since $\ell_1 \in N(v)$ and $\ell'_1 \notin N(v)$, it follows that $c_1 \in N(v)$. But then $c_1$ and $c_2$ are not distant in $H_1$ with respect to $v$, a contradiction. This proves that $v$ is not a hub for $H_1$. Now, since $v$ is anticomplete to $\ell'_1-H_{2L}-\ell'_2$, it follows from Theorem 2.13 that $\ell'_1$ and
$\ell'_2$ are not distant in $H_1$ with respect to $v$. Since $v$ is not adjacent to $\ell'_2$, it follows that $\ell'_2 \in Q$, so $N(v) \cap H_{1L}^* \subseteq \{\ell_1, \ell_2\}$. This proves (1).

By Lemma 3.3, we may assume that $v$ has no neighbor in $H_{2L}^* \setminus \{\ell_1, \ell_2\}$. By (1), it follows that $N(v) \cap H_{1L}^* \subseteq \{\ell_1, \ell_2\}$.

(2) $v$ has a neighbor in $H_{2R}^* \setminus \{r_1, r_2\}$.

Assume that $v$ has no neighbor in $H_{2R}^* \setminus \{r_1, r_2\}$. Then, by (1), $N(v) \cap H_{1R}^* \subseteq \{r_1, r_2\}$. But now, $N(v) \cap H_1 = N(v) \cap H_2$, and so $c_1$ and $c_2$ are distant in $H_2$ with respect to $v$, a contradiction. This proves (2).

Since $c_1$ and $c_2$ are not distant in $H_2$ with respect to $v$, there exists an extended neighborhood $\overline{Q}$ of $v$ in $H_2$ such that $c_1$ and $c_2$ are both in $\overline{Q}$. Let $\overline{Q} = Q \cup (N_{H_2}(v) \cap \{x', y'\})$ where $Q = x \dots y$ is a $v$-sector in $H_2$ and $x'$ and $y'$ are the neighbors of $x$ and $y$ in $H_2 \setminus Q$, respectively. Since $\overline{Q}$ contains $c_1$ and $c_2$, it follows that either $H_{2L} \subseteq \overline{Q}$ or $H_{2R} \subseteq \overline{Q}$. Suppose that $H_{2L} \subseteq \overline{Q}$. Since $c_1$ and $c_2$ are distant in $H_1$ with respect to $v$ and $N(v) \cap H_{1L}^* \subseteq \{\ell_1, \ell_2\}$, we may assume that $v$ is adjacent to $\ell_1$. Since $c_1$ is in $\overline{Q}$, it follows that $v$ is also adjacent to $c_1$. Because $\overline{Q}$ is an extended neighborhood of $v$ in $H_2$ that contains $c_1$ and $c_2$, $v$ is either non-adjacent to $\ell_2$, or $v$ is adjacent to $\ell_2$ and $c_2$. But now $c_1$ and $c_2$ are not distant in $H_1$ with respect to $v$, a contradiction. Therefore, $H_{2R} \subseteq \overline{Q}$. However, by (2), $v$ has a neighbor in $H_{2R}^* \setminus \{r_1, r_2\}$, a contradiction. $\square$

Let $F = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2)$ be a $(C, c_1, c_2)$-frame. We say that a vertex $v \in V(G)$ is $F$-heavy if there exists an $F$-hole $H$ such that $v$ is $(c_1, c_2)$-heavy with respect to $H$. Note that Lemma 3.4 implies that an $F$-heavy vertex $v$ is $(c_1, c_2)$-heavy with respect to every hole $H$ with frame $F$. A vertex $v$ that is not $F$-heavy is said to be $F$-light. The potential of $F$ is the total number of $F$-heavy vertices.

Let $c_1, c_2 \in C$. We denote by $\text{dist}_L(c_1, c_2)$ and $\text{dist}_R(c_1, c_2)$ the length of the shortest path from $c_1$ to $c_2$ through $L$ and $R$, respectively, and we let $\text{dist}(c_1, c_2) = \min(\text{dist}_R(c_1, c_2), \text{dist}_L(c_1, c_2))$. We say that $(c_1, c_2)$ is a long pair of $C$ if $\text{dist}(c_1, c_2) \ge 4$. A $(C, c_1, c_2)$-frame $F$ is long if $(c_1, c_2)$ is a long pair of $C$. A proper separator $C$ is rich if there exist $c_1, c_2 \in C$ such that $(c_1, c_2)$ is a long pair, and poor otherwise.

**Lemma 3.5.** Suppose $F$ is a $(C, c_1, c_2)$-frame, $H$ is an $F$-hole, and $c_3 \in C \setminus \{c_1, c_2\}$ is $F$-light. Let $P = p_k - \dots - p_1 - c_3 - q_1 - \dots - q_j$ be a path such that $c_3 - p_1 - \dots - p_k$ is a path from $c_3$ to $H_L^*$ through $L$ and $c_3 - q_1 - \dots - q_j$ is a path from $c_3$ to $H_R^*$ through $R$ (possibly $c_3 = p_k$ or $c_3 = q_j$), and assume $P$ has length at least two. Then, up to symmetry between $c_1$ and $c_2$, one of the following holds:

(i) $c_1$ and $c_2$ are anticomplete to $P^*$, $N_H(p_k) = \{\ell_1, c_1\}$, and $N_H(q_j) = \{c_1, r_1\}$,

(ii) $c_2$ is anticomplete to $P^*$, $c_1$ has neighbors in $P^*$, $p_k$ is either adjacent to $c_1$ or a pendant of $H$ with neighbor $\ell_1$, and $q_j$ is either adjacent to $c_1$ or a pendant of $H$ with neighbor $r_1$.

*Proof.* If both $c_1$ and $c_2$ have neighbors in $P^*$, then $G$ contains a theta between $c_1$ and $c_2$ through $H_L$, $H_R$, and $P^*$, so we may assume that $c_2$ is anticomplete to $P^*$.

Suppose $c_1$ is also anticomplete to $P^*$. By Lemma 2.9, either $p_k$ and $q_j$ have a common neighbor in $H$, or their neighbors in $H$ form an edge. Since $p_k$ has a neighbor in $H_L^*$ and $q_j$ has a neighbor in $H_R^*$, it follows that the neighbors of $p_k$ and $q_j$ in $H$ do not form an edge. Hence, we may assume that $p_k$ and $q_j$ are both adjacent to $c_1$. If $p_k$ and $q_j$ both have neighbors in $H \setminus \{c_1\}$ other than $\ell_1$ and $r_1$, respectively, then $G$ contains a theta between $p_k$ and $q_j$ through $P$, $c_1$, and $H \setminus \{\ell_1, c_1, r_1\}$, a contradiction. Suppose $N_H(q_j) = \{c_1, r_1\}$ and $p_k$ has a neighbor in $H_L$ other than $\ell_1$. Let $s$ be the neighbor of $p_k$ in $H_L$ closest to $c_2$. Then, $G$ contains a pyramid from $p_k$ to $q_j c_1 r_1$ through $p_k-P-q_j$,
$p_k-c_1$, and $p_k-s-H \setminus \{c_1\}-r_1$, a contradiction. By definition, $p_k$ and $q_j$ have neighbors in $H_L^*$ and $H_R^*$, respectively, and so $N_H(p_k) = \{\ell_1, c_1\}$ and $N_H(q_j) = \{c_1, r_1\}$, and outcome (i) holds.

Next, suppose $c_1$ has neighbors in $P^*$. Let $r$ be the closest neighbor of $c_1$ to $p_k$ in $P^*$. By Lemma 2.9 applied to the path $p_k-P-r$, either $p_k$ and $r$ have a common neighbor in $H$, or $p_k$ and $r$ are pendants of $H$ with adjacent neighbors in $H$. Since $N_H(r) = \{c_1\}$, either $p_k$ is adjacent to $c_1$ or $N_H(p_k) = \{\ell_1\}$. By symmetry, either $q_j$ is adjacent to $c_1$ or $N_H(q_j) = \{r_1\}$, and outcome (ii) holds. □

Let $H$ be an $F$-hole and let $c_3 \in C \setminus \{c_1, c_2\}$ be $F$-light. A $c_3$-butterfly is a path $P = p_k \dots p_1 c_3 q_1 \dots q_j$, where $c_3 p_1 \dots p_k$ is a shortest path from $c_3$ to $H_L^*$ through $L$ and $c_3 q_1 \dots q_j$ is a shortest path from $c_3$ to $H_R^*$ through $R$ (possibly $p_k = c_3$ or $c_3 = q_j$). We call the path $c_3 p_1 \dots p_k$ the left wing of $P$, and the path $c_3 q_1 \dots q_j$ the right wing of $P$. We say that $c_3$ is a central vertex of $P$ if $c_3 \neq p_k, p_{k-1}, q_j, q_{j-1}$.

The following results deal with the structure of $c_3$-butterflies.

**Lemma 3.6.** Suppose $F$ is a $(C, c_1, c_2)$-frame, $H$ is an $F$-hole, and $c_3 \in C \setminus \{c_1, c_2\}$ is $F$-light. Suppose further that if $C$ is a rich separator, then $F$ is long, and if $C$ is a poor separator, then $\text{dist}(c_1, c_2)$ is maximum over all non-adjacent pairs in $C$. Let $P$ be a $c_3$-butterfly and assume $c_2$ is anticomplete to $P^*$. Suppose that $c_3$ is a central vertex of $P$. Then, $(c_3, c_2)$ is a long pair of $C$. In particular, $C$ is a rich separator.

*Proof.* Assume for a contradiction that $(c_3, c_2)$ is not a long pair of $C$. Then, there exists a path from $c_3$ to $c_2$ of length less than or equal to three through $L$ or through $R$. First, assume that there exists a path of length two from $c_3$ to $c_2$, say $c_3-x-c_2$, and without loss of generality let $x \in L$. Because $P$ is a butterfly and $c_3$ is a central vertex of $P$, neither $c_3$ nor $c_3-x$ is the left wing of a $c_3$-butterfly, so $x \notin H$ and $x$ is anticomplete to $H_L^*$. It follows that $N_H(x) \subseteq \{c_1, c_2\}$. If $N_H(x) = \{c_1, c_2\}$, then $G$ contains a theta between $c_1$ and $c_2$ through $H_L, H_R$, and $x$, so $N_H(x) = \{c_2\}$. If $c_1$ has neighbors in $P^*$, then $G$ contains a theta between $c_1$ and $c_2$ through $H_L, H_R$, and $P^* \cup \{x\}$, so $c_1$ is anticomplete to $P^*$. It follows from Lemma 3.5 that $N_H(p_k) = \{\ell_1, c_1\}$. Now, $G$ contains a pyramid from $c_2$ to $p_k \ell_1 c_1$ through $c_2-x-c_3-P-p_k, c_2-H_L-\ell_1$, and $c_2-H_R-c_1$, a contradiction. Therefore, there is no path of length two from $c_3$ to $c_2$.

Next, let $c_3-x-y-c_2$ be a path of length three from $c_3$ to $c_2$, and without loss of generality let $x, y \in L$. Since $\text{dist}(c_3, c_2) = 3$, it follows that $\text{dist}(c_1, c_2) \ge 3$. In particular, $c_1$ is not adjacent to $y$. Because $c_3$ is a central vertex of $P$, it follows that neither $c_3$ nor $c_3-x$ is the left wing of a $c_3$-butterfly. Therefore, $x, y \notin H$ and $N_H(x) \subseteq \{c_1\}$. Suppose $x$ is adjacent to $c_1$. Then, $x$ and $y$ are strictly nested with respect to $H$. By Lemma 2.9, $x$ and $y$ are pendants of $H$ with adjacent neighbors in $H$, so $c_1$ is adjacent to $c_2$, a contradiction. Hence, $x$ is anticomplete to $H$.

Suppose first that $c_1$ is adjacent to $c_3$. Consider the path $y-x-c_3$. By Lemma 2.9, either $y$ and $c_3$ have a common neighbor in $H$, or $y$ and $c_3$ are pendants of $H$ with adjacent neighbors in $H$. Since $N_H(c_3) = \{c_1\}$ and $y$ is not adjacent to $c_1$, it follows that $y$ is a pendant with $N_H(y) = \{\ell_1\}$. But $c_2 \in N_H(y)$, a contradiction. This shows that $c_1$ is not adjacent to $c_3$. Next, suppose that $c_1$ has a neighbor in $\{q_1, q_2, \dots, q_j\}$. Let $t$ be minimum such that $c_1$ is adjacent to $q_t$. Let $Q$ be a path from $y$ to $q_t$ with $Q^* \subseteq \{x, c_3, q_1, \dots, q_{t-1}\}$. By Lemma 2.9, either $y$ and $q_t$ have a common neighbor in $H$, or $y$ and $q_t$ are pendants of $H$ with adjacent neighbors in $H$. Suppose $t \neq j$, so $N_H(q_t) = \{c_1\}$. Since $y$ is not adjacent to $c_1$, it follows that $y$ is a pendant of $H$ and $N_H(y) = \{\ell_1\}$. But $c_2 \in N_H(y)$, a contradiction. Therefore, $t = j$. Since $q_j$ is adjacent to $c_1$ and $q_j$ has a neighbor in $H_R^*, q_j$ is not a pendant of $H$. Therefore, $q_j$ and $y$ have a common neighbor in $H$. Since $y \in L$ and $q_j \in R$, the common neighbor of $y$ and $q_j$ is $c_2$. Then, $q_j$ is a common neighbor of $c_1$ and $c_2$, contradicting that $\text{dist}(c_1, c_2) \ge 3$. This proves that $c_1$ is anticomplete to $\{c_3, q_1, \dots, q_j\}$.
Since $q_j$ is not adjacent to $c_1$, by Lemma 3.5, $N_H(q_j) = \{r_1\}$. Now, consider the path $Q = y-x-c_3\dots-q_j$. By Lemma 2.9, either $y$ and $q_j$ are pendants of $H$ with adjacent neighbors in $H$, or $y$ and $q_j$ have a common neighbor in $H$. Since $y \in L$ and $N_H(q_j) = \{r_1\}$, $y$ and $q_j$ do not have a common neighbor in $H$. Therefore, $r_1$ is adjacent to $c_2$, contradicting that $\text{dist}(c_1, c_2) \ge 3$. $\square$

By Lemma 3.5 and Lemma 3.6, if $C$ is a poor separator and $\text{dist}(c_1, c_2)$ is maximum over all non-adjacent pairs in $C$, then $c_3$ is not a central vertex of $P$. The following two lemmas prove a similar result for rich separators.

**Lemma 3.7.** Suppose $C$ is a rich separator, $(c_1, c_2)$ is a long pair of $C$, $F$ is a $(C, c_1, c_2)$-frame, $H$ is an $F$-hole, $c_3 \in C \setminus \{c_1, c_2\}$ is $F$-light, and $P = p_k\dots-c_3\dots-q_j$ is a $c_3$-butterfly with $c_2$ anticomplete to $P^*$. Assume that $c_3$ is a central vertex of $P$ and let $w$ be an $F$-heavy vertex. Let $s$ be the neighbor of $p_k$ in $H_L$ closest to $c_2$, and let $t$ be the neighbor of $q_j$ in $H_R$ closest to $c_2$. Let $S$ be the path from $s$ to $t$ in $H \setminus \{c_1\}$, and consider the $(C, c_3, c_2)$-hole given by $J = P \cup S$. Then, $w$ is a $(c_3, c_2)$-heavy vertex with respect to $J$.

*Proof.* By Lemma 3.5, $p_k$ is either adjacent to $c_1$ or $N_H(p_k) = \{\ell_1\}$. Since $(c_1, c_2)$ is a long pair of $C$, it follows that $s \ne \ell_2$. By symmetry, $t \ne r_2$. Assume for a contradiction that $w$ is not $(c_3, c_2)$-heavy with respect to $J$.

(1) If $p_k$ is adjacent to $c_1$, then $w$ has a neighbor in $p_k-s-H_L-\ell_2$.

Because $(c_1, c_2)$ is a long pair of $C$, $H$ has length at least eight. By Lemma 3.4, $w$ is $(c_1, c_2)$-heavy with respect to $H$. Suppose $w$ is anticomplete to the path given by $p_k-s-H_L-\ell_2$. If $w$ is not complete to $\{c_1, c_2\}$, then since $c_1$ and $c_2$ are distant in $H$ with respect to $w$, the path $p_k-s-H_L-\ell_2$ is $(H, w)$-significant and $w$ is not a hub for $H$, a contradiction to Theorem 2.13. So $w$ is complete to $\{c_1, c_2\}$. Let $w'$ be the neighbor of $w$ in $H_L^*$ that is closest to $\ell_2$. Note that $w'$ exists and $w' \ne \ell_1$ since $w$ is $(c_1, c_2)$-heavy with respect to $H$. Also, observe that there is a path $Q$ from $w$ to $p_k$ through $P \cup H_R \setminus \{c_1, r_1\}$: either $w$ has a neighbor in $P \setminus \{p_k\}$, or there is a path $Q' = q_j-t-H_R-w''-w$, where $w''$ is the neighbor of $w$ in $t-H_R-c_2$ closest to $t$ (possibly $w'' = c_2$). Let $s'$ be the neighbor of $p_k$ in $w'-H_L-c_2$ closest to $w'$; note that $s'$ exists since $s$ is in $w'-H_L-c_2$ (possibly $s' = w'$). Now, $G$ contains a theta between $p_k$ and $w$ through $p_k-s'-H_L-w'-w$, $p_k-c_1-w$, and $p_k-Q-w$, a contradiction. This proves (1).

(2) $w$ has a neighbor in $J_L^* \setminus N_J(c_3)$ and a neighbor in $J_R^* \setminus N_J(c_3)$.

By symmetry, it suffices to show that $w$ has a neighbor in $J_L^* \setminus N_J(c_3)$. Assume first that $s = \ell_1$. Then, $H_L^* \subseteq J_L^*$. Further, $c_3$ does not have a neighbor in $H_L^*$, otherwise $c_3 = p_k$, contradicting that $c_3$ is a central vertex of $P$. Finally, since $w$ is $(c_1, c_2)$-heavy with respect to $H$, $w$ has a neighbor in $H_L^*$, and we are done. Hence, we may assume that $s \ne \ell_1$. By Lemma 3.5, $p_k$ is adjacent to $c_1$, so by (1), $w$ has a neighbor in $p_k-s-H_L-\ell_2$. Note that $p_k-s-H_L-\ell_2 \subseteq J_L^*$, so $w$ has a neighbor in $J_L^*$. Further, $c_3$ does not have a neighbor in $p_k-s-H_L-\ell_2$, otherwise $c_3$ is adjacent to $p_k$, contradicting that $c_3$ is a central vertex of $P$. Therefore, $w$ has a neighbor in $J_L^* \setminus N_J(c_3)$. This proves (2).

By Lemma 3.3, $w$ does not have a neighbor in both $J_L^* \setminus N_J(\{c_3, c_2\})$ and $J_R^* \setminus N_J(\{c_3, c_2\})$, so by (2) we may assume that $\ell_2$ is the only neighbor of $w$ in $J_L^* \setminus N_J(c_3)$. By (2) $w$ has a neighbor in $J_R^* \setminus N_J(c_3)$ and since $c_3$ and $c_2$ are not distant in $J$ with respect to $w$, it follows that $w$ is also adjacent to $c_2$. Because $c_1$ and $c_2$ are distant in $H$ with respect to $w$, it follows that $s \ne \ell_1$ and $w$ has neighbors in the interior of $c_1-H_L-s$. Since $s \ne \ell_1$, by Lemma 3.5, it follows that $p_k$ is adjacent to $c_1$. Thus, $w$ and $p_k$ cross with respect to $H$. There are two cases: either $p_k$ is a clone of $\ell_1$, or $p_k$ is major and by Lemma 2.7 $H \cup \{w, p_k\}$ is MNC configuration (4), (5), (6), (7), or (8). Suppose the first case holds, so $p_k$ is a clone of $\ell_1$. Since $p_k$ is a clone of $\ell_1$, it holds that $s = \ell_1'$. By Lemma 2.8, $H$ contains a $\{w, p_k\}$-complete edge, so $w$ is adjacent to $\ell_1$ and $c_1$ (note that $w$ is not adjacent
to $s = \ell'_1$ since $\ell_2$ is the only neighbor of $w$ in $J_L^* \setminus N_J(c_3))$. Then, $N(w) \cap H_L = \{c_1, \ell_1, \ell_2, c_2\}$,
so $c_1$ and $c_2$ are not distant in $H$ with respect to $w$, a contradiction. Therefore, $p_k$ is major and
$H \cup \{w, p_k\}$ is MNC configuration (4), (5), (6), (7), or (8). It follows that there is a $\{w, p_k\}$-complete
edge in $c_1-H_L$-s. Let $e = v_1v_2$ be a $\{w, p_k\}$-complete edge in $c_1-H_L$-s such that $v_2$ is between $v_1$
and $s$ in $H_L$. Suppose that $w$ is not a cap with respect to $J$ and let $u$ be the neighbor of $w$ in the
$p_k c_2$-subpath of $J \setminus \ell_2$ that is closest to $p_k$. Then $G$ contains a theta between $p_k$ and $w$ through
$p_k-v_1-w$, $p_k-s-H_L-\ell_2-w$, and $p_k-J \setminus \{\ell_2\}-u-w$. Hence, $N_J(u) = \{\ell_2, c_2\}$. Then, $G$ contains a pyramid
from $p_k$ to $w\ell_2c_2$ through $p_k-v_1-w$, $p_k-s-H_L-\ell_2$, and $p_k-P-q_j-t-H_R-c_2$, a contradiction.
□

**Lemma 3.8.** Suppose $C$ is a rich separator, $F$ is a $(C, c_1, c_2)$-frame with maximum potential over all long frames, and $H$ is an $F$-hole. Let $c_3 \in C \setminus \{c_1, c_2\}$ be $F$-light, and let $P = p_k \dots c_3 \dots q_j$ be a $c_3$-butterfly. Then, $c_3$ is not a central vertex of $P$.

*Proof.* Suppose that $c_3$ is a central vertex of $P$. By Lemma 3.5, we may assume that $c_2$ is anti-complete to $P^*$. Furthermore, by Lemma 3.5, $p_k$ is adjacent to $c_1$ or $N_H(p_k) = \{\ell_1\}$. Since $(c_1, c_2)$ is a long pair of $C$, it follows that $p_k$ is anticomplete to $\{c_2, \ell_2\}$. By symmetry, $q_j$ is anticomplete to $\{c_2, r_2\}$. Let $r$ be the neighbor of $p_k$ in $H_L$ closest to $c_2$, and let $s$ be the neighbor of $q_j$ in $H_R$ closest to $c_2$. Let $S$ be the path in $H$ from $r$ to $s$ through $c_2$. Let $J$ be the $(C, c_3, c_2)$-hole given by $P \cup S$, and let $F'$ be the $(C, c_3, c_2)$-frame of $J$. By Lemma 3.7 it follows that every $F$-heavy vertex is $(c_2, c_3)$-heavy with respect to $J$, and therefore is $F'$-heavy. Now, consider $c_1$ with respect to the hole $J$. Either $c_1$ is adjacent to $p_k$, or $\ell_1$ is in $J$ and $c_1$ is adjacent to $\ell_1$. Similarly, either $c_1$ is adjacent to $q_j$, or $r_1$ is in $J$ and $c_1$ is adjacent to $r_1$. Then, $c_1$ has a neighbor in $J_L^* \setminus N_J(\{c_3, c_2\})$ and a neighbor in $J_R^* \setminus N_J(\{c_3, c_2\})$, so by Lemma 3.3, $c_1$ is a $(c_3, c_2)$-heavy vertex of $J$. Finally, it follows from Lemma 3.6 that $(c_3, c_2)$ is a long pair of $C$. Then, $F'$ is a long $(C, c_3, c_2)$-frame with higher potential than $F$, a contradiction.
□

We call a $(C, c_1, c_2)$-frame $F$ optimal if one of the following holds:

(i) $C$ is a rich separator and $F$ has maximum potential over all long frames of $C$

(ii) $C$ is a poor separator and $\text{dist}(c_1, c_2)$ is maximum over all non-adjacent pairs of vertices in $C$.

The following theorem combines the results of Lemma 3.5, Lemma 3.6, and Lemma 3.8.

**Theorem 3.9.** Let $F$ be an optimal $(C, c_1, c_2)$-frame, $H$ be an $F$-hole, $c_3 \in C \setminus \{c_1, c_2\}$ be $F$-light, and $P = p_k \dots c_3 \dots q_j$ be a $c_3$-butterfly. Then, $c_3$ is not a central vertex of $P$.

# 4 Constructing proper separators

In this section, we show how to use the structure results from previous sections to prove the main result of the paper. Our goal is to reconstruct proper separators $C$ given only an optimal frame $F$ of $C$, and two 4-tuples $M_1(C), M_2(C)$ of vertices in $C$. We first show that we can construct an $F$-hole $H$, and then show that we can construct three sets $C_1, C_2, C_3$ such that $C = C_1 \cup C_2 \cup C_3$.

We begin with a key observation about the structure of graphs in $C$.

**Lemma 4.1.** If $G \in C$, then $G$ does not contain a 3- creature.

*Proof.* Assume that $G$ contains a 3- creature with notation as in the definition of a $k$- creature. Suppose first that $x_3$ is adjacent to $x_1$ and $x_2$. Let $Q_A$ be a path from $x_1$ to $x_2$ through $A$, and let $Q_B$ be a path from $y_1$ to $y_2$ through $B$. Then, $x_1-Q_A-x_2-y_2-Q_B-y_1-x_1$ is a hole in $G$. Let $R_B = y_3 \dots b$ be a path from $y_3$ to $Q_B$ through $B$. Consider the path $R = x_3-y_3-R_B-b$. Since $x_3$
and $b$ are strictly nested with respect to $H$, by Lemma 2.9, it follows that $x_3$ and $b$ are pendants of $H$ with adjacent neighbors in $H$. However, $x_3$ is adjacent to $x_1$ and $x_2$, a contradiction.

We may therefore assume that $x_1$ is not adjacent to $x_2$ and $y_1$ is not adjacent to $y_2$. Let $Q_A$ be a path from $x_1$ to $x_2$ through $A$, and let $Q_B$ be a path from $y_1$ to $y_2$ through $B$. Then, $x_1-Q_A-x_2-y_2-Q_B-y_1-x_1$ is a hole in $G$. Let $R_A = x_3-\dots-a$ be a path from $x_3$ to $Q_A^*$ through $A$ and let $R_B = y_3-\dots-b$ be a path from $y_3$ to $Q_B^*$ through $B$. Consider the path $R = a-R_A-x_3-y_3-R_B-b$. If $\{x_1, y_1, x_2, y_2\}$ is anticomplete to $R^*$, then $a$ and $b$ are strictly nested with respect to $H$, and $a$ and $b$ are not pendants of $H$ with adjacent neighbors in $H$, contradicting Lemma 2.9. Hence, one of $x_1, y_1, x_2, y_2$ has a neighbor in $R^*$. In particular, $R^*$ is not empty. Suppose $x_1$ and $x_2$ both have neighbors in $R^*$. Then, $G$ contains a theta between $x_1$ and $x_2$ through $Q_A, Q_B$, and $R^*$, a contradiction. Therefore, not both $x_1$ and $x_2$ have neighbors in $R^*$. Similarly, not both $y_1$ and $y_2$ have neighbors in $R^*$. Since $\{x_1, y_1, x_2, y_2\}$ is not anticomplete to $R^*$, we may assume that $x_1$ has a neighbor in $R^*$. If $y_2$ also has a neighbor in $R^*$, then $G$ contains a theta between $x_1$ and $y_2$ through $Q_A, Q_B$, and $R^*$, a contradiction. Therefore, $y_2$ is anticomplete to $R^*$.

Let $c$ be the closest neighbor of $x_1$ to $x_3$ in $R_A$. Suppose $y_1$ is anticomplete to $R^*$ and consider the path $c-R_A-x_3-y_3-R_B-b$. Then, $c$ and $b$ are strictly nested with respect to $H$. Since $b$ has a neighbor in $Q_B^*$, $c$ and $b$ are not pendants of $H$ with adjacent neighbors in $H$, contradicting Lemma 2.9. Hence, $y_1$ has a neighbor in $R^*$. Let $a'$ be the neighbor of $a$ in $Q_A$ closest to $x_2$, and let $b'$ be the neighbor of $b$ in $Q_B$ closest to $y_2$. Let $H'$ be the hole given by $H' = x_3-R_A-a-a'-Q_A-x_2-y_2-Q_B-b'-b-R_B-y_3-x_3$. Since $x_1$ and $y_1$ are strictly nested with respect to $H'$, by Lemma 2.9, $x_1$ and $y_1$ are pendants of $H'$ with adjacent neighbors in $H'$. Therefore, $N_{H'}(x_1) = \{x_3\}$ and $N_{H'}(y_1) = \{y_3\}$. In particular, $a'x_1, b'y_1 \notin E(G)$. Since $R^* \neq \emptyset$, without loss of generality $y_3 \neq b$. Now, $G$ contains a theta between $x_3$ and $y_1$ through $y_3, x_1$, and $x_3-R_A-a-a'-Q_A-x_2-y_2-Q_B-y_1$, a contradiction. $\square$

For the rest of the section, unless otherwise specified, let $C$ be a proper separator of $G \in \mathcal{C}$ and let $F = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2)$ be an optimal $(C, c_1, c_2)$-frame. We denote by $G_F$ the graph $G \setminus (N(\{c_1, c_2, \ell_1, r_1, \ell_2, r_2\}) \setminus \{\ell'_1, \ell'_2, r'_1, r'_2\})$. The following two lemmas show that we can construct a set $W = W(F)$ containing every $F$-heavy vertex $v$ such that $v \in V(G_F)$.

**Lemma 4.2.** Let $H$ be an $F$-hole and let $v \in C \cap V(G_F)$ be major for $H$. Then, $v$ is $F$-heavy.

*Proof.* Assume that $v$ is not $F$-heavy, and let $P$ be a $v$-butterfly. Since $v$ is major for $H$, $v$ must be an endpoint of $P$. Since $v \in V(G_F)$, $v$ is anticomplete to $\{c_1, c_2, \ell_1, r_1, \ell_2, r_2\}$, and so by Lemma 3.5, $P$ is of length at most one. Since $v$ is $F$-light, by Lemma 3.3, $P$ is of length exactly one. But then since $v$ is anticomplete to $\{c_1, c_2, \ell_1, r_1, \ell_2, r_2\}$, $P$ and $H$ contradict Lemma 2.9. $\square$

We call $v \in C$ a $(c_1, c_2)$-strong vertex of $G$ if $c_1$ and $c_2$ belong to different components of $G \setminus N[v]$. Note that given a graph $G$, and $v, c_1, c_2 \in V(G)$, one can determine if $v$ is $(c_1, c_2)$-strong in time $O(|V(G)|^2)$.

**Lemma 4.3.** One can construct in polynomial time a set $W = W(F)$ that contains all $F$-heavy vertices $v$ such that $v$ is anticomplete to $\{c_1, c_2, \ell_1, \ell_2, r_1, r_2\}$ and $W \subseteq C$.

*Proof.* Let $H$ be an $F$-hole where the path from $\ell'_1$ to $\ell'_2$ through $H_L$ is a shortest path from $\ell'_1$ to $\ell'_2$ in $L$, and the path from $r'_1$ to $r'_2$ through $H_R$ is a shortest path from $r'_1$ to $r'_2$ through $R$. We may assume that $H$ has length greater than six since otherwise $W$ is empty. Let $X_1$ be the set of all $(c_1, c_2)$-strong vertices of $G_F$, and let $X_2$ be the set of all $(c_1, c_2)$-strong vertices of $G_F \setminus X_1$. Note that $X_1$ and $X_2$ can be constructed in time $O(|V(G)|^3)$. If $v$ is $(c_1, c_2)$-strong, then $v$ has a neighbor in $H_L^*$ and a neighbor in $H_R^*$, so $v \in C$. It follows that $X_1 \cup X_2 \subseteq C$. We claim that $W = X_1 \cup X_2$ contains all $F$-heavy vertices $v$ such that $v$ is anticomplete to $\{c_1, c_2, \ell_1, r_1, \ell_2, r_2\}$.
By Theorem 2.13, $X_1$ contains all $F$-heavy vertices $v$ in $G_F$ such that $v$ is not a hub of $H$. Now, consider $G_F \setminus X_1$. Every $F$-heavy vertex in $G_F \setminus X_1$ is a hub. Suppose $v \in V(G_F \setminus X_1)$ is a major vertex for $H$ and $v$ is $F$-light. By Lemma 4.2, $v \in L$ or $v \in R$. Without loss of generality suppose $v \in L$. Since $v$ is a major vertex for $H$ and $v \in V(G_F \setminus X_1)$, it follows that $N(v) \cap (H_L^* \setminus \{\ell_1, \ell_2\})$ is not contained in a path of length three, so there exists a shorter path from $\ell'_1$ to $\ell'_2$ in $L$ through $v$, a contradiction. Therefore, every major vertex for $H$ in $G_F \setminus X_1$ is $F$-heavy, so every major vertex for $H$ in $G_F \setminus X_1$ is a hub. Then, it follows from Theorem 2.13 that $X_2$ contains every $F$-heavy vertex of $H$ in $G_F \setminus X_1$.

Finally, let $v$ be an $F$-heavy vertex in $G$ such that $v$ is anticomplete to $\{c_1, c_2, \ell_1, r_1, \ell_2, r_2\}$. If $v$ is not a hub, then $v$ is an $F$-heavy vertex in $G_F$, so $v \in X_1$. If $v$ is a hub and $v \notin X_1$, then $v$ is an $F$-heavy vertex of $G_F \setminus X_1$, so $v \in X_2$. $\square$

**Lemma 4.4.** *Given an optimal frame $F$ of $C$, one can construct in polynomial time an $F$-hole $H$.*

*Proof.* By Lemma 4.3, we can construct the set $W = W(F) \subseteq C$ of all $F$-heavy vertices $v$ such that $v$ is anticomplete to $\{c_1, c_2, \ell_1, \ell_2, r_1, r_2\}$. Let $H$ be the graph given by the union of $V(F)$, a shortest path $Q_L$ from $\ell'_1$ to $\ell'_2$ through $G_F \setminus W$, and a shortest path $Q_R$ from $r'_1$ to $r'_2$ through $G_F \setminus W$. We claim that $H$ is an $F$-hole.

If $Q_L \subseteq L$ and $Q_R \subseteq R$, then clearly $H$ is an $F$-hole, so assume without loss of generality that $Q_L \not\subseteq L$. Let $\ell^*$ be the vertex of $Q_L \setminus L$ closest to $\ell'_1$ on $Q_L$. Since $\ell^*$ has a neighbor in $L$ and $\ell^* \notin L$, it follows that $\ell^* \in C$. Suppose $\ell^*$ is $F$-heavy. Since $W$ contains all $F$-heavy vertices anticomplete to $\{c_1, c_2, \ell_1, \ell_2, r_1, r_2\}$, it follows that $\ell^*$ has a neighbor in $\{c_1, c_2, \ell_1, \ell_2, r_1, r_2\}$, a contradiction. Therefore, $\ell^*$ is $F$-light. Let $J$ be an $F$-hole. Let $P_R$ be a path from $\ell^*$ to $J_R^*$ through $R$, and let $P_L$ be a path from $\ell^*$ to $J_L^*$ contained in $\ell^*-Q_L-\ell'_1$. Consider the path $P = P_L-\ell^*-P_R$ and let $p_k$ be the end of $P_L$ with neighbors in $J_L^*$. Suppose $P$ is of length at least two. By Lemma 3.5, it follows that either $p_k$ is adjacent to $c_1$ or $p_k$ is a pendant with $N_J(p_k) = \{\ell_1\}$. Since $P_L \subseteq V(G_F \setminus W)$, $p_k$ is not adjacent to $c_1$ or $\ell_1$, a contradiction. Therefore, $P$ is of length at most one. Because $\ell^*$ is $F$-light and $\ell^*$ is anticomplete to $\{c_1, c_2, \ell_1, \ell_2, r_1, r_2\}$, it follows that $\ell^*$ does not have a neighbor in both $J_L^*$ and $J_R^*$. Therefore, $P$ has length exactly one, and $P$ and $J$ contradict Lemma 2.9. $\square$

By Lemma 4.4, we can construct an $F$-hole $H$. Let $c_3 \in C$ be $F$-light, and let $P = p_{k-1}-\dots-p_1-c_3-q_1-\dots-q_5$ be a $c_3$-butterfly for $H$. By Theorem 3.9, $c_3$ is not a central vertex of $P$. We call $c_3$ an $L$-end vertex if $c_3 = p_k$, and an $L$-adjacent vertex if $c_3 = p_{k-1}$. We define similarly $R$-end and $R$-adjacent. The following lemma shows that every $L$-adjacent vertex is in the neighborhood of two vertices in $L$ and that every $R$-adjacent vertex is in the neighborhood of two vertices in $R$.

**Lemma 4.5.** *Let $X \subseteq N(H_L^*) \cap L$ be a minimal subset of $N(H_L^*) \cap L$ such that every $L$-adjacent vertex has a neighbor in $X$. Then, $|X| \le 2$. Similarly, let $Y \subseteq N(H_R^*) \cap R$ be a minimal subset of $N(H_R^*) \cap R$ such that every $R$-adjacent vertex has a neighbor in $Y$. Then, $|Y| \le 2$.*

*Proof.* Suppose $|X| > 2$ and let $x_1, x_2, x_3 \in X$. It follows from the minimality of $X$ that for every $x_i \in X$ there exists $y_i \in C$ such that $y_i$ is $L$-adjacent and $N_X(y_i) = \{x_i\}$. For $i = 1, 2, 3$, let $P_i$ be the right wing of a $y_i$-butterfly. Let $A = H_L^*$ and let $B = (P_1 \setminus \{y_1\}) \cup (P_2 \setminus \{y_2\}) \cup (P_3 \setminus \{y_3\}) \cup H_R^*$. Then, $A$ is anticomplete to $B$, $G[A]$ and $G[B]$ are connected, and for $i = 1, 2, 3$, $x_i$ has a neighbor in $A$ and is anticomplete to $B$, and $y_i$ has a neighbor in $B$ and is anticomplete to $A$. It follows that $A \cup B \cup \{x_1, x_2, x_3\} \cup \{y_1, y_2, y_3\}$ is a 3- creature, contradicting Lemma 4.1. $\square$

Let $X = \{x_1, x_2\}$ and $Y = \{y_1, y_2\}$ be as in Lemma 4.5 (so possibly $x_1 = x_2$ or $y_1 = y_2$). Let $M_1(C) = (x_1, x_2, y_1, y_2)$. Let $C_L = N(H_L^* \cup \{x_1, x_2\})$ and $C_R = N(H_R^* \cup \{y_1, y_2\})$. Note that $C_L$ and $C_R$ depend only on $H$ and $M_1(C)$.
**Lemma 4.6.** $C_L \cap C_R \subseteq C \subseteq C_L \cup C_R$.

*Proof.* It follows from the definition of $C_L$ that $C_L \subseteq L \cup C$. Similarly, $C_R \subseteq R \cup C$. Since $L$ and $R$ are disjoint, it follows that $C_L \cap C_R \subseteq C$. Next, suppose $c \in C$. Since $\{c_1, c_2\} \subseteq C_L \cap C_R$, we may assume that $c \in C \setminus \{c_1, c_2\}$. If $c$ is $F$-heavy, then by Lemma 3.4 $c$ is $(c_1, c_2)$-heavy with respect to $H$, and hence $c$ has neighbors in both $H_L^*$ and $H_R^*$, so $c \in C_L \cap C_R$. Therefore, we may assume that $c$ is $F$-light. By Theorem 3.9, $c$ is either $L$-end, $L$-adjacent, $R$-end, or $R$-adjacent. If $c$ is $L$-end, then $c$ has a neighbor in $H_L^*$. If $c$ is $L$-adjacent, it follows from Lemma 4.5 that $c$ has a neighbor in $\{x_1, x_2\}$. Therefore, if $c$ is $L$-end or $L$-adjacent, then $c \in C_L$. By symmetry, if $c$ is $R$-end or $R$-adjacent, $c \in C_R$. Hence, $C \subseteq C_L \cup C_R$. $\square$

Let $C_1 = C_L \cap C_R$. Note that for every $s \in C$, if there exists an $s$-butterfly $P$ of length zero or one, then $s \in C_1$. Let $D = V(G) \setminus (H \cup C_L \cup C_R)$. The following lemmas show how to identify the vertices of $C \setminus C_1$.

**Lemma 4.7.** Let $S \subseteq C_R \cap R$ be a minimal subset of $C_R \cap R$ such that for every vertex $z \in (C_L \setminus C_R) \cap C$, there exists a path from $z$ to $S$ through $D$. Then, $|S| \le 2$. Similarly, let $T \subseteq C_L \cap L$ be a minimal subset of $C_L \cap L$ such that for every vertex $z \in (C_R \setminus C_L) \cap C$, there exists a path from $z$ to $T$ through $D$. Then, $|T| \le 2$.

*Proof.* First, note that for every vertex $z \in (C_L \setminus C_R) \cap C$ there exists a path from $z$ to $C_R \cap R$ through $D$ given by a subpath of the right wing of a $z$-butterfly. Suppose $|S| > 2$ and let $s_1, s_2, s_3 \in S$. By the minimality of $S$, it follows that there exist $z_1, z_2, z_3 \in (C_L \setminus C_R) \cap C$ such that there exists a path $P_i$ from $z_i$ to $s_i$ through $D$ for $i = 1, 2, 3$, and there does not exist a path from $z_i$ to $s_j$ through $D$ for $1 \le i \ne j \le 3$. Let $z'_1, z'_2, z'_3$ be the neighbors of $z_1, z_2, z_3$ in $P_1, P_2, P_3$, respectively. Let $A = H_L^* \cup \{x_1, x_2\}$ and let $B = (P_1 \setminus \{z_1, z'_1\}) \cup (P_2 \setminus \{z_2, z'_2\}) \cup (P_3 \setminus \{z_3, z'_3\}) \cup (H_R^* \cup \{y_1, y_2\})$. Then, $A$ is anticomplete to $B$, $G[A]$ and $G[B]$ are connected, and for $i = 1, 2, 3$ $z_i$ has a neighbor in $A$ and is anticomplete to $B$, and $z'_i$ has a neighbor in $B$ and is anticomplete to $A$. It follows that $A \cup B \cup \{z_1, z_2, z_3\} \cup \{z'_1, z'_2, z'_3\}$ is a $3$- creature, contradicting Lemma 4.1. $\square$

Let $S = \{r_a, r_b\}$ and $T = \{\ell_a, \ell_b\}$ be as in Lemma 4.7 (possibly $r_a = r_b$ or $\ell_a = \ell_b$). Let $M_2(C) = (\ell_a, \ell_b, r_a, r_b)$. Let $C_2$ be the set of all vertices $c \in C_L$ such that there exists a path $P$ from $c$ to $\{r_a, r_b\}$ through $D$. Similarly, let $C_3$ be the set of all vertices $c \in C_R$ such that there exists a path $P$ from $c$ to $\{\ell_a, \ell_b\}$ through $D$. Note that $C_2$ and $C_3$ depend only on $H$, $W$, $C_L$, $C_R$, and $M_2(C)$.

**Lemma 4.8.** $C_2 \cup C_3 \subseteq C$.

*Proof.* Suppose $c \in C_L$ such that there exists a path $P$ from $c$ to $\{r_a, r_b\}$ through $D$. Since $c \in C_L$, $c$ has a neighbor in $L$, so some vertex of $P$ belongs to $C$. Since, by Lemma 4.6, $C \subseteq C_L \cup C_R$, no vertex of $P \setminus \{c\}$ is in $C$. It follows that $c \in C$. Therefore, $C_2 \subseteq C$. By symmetry, $C_3 \subseteq C$. $\square$

**Lemma 4.9.** $C = C_1 \cup C_2 \cup C_3$. In particular, $C$ is uniquely determined by $F$, $M_1(C)$, and $M_2(C)$.

*Proof.* By Lemmas 4.6 and 4.8, it follows that $C_1 \cup C_2 \cup C_3 \subseteq C$. Consider $c \in C$. We may assume $c \notin C_1$. Then, by Lemma 4.6, either $c \in (C_L \setminus C_R) \cap C$ or $c \in (C_R \setminus C_L) \cap C$. If $c \in (C_L \setminus C_R) \cap C$, it follows from Lemma 4.7 that there is a path $P$ from $c$ to $\{r_a, r_b\}$, so $c \in C_2$. Similarly, if $c \in (C_R \setminus C_L) \cap C$, then $c \in C_3$. Therefore, $C \subseteq C_1 \cup C_2 \cup C_3$. $\square$

Let $C(F, M_1(C), M_2(C)) = C_1 \cup C_2 \cup C_3$ be the set constructed from $F$, $M_1(C)$, and $M_2(C)$, as described in this section. We proved that if $C$ is a proper separator and $F$ is an optimal frame of $C$, then $C(F, M_1(C), M_2(C)) = C$. The following corollary is a summary of the results presented in Section 4 so far.
**Corollary 4.10.** Given the tuples $F, M_1$, and $M_2$, one can construct $C(F, M_1, M_2)$ in polynomial time. Further, if $F$ is an optimal frame of $C$, then $C(F, M_1(C), M_2(C)) = C$.

Finally, we prove Theorem 1.2, which we restate here for convenience. Recall that by [3], to construct a list of all minimal separators of a graph, it suffices to prove that it has polynomially many minimal separators. We prove that $C$ has the polynomial separator property and provide in addition a polynomial-time algorithm to construct the minimal separators of graphs in $C$, which follows naturally from the results in this section.

**Theorem 4.11.** Let $G \in C$. One can construct a set $S$ of size at most $|V(G)|^{18}$ in polynomial time such that $S$ is the set of all minimal separators of $G$.

*Proof.* Let $S = \{\}$.
By Lemma 3.1, we add to $S$ all minimal clique separators of $G$. Next, we list the proper separators of $G$. Let $T = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2, x_1, x_2, y_1, y_2, \ell_a, \ell_b, r_a, r_b)$ be an 18-tuple consisting of vertices in $V(G)$. Let $F^T = (c_1, c_2, \ell'_1, \ell_1, r_1, r'_1, \ell'_2, \ell_2, r_2, r'_2)$, $M_1^T = (x_1, x_2, y_1, y_2)$, and $M_2^T = (\ell_a, \ell_b, r_a, r_b)$. For every 18-tuple $T$, let $C^T = C(F^T, M_1^T, M_2^T)$. By Corollary 4.10, $C^T$ can be constructed in polynomial time. We can test in time $O(|E(G)||V(G)|)$ whether $C^T$ is a minimal separator of $G$. We add $C^T$ to $S$ if and only if $C^T$ is a minimal separator of $G$. Clearly, $S$ has size at most $|V(G)|^{18}$ and can be constructed in polynomial time.

It remains to show that $S$ contains every minimal separator of $G$. Let $C$ be a minimal separator of $G$. We may assume that $C$ is proper. Let $F$ be an optimal frame of $C$ and let $T$ be the 18-tuple given by the union of $F$, $M_1(C)$, and $M_2(C)$, in that order. It follows from Corollary 4.10 that $C^T = C$, so $C \in S$. $\square$

## References

[1] T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzążewski, P. Seymour. "Induced subgraphs of bounded treewidth and the container method", *arXiv preprint*, arXiv:2003.05185 (2020).

[2] I. Adler, N.K. Le, H. Müller, M. Radovanović, N. Trotignon, K. Vušković. "On rank-width of (diamond, even hole)-free graphs", *Discrete Mathematics and Theoretical Computer Science*, 19(1) (2017).

[3] A. Berry, J.P. Bordat, O. Cogis. "Generating all the minimal separators of a graph", In *Lecture Notes in Computer Science*, Workshop on Graph-theoretic Concepts in Computer Science, WG (1999), Vol. 1665, Springer, Berlin, 1999.

[4] A. Berry, R. Pogorelcnik, G. Simonet. "An introduction to clique minimal separator decomposition", *Algorithms*, 3(2) (2010), 197-215.

[5] V. Bouchitté, I. Todinca. "Treewidth and minimum fill-in: Grouping the minimal separators", *SIAM J. Comput.*, 31 (1)(2001), 212-232.

[6] V. Bouchitté, I. Todinca. "Listing all potential maximal cliques of a graph", *Theor. Comput. Sci.*, 276 (1-2)(2002), 17-32.

[7] M. Chudnovsky, S. Thomassé, N. Trotignon, K. Vušković. "Maximum independent sets in (pyramid, even hole)-free graphs", *arXiv preprint*, arXiv:1912.11246 (2019).

[8] M. Conforti, B. Gerards, K. Pashkovich. "Stable sets and graphs with no even holes", *Mathematical Programming*, 153(1) (2015), 13-39.

[9] F.V. Fomin, Y. Villanger. "Finding induced subgraphs via minimal triangulations", In *27th International Symposium on Theoretical Aspects of Computer Science*, STACS (2010), 383-394. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.

[10] A. Grzesik, T. Klimošová, M. Pilipczuk, M. Pilipczuk. "Polynomial-time algorithm for maximum weight independent set on $P_6$-free graphs", In *Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA (2019), 1257-1271.

[11] D. Lokshantov, M. Vatshelle, Y. Villanger. "Independent set in $P_5$-free graphs in polynomial time", In *Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA (2014), 570-581.