# On graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph

Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon

## ► To cite this version:

Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon. On graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. 2007. halshs-00180961

HAL Id: halshs-00180961

https://shs.hal.science/halshs-00180961

Submitted on 22 Oct 2007

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

UNIVERSITÉ PARIS 1
- PANTHÉON - SORBONNE -

Documents de Travail du
Centre d'Economie de la Sorbonne

CES Working Papers

<figure><img src="image_3.png" /></figure>

On graphs that do not contain a subdivision of the
complete graph on four vertices as an induced subgraph

Benjamin LEVEQUE, Frédéric MAFFRAY, Nicolas TROTIGNON

2007.51

<figure><img src="image_4.png" /></figure>

CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE

Maison des Sciences Économiques, 106-112 boulevard de L'Hôpital, 75647 Paris Cedex 13

http://ces.univ-paris1.fr/cesdp/CES-docs.htm

ISSN : 1955-611X
# On graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph

Benjamin Lévêque,\* Frédéric Maffray\*, Nicolas Trotignon\dagger

October 19, 2007

## Abstract

We prove a decomposition theorem for graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph.

AMS Classification: 05C75

## 1 Introduction

Here graphs are simple. We use the standard notation from [2]. In particular $uvw$ denotes the path on vertices $uvw$ with edges $uv, vw$. We also use the notation $u-v-w$. These notations are formally equivalent, but we use the second one when we want to emphasize that the path is an induced subgraph of some graph that we are working on. When $G, G'$ are graphs, we denote by $G \cup G'$ the graph whose vertex set is $V(G) \cup V(G')$ and whose edge set is $E(G) \cup E(G')$.

We say that $G$ contains $H$ when $H$ is isomorphic to an induced subgraph of $G$. We say that $H$ is an *ISK4* of a graph $G$ when $H$ is an induced subgraph of $G$ and $H$ is a subdivision of $K_4$. A graph that does not contain any subdivision of $K_4$ is said to be *ISK4-free*. Our main result is Theorem 8.1, saying that every ISK4-free graph is either in some basic class or has some special cutset. In [3], it is mentioned that deciding in polynomial time whether a given graph is ISK4-free is an open question of interest. This question was our initial motivation. But our theorem does not lead to a polynomial-time recognition algorithm so far.

A *branch-vertex* in a graph $G$ is a vertex of degree at least 3. A *branch* is a path of $G$ of length at least one whose ends are branch vertices and whose internal vertices are not (so they all have degree 2). Note that a branch of $G$ whose ends are $u, v$ has at most one chord: $uv$. A *theta* is a connected graph with exactly two vertices of degree three, all the other vertices of degree two, and three branches,

<footnote>\*Laboratoire G-SCOP, 46 Avenue Félix Viallet, 38031 Grenoble Cedex, France. (benjamin.leveque@g-scop.inpg.fr, Frederic.Maffray@g-scop.inpg.fr)</footnote>

<footnote>†Université Paris I, Centre d'Économie de la Sorbonne, 106-112 boulevard de l'Hôpital, 75647 Paris cedex 13, France. nicolas.trotignon@univ-paris1.fr</footnote>

<footnote>This work has been partially supported by ADONET network, a Marie Curie training network of the European Community.</footnote>
each of length at least two. A *prism* is a graph that is the line-graph of a theta. A *wheel* is a graph that consists of a hole $H$ plus a vertex $x \notin H$, called the *hub* of the wheel, that sees at least four vertices of $H$.

**Lemma 1.1** Let $G$ be an ISK4-free graph. Then either $G$ is a series-parallel graph, or $G$ contains a prism, or $G$ contains a wheel or $G$ contains $K_{3,3}$.

**PROOF** — If $G$ is not series-parallel, then it is a well known fact that $G$ contains a subdivision $H$ of $K_4$ as a possibly non-induced subgraph. Let us choose such a subgraph $H$ minimal. So $H$ is obtained by first taking a subdivision $H'$ of $K_4$ whose vertex set is $\{a, b, c, d\}$. The branches of $H'$ are called $P_{ab}, P_{ac}, P_{ad}, P_{bc}, P_{bd}, P_{cd}$ with the obvious notation. Then $H$ is obtained from $H'$ by adding several edges between the vertices of $H'$. Since $G$ is ISK4-free, there is at least one such edge $e$ in $H$.

If $e$ is incident to one of $a, b, c, d$, say $a$ up to symmetry, then the other end of $e$ is in none of $P_{ab}, P_{ac}, P_{ad}$ by minimality of $H$. Also $P_{ab}, P_{ac}, P_{ad}$ have all length one for otherwise, by deleting the interior vertices of one of them, we contradict the minimality of $H$. If $H$ has a chord non-incident to $a$ then by deleting one of $b, c, d$ we contradict the minimality of $H$. Hence, every chord of $H$ is incident to $a$ and $H$ is a wheel with hub $a$.

If $e$ is between two branches of $H$ with a common end, $P_{ab}$ and $P_{ad}$ say up to symmetry, then let us put $e = uv, u \in P_{ab}, v \in P_{ad}$. Vertices $a, u$ are adjacent for otherwise by deleting the interior vertices of $a-P_{ab}-u$ we contradict the minimality of $H$. Similarly, $a, v$ are adjacent, and $P_{bc}, P_{bd}, P_{cd}$ all have length one. So, $G$ contains a prism $H'$ as a possibly non induced subgraph, whose triangles are $auv, bcd$. If $H' \neq H$ then $H$ has an edge $e'$ that is not an edge of $H'$. Up to symmetry, we assume that $e'$ has an end $u'$ in $uP_{ab}b$ and an end $v'$ in $vP_{vd}d$. Since $e \neq e'$ we may assume $u \neq u'$. So, $H \setminus u$ contains a subdivision of $K_4$ and this contradicts the minimality of $H$. Hence $H$ is a prism.

If $e$ is between two branches of $H$ with no common end, $P_{ad}$ and $P_{bc}$ say up to symmetry, then let us put $e = uv, u \in P_{ad}, v \in P_{bc}$. As above, we prove that $P_{ab}, P_{ac}, P_{bd}, P_{cd}$ all have length one so that $ua, ud, vb, vc$ are all edges of $H$. Hence $H$ is isomorphic to $K_{3,3}$. $\square$

When $G$ is a graph, $K$ an induced subgraph, and $C$ a set of vertices disjoint from $K$, the *attachment* of $C$ over $K$ is $N(C) \cap V(K)$, that we also denote by $N_K(C)$.

## 2 $K_{3,3}$

Here we decompose ISK4-free graphs that contain $K_{p,q}, p, q \ge 3$. When $H$ is isomoprhic to $K_{p,q}$, we denote by $A, B$ the two sides of the bipartition, and we put $A = \{a_1, \dots, a_p\}$ and $B = \{b_1, \dots, b_q\}$. A vextex $v$ of a graph is *complete* to a set of vertices $C$ if $v$ is adjacent to every vertex in $C$. A vertex $v$ is *anticomplete* to a set of vertices $C$ if $v$ is adjacent to no vertex in $C$.
**Lemma 2.1** Let $G$ be an ISK4-free graph, and $H$ be a maximal induced $K_{p,q}$ in $G$, such that $p,q \ge 3$. Let $v \notin H$ be a vertex of $G$. Then the attachment of $v$ over $H$ is either empty, or consists of one vertex or of one edge or is $V(H)$.

**PROOF** — Suppose first that $v$ is adjacent at least two vertices in $A$, say $a_1, a_2$. Then $v$ is either adjacent to every vertex in $B$ or to no vertex in $B$. Because otherwise, up to symmetry, $v$ sees $b_1$ and misses $b_2$, and $\{a_1, a_2, b_1, b_2, v\}$ is an ISK4. If $v$ has no neighbor in $B$, then $v$ sees every vertex in $A$, because otherwise $va_3 \notin E(G)$ say, and $\{a_1, a_2, a_3, b_1, b_2, v\}$ is an ISK4. So, $v$ is complete to $A$ and anticomplete to $B$ contradictory to the maximality of $H$. If $v$ is complete to $B$ then $v$ is adjacent to at least two vertices in $B$ and symmetrically we can prove that $v$ is complete to $A$. So, the attachment of $v$ is $H$.

Hence we may assume that $v$ is adjacent to at most one vertex in $A$, and symmetrically in $B$. Hence, $N_H(v)$ is either empty, or consists of one vertex or of one edge. $\square$

**Lemma 2.2** Let $G$ be an ISK4-free graph, and $H$ be a maximal induced $K_{p,q}$ of $G$, such that $p, q \ge 3$. Let $U$ be the set of those vertices of $V(G) \setminus H$ that are complete to $H$. Let $C$ be a component of $G \setminus (H \cup U)$. Then the attachment of $C$ over $H$ is either empty or consists of one vertex or of one edge.

**PROOF** — Suppose not. Then up to symmetry we may assume that there are vertices $c_1, c_2$ in $C$ such that $|N(\{c_1, c_2\}) \cap D| \ge 2$ where $D$ is one of $A, B$. Since $C$ is connected, there is a path $P = c_1 - \cdots - c_2$ in $C$ from $c_1$ to $c_2$. We choose $c_1, c_2$ such that $P$ is minimal. Up to symmetry, we assume that $c_1a_1, c_2a_2 \in E(G)$. Note that by Lemma 2.1, $P$ has length at least 1. If $a_3$ has a neighbor in $P$, then by Lemma 2.1 this neighbor must be an interior vertex of $P$, but this contradicts the minimality of $P$. So, $a_3$ has no neighbor in $P$.

If no vertex in $B$ has neighbors in $P$, then $V(P) \cup \{a_1, a_2, a_3, b_1, b_2\}$ induces an ISK4. If exactly one vertex in $B$, say $b_1$, has neighbors in $P$, then $V(P) \cup \{a_1, a_2, a_3, b_2, b_3\}$ induces an ISK4. If at least two vertices in $B$, say $b_1, b_2$, have neighbors in $P$, then by Lemma 2.1 and by minimality of $P$ we may assume $N(b_1) \cap V(P) = \{c_1\}$ and $N(b_2) \cap V(P) = \{c_2\}$. Hence $V(P) \cup \{a_1, a_3, b_1, b_2\}$ induces an ISK4. In every case there is a contradiction. $\square$

**Lemma 2.3** Let $G$ be an ISK4-free graph that contains $K_{3,3}$. Then either $G$ is a bipartite complete graph, or $G$ is a tripartite complete graph, or $G$ has a clique-cutset of size at most 3.

**PROOF** — Let $H$ be a maximal $K_{p,q}$, $p, q \ge 3$, in $G$ and $U$ be the set of those vertices that are complete to $H$. Note that $U$ is a stable set because if $U$ contains an edge $uv$ then $\{u, v, a_1, b_1\}$ is an ISK4.

If $V(G) = H \cup U$, then $G$ is either a tripartite complete graph (if $U \ne \emptyset$) or a bipartite complete graph (if $U = \emptyset$). Else, let $C$ be a component of $G \setminus (H \cup U)$. We claim that $|N(C) \cap U| \le 1$. Else, consider $u \ne v$ in $N(C) \cap U$ and a minimal path $P$ in $C$ from a neighbor of $u$ to a neighbor of $v$. By Lemma 2.2, we may assume
that $a_3, b_3$ have no neighbor in $C$ (hence in $P$). So $P \cup \{u, v, a_3, b_3\}$ is an ISK4, a contradiction. This proves our claim. Now, by Lemma 2.2, $N(C) \cap (H \cup U)$ is a clique-cutset of $G$ of size at most 3. $\square$

# 3 Cyclically 3-connected graphs

A *separation* of a graph $H$ is a pair $(A, B)$ of subsets of $V(H)$ such that $A \cup B = V(H)$ and there are no edges between $A \setminus B$ and $B \setminus A$. It is *proper* if both $A \setminus B$ and $B \setminus A$ are non-empty. The order of the separation is $|A \cap B|$. A *k-separation* is a separation $(A, B)$ such that $|A \cap B| \le k$. A separation $(A, B)$ is *cyclic* if both $H[A]$ and $H[B]$ has cycles. A graph $H$ is *cyclically 3-connected* if it is 2-connected, not a cycle, and there is no cyclic 2-separation. Note that a cyclic 2-separation of any graph is proper.

Here we state simple lemmas about cyclically 3-connected graphs needed in the next section. Most of them are stated and proved implicitly in [1], Section 7. But they are worth stating separately here: they are needed at least for the second time and avoiding writing their proof would be convenient for another time. A cyclically 3-connected graph has at least four vertices and $K_4$ is the only cyclically 3-connected graph on four vertices. As any 2-connected graph that is not a cycle, a cyclically 3-connected graph is edge-wise partitioned into its branches.

**Lemma 3.1** Let $H$ be a cyclically 3-connected graph. For every proper 2-separation $(A, B)$ of $H$, $A \cap B$ consists of two non-adjacent vertices, one of $H[A]$, $H[B]$ is a path, and thus is included in a branch of $H$, and the other one has a cycle.

*PROOF* — Since $(A, B)$ is proper, $A \cap B$ is a cutset, and so it has size two since $H$ is 2-connected. We put $A \cap B = \{a, b\}$. Since $(A, B)$ is not cyclic, up to symmetry, $H[A]$ has no cycle. Note that $H[A]$ contains a path $P$ from $a$ to $b$ since otherwise one of $a, b$ is a cutvertex of $H$, and this contradicts $H$ being 2-connected. Actually, $H[A] = P$ for otherwise $H[A]$ is a tree with at least one vertex $c$ of degree 3, and $c$ is a cutvertex of this tree that is also a cutvertex of $H$, a contradiction again. Since $(P, B)$ is a separation, every internal vertex of $P$ has degree 2 in $H$, so $P$ is included in a branch of $H$ and $a, b$ are members of a branch of $H$ as claimed. If $B$ has no cycle, then by the same proof as we wrote for $A$, $H[B]$ is a path. So, $H$ is a cycle, a contradiction. $\square$

**Lemma 3.2** Let $H$ be a cyclically 3-connected graph and $a, b$ be two adjacent vertices of $H$. Then $\{a, b\}$ is not a cutset of $H$.

*PROOF* — Follows directly from Lemma 3.1. $\square$

**Lemma 3.3** Let $H$ be a cyclically 3-connected graph, $a, b$ be two branch vertices of $H$, and $P_1, P_2, P_3$ be three induced paths of $H$ whose ends are $a, b$. Then either:

* $P_1, P_2, P_3$ are branches of $H$ of length at least two and $H = P_1 \cup P_2 \cup P_3$, and $H$ is a theta;
* there exist integers $i, j$ where $1 \le i < j \le 3$ and a path $S$ of $H$ with an end in the interior of $P_i$, an end in the interior of $P_j$ and whose interior is disjoint of $V(P_1 \cup P_2 \cup P_3)$; and $P_1 \cup P_2 \cup P_3 \cup S$ is a subdivision of $K_4$.

**PROOF** — Let us put $H' = P_1 \cup P_2 \cup P_3$. Suppose $H = H'$. If $P_1$ is of length one, then $(V(P_1 \cup P_2), V(P_1 \cup P_3))$ is a cyclic 2-separation of $H$. So $P_1$, and similarly $P_2, P_3$ are of length at least two and the first output holds. So we may suppose $H \neq H'$. If the lemma fails then no path such $S$ exists. In particular there are no edges between the interior of any two of the three paths. The interiors of the three paths lie in distinct components of $H \setminus \{a, b\}$. Since $H$ is connected and $H \neq H'$, there exists some vertex in $V(H) \setminus V(H')$ with a neighbor $c$ in one of $P_1, P_2, P_3$. Since $H$ is 2-connected, $\{c\}$ is not a cutset of $H$ and there exists a path $R$ from $c$ to some other vertex $c'$ in $H'$. Since no path like $S$ exists, $R$ must have its two ends in the same branch of $H'$, say in $P_1$. It follows that $P_1$ has some interior vertices, and we call $B$ the component of $H \setminus \{a, b\}$ that contains the interior of $P_1$. Now, we put $A = \{a, b\} \cup V(H) \setminus C$, and we observe that $(A, B)$ is a cyclic 2-separation of $H$, a contradiction. $\square$

**Lemma 3.4** Let $H$ be a cyclically 3-connected graph and let $a, b$ be two branch vertices of $H$ such that there exist two distinct branches of $G$ linking them. Then $H$ is a theta.

**PROOF** — Let $P_1, P_2$ be two distinct branches of $H$ whose ends are $a, b$. We denote by $\mathring{P}$ the set of the interior vertices of a path $P$. So, we put $A = V(P_1 \cup P_2)$, $B = V(H) \setminus (\mathring{P}_1 \cup \mathring{P}_2)$ and observe that $(A, B)$ is a 2-separation of $H$. Since $H$ is not a cycle, $B$ contains at least three vertices, and $H[B]$ contains a shortest path $P_3$ from $a$ to $b$ since $H$ is 2-connected. We apply Lemma 3.3 to $P_1, P_2, P_3$. Since $P_1, P_2$ are branches, the second output cannot happen. So $H$ is a theta. $\square$

**Lemma 3.5** A graph $H$ is a cyclically 3-connected graph if and only if it is either a theta or a subdivision of a 3-connected graph.

**PROOF** — We remind the reader that according to the definition in [2], a 3-connected graph must have at least 4 vertices. So, thetas and 3-connected graphs are clearly cyclically 3-connected. Conversely, if $H$ is a cyclically 3-connected graph then let $H'$ be the multigraph on the branch vertices of $H$ obtained as follows: we link two vertices $a, b$ by an edge for every branch of $H$ with ends $a, b$.

If $H'$ has no multiple edge then $H'$ is a graph and $H$ is a subdivision of $H'$. Since $H$ is 2-connected, $H'$ is also 2-connected. We claim that $H'$ is 3-connected. Else $H'$ has a proper 2-separation $(A, B)$. Since $H'$ has minimum degree at least 3, it is impossible that $H'[A]$ is a path. So $H'[A]$ cannot be a tree since $H'$ is 2-connected, and it must contain a cycle. Symmetrically, $H'[B]$ must contain a cycle. Now we define $A'$ to be the union of $A$ and of the set of these vertices of degree two of $H$ that arise from subdividing edges of $H'[A]$. We define similarly $B'$. If $H'[A \cap B]$ is an edge and if some vertices of $H$ arise from the subdivision of that edge, then we put them
in $A'$. Now we observe that $(A', B')$ is a cyclic 2-separation of $H$, a contradiction. This proves our claim. It follows that $H$ is a subdivision of a 3-connected graph.

If $H'$ has at least one multiple edge, then there exists two vertices $a, b$ of $H$ and two branches $P, Q$ of $H$ with ends $a, b$. So, by Lemma 3.4, $H$ is a theta. $\square$

**Lemma 3.6** Let $H$ be a cyclically 3-connected graph and $a, b$ be two distinct vertices of $H$. If there is no branch that contains both $a, b$ then $H' = (V(H), E(H) \cup \{ab\})$ is a cyclically 3-connected graph and every graph obtained from $H'$ by subdividing $ab$ is cyclically 3-connected.

**PROOF** — The graph $H'$ is clearly 2-connected and not a cycle. So we have to prove that $H'$ has no cyclic 2-separation. For suppose it has one, $\{A, B\}$ say. Up to symmetry we may assume $a, b \in A$ because there is no edge between $A \setminus B$ and $B \setminus A$. Since $(A, B)$ is cyclic in $H'$, $B$ has a cycle in $H'$ and so in $H$. Hence, by Lemma 3.1, $A$ induces a path of $H$ and so it is included in a branch of $H$, contrary to our assumption.

By Lemma 3.5, $H'$ is a subdivision of a three connected graph since it cannot be a theta because of the edge $ab$. So, every graph that we obtain by subdividing $ab$ is a subdivision of a 3-connected graph, and so is cyclically 3-connected. $\square$

The statement of the following lemma is longer than its proof.

**Lemma 3.7** Let $H$ be a cyclically 3-connected graph, let $C$ be a cycle of $H$ and $a, b, c, d$ be four distinct vertices of $C$ that appear in this order on $C$ and such that $ab \in E(C)$ and $cd \in E(C)$. Let $P, Q$ be the paths respectively from $a$ to $d$ and from $b$ to $c$ that vertex-wise partition $C$. Suppose that the edges $ab, cd$ are in two distinct branches of $H$. Then there is a path $R$ with an end-vertex in $P$, an end-vertex in $Q$ and no interior vertex in $C$. Moreover, $R$ is not from $a$ to $b$, and not from $c$ to $d$

**PROOF** — For suppose there does not exist a path like $R$. Then $\{a, c\}$ is a cutset of $H$ that separates $b$ from $d$. So by Lemma 3.1, up to symmetry, we may assume that $aPdc$ is included in a branch of $H$. Also $\{b, d\}$ is a cutset, so one of $baPd, bQcd$ is included in a branch of $H$. If it is $bQcd$ then $\{a, b\}$ is a cutset of $H$ contradictory to Lemma 3.2. So it is $baPd$, and $baPdc$ is included in a branch of $H$. Hence, $ab, cd$ are in the same branch of $H$, and this contradicts our assumptions. $\square$

**Lemma 3.8** Let $H$ be a subdivision of $K_4$, let $P, Q$ be two distinct branches of $H$, and $T$ be a path with an end in a branch of $H$, an end in another branch of $H$ and whose interior in disjoint of $H$. Then $H \cup T$ has a subgraph that is a subdivision of $K_4$ and $P, Q, T$ are branches of this subgraph.

**PROOF** — We denote by $a, b, c, d$ the branch vertices of $H$, and by $P_{xy}$ the branch of $H$ whose ends are $x, y \in \{a, b, c, d\}$. Up to symmetries, $P, Q, T$ can be placed in several ways that we will describe and examine. Each time, will find the desired subdivision of $K_4$ by deleting the interior vertices and the edges of some $P_{xy}$ (for short, we simply say that we delete $\mathring{P}_{xy}$).

**Case 1:** $P, Q$ have one common end. Up to symmetry we suppose $P = P_{ab}, Q = P_{ac}$.
Suppose that $T$ has an end in one of $P, Q$. Up to symmetry, we suppose that $T$ has an end in $P$. If the other end is in $Q$, then delete $\vec{P}_{bc}$. If the other end is in $P_{ad}$ then delete $\vec{P}_{bd}$. If the other end is in $P_{bd}$ then delete $\vec{P}_{cd}$. If the other end is in $P_{bc}$ then delete $\vec{P}_{cd}$. If the other end is in $P_{cd}$ then delete $\vec{P}_{bd}$. From now on, we suppose that $T$ has ends in none of $P, Q$.

Suppose that $T$ has an end in one of $P_{bd}, P_{cd}$. Up to symmetry, we suppose that $T$ has one end in $P_{bd}$. If the other end is in $P_{cd}$ then delete $\vec{P}_{bc}$. If the other end is in $P_{ad}$ then delete $\vec{P}_{bd}$. If the other end is in $P_{bc}$ then delete $\vec{P}_{ad}$.

We are left with the case when $T$ has an end in $P_{ad}$ and an end in $P_{bc}$. Then delete $\vec{P}_{bd}$.

**Case 2:** $P, Q$ have no common ends. Up to symmetry we suppose that $P = P_{ab}$ and $Q = P_{cd}$.

Suppose that $T$ has an end in one of $P, Q$. Up to symmetry, we suppose that $T$ has an end in $P$. If the other end is in $Q$, then delete $\vec{P}_{bc}$. Else, up to symmetry we may assume that the other end is in $P_{bd}$. Then delete $\vec{P}_{bd}$. From now on, we suppose that $T$ has ends in none of $P, Q$.

If $T$ has its ends in two adjacent branches of $H$ then up to symmetry we assume that $T$ has an end in $P_{bd}$, an end in $P_{bc}$ and we delete $\vec{P}_{ac}$. Else, we may assume that $T$ has an end in $P_{ad}$, an end in $P_{bc}$ and we delete $\vec{P}_{bd}$. $\square$

# 4 Line-graph of substantial graphs

A *basic branch* in a graph is a branch such that no two vertices in it are members of a triangle. A branch in a graph is either *basic*, or is an edge *uv* and there is a common neighbor of *u*, *v*.

A *triangular subdivision* of $K_4$ is a subdivision of $K_4$ that contains a triangle. A *square* theta is theta that contains a square. Rephrased: a theta with two branches of length two. A *square* prism is a prism that contains a square. Rephrased, a prism with two basic branches of length one. Rephrased again, the line-graph of a square theta. A *square* subdivision of $K_4$ is a subdivision of $K_4$ such that the four vertices of degree three in it lie in a possibly non-induced square. Rephrased: a subdivision of $K_4$ where only two edges with no common ends are possibly subdivided. An induced square in a graph is *basic* if an even number of edges in it lie in a triangle of the graph. It easily checked that the line-graph of a subdivision $H$ of $K_4$ contains a basic square if and only if $H$ is a square subdivision of $K_4$, and that the vertices in any basic square of $L(H)$ arise from the edges of a square on the branch vertices of $H$. It easily checked that a prism contains only basic squares.

A *connected diamond* is a $K_4$ with one edge subdivided. So it is either a $K_4$ or a graph with four vertices $x, y, z, t$ that induce a diamond, plus a path $P$ of length at least two with end-vertices the two non-adjacent vertices of the diamond and no other edges. Then we say that $P$ *connects* the diamond. The fact that a connected diamond is an ISK4 and that no path can connect a diamond in an ISK4-free graph will be used with no explicit mention.

If $X, Y$ are two basic branches of a graph $G$, a *connection between* $X, Y$ is a path $P = p-\cdots-p'$ such that $p$ has neighbors in $X$, $p'$ has neighbors in $Y$, no interior
vertex of $P$ has neighbors in $X \cup Y$, and if $p \neq p'$ then $p$ has no neighbor in $Y$ and $p'$ has no neighbor in $X$.

When $S = \{u_1, u_2, u_3, u_4\}$ induces a square in a graph $G$ with $u_1, u_2, u_3, u_4$ in this order along the square, a connection of $S$ is an induced path of $G$, no interior vertex of which has a neighbor in $S$, with ends $p, p'$ such that either $p = p'$ and $N_S(p) = S$; or $N_S(p) = \{u_1, u_2\}$ and $N_S(p') = \{u_3, u_4\}$; or $N_S(p) = \{u_1, u_4\}$ and $N_S(p') = \{u_2, u_3\}$.

The line-graph of $K_4$ is isomorphic to $K_{2,2,2}$. It usually called the *octahedron*. It contains three basic squares. For every basic square $S$ of an octahedron $G$, the two vertices of $G \setminus S$ are both connexions of $S$. Note also that when $K$ is a square prism with a square $S$, then $V(K) \setminus S$ is a connection of $S$.

When $G$ is a graph, $H$ is a graph such that $L(H)$ is an induced subgraph of $G$, and $C$ is a connected induced subgraph of $V(G) \setminus L(H)$, we define several types that $C$ can have, according to its attachment over $L(H)$:

* $C$ is of type *branch* if the attachment of $C$ over $L(H)$ is included in a basic branch of $L(H)$;

* $C$ is of type *triangle* if the attachment of $C$ over $K$ is included in a triangle of $L(H)$;

* $C$ is of type *augmenting* if $C$ contains a connection $p-\cdots-p'$ of two distinct basic branches $X, Y$ of $L(H)$, $N_X(p)$ is an edge of $X$ and $N_Y(p')$ is an edge of $Y$. Moreover, there are no edges between $L(H) \setminus (X \cup Y)$ and $P$.

* $C$ is of type *square* if $L(H)$ contains a basic square $S$, and $C$ contains a connection $P$ of $S$. Moreover, there are no edges between $L(H) \setminus S$ and $P$.

Note that the types may overlap: a subgraph $C$ may be of more than one type. Since we view a vertex of $G$ as a connected induced subgraph of $G$, we may speak about the type of vertex with respect to $L(H)$.

**Lemma 4.1** Let $G$ be a graph that contains no triangular ISK4. Let $K$ be a prism that is an induced subgraph of $G$ and let $C$ be a connected induced subgraph of $G \setminus K$. Then $C$ is either of type *branch*, *triangle*, *augmenting* or *square* with respect to $K$.

*PROOF* — Let $X = x-\cdots-x'$, $Y = y-\cdots-y'$, $Z = z-\cdots-z'$ be the three basic branches of $K$ denoted in such a way that $xyz$ and $x'y'z'$ are triangles. Suppose that $C$ is not of type *branch* or *triangle* and consider an induced subgraph $P$ of $C$ minimal with respect to the property of being a connected induced subgraph, not of type *branch* or *triangle*.

(1) $P$ is a path with ends $p, p'$, no internal vertex of which has neighbors in $K$ and $N_K(P) = N_K(p, p')$ is not included in a basic branch or in a triangle of $K$.

If $P$ is a vertex, then our claim holds since by definition, $P$ is not of type *branch* or *triangle*. So, by minimality, $P$ is a path with ends $p, p'$ and we may assume that $P$ is has length at least one. Suppose that our claim fails. Then by minimality of $P$, $N_K(p) \subset A$ and $N_K(p') \subset B$, where $A, B$ are distinct basic-branch-or-triangle of $K$.
Also some interior vertex of $P$ must have neighbors in $K$. By minimality of $P$, the attachment of the interior of $P$ over $K$ is included in $A \cap B$. Since two distinct basic branches of $K$ are disjoint, two distinct triangles of $K$ are disjoint, we may assume that $N_K(p) \subseteq \{x, y, z\}$, $N_K(p') \subseteq X$ and some interior vertices of $P$ are adjacent to $x$. Note that $p$ has at most two neighbors in $\{x, y, z\}$ because $G$ has no $K_4$ and that $p$ must have at least one neighbor in $\{y, z\}$ for otherwise $P$ is of type branch. If $py, pz \in E(G)$ then since some interior vertex of $P$ has neighbor $x$, $P$ contains a subpath that connects the diamond $\{x, y, z, p\}$, a contradiction. Else, note that $p'$ has neighbors in $X \setminus x$ for otherwise $P$ is of type triangle. Let $v^R$ be the neighbor of $p'$ closest to $x'$ along $v$. Because of the symmetry between $y$ and $z$ we may assume $pz \in E(G)$, $py \notin E(G)$. So $z-p-P-p'$, $z-Z-z'$ and $z-y-Y-y'$ form a triangular ISK4, a contradiction. This proves (1).

Now, we consider two cases.

**Case 1:** $P$ is a connection between two basic branches of $K$ and has no neighbors in the third basic branch. So, we may assume that $p$ has neighbors $X$, $p'$ in $Y$ and none of $p, p'$ has neighbors in $Z$. Let $x^L$ (resp. $x^R$) be the neighbor of $p$ closest to $x$ (resp. to $x'$) along $X$. Up to the symmetry between $X$ and $Y$, we may assume $x^L x^R \notin E(G)$, for otherwise $C$ is of type augmenting and the lemma holds. Let $y^L$ (resp. $y^R$) be the neighbor of $p'$ closest to $y$ (resp to $y'$) along $Y$. If $x^L \neq x^R$ then, up to symmetry, we may assume $y^L \neq y'$. We observe that $p-x^L-X-x$, $p-x^R-X-x'-z'-Z-z$, $p-P-p'-y^L-Y-y$ form a triangular ISK4, a contradiction. So $x^L = x^R$ and symmetrically $y^L = y^R$. If $x^L$ is neither $x$ nor $x'$ then up to symmetry we may assume $y^L \neq y'$. We observe that $x^L-X-x$, $x^L-p-P-p'-y^L-Y-y$ and $x^L-X-x'-z'-Z-z$ form a triangular ISK4, a contradiction. So up to symmetry we may assume $x^L = x$ and $y^L = y'$ for otherwise there is a contradiction with (1). Now $x-X-x'$, $x-p-P-p'-y'$, $x-z-Z-z'$ form a triangular ISK4, a contradiction.

**Case 2:** We are not in Case 1.

Suppose first that one of $p, p'$ has at least two neighbors in a triangle of $K$. Then we may assume up to symmetry $px, py \in E(G)$, and $pz \notin E(G)$ because $G$ contains no $K_4$. By (1) and up to symmetry, $p'$ must have a neighbor either in $Y \setminus y$ or in $Z$. Note that either $p = p'$ or $N_K(p) = \{x, y\}$ for otherwise $p$ would contradicts the minimality of $P$. If $p'$ has a neighbor in $Z$ then let $w$ be such a neighbor closest to $z$ along $Z$. We observe that $p-P-p'-w-Z-z$ connects the diamond $\{p, x, y, z\}$. So, $p'$ has no neighbor in $Z$, and so it has neighbors in $Y \setminus y$. Let $w^L$ (resp. $w^R$) a neighbor of $p'$ closest to $y$ (resp. to $y'$) along $Y$. Note that $w^R \neq y$. If $p'$ has no neighbor in $X$ then $x-X-x'$, $x-p-P-p'-w^R-Y-y'$ and $x-z-Z-z'$ form a a triangular ISK4, so $p'$ has a neighbor in $X$ and we denote by $v^L$ (resp. $v^R$) such a neighbor closest to $x$ (resp. to $x'$) along $X$. If $p = p'$ then we are in Case 1, a contradiction. So, $p \neq p'$ and $p'$ contradicts the minimality of $P$ except if $v^L = v^R = x'$ and $w^L = w^R = y'$. So these two equalities hold and $p-P-p'-x'-z'-Z-z$ connects the diamond $\{p, x, y, z\}$ except if $X$ has length one, so $X$ has length one, and symmetrically, $Y$ has length one. We observe that $P$ is a connection of the basic square $\{x, y, x', y'\}$ of $K$, so $C$ is of type square.

So from now on we suppose that both $p, p'$ have at most one neighbor in a triangle of $K$. But at least one of $p, p'$ (say $p$) must have neighbors in more than one branch
of $K$ since otherwise we are in Case 1, a contradiction. So $p = p'$ by minimality of $P$, and $p$ has neighbors in $X, Y, Z$ for otherwise we are in Case 1, a contradiction. We may assume that $py, pz \notin E(G)$. Let $x^R, y^R, z^R$ be the neighbors of $p$ closest to $x', y', z'$ along $X, Y, Z$ respectively. Then $p-x^R-X-x', p-y^R-Y-y', p-z^R-Z-z'$ form a triangular ISK4, a contradiction. $\square$

**Lemma 4.2** Let $G$ be a graph that contains no triangular ISK4. Let $H$ be a sub-
division of $K_4$ such that $L(H)$ is an induced subgraph of $G$. Let $C$ be a connected
induced subgraph of $G \setminus L(H)$. Then $C$ is either of type branch, triangle, augmenting
or square with respect to $L(H)$.

**PROOF** — Let us denote by $a, b, c, d$ the four branch vertices of $H$. On Figure ??,
$L(H)$ is depicted with the notation for its vertices that we describe below. The
three edges incident to each vertex $x = a, b, c, d$ form a triangle in $L(H)$, which will
be labelled $T_x$. In $L(H)$, for every pair $x, y \in \{a, b, c, d\}$ there is one path with an
end in $T_x$ and an end in $T_y$, and no interior vertex in the triangles. We denote this
path by $P_{xy}$. Note that $P_{xy} = P_{yx}$, and these six distinct paths are vertex disjoint.
Some of these paths may have length 0. In the triangle $T_x$, we denote by $v_{xy}$ the
vertex that is the end of the path $P_{xy}$. Thus the basic branches of $L(H)$ are the
paths among $P_{ab}, P_{ac}, P_{ad}, P_{bc}, P_{bd}, P_{cd}$ that have length at least one. Note that
$L(H)$ may have as many as four more triangles than the $T$'s. The branch vertices
of $L(H)$ are $v_{ab}, v_{ac}, v_{ad}, v_{ba}, v_{bc}, v_{bd}, v_{ca}, v_{cb}, v_{cd}, v_{da}, v_{db}$ and $v_{dc}$. The subgraph
$L(H)$ has no other edges than those in the four triangles and those in the six paths.

Suppose that $C$ is neither of type branch nor triangle with respect to $L(H)$ and
consider an induced subgraph $P$ of $C$ minimal with respect to the property of being
a connected induced subgraph not of type branch or triangle.

(1) $P$ is a path with ends $p, p'$, no internal vertex of which has neighbors in $L(H)$ and $N_{L(H)}(P) = N_{L(H)}(p, p')$ is not included in a basic branch or in a triangle of $L(H)$.

If $P$ is a vertex, then our claim holds since by definition, $P$ is not of type branch or triangle. So, by minimality, $P$ is a path with ends $p, p'$ and we may assume that is has length at least one. Suppose that our claim fails. Then by minimality of $P$, $N_{L(H)}(p) \subset A$ and $N_{L(H)}(p') \subset B$, where $A, B$ are distinct basic-branch-or-triangle of $L(H)$. Also some interior vertex of $P$ must have neighbors in $L(H)$. By minimality of $P$, the attachment of the interior of $P$ over $L(H)$ is included in $A \cap B$. Since two distinct basic branches of $L(H)$ are disjoint, we may assume that $A = T_d$ and either $B = P_{ad}$, or $P_{ad}$ has length zero and $B = T_a$. In either cases, $A \cap B = \{v_{da}\}$. Note that $p$ has at most two neighbors in $T_d$ because $G$ has no $K_4$ and that $p$ must have at least one neighbor in $\{v_{db}, v_{dc}\}$ for otherwise the attachment of $P$ is included in $B$ and $P$ is of type branch or triangle. Note that $p'$ has neighbors in $B \setminus v_{da}$ for otherwise $P$ is of type triangle. If $pv_{db}, pv_{dc} \in E(G)$ then since some interior vertex of $P$ is adjacent to $v_{da}$, $P$ contains a subpath that connects the diamond $T_d \cup \{p\}$ a contradiction.

Else, $P \cup P_{ac} \cup B$ contains an induced path $Q$ from $p$ to $v_{ac}$, and no vertex of $Q$
has neighbors in $V(P_{cd}) \cup V(P_{bd} \cup P_{bc} \cup P_{ac})$. Now, we observe that $Q$, $P_{cd}$, $P_{bd}$, $P_{bc}$,
$P_{ac}$ form a triangular ISK4 (whose triangle is $T_c$) except if $Q$ goes through $v_{ab}$ and $P_{ab}$ has length zero (so $v_{ab} = v_{ba}$). But then, we must have $N_B(p') = \{v_{ab}\}$ since $Q$ has no chord, so $B = T_a$ and $P_{ad}$ has length zero. So, $v_{db}-P-p'-v_{ba}$, $v_{db}-P_{bd}-v_{bd}$ and $v_{db}-v_{dc}-P_{cd}-v_{cd}-v_{cb}-P_{cb}-v_{bc}$ form a triangular ISK4 except if $P_{db}$ has length zero. But then, $T = \{v_{da}, v_{db}, v_{ab}\}$ is a triangle, and $T$ is the attachment of $P$ over $L(H)$, so $P$ is of type triangle with respect to $L(H)$, a contradiction. This proves (1).

Suppose first that $P_{ab}$, $P_{ac}$, $P_{ad}$, $P_{bc}$, $P_{bd}$, $P_{cd}$ have all length zero. Then, $L(H)$ is the octahedron and is isomorphic to $K_{2,2,2}$. Note that $L(H)$ has no basic branch. For convenience, we rename the vertices of $L(H)$: $x, x', y, y', z, z'$ so that $xx', yy', zz' \notin E(L(H))$ and there are every possible other edge. If $P$ has neighbor at most one vertex in every pair $\{x, x'\}$, $\{y, y'\}$, $\{z, z'\}$ then up to symmetry we assume $N_{L(H)}(P) \subset \{x, y, z\}$, a contradiction. So, up to symmetry we may assume that $p$ is adjacent to $x$ and $p'$ to $x'$. Vertices $y, y', z, z'$ induce a square of $L(H)$ and $p$ cannot be adjacent to both vertices of an edge of that square since this would yield a $K_4$ in $G$. So we may assume $py, py' \notin E(G)$. If $pz, pz' \in E(G)$ then $p$ itself is a vertex not of type branch or triangle, so by minimality of $P$, $p = p'$. Since $S = \{x, x', z, z'\}$ is a basic square of $L(H)$ and $N_{L(H)}(P) = S$, $C$ is of type square. Hence we may assume that $x$ has at most one neighbor in $S$ and up to symmetry $pz' \notin E(G)$. Symmetrically, $p'$ has at most one neighbor in $S$. If $pz \notin E(G)$ then $P$ connects $\{x, z, y, x'\}$, $\{x, z', y, x'\}$ or $\{x, z, y', x'\}$, so $pz \in E(G)$. If $p'z' \notin E(G)$ then $P$ connects $\{x, z', y, x'\}$ or $\{x, z', y', x'\}$, so $p'z' \in E(G)$. Now we observe that $P$ is a connection of the square $\{x, z, x', z'\}$ of $L(H)$, hence $C$ is of type square.

Hence, up to symmetry, we may assume that $P_{ab}$ has length at least one. So the vertices of $P_{ad}$, $P_{bd}$, $P_{ab}$, $P_{ac}$, $P_{bc}$ induce a prism $K$ of $G$ and we may apply Lemma 4.1 to $K$ and $P$.

**Case 1:** $P$ is of type branch with respect to $K$. Suppose first that $N_K(C) \subseteq V(P_{ab})$. By (1), $P$ has neighbors in $P_{cd}$. So one end of $P$ (say $p$) has neighbors in $P_{ab}$, one end of $P$ (say $p'$) has neighbors in $P_{cd}$, and no proper subpath of $P$ has such a property. Let $v^L$ (resp. $v^R$) the neighbor of $p$ closest to $v_{ab}$ (resp. to $v_{ba}$) along $P_{ab}$. Up to the symmetry between $P_{ab}$ and $P_{cd}$ we may assume $v^L v^R \notin E(G)$ for otherwise $C$ is of type augmenting with respect to $L(H)$ and the lemma holds. Let $w^R$ the neighbor of $p'$ closest to $v_{cd}$ along $P_{cd}$. If $w^R = v_{dc}$ then we may assume $v^L \neq v_{da}$ for otherwise, $N_{L(H)}(P) \subseteq T_d$, contradictory to (1). Hence, $v_{dc}-p'-P-p-v^L-P_{ad}-v_{ad}$, $v_{dc}-P_{cd}-v_{cd}-v_{ca}-P_{ac}-v_{ac}$ and $v_{dc}-v_{db}-P_{db}-v_{bd}-v_{ba}P_{ab}-v_{ab}$ form a triangular ISK4, a contradiction. So, $w^R \neq v_{dc}$. If $v^L = v^R$ then $v^L-P_{ab}-v_{ab}-v_{ac}-P_{ac}-v_{ca}$, $v^L-P_{ab}-v_{ba}-v_{bc}-P_{bc}-v_{cb}$, $v^L-p-P-p'-w^R-P_{cd}-v_{cd}$ form a triangular ISK4, a contradiction. If $v^L \neq v^R$ then $p-v^L-P_{ab}-v_{ab}-v_{ac}-P_{ac}-v_{ca}$, $p-v^R-P_{ab}-v_{ba}-v_{bc}-P_{bc}-v_{cb}$, $p-P-p'-w^R-P_{cd}-v_{cd}$ form a triangular ISK4, a contradiction.

Hence we may assume up to symmetry $N_K(P) \subseteq V(P_{ad}) \cup V(P_{bd})$. If $P$ has neighbors in $P_{ad}$, $P_{bd}$ and $P_{cd}$ then let $v^a, v^b, v^c$ be the neighbors of $P$ closest to $v_{da}$, $v_{db}$ and $v_{dc}$ respectively along these paths. We observe that $V(P) \cup V(v^a-P_{ad}-v_{da}) \cup V(v^b-P_{bd}-v_{db}) \cup V(v^c-P_{cd}-v_{dc})$ induces a triangular ISK4, a contradiction. So, $P$ has no neighbor in at least one of $P_{ad}$, $P_{bd}$, $P_{cd}$.

If $P$ has no neighbors in $P_{bd}$ then by (1), one end of $P$ (say $p$) has neighbors in $P_{ad}$, an end of $P$ (say $p'$) has neighbors in $P_{cd}$, and no proper subpath of $P$ has
such a property. Let $v^R$ be the neighbor of $p$ closest to $v_{ad}$ along $P_{ad}$. If $p'$ has a unique neighbor $w$ in $P_{cd}$, then either $v^R = v_{da}$ so $w \neq v_{dc}$ by (1) and $w-P_{cd}-v_{dc}$, $w-p'-P-p-v_{da}$, $w-P_{cd}-v_{cd}-v_{cb}-P_{bc}-v_{bc}-v_{bd}-P_{bd}-v_{db}$ form a triangular ISK4; or $v^R \neq v_{da}$ and $w-p'-P-p-v^R-P_{ad}-v_{ad}$, $w-P_{cd}-v_{cd}-v_{ca}-P_{ac}-v_{ac}$, $w-P_{cd}-v_{dc}-v_{db}-P_{bd}-v_{bd}-v_{ba}-P_{ab}-v_{ab}$ form a triangular ISK4, a contradiction. So $p'$ has at least two neighbors on $P_{cd}$, and in particular $P_{cd}$ has length at least one, so $P_{cd}, P_{ad}, P_{ac}, P_{bd}, P_{cb}$ form a prism $K'$. Let us apply Lemma 4.1 to $K'$ and $P$. Since $P$ has at least two neighbors in the basic branch $P_{cd}$ of $K'$, and at least one neighbor in $P_{ad}$, $P$ is not of type branch or triangle with respect to $K'$. If $P$ is of type square with respect to $K'$, there is a contradiction because the neighborhood of $P$, included in $V(P_{ad}) \cup V(P_{cd})$ cannot induce a basic square of $K'$. So $P$ is of type augmenting with respect to $K'$: $p$ sees an edge of $P_{ad}$ (and this implies that $P_{ad}$ is a basic branch of $L(H)$), $p'$ sees an edge of $P_{cd}$, hence $P$ is of type augmenting with respect to $L(H)$.

If $P$ has no neighbor in $P_{ad}$, the situation is symmetric to that in the paragraph above, so we are left to the case when $P$ has no neighbor in $P_{cd}$. By (1), one end of $P$ (say $p$) has neighbors in $P_{ad}$, an and of $P$ (say $p'$) has neighbors in $P_{bd}$, and no proper subpath of $P$ has such a property. Let $v^R$ (resp. $v^L$) be the neighbor of $p$ closest to $v_{ad}$ (resp. to $v_{da}$) along $P_{ad}$. Up to symmetry between $P_{ad}$ and $P_{bd}$, we may assume that $v^L v^R \notin E(G)$ for otherwise $C$ is of type augmenting with respect to $L(H)$. Let $w$ be the neighbor of $p'$ closest to $v_{db}$ along $P_{bd}$. If $v^L \neq v^R$ then $p-v^L-P_{ad}-v_{da}$, $p-v^R-P_{ad}-v_{ad}-v_{ac}-P_{ac}-v_{ca}-v_{cd}-P_{cd}-v_{dc}$ and $p-P-p'-w-P_{bd}-v_{db}$ form a triangular ISK4, a contradiction. If $v^L = v^R$ then up to symmetry we may assume $v^L \neq v_{da}$ for otherwise $N_{L(H)}(P) \subseteq T_d$, contradictory to (1). So, $v^L-P_{ad}-v_{da}$, $v^L-P_{ad}-v_{ad}-v_{ac}-P_{ac}-v_{ca}-v_{cd}-P_{cd}-v_{dc}$ and $v^L-p-P-p'-w-P_{bd}-v_{db}$ form a triangular ISK4, a contradiction.

**Case 2:** $P$ is of type triangle with respect to $K$. Up to symmetry we assume $N_K(P) \subseteq T_a$. By (1), we may assume that $P$ has neighbors in $P_{cd}$. So one end of $P$ (say $p$) has neighbors in $T_a$, an end of $P$ (say $p'$) has neighbors in $P_{cd}$, and no proper subpath of $P$ has such a property. Vertex $p$ has at most two neighbors in $T_a$ for otherwise there is a $K_4$ in $G$, and since we are not in Case 1, we may assume that $p$ has at least two neighbors in $T_a$. So and $D = \{v\} \cup T_a$ induces a diamond of $G$. Let $w$ be the neighbor of $p'$ closest to $v_{dc}$ along $P_{cd}$. If $pv_{ab} \notin E(G)$ then $p-P-p'-w-P_{cd}-v_{dc}-v_{db}-P_{bd}-v_{bd}-v_{ba}-P_{ab}-v_{ab}$ is a connection for $D$ except if $w = v_{cd}$ and $P_{ac}$ has length zero. Hence, these two fact hold, and symmetrically $w = v_{dc}$ and $P_{ad}$ has length zero. Since $v_{cd}, v_{dc}$ both equal $w$, they are equal and we observe that $T = \{v_{cd}, v_{ad}, v_{ac}\}$ is a triangle and that the attachment of $P$ over $L(H)$ is included in $T$, contradictory to (1). So $vv_{ab} \in E(G)$ and we may assume up to symmetry $vv_{ad} \notin E(G)$. But then $v_{ab}-p-P-p'-w-P_{cd}-v_{dc}$, $v_{ab}-v_{ad}-P_{ad}-v_{da}$ and $v_{ab}-P_{ab}-v_{ba}-v_{bd}-P_{bd}-v_{db}$ form an triangular ISK4, a contradiction.

**Case 3:** $P$ is of type augmenting with respect to $K$. Up to symmetry we may assume that $p$ has some neighbor in $v_{ad}-P_{ad}-v_{da}-v_{db}-P_{bd}-v_{bd}$. Since $P$ is of type augmenting with respect to $K$, $p'$ has some neighbor either in $P_{ab}$ or in $Q = v_{ac}-P_{ac}-v_{ca}-v_{cb}-P_{bc}-v_{bc}$ (not in both). If $p'$ has some neighbor in $P_{ab}$ let $v^R$ be such a neighbor closest to $v_{ba}$. If $p'$ has some neighbor in $Q$ let $v^R$ be such a neighbor closest to $v_{bc}$.
Suppose first that $pv_{da}, pv_{db} \in E(G)$. Note that $P$ has no neighbor in $P_{cd}$ because then, $P \cup P_{cd}$ would contain a connection of the diamond $\{p\} \cup T_d$. If $v^R \in V(P_{ab})$ then up to symmetry we may assume $v^R \neq v_{ab}$ since $P_{ab}$ has length at least one. So, $v_{da}-p-P-p'-v^R-P_{ab}-v_{ba}-v_{bc}-P_{bc}-v_{cb}$, $v_{da}-v_{dc}-P_{cd}-v_{cd}$ and $v_{da}-P_{ad}-v_{ad}-v_{ac}-P_{ac}-v_{ca}$ form a triangular ISK4, a contradiction (a careful reader should check that this holds even when $P$ and every $P_{xy}$ except $P_{ab}$ has length zero !). Hence $v^R \in V(Q)$. If $v^R \in P_{ac}$ then $P_{ac}$ has length at least one and $v^R \neq v_{ac}$ so $p-P-p'-v^R-P_{ac}-v_{ca}-v_{cd}-P_{cd}-v_{dc}$ connects the diamond $\{v, v_{da}, v_{db}, v_{dc}\}$. So $v^R \notin V(P_{ac})$ and by symmetry we must have $v^R = v_{cb}$ and $vv_{ca} \in E(G)$. Now, $p-P-p'-v_{ca}-v_{cd}-P_{cd}-v_{dc}$ connects the diamond $\{v, v_{da}, v_{db}, v_{dc}\}$ except if both $P_{ad}, P_{ac}$ have length zero. So, both $P_{ad}, P_{ac}$, and symmetrically both $P_{bd}, P_{bc}$ have length zero. We observe that $P$ is a connection of the basic square induced by the vertices $v_{da} = v_{ad}, v_{ac} = v_{ca}, v_{cb} = v_{bc}$ and $v_{bd} = v_{db}$ of $L(H)$, hence, $C$ is of type square with respect to $L(H)$.

So we may assume that $pv_{da}, pv_{db} \in E(G)$ is impossible and symmetrically, that $p'v_{ca}, p'v_{cb} \in E(G)$ is also impossible. Up to symmetry we may assume that $p$ has neighbors in $P_{ad}$ and that no vertex of $P$ has a neighbor in $P_{bd}$. Let $v^L$ be a neighbor of $p$ closest to $v_{da}$ along $P_{ad}$. Let us suppose that some vertex of $P_{cd}$ has some neighbor in $P$ and call $w$ such a vertex closest to $v_{dc}$. Note that $w$ must be adjacent to $x \in \{p, p'\}$, so $x$ itself is a connected induced subgraph of $G$, not of type branch or triangle with respect to $L(H)$. This implies by minimality of $P$ that $x = p = p'$. We put $Q_1 = p-v^L-P_{ad}-v_{da}$, $Q_2 = p-w-P_{cd}-v_{dc}$. If $v^R \in V(P_{ab})$ we put $Q_3 = p-v^R-P_{ab}-v_{ba}-v_{bd}-P_{bd}-v_{db}$. If $v^R \in V(Q)$ we put $Q_3 = p-v^R-Q-v_{bc}-v_{bd}-P_{bd}-v_{db}$. We observe that $Q_1, Q_2, Q_3$ form a triangular ISK4 except if $w$ has some neighbor in $Q_3$. This last case implies $w = v_{cd}$ and $v^R \in P_{ac}$ since $p'v_{ca}, p'v_{cb} \in E(G)$ is impossible. Let $u^L$ be the neighbor of $p$ closest to $v_{ad}$ along $P_{ad}$ and $u^R$ be the neighbor of $p$ closest to $v_{ac}$ along $P_{ac}$. We observe that $p-v_{cd}-v_{cb}-P_{bc}-v_{bc}-v_{ba}-P_{ab}-v_{ab}$, $p-u^R-P_{ac}-v_{ac}$ and $p-u^L-P_{ad}-v_{ad}$ form a triangular ISK4, a contradiction. So no vertex of $P$ has a neighbor in $P_{cd}$. Since $P$ is of type augmenting with respect to $K$ and since $pv_{da}, pv_{db} \in E(G)$, $p'v_{ca}, p'v_{cb} \in E(G)$ are both impossible, we see that $C$ is of augmenting with respect to $L(H)$.

**Case 4:** $P$ is of type square with respect to $K$. So $P$ is a connection of a basic square $S$ of $K$ and has no neighbor in $K \setminus S$. If $P_{ab} \subset S$ then up to symmetry we may assume that $P_{ad}, P_{bd}$ have both length zero, $P_{ab}$ has length one, and $S$ has vertices $v_{ad} = v_{da}, v_{db} = v_{bd}, v_{ab}$ and $v_{ba}$. Note that $S$ is a basic square of $K$, but a non-basic square of $L(H)$. If one of $p, p'$ (say $p$) has a neighbor $w$ in $P_{cd}$, then $p = p'$ by minimality of $P$. So $w \neq v_{dc}$ because $G$ contains no $K_4$. In particular, $P_{cd}$ has length at least one, so $P_{cd}, P_{ad}, P_{ac}, P_{bd}, P_{cb}$ form a prism $K'$, and $p$ contradicts Lemma 4.1 applied to $K'$. Hence, none of $p, p'$ has a neighbor in $P_{cd}$. Now, in $V(P) \cup \{v_{da}, v_{ba}\}$ there is an induced path $Q$ from $v_{da}$ to $v_{ba}$ and no interior vertex of $Q$ has neighbors in $(L(H) \setminus S) \cup \{v_{da}, v_{ba}\}$. So, $v_{da}-Q-v_{ba}-v_{bc}-P_{bc}-v_{cb}$, $v_{da}-v_{ac}-P_{ac}-v_{ca}$ and $v_{da}-v_{dc}-P_{cd}-v_{cd}$ form a triangular subdivision of $K_4$, a contradiction.

Hence, $S$ has vertices $v_{ad} = v_{da}, v_{db} = v_{bd}, v_{bc} = v_{cb}$ and $v_{ac} = v_{ca}$. If one of $p, p'$ (say $p$) has a neighbor in $P_{cd}$ then $p = p'$ by minimality of $P$. So $w \neq v_{dc}$ because $G$ contains no $K_4$. In particular, $P_{cd}$ has length at least one, so $P_{cd}, P_{ad}, P_{ac}, P_{bd}, P_{cb}$ form a prism $K'$, and $p$ contradicts Lemma 4.1 applied to $K'$. Hence, none of $p, p'$ has a neighbor in $P_{cd}$. Now, we observe that $C$ is of type square with respect to
$L(H)$ because of $S$ and $P$.

□

A graph $H$ is *substantial* if it is cyclically 3-connected and neither a square theta nor a square subdivision of $K_4$.

**Lemma 4.3** Let $G$ be a graph that contains no triangular ISK4. Let $H$ be a substantial graph such that $L(H)$ is an induced subgraph of $G$. Let $C$ be a component of $G \setminus L(H)$. Then $C$ is either of type branch, triangle or augmenting with respect to $L(H)$.

**PROOF** — Note every vertex in $H$ has degree at most three since $L(H)$ contains no $K_4$. We may assume that there are two edges $e_1, e_2$ of $H$ that are members of the attachment of $C$ over $L(H)$, that are not in the same branch of $H$ and that are not incident in $H$. Because else either every edge of the attachment of $C$ over $L(H)$ is in the same branch of $H$ and so $C$ is of type branch or triangle; or there are at most three edges of $H$ in the attachment of $C$ over $L(H)$ that are pairwise incident and $C$ is of type triangle. Since $H$ is 2-connected, there exists a cycle $C$ of $H$ that goes through $e_1, e_2$ and we put $e_1 = ab, e_2 = cd$ so that $a, b, c, d$ appear in this order along $C$. Note that $a, b, c, d$ are pairwise distinct. Let $P, Q, R$ be paths like in Lemma 3.7.

Suppose first that $V(H) = V(P) \cup V(Q) \cup V(R)$. Then $R$ must have length at least two and $H$ must be a theta since $H$ is substantial, so $L(H)$ is a prism. By the discussion above, the attachment of $C$ over $L(H)$ contains at least vertices in two different basic branches $L(H)$, and not in a triangle of that prism. So, by Lemma 4.1 $C$ is of type augmenting or square with respect to the prism. Since type square is impossible because $H$ is substantial, we are left with the type augmenting, so our lemma holds.

So we may assume that $H$ has more vertices than those in $P, Q, R$. Let $r \in V(P), r' \in V(Q)$ and let us put $P_1 = rPabQr', P_1 = rPdcQr', \text{ and } P_3 = R$. By Lemma 3.3, there exists a path $S$ of $H$, with an end in the interior of $P_i$, an end in the interior of $P_j$ where $1 \le i < j \le 3$, and the interior of $S$ is disjoint of $P_1, P_2, P_3$. Since $H' = P_1 \cup P_2 \cup P_3 \cup S$ is a subdivision of $K_4$, we may apply Lemma 4.2 to $C$ and $L(H')$. Note that $C$ cannot be of type branch or triangle with respect to $L(H')$ because of the edges $ab$ and $cd$. So we must be in one of following two cases:

**Case 1:** $H$ contains a square subdivision of $K_4$ as a subgraph, and $C$ is of type square with respect to it. Then up to a relabeling we may assume that $C$ is of type square with respect to $L(H')$ and that $abcd$ is a square of $H$, $P_1 = ab, P_2 = dc, R$ is from $a$ to $c$ and $S$ is from $b$ to $d$. Since $H$ is substantial, it not a square subdivision of $K_4$, so there must be some vertices in $H \setminus H'$. We claim that there exists a path $T$ with an end in the interior of $S$, an end in the interior of $R$ and whose interior is disjoint of $H'$. Because every vertex of $H$ has degree at most three since $L(H)$ contains no $K_4$. Since $H$ is connected and $H \neq H'$, there exists some vertex in $V(H) \setminus V(H')$ with a neighbor $e \in V(H') \setminus \{a, b, c, d\}$ because $a, b, c, d$ have already three neighbors, so $e$ is in the interior of one of $S, R$ (say $S$). Since $H$ is 2-connected, $\{e\}$ is not a cutset of $H$ and there exists a path from $e$ to some other vertex $e'$ in $H'$. If every such path is such that $e' \in V(S)$ then we put $A = V(P) \cup V(Q) \cup V(R)$, $B = (V(H) \setminus A) \cup \{b, d\}$ and we observe that $(A, B)$ is a cyclic 2-separation of $H$,
a contradiction. So we may assume that $e'$ is in the interior of $R$ and $T$ exists as claimed.

Now let us consider the subgraph $H''$ of $H$ obtained from $P \cup Q \cup R \cup S \cup T$ by deleting the edges that lie on the subpath of $S$ from $e$ to $d$. We observe that $H''$ is a subdivision of $K_4$. We now apply Lemma 4.2 to $C$ and $L(H'')$: $C$ cannot be of type branch, triangle or augmenting with respect to $L(H'')$ because $C$ has neighbors at least three distinct branches of $L(H'')$, and $C$ cannot be of type square because the edge $ab, bc, cd, da$ of $H$ do not form a basic square in $L(H'')$ since $d$ has degree two in $H''$. So there is a contradiction, and we cannot be in Case 1.

**Case 2:** $H$ does not contain a square subdivision of $K_4$ such that $C$ is of type square with respect to it.

Hence, $C$ is of type augmenting with respect to $L(H')$. Up to a relabeling, we may assume that the attachment of $C$ over $L(H')$ consists of two incident edges $ab, be$ of $P_1$ and two incident edges $cd, df$ of $P_2$. We claim that $b, d$ both have degree two in $H$ (they clearly have degree two in $H'$). Else we may assume that $b$ has degree three in $H$. Up to symmetry, we suppose that $P$ is the branch of $H$ that contains $b$. Since $\{b\}$ is not a cutset of $H$ there is a path $T$ from $b$ to a vertex $b' \in (V(P_1) \cup V(P_2) \cup V(P_3) \cup V(S)) \setminus \{b\}$. If every such $b'$ is in $P_1$ then we put $A = V(P_2) \cup V(P_3) \cup V(S)$, $B = (V(H) \setminus A) \cup \{r, r'\}$ and we observe that $(A, B)$ is a cyclic 2-separation of $H$, a contradiction. So, we may assume that $b'$ is in a branch $Q'$ of $H'$, and $Q' \neq P$. By Lemma 3.8 there exist a subgraph $H''$ of $H$, that is a subdivision of $K_4$, and that has $P_1, P_2, T$ as branches. The connected graph $C$ has at least four neighbors in $L(H'')$ and two of them are in a triangle (these arising from $ab, be$). So, by Lemma 4.2 applied to $C$ and $L(H'')$, $C$ must be of type square with respect to $L(H'')$, which contradicts that we are in case 2. This proves our claim.

Since $b$, and symmetrically $d$ have both degree two in $H$, it follows that $C$ is of type augmenting with respect to $L(H)$. $\square$

A 2-cutset of a graph $G$ is a set $\{u, v\}$ of two non-adjacent vertices such that $G \setminus \{u, v\}$ is disconnected.

**Lemma 4.4** Let $G$ be a graph that contains no triangular ISK4. Let $H$ be a substan-
tial graph such that $L(H)$ is an induced subgraph of $G$. Suppose $L(H)$ inclusion-wise
maximum with respect to that property.

Then either $G = L(H)$ or $G$ has a clique-cutset of size at most three, or $G$ has a 2-cutset.

PROOF — Suppose that $G \neq L(H)$. So there is a component $C$ of $G \setminus L(H)$. Let us apply Lemma 4.3 to $C$ and $L(H)$. Suppose first that $C$ is of type branch or triangle. Then either the ends of the branch that contain the attachment of $C$ form a cutset of $G$ of size at most two, or the triangle that contains the attachment of $C$ form a triangle cutset of $G$.

We are left with the case when $C$ is of type augmenting, so there is a path $P$ like
in the definition of the type augmenting. So, in $H$ the attachment of $C$ consists of
four edge $ab, be, cd, df$ so that $b, d$ have degree two in $H$. Let us consider the graph
$H'$ obtained from $H$ by linking $b, d$ by a path $R$ whose length is one plus the length
of $P$. Then $H'$ is substantial. Indeed, it is cyclically 3-connected by Lemma 3.6, clearly not a square theta and not a square subdivision of $K_4$ since $H$ is not a square theta. Moreover, $L(H')$ is an induced subgraph of $G$ where $P$ corresponds to the path $R$, a contradiction to the maximality of $L(H)$. $\square$

# 5 Rich squares

A rich square is a graph $K$ that contains a square $S$ as an induced subgraph, and such that $K \setminus S$ has at least two components and every component of $K \setminus S$ is a connection of $S$.

**Lemma 5.1** Let $G$ be an ISK4-free graph that contains no line-graph of a substantial graph. Let $K$ be a rich square that is an induced subgraph of $G$, and maximal with respect to this property. Then either $G = K$ or $G$ has a clique-cutset of size at most three or $G$ has a 2-cutset.

**PROOF** — Suppose $G \neq K$. Let $S$ be a square for which $K$ is a rich square and such that $S$ has vertices $u_1, u_2, u_3, u_4$ in this order along the square. A component of $K \setminus S$ is a connection of $S$. A connection with ends $p, p'$ is said to be a connection of type 1 if $p = p'$ and $N_S(p) = S$; of type 2 if $N_S(p) = \{u_1, u_2\}$ and $N_S(p') = \{u_3, u_4\}$; of type 3 if $N_S(p) = \{u_1, u_4\}$ and $N_S(p') = \{u_2, u_3\}$. Note that connections of type 2 and 3 are basic branches of $K$. Let $C$ be a component of $G \setminus K$. We consider now three cases according to the attachment of $C$ over $K$. Note that we may assume that this attachment is not empty for otherwise any vertex of $K$ would be a cutset of $G$.

**Case 1:** The attachment of $C$ over $K$ contains vertices of a connection of type 2 or 3 of $S$. Let $B_1$ be such a connection. Up to symmetry, we suppose $B_1 = p_1 - \cdots - p'_1$ of type 2, $N_S(p_1) = \{u_1, u_2\}$, $N_S(p'_1) = \{u_3, u_4\}$. If $N_K(C)$ contains no vertex of $K \setminus B_1$, then $\{p_1, p'_1\}$ is a cutset of size 2 of $G$ and the lemma holds.

Suppose first that $N_K(C)$ contains vertices of a component $B_2 \neq B_1$ of $K \setminus S$. If $B_2$ is a connection of type 1 or 3 with respect to $S$ then $K' = G[S \cup B_1 \cup B_2]$ is the line-graph of a subdivision of $K_4$. So by Lemma 4.2 applied to $K'$ and $C$, we can deduce that $C$ is of type augmenting with a path $P$ because types branch and triangle are clearly impossible and $B_1 \cup B_2$ contain no basic square of $K'$. Note that this implies that $B_2$ is a basic branch of $K$, and so it is a connection of type 3 with respect to $S$. Now we observe that $G[S \cup B_1 \cup B_2 \cup P]$ is the line-graph of a substantial graph, a contradiction.

So $B_2 = p_2 - \cdots - p'_2$ is a connection of type 2 with respect to $S$, $N_K(p_2) = \{u_1, u_2\}$ and $N_K(p'_2) = \{u_3, u_4\}$. Let $P$ be the shortest path of $C$ with neighbors in $B_1$ and $B_2$. Let $p_3, p'_3$ be the end of $P$, where $p_3$ has neighbors in $B_1$ and $p'_3$ in $B_2$. If no vertex of $P$ has neighbors in $\{u_1, u_2\}$ then $B_1 \cup B_2 \cup P$ contains a connection of the diamond $\{p_1, p_2, u_1, u_2\}$, a contradiction. So some vertex of $P$ has a neighbor in $\{u_1, u_2\}$ and similarly a neighbor in $\{u_3, u_4\}$. By Lemma 4.1 applied to the prism $K' = G[S \cup B_1]$ and $P$, we deduce that $P$ is of type augmenting with respect to $K'$. Let $P'$ be the augmenting subpath of $P$, that is the shortest subpath of $P$ that
contains neighbors of $B_1$ and $S$. One end of $P'$ is $p_3$ and $N_{B_1}(p_3) = \{q_1, q'_1\}$ where $q_1q'_1$ is an edge of $B_1$ and $p_1, q_1, q'_1, p'_1$ appear in this order along $B_1$. We denote the other end by $p_3'',$ and, up to symmetry, we can assume that $N_K(p_3'') = \{u_2, u_3\}$. If $p_3' \neq p_3''$, then $B_1 \cup B_2 \cup P' \cup \{u_1, u_3\}$ is a triangular ISK4, a contradiction. So $p_3' = p_3''$. By Lemma 4.1 applied on $K'' = G[S \cup B_2]$ and $p_3'$, we can deduce that $p_3'$ is of type augmenting with respect to $K''$, so $N_{B_2}(p_3') = \{q_2, q'_2\}$, where $q_2, q'_2$ is an edge of $B_2$ and $p_2, q_2, q'_2, p'_2$ appear in this order along $B_2$. Then $p_3'-u_2, p_3'-q_2-B_2-p_2$ and $p_3'-P-p_3-q'_1-B_1-p'_1-u_4-u_1$ form a triangular ISK4, a contradiction. So no vertex of $C$ has a neighbor in $K \setminus (S \cup B_1)$.

Hence some vertex of $C$ has neighbors in $S$. By lemma 4.1 applied to the prism $S \cup B_1$ and $C$, we can deduce that $C$ is of type augmenting or triangle. If $C$ is of type triangle, then there is a triangle cutset in $G$, and the lemma holds. If $C$ is of type augmenting, let $P$ be an augmenting path of $C$ that sees $B_1$. Let $B_2$ be a component of $K \setminus (S \cup B_1)$. Then $G[B_1 \cup B_2 \cup P \cup \{a_1, a_3\}]$ is an ISK4, a contradiction.

**Case 2:** The attachement of $C$ over $K$ contains no vertices of connections of type 2 and 3 of $S$, and contains vertices of a connection of type 1 of $S$. So there exists a vertex $b_1$ adjacent to all of $S$. Suppose some vertex of $C$ has neighbors in another component of $K \setminus (S \cup B_1)$, that is a single vertex $b_2$ adjacent to all of $S$. Note that $K' = G[S \cup \{b_1, b_2\}]$ is the line-graph of $K_4$. By lemma 4.2 applied on $K'$ and $C$, we deduce that $C$ is of type square with a connection $P$. By symmetry, we can assume that $N_{K'}(P) = \{u_1, u_3, b_1, b_2\}$ for otherwise, $K \cup P$ would be a rich square, contradictory to the maximality of $K$. Since $K$ is a maximal rich square, and $S \cup P \cup \{b_1, b_2\}$ is a rich square, we can deduce that $K \setminus (S \cup \{b_1, b_2\})$ contains a component $B_3$, that is a connection of $S$. Then $B_3 \cup P \cup \{u_2, u_4, b_1, b_2\}$ is an ISK4 (non-triangular), a contradiction. So no vertex of $C$ has a neighbor in $K \setminus (S \cup \{b_1\})$. Let $B_2$ be a component of $K \setminus (S \cup \{b_1\})$. Note that $K' = S \cup B_2 \cup \{b_1\}$ is the line-graph of a subdivision of $K_4$. By lemma 4.2 applied to $K'$ and $C$, we deduce that $C$ is of type triangle with respect to $K'$. Since no vertex of $C$ has a neighbor in a component of $K \setminus S$ (except $b_1$), we see that $G$ has a triangle cutset.

**Case 3:** The attachement of $C$ over $K$ is included in $S$.

Let $K'$ be a subgraph of $K$ that contains $S$ and that is the line-graph of an ISK4 or a prism (take one connection of type 2 or 3 if possible or two connection of type 1 otherwise). Let us apply Lemma 4.1 or 4.2 to $K'$ and $C$. If $C$ is of type augmenting or square with respect to $K'$ with a path $P$, we observe that $K \cup P$ is a rich square, contradictory to the maximality of $K$. If $C$ is of type branch or triangle, then $G$ has a cutset of size at most two. $\square$

# 6 Prisms

**Lemma 6.1** Let $G$ be an ISK4-free graph that contains no line-graph of a substantial graph and no rich square as an induced subgraph. Let $K$ be a prism that is an induced subgraph of $G$. Then either $G = K$ or $G$ has a clique-cutset of size at most three or $G$ has a 2-cutset.
**PROOF** — If $G \neq K$ then let $C$ be a component of $G \setminus K$ and apply Lemma 4.1 to $K$ and $C$. If $C$ is of type branch, then the ends of the branch of $K$ that contains the attachment of $C$ over $K$ is a cutset of size at most two. If $C$ is of type triangle, then $G$ has a triangle cutset. If $C$ is of type augmenting with a connection $P$ then $P \cup K$ is either the line-graph a non-square subdivision of $K_4$, or a rich square, in both cases a contradiction. If $C$ is of type square with a connection $P$, then $K \cup P$ is a rich square, a contradiction. $\square$

**Lemma 6.2** Let $G$ be an ISK4-free graph that contains a prism. Then either $G$ is the line-graph of a graph with maximum degree three, or $G$ is a rich square, or $G$ has a clique-cutset of size at most three or $G$ has a 2-cutset.

**PROOF** — Since $G$ contains a prism, it contains the line-graph $L(H)$ of a cyclically 3-connected graph as an induced subgraph. By Lemma 3.5, $H$ is either a theta or a subdivision of $K_4$. In this last case, if $H$ is substantial, then our result holds by Lemma 4.4. Else, we may assume that $G$ contains no line-graph of a substantial graph and $L(H)$ is a rich square made of a square with two connections, and our result holds by Lemma 5.1. Hence, in the first case, we may assume that $G$ contains no rich square and no line-graph of a substantial graph. Then our result holds by Lemma 6.1. $\square$

# 7 Wheels and double star cutset

A paw is a graph with four vertices $a, b, c, d$ and four edges $ab, ac, ad, bc$. A star-cutset of a graph is a set $S$ of vertices such that $G \setminus S$ is disconnected and such that $S$ contains a vertex adjacent to every other vertex of $S$.

**Lemma 7.1** Let $G$ be a graph that does not contain a $K_4$ or a prism. If $G$ contains a paw, then $G$ has a star-cutset.

**PROOF** — Suppose that $G$ does not have a star-cutset. Let $X$ be a paw in $G$, with vertices $a, b, c, d$ and edges $ab, ac, ad, bc$. Since $G$ does not admit a star-cutset, the set $\{a\} \cup N(a) \setminus \{b, d\}$ is not a cutset of $G$, so there exists a chordless path $P_1$ with endvertices $b, d$ such that the interior vertices of $P_1$ are distinct from $a$ and not adjacent to $a$. Likewise, the set $\{a\} \cup N(a) \setminus \{c, d\}$ is not a cutset of $G$, so there exists a chordless path $P_2$ with endvertices $c, d$ such that the interior vertices of $P_2$ are distinct from $a$ and not adjacent to $a$. The definition of $P_1, P_2$ implies that there exists a path $Q$ with endvertices $b, c$ such that $V(Q) \subseteq V(P_1) \cup V(P_2)$, $Q$ is not equal to the edge $bc$, and $bc$ is the only chord of $Q$. So $V(Q)$ induces a cycle. If $d$ is in $Q$, then $V(Q) \cup \{a\}$ induces a subdivision of $K_4$. If $d$ is not in $Q$, then the definition of $P_1, P_2$ implies that there exists a path $R$ whose endvertices are $d$ and a vertex $q$ of $Q$ and $V(R) \subseteq V(P_1) \cup V(P_2)$. We choose a minimal such path $R$. Let $d'$ be the neighbor of $q$ in $R$. The minimality of $R$ implies that $R$ is chordless, $(V(R) \setminus \{q\}) \cap V(Q) = \emptyset$, and $d'$ is the only vertex of $R$ with a neighbor in $Q$. If $d'$ has only one neighbhor in $Q$, then $V(Q) \cup V(R) \cup \{a\}$ induces a subdivision
of $K_4$ (whose vertices of degree 3 are $a, b, c, q$). If $d'$ has exactly two neighbors in $Q$ and these are adjacent, then $V(Q) \cup V(R) \cup \{a\}$ induces a prism. If $d'$ has at least two non-adjacent neighbors in $Q$, then $V(Q) \cup V(R) \cup \{a\}$ contains an induced subdivision of $K_4$ (whose vertices of degree 3 are $a, b, c, d'$). $\square$

**Lemma 7.2** Let $G$ be an ISK4-free graph that does not contain a prism or an octahedron. If $G$ contains a wheel ($H, u$) with $|V(H)| = 4$, then $G$ has a star-cutset.

**PROOF** — Suppose that $G$ does not have a star-cutset. Let the vertices of $H$ be $u_1, \dots, u_4$ in this order. If $u$ is adjacent to only three of them, then $V(H) \cup \{u\}$ induces a subdivision of $K_4$. So we may assume that $u$ is adjacent to all vertices of $H$. Since $G$ does not admit a star-cutset, the set $\{u\} \cup N(u) \setminus \{u_1, u_3\}$ is not a cutset of $G$, so there exists a chordless path $P$ with endvertices $u_1, u_3$ such that the interior vertices of $P$ are distinct from $u$ and not adjacent to $u$. Let $P = u_1-v-\dots-v_3$. Vertex $v$ must be adjacent to $u_2$, for otherwise $u, u_1, u_2, v$ induce a paw, which contradicts Lemma 7.1. Likewise, $v$ is adjacent to $u_4$. If $v$ is not adjacent to $u_3$, then $u_1, u_2, u_3, u_4, v$ induce a subdivision of $K_4$. If $v$ is adjacent to $u_3$, then $u, u_1, u_2, u_3, u_4, v$ induce an octahedron, a contradiction. $\square$

A double star cutset of a graph is a set $S$ of vertices such that $G\setminus S$ is disconnected and such that $S$ contains two vertices $u, v$ and every vertex of $G$ is adjacent at least one of $u, v$. In particular $u$ and $v$ are adjacent. Note that a star-cutset is either a double star cutset or consists of one vertex.

**Lemma 7.3** Let $G$ be an ISK4-free graph that does not contain a prism or an octahedron. If $G$ contains a wheel, then $G$ has a star-cutset or a double star cutset.

**PROOF** — Suppose that the theorem does not hold. Let $(H, u)$ be a wheel in $G$ such that $|V(H)|$ is minimum. Let $u_1, \dots, u_h$ be the neighbors of $u$ in $H$ in this order. If $h=3$, then $V(H) \cup \{u\}$ induces a subdivision of $K_4$, so we may assume that $h \ge 4$. By Lemma 7.2, we may assume that $|V(H)| \ge 5$. A fan is pair $(P, x)$ where $P$ is a chordless path, $x$ is a vertex not in $P$, and $x$ has exactly four neighbours in $P$, including the two endvertices of $P$. Since $|V(H)| \ge 5$, we may assume up to symmetry that $u_1$ and $u_4$ are not adjacent; and so, if $Q$ is the subpath of $H$ whose endvertices are $u_1, u_4$ and which contains $u_2, u_3$, then $(Q, u)$ is a fan. Since $G$ contains a fan, we may choose a fan $(P, x)$ with a shortest $P$. Let $x_1, x_2, x_3, x_4$ be the four neighbours of $x$ in $P$ in this order, where $x_1, x_4$ are the endvertices of $P$. If $x_1$ is adjacent to $x_2$, then $x, x_1, x_2, x_4$ induce a paw, which contradicts Lemma 7.1. So $x_1$ is not adjacent to $x_2$, and similarly $x_3$ is not adjacent to $x_4$. Also $x_2$ is not adjacent to $x_3$, for otherwise $x, x_1, x_2, x_3$ induce a paw. For $i=1, 2, 3$, let $P_i$ be the subpath of $P$ whose endvertices are $x_i$ and $x_{i+1}$. Let $x_2', x_2''$ be the two neighbours of $x_2$ in $P$, such that $x_1, x_2', x_2, x_2'', x_3, x_4$ lie in this order in $P$.

Since $G$ does not admit a double star cutset, the set $\{x, x_2\} \cup N(x) \cup N(x_2) \setminus \{x_2', x_2''\}$ is not a cutset, and so there exists a path $Q = v_1-\dots-v_k$ such that $v_1$ has a neighbour in the interior of $P_1$, $v_k$ has a neighbour in the interior of $P_2$, and the vertices of $Q$ are not adjacent to either $x$ or $x_2$. We may choose a shortest such path $Q$, so $Q$ is chordless and its interior vertices have no neighbour in $V(P_1) \cup V(P_2)$.
If $v_1$ has at least four neighbours in $P_1$, then there is a subpath $P'_1$ of $P_1$ such that $(P'_1, v_1)$ is a fan, which contradicts the minimality of $(P, x)$. If $v_1$ has exactly three neighbours in $P_1$, then $V(P_1) \cup \{x, v_1\}$ induces a subdivision of $K_4$. So $v_1$ has at most two neighbours in $P_1$. Let $\{y_1, z_1\}$ be the set of neighbours of $v_1$ in $P_1$, such that $x_1, y_1, z_1, x_2$ lie in this order in $P_1$ (possibly $y_1 = z_1$). Likewise, $v_k$ has at most two neighbours in $P_2$. Let $\{y_2, z_2\}$ be the set of neighbours of $v_k$ in $P_2$, such that $x_2, y_2, z_2, x_3$ lie in this order in $P_2$ (possibly $y_2 = z_2$).

Suppose that $y_1 \neq z_1$. Note that $z_1$ and $z_2$ are not adjacent, for that would be possible only if $z_1 = x_2$ (and $z_2 = x_2''$), which would contradict the definition of $Q$. Then $V(P_1) \cup V(P_2[z_2, x_3]) \cup V(Q) \cup \{x\}$ induces a subdivision of $K_4$. So $y_1 = z_1$. Likewise, $y_2 = z_2$. But then $V(P_1) \cup V(P_2) \cup V(Q) \cup \{x\}$ induces a subdivision of $K_4$. $\square$

# 8 Decomposition theorem

**Theorem 8.1** Let $G$ be an ISK4-free graph. Then either:

* $G$ is series parallel;

* $G$ is the line-graph of a graph with maximum degree at most three;

* $G$ is a complete bipartite graph or $G$ is a complete tripartite graph;

* $G$ has clique-cutset, a 2-cutset, a star-cutset or a double star cutset.

**PROOF** — By Lemma 1.1, we may assume that $G$ either contains $K_{3,3}$, a prism or a wheel. If $G$ contains $K_{3,3}$ then we are done by Lemma 2.3. If $G$ contains a prism then we are done by Lemma 6.2 (because every rich square has a double star cutset). If $G$ contains the line-graph of a substantial graph then we are done by Lemma 4.4. So we may assume that $G$ does not contain the line-graph of a substantial graph. So, if $G$ contains an octahedron then we are done by Lemma 5.1 since an octahedron is a rich square. So we may assume that $G$ contains no prism and no octahedron. Hence, if $G$ contains a wheel then we are done by Lemma 7.3. $\square$

# References

[1] M. Chudnovsky and P. Seymour. Claw-free graphs. IV. Decomposition theorem. Manuscript, 2003.

[2] R. Diestel. *Graph Theory*. Springer, New York, third edition, 2006.

[3] B. Lévêque, D. Lin, F. Maffray, and N. Trotignon. Detecting induced subgraphs. Manuscript, 2007.