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

HAL
open science

# A new decomposition theorem for Berge graphs

Nicolas Trotignon

► To cite this version:

Nicolas Trotignon. A new decomposition theorem for Berge graphs. 2005. halshs-00196448

HAL Id: halshs-00196448

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

Submitted on 12 Dec 2007

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_2.png" /></figure>

UNIVERSITÉ PARIS 1

Cahiers de la MSE

CERMSEM

UMR CNRS 8095

A new decomposition theorem for Berge graphs

Nicolas TROTIGNON, CERMSEM

2005.79

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

CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE

Maison des Sciences Économiques, 106-112 boulevard de L'Hôpital, 75647 Paris Cedex 13
http://mse.univ-paris1.fr/Publicat.htm

ISSN : 1624-0340
A new decomposition theorem for Berge
graphs

Nicolas Trotignon*

November 17, 2005

**Abstract**

A hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no odd hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem for Berge graphs saying that every Berge graph either is in a well understood basic class or has some kind of decomposition. Then, Chudnovsky proved a stronger theorem by restricting the allowed decompositions. We prove here a stronger theorem by restricting again the allowed decompositions. Motivation for this new theorem will be given in a work in preparation.

AMS Mathematics Subject Classification: 05C17, 05C75

# 1 Definitions

In this paper graphs are simple, non-oriented, with no loop and finite. We call *path* any connected graph with at least a vertex of degree 1 and no vertex of degree greater than 2. A path has at most two vertices of degree 1 that are the *ends* of the path. If *a*, *b* are the ends of *P* we say that *P* is *from a to b*. The other vertices are the *interior* vertices of the path. We denote by *v*₁–···–*v*ₙ the path on *n* vertices whose edge set is {*v*₁*v*₂, ··, *v*ₙ₋₁*v*ₙ}. When *P* is a path, we say that *P* is a path of *G* if *P* is an induced subgraph of *G*. If *P* is a path and if *a*, *b* are two vertices of *P* then we denote by *a*–*P*–*b* the

<footnote>*Université de Paris I Panthéon-Sorbonne, CERMSEM,
106-112 Boulevard de l'Hopital, 75647 Paris cedex 13, France
nicolas.trotignon@univ-paris1.fr</footnote>
only induced subgraph of $P$ that is path from $a$ to $b$. The length of a path is the number of its edges. An antipath is the complement of a path.

Let $G$ be a graph and let $A$ and $B$ be two subsets of $V(G)$. A path is said to be outgoing from $A$ to $B$ if it has an end in $A$, an end in $B$, length at least 2, and no interior vertex in $A \cup B$.

A skew partition of a graph $G = (V, E)$ is a partition of $V$ into two sets $A$ and $B$ such that $A$ induces a graph that is not connected, and $B$ induces a graph that is not anticonnected. Skew partitions were first introduced by Chvátal for the study of perfect graphs [4]. An even skew partition is a skew partition $(A, B)$ with the additional property that every induced path with ends in $B$, interior in $A$ and every antipath with ends in $A$, interior in $B$ have even length. If $(A, B)$ is a skew partition, we say that $B$ is a skew cutset. If $(A, B)$ is even we say that the skew cutset $B$ is even.

Even skew partitions were introduced by Chudnovsky, Robertson, Seymour and Thomas in order to prove the Berge's strong perfect graph conjecture [1]. We say that a graph is Berge if it contain no odd hole (ie induced cycle of odd length, at least 4) and no odd antihole (complement of cycle of odd length, at least 4). A graph $G$ is perfect if for every induced subgraph $G'$, the chromatic number of $G'$ equals the size of the maximum clique of $G'$. The strong perfect graph conjecture proved by Chudnovsky et al. says that every Berge graph is perfect. In fact they proved a decomposition theorem for Berge graphs [3] (first conjectured by Conforti, Cornuéjols and Vušković [5]) that implies the strong perfect graph theorem. And then, Chudnovsky [2] proved a stronger decomposition theorem.

Before giving this decomposition theorem, we need some definitions. We call *double split graph* (defined in [3]) any graph $G$ that may be constructed as follows. Let $m, n \ge 2$ be integers. Let $A = \{a_1, \dots, a_m\}$, $B = \{b_1, \dots, b_m\}$, $C = \{c_1, \dots, c_n\}$, $D = \{d_1, \dots, d_n\}$ be four disjoint sets. Let $G$ have vertex set $A \cup B \cup C \cup D$ and edges in such a way that:

* $a_i$ is adjacent to $b_i$ for $1 \le i \le m$. There are no edges between $\{a_i, b_i\}$ and $\{a_{i'}, b_{i'}\}$ for $1 \le i < i' \le m$.

* $c_j$ is non-adjacent to $d_j$ for $1 \le i \le m$. There are all four edges between $\{c_j, d_j\}$ and $\{c_{j'}, b_{j'}\}$ for $1 \le j < j' \le n$.

* There are exactly two edges between $\{a_i, b_i\}$ and $\{c_j, d_j\}$ for $1 \le i \le m$ and $1 \le j \le n$ and these two edges are disjoint.

We need to know how the smallest double split graphs look like. Following the definition, the smallest double-split graphs have 8 vertices : $a_1, a_2, b_1, b_2, c_1, c_2, d_1, d_2$. The set $\{c_1, c_2, d_1, d_2\}$ induces a $C_4$. Vertex $a_1$ sees
an edge of this $C_4$, and $b_1$ the opposite edge. Also, $a_2$ sees an edge of this $C_4$ and $b_2$ the opposite edge. Up to an isomorphism, there are only two cases: $a_1, a_2$ see the same edge of the $C_4$, or $a_1, a_2$ see consecutive edges of the $C_4$. In the first case, the graph obtained is called the *double-diamond*, and in the second case we obtain $L(K_{3,3} \setminus e)$ — see figure 1. It is easy to check that the complement of a double split graph is always a double split graph.

<figure><img src="image_4.png" /><figcaption>Figure 1: The two smallest double split graphs: the double-diamond and $L(K_{3,3} \setminus e)$</figcaption></figure>

A graph is said to be *basic* if one of $G, \overline{G}$ is either a bipartite graph, the line-graph of a bipartite graph or a double-split graph.

The *2-join* is a kind of decomposition first defined by Cornuéjols and Cunningham [6]. But the definition that we give here is a slight modification used in [3]. We say that a partition $(X_1, X_2)$ of the vertex set is a 2-join when there exist disjoint non-empty $A_i, B_i \subseteq X_i$ ($i=1,2$) satisfying:

* Every vertex of $A_1$ is adjacent to every vertex of $A_2$ and every vertex of $B_1$ is adjacent to every vertex of $B_2$.

* There are no other edges between $X_1$ and $X_2$.

The sets $X_1, X_2$ are the two *sides* of the 2-join. Implicitly, when $(X_1, X_2)$ is a 2-join of a graph, we use the notation of the definition for the sets $A_i, B_i$'s. Also, when sets $A_i$'s $B_i$'s are like in the definition we say that $(A_1, B_1, A_2, B_2)$ is a *split* of $(X_1, X_2)$. Note that a 2-join has two splits, obtained by swapping $A$ and $B$. Implicitly we will denote by $C_i$ the set $X_i \setminus (A_i \cup B_i)$.

A 2-join $(X_1, X_2)$ in a graph $G$ is said to be *connected* when for $i=1,2$, every component of $G[X_i]$ meets both $A_i$ and $B_i$. A 2-join $(X_1, X_2)$ in a graph $G$ is said to be *proper* when it is connected and when for $i=1,2$, if $|A_i| = |B_i| = 1$, and if $X_i$ induces a path of $G$ joining the vertex of $A_i$ and the vertex of $B_i$, then it has length at least 3.

Now we can state the decomposition theorem of Berge graphs, proved by Chudnovsky.

**Theorem 1.1 ([3, 2])** Let $G$ be a Berge graph. Then either $G$ is *basic*, or one of $G, \overline{G}$ has a proper 2-join or $G$ has an even skew partition.
Here we give a stronger theorem: Theorem 2.13. Motivation for this stronger theorem will be given in a work in preparation. Note that Chudnovsky proved Theorem 1.1 from scratch, without using the slightly weaker theorem stated in [3]. Theorem 2.13 is slightly stronger than Theorem 1.1, but our proof uses Theorem 1.1.

## 2 results

The following fact is clear and useful:

**Lemma 2.1** If $(A, B)$ is an even skew partition of a graph $G$ then $(B, A)$ is an even skew partition of $\bar{G}$. In particular, a graph $G$ has an even skew partition if and only if $\bar{G}$ has an even skew partition.

A *star cutset* in a graph is a set of vertices $B$ such that $G \setminus B$ is disconnected and such that there a vertex $x$ in $B$ seeing every vertices of $B \setminus x$. Note that a star cutset of size at least 2 is a skew cutset.

**Lemma 2.2** Let $G$ be a *Berge graph*. If $G$ has a *star cutset* then $G$ has an *even skew partition* or $G$ has no edges or $G$ has size 3 or $G$ is the complement of $C_4$.

**PROOF** — Let $B$ be a star cutset of $G$. Let us suppose $B$ being maximum with that property. Let $A_1, A_2$ being such that $A_1, A_2, B$ are pairwise disjoint, there are no edges between $A_1, A_2$, and $A_1 \cup A_2 \cup B = V(G)$.

Suppose first that $B$ has size 1. Then $A_1, A_2$ are both of size one ($|V(G)| = 3$) or we may assume there are no edges between $B$ and $A_1$. Then we may assume that $G$ has at least one edge $e$. If $e$ is an edge of $A_1$, then we may assume $|A_1| = 2$ for otherwise, $e$ is a cutting edge of $G$, contradicting $B$ being maximum. Then there must be an edge in $B \cup A_2$ for otherwise, $e$ is a cutting edge of $G$. So we may assume $|B \cup A_2| = 2$ for otherwise $e$ is a cutting edge of $G$. Thus, $G$ is a perfect matching one four vertices. If $e$ is not an edge of $A_1$ then we may assume that $A_1$ has no edge. Thus if $V(G) \ge 4$ then every edge of $B \cup A_2$ is a cutting edge of $G$.

If $B$ has size at least 2 then $B$ is skew cutset of $G$. Let $x$ be the center of $B$. By maximality of $B$, every component of $G \setminus B$ has either size 1 or contains no neighbor of $x$. Thus, if $P$ is path that makes the skew cutset $B$ non even, then $P \cup x$ induces an odd hole of $G$. If $Q$ is an antipath that makes the skew cutset $B$ non even, then $Q \cup x$ induces an odd antihole of $G$.
□
**Lemma 2.3** Let $G$ be a Berge graph with a connected 2-join $(X_1, X_2)$. Then all the outgoing paths from $A_1$ to $B_1$ and all the outgoing paths from $A_2$ to $B_2$ have same parity.

**PROOF** — Note that since $(X_1, X_2)$ is connected there actually exists in $G[X_1]$ an outgoing path $P_1$ from $A_1$ to $B_1$. Similarly, there exists in $G[X_2]$ an outgoing path $P_2$ from $A_2$ to $B_2$. Suppose now that there exist two paths $Q, Q'$ that makes the lemma fails. Then one of $Q \cup P_1, Q' \cup P_1, Q \cup P_2$ or $Q' \cup P_2$ induces an odd hole. $\square$

**Lemma 2.4** Let $G$ be a Berge graph with a 2-join $(X_1, X_2)$. Let $i$ be in $\{1, 2\}$. Then every outgoing path from $A_i$ to $A_i$ (resp. from $B_i$ to $B_i$) has even length.

**PROOF** — Note that we do not suppose $(X_1, X_2)$ being proper. Let $P$ be an outgoing path from $A_1$ to $A_1$ (the other case is similar). If $P$ has a vertex in $A_2$, then $P$ has length 2. Else, $P$ must lie entirely in $X_1$ except possibly for one vertex in $B_2$. If $P$ lies entirely in $X_1$, then $P \cup \{a_2\}$ where $a_2$ is any vertex in $A_2$ induces a hole, so $P$ has even length. If $P$ has a vertex $b_2 \in B_2$, then we must have $P = a-\cdots-b-b_2-b'-\cdots-a'$ where $a-P-b$ and $b'-P-a'$ are outgoing paths from $A_1$ to $B_1$. Suppose that $P$ has odd length. Let $a_2$ be a vertex of $A_2$. Then $V(P) \cup \{a_2, b_2\}$ induces an odd cycle of $G$ whose only chord is $a_2b_2$. So one of $V(a-P-b_2) \cup \{a_2\}, V(a'-P-b_2) \cup \{a_2\}$ induces an odd hole of $G$, a contradiction. $\square$

The following four lemmas are a description of the paths and antipaths of a Berge graph with a 2-join (possibly non proper).

**Lemma 2.5** Let $G$ be a graph with a 2-join $(X_1, X_2)$. Let $P$ be a path of $G$ whose end vertices are in $X_2$. Then either:

1. There are vertices $a \in A_1, b \in B_1$ such that $V(P) \subseteq X_2 \cup \{a, b\}$. Moreover, if $a, b$ are both in $V(P)$, then they are non adjacent.

2. $P = c-\cdots-a_2-a-\cdots-b-b_2-\cdots-c'$ where: $a \in A_1, b \in B_1, a_2 \in A_2, b_2 \in B_2$. Moreover $V(c-P-a_2) \subset X_2, V(b_2-P-c') \subset X_2, V(a-P-b) \subset X_1$.

**PROOF** — If $P$ has no vertex in $X_1$, then for any $a \in A_1, b \in B_1$, the first outcome holds. Else let $c, c'$ be the end vertices of $P$. Starting from $c$, we may assume that first vertex of $P$ in $X_1$ is $a \in A_1$. Note that $a$ is the only vertex of $P$ in $A_1$. If $a$ has its two neighbors on $P$ in $X_2$, then $P$ has no other vertex in $X_1$, except possibly a single vertex $b \in B_1$ and the first outcome
holds. If $a$ has only one neighbor on $P$ in $X_2$, then let $a_2$ be this neighbor. Note that $P$ must have a single vertex $b$ in $B_1$. Let $b_2$ be the neighbor of $b$ in $X_2$ along $P$. So, the second outcome holds. $\square$

**Lemma 2.6** Let $G$ be a Berge graph with a 2-join $(X_1, X_2)$. Let $P$ be a path of $G$ whose end vertices are in $A_1 \cup X_2$ (resp. $B_1 \cup X_2$) and whose interior vertices are not in $A_1$ (resp. $B_1$). Then either:

1. $P$ has even length.

2. There are vertices $a \in A_1, b \in B_1$ such that $V(P) \subseteq X_2 \cup \{a, b\}$. Moreover, if $a, b$ are both in $V(P)$, then they are non adjacent.

3. $P = a \cdots b - b_2 - \cdots - c$ where: $a \in A_1, b \in B_1, b_2 \in B_2$.

Moreover $V(a-P-b) \subset X_1$ and $V(b_2-P-c) \subset X_2$.

(resp. $P = b \cdots a - a_2 - \cdots - c$ where: $b \in B_1, a \in A_1, a_2 \in A_2$.)

Moreover $V(b-P-a) \subset X_1$ and $V(b_2-P-c) \subset X_2$.)

**PROOF** — Note that we do not suppose $(X_1, X_2)$ being proper. Suppose first that the end vertices of $P$ are in $A_1 \cup X_2$.

If $P$ has its two end vertices in $A_1$, then by Lemma 2.4 $P$ has even length and Output 1 of the lemma holds.

If $P$ has exactly one end vertex in $A_1$, let $a$ be this vertex. Let $c \in X_2$ be the other end vertex of $P$. Let $a'$ be the neighbor of $a$ along $P$. If $a'$ is in $A_2$, then we may apply Lemma 2.5 to $a'-P-c$: Outcome 2 is impossible and Outcome 1 yields Outcome 2 of the lemma we are proving now since $P$ has exactly one vertex in $A_1$. If $a'$ is not in $A_2$, then let $b$ be the last vertex of $X_1$ along $P$ and $b_2$ the first vertex of $X_2$ along $P$. Outcome 3 of the lemma holds.

If $P$ has no end vertex in $A_1$ then Lemma 2.5 applies to $P$. The second outcome is impossible. The first outcome implies that there is a vertex $b \in B_1$ such that $V(P) \subseteq X_2 \cup \{b\}$ since no interior vertex of $P$ is in $A_1$. So, Outcome 2 of the lemma we are proving now holds.

The case when the end vertices of $P$ are all in $B_1 \cup X_2$ is similar. $\square$

**Lemma 2.7** Let $G$ be a graph with a 2-join $(X_1, X_2)$. Let $Q$ be an antipath of $G$ of length at least 5 whose interior vertices are all in $X_2$. Then there is a vertex $a$ in $A_1 \cup B_1$ such that $V(Q) \subseteq X_2 \cup \{a\}$.
**PROOF** — Let $c, c'$ be the end vertices of $Q$. Note that $N(c) \cap N(c') \cap X_2$ have to be non empty and that $N(c) \cap X_2$ must be different of $N(c') \cap X_2$, because $c, c'$ are the end vertices of an antipath of length at least 4. No pair of vertices in $X_1$ satisfies these two properties, so at most one of $c, c'$ is in $V(Q) \cap X_1$. If none of $c, c'$ are in $X_1$, then let $a$ be any vertex in $A_1$. Else, let $a$ be the unique vertex in $X_1$ among $c, c'$. Since $c, c'$ must have a neighbor in $X_2$, $a \in A_1 \cup B_1$ and clearly $V(Q) \subseteq X_2 \cup \{a\}$. $\square$

**Lemma 2.8** Let $G$ be a Berge graph with a 2-join $(X_1, X_2)$. Let $Q$ be an antipath of $G$ of length at least 5 whose interior vertices are all in $A_1 \cup X_2$ (resp. $B_1 \cup X_2$) and whose end vertices are not in $A_1$ (resp. $B_1$). Then either:

1. $Q$ has even length.

2. There is a vertex $a \in A_1 \cup B_1$ such that $V(Q) \subseteq X_2 \cup \{a\}$.

**PROOF** — Suppose first that the interior vertices of $Q$ are all in $A_1 \cup X_2$. The case when the interior vertices of $Q$ are all in $B_1 \cup X_2$ is similar.

If $Q$ has at least 2 vertices in $A_1$, then let $a \neq a'$ be two of these vertices. Since the end vertices of $Q$ are not in $A_1$, $a, a'$ may be chosen in such a way that there are vertices $c, c' \notin A_1$ such that $c-a-\overline{Q}-a'-c'$ is an antipath of $G$. Since $c$ must miss $a$ while seeing $a'$, $c$ must be in $X_1 \setminus A_1$, and so is $c'$. But the interior vertices of $Q$ cannot be in $X_1 \setminus A_1$, so $c, c'$ are in fact the end vertices of $Q$. Also, every interior vertex of $Q$ must be adjacent to at least one of $c, c'$, so all the interior vertices of $Q$ are in $A_1$. Now if we add to $Q$ any vertex of $A_2$, we obtain an antihole of $G$ that must be even. So $Q$ has even length and Output 1 of the lemma holds.

If $Q$ has exactly one vertex in $A_1$, let $a$ be this vertex. If $Q$ has no vertex in $X_1 \setminus A_1$ then Outcome 2 of the lemma holds. If $Q$ has at least two vertices in $X_1 \setminus A_1$ then these vertices are the end vertices of $Q$ and $Q$ has length 2. So we may assume that $Q$ has exactly one vertex $b$ in $X_1 \setminus A_1$. Since by assumption, $Q$ has length at least 5 and since $b$ must be an end vertex of $Q$, $a$ and $b$ have a common neighbor in $Q$. This is a contradiction since $a$ and $b$ have no common neighbor in $X_2$.

If $Q$ has no vertex in $A_1$ then Lemma 2.7 applies. Outcomes 1 and 2 yield a contradiction because of the length of $Q$. If we have the third outcome, then there is a vertex $a \in A_1 \cup B_1$ such that $V(Q) \subseteq X_2 \cup \{a\}$. $\square$

It is convenient to consider a degenerated kind of 2-join that implies the existence of an even skew partition. A 2-join $(X_1, X_2)$ is said to be degenerate if either:
* There exists $i \in \{1, 2\}$ and a vertex $v$ in $A_i$ that has no neighbor in $X_i \setminus (A_i \setminus \{v\})$;

* There exists $i \in \{1, 2\}$ and a vertex $v$ in $B_i$ that has no neighbor in $X_i \setminus (B_i \setminus \{v\})$;

* One of $A_1 \cup A_2$, $B_1 \cup B_2$ is a skew cutset of $G$;

* There exists $i \in \{1, 2\}$ and a vertex in $A_i$ that is complete to $B_i$ or a vertex in $B_i$ that is complete to $A_i$.

* There is an outgoing path of even length from $A_2$ to $B_2$ and one of $X_1$, $X_2$ is a skew cutset of $G$.

**Lemma 2.9** Let $G$ be a Berge graph and $(X_1, X_2)$ be a degenerate proper 2-join of $G$. Then $G$ has an even skew partition.

**PROOF** — Let us look at the possible reasons why $(X_1, X_2)$ is degenerate.

If there is a vertex $v$ in $A_1$ that has no neighbor in $X_1 \setminus (A_1 \setminus \{v\})$, then note that $|A_1| > 1$ since every component of $X_1$ meets $A_1$. So $(A_1 \setminus \{v\}) \cup A_2$ is a skew cutset separating $v$ from the rest of the graph. Let us check that this skew cutset is even. Let $P$ be an outgoing path from $(A_1 \setminus \{v\}) \cup A_2$ to $(A_1 \setminus \{v\}) \cup A_2$. If $P$ goes through $v$, then $P$ has length 2. Else, $P$ is outgoing from $A_1$ to $A_1$ or outgoing from $A_2$ to $A_2$, so $P$ has even length by Lemma 2.4. If there is an antipath $Q$ of length at least 5 with its interior in $(A_1 \setminus \{v\}) \cup A_2$ and its ends in the rest of the graph, then it must lie entirely in $X_1$ or $X_2$, say $X_1$ up to symmetry. Then $Q \cup \{a_2\}$, where $a_2 \in A_2$, induces an antihole. So, $Q$ has even length. Finally, the skew cutset $(A_1 \setminus \{v\}) \cup A_2$ is even. If there is a vertex $v$ in $A_2$, $B_1$ or $B_2$ that makes the 2-join degenerate like in the definition, we prove as above that $G$ has an even skew partition.

If $A_1 \cup A_2$ is a skew cutset of $G$ then the proof is the same as above: any path or antipath that could make the skew partition non-even yields a hole or an antihole by adding a vertex of $A_1 \cup A_2$, or has even length by Lemma 2.4. The case when $B_1 \cup B_2$ is a skew cutset is similar.

If $X_1 \cup A_2$ is a skew cutset of $G$, there is at least a vertex $a_1 \in A_1$ that is complete to $B_1$. Otherwise $\bar{G}[X_1 \cup A_2]$ would be connected because there would be an antipath of length at most 2 from any vertex of this graph to any vertex of $A_2$. So, there is at least a path of length 1 between a vertex of $A_1$ and a vertex of $B_1$, and by Lemma 2.3 every outgoing path from $A_2$ to $B_2$ has odd length. By this remark and by Lemma 2.4, every outgoing path from $X_1 \cup A_2$ to $X_1 \cup A_2$ has even length. Let $Q$ be an antipath with its ends in $V(G) \setminus (X_1 \cup A_2)$ and its interior in $X_1 \cup A_2$. If $Q$ goes through a vertex of $X_1 \setminus B_1$, it has length 2. Else, $V(Q) \cup \{a_1\}$ induces an antihole, so $Q$ has
even length. Finally, the skew cutset $X_1 \cup A_2$ is even. If one of $X_1 \cup B_2$, $X_2 \cup A_1$ and $X_2 \cup B_1$ is a skew cutset of $G$ the proof is again the same.

Suppose that there is a vertex $a \in A_i$ that is complete to $B_i$ (the case when a vertex in $B_i$ is complete to $A_i$ is similar). Suppose up to a symmetry that $i=1$. If $|A_1| > 1$ then pick $a' \neq a$ in $A_1$. Now $(\{a\} \cup N(a)) \setminus a'$ is a star cutset of $G$ separating $a'$ from $B_2$. So, by Lemma 2.2, we may assume that $A_1 = \{a\}$. If $|B_1| > 1$, consider $b \neq b'$ in $B_1$. Now, $(\{b\} \cup N(b)) \setminus b'$ is a star cutset of $G$ separating $b'$ from $A_2$. So again we may assume $B_1 = \{b\}$. Since $|X_1| \ge 3$ and $|X_2| \ge 3$, there is a vertex $c$ in $V(G) \setminus (A_1 \cup B_1)$. Now, $\{a, b\}$ is a star cutset separating $c$ from $X_2$.

If there is an outgoing path of even length from $A_2$ to $B_2$ and if one of $X_1$ is a skew cutset of $G$ (the case with $X_2$ is similar) then we claim that $(X_2, X_1)$ is an even skew partition. Every outgoing path from $X_1$ to $X_1$ has even length because such a path is an outgoing path from $A_1$ to $B_1$, that has even length by Lemma 2.3. Now, we know that every antipath of odd length with its ends in $X_2$ and its interior in $X_1$ has length at least 5. If there is an such an antipath $Q$ then the ends of $Q$ must have a common neighbor in $X_1$, thus we may assume that the ends of $Q$ are in $A_2$. Hence, every interior vertex of $Q$ is either complete to the ends of $Q$ or has no neighbor among the ends of $Q$. This is a contradiction. $\square$

**Lemma 2.10** Let $G$ be a graph with a non degenerate connected 2-join $(X_1, X_2)$. Let $i$ be in $\{1, 2\}$. Then for every vertex $v \in X_i$ there is a path $P_a = a-\cdots-v$ and a path $P_b = b-\cdots-v$ such that:

* $a \in A_i, b \in B_i$;

* Every interior vertex of $P_a, P_b$ is in $X_i \setminus (A_i \cup B_i)$.

**PROOF** — Suppose first $v \in X_i \setminus (A_i \cup B_i)$. By the definition of the connected 2-join, every connected component of $X_i$ must meet both $A_i$ and $B_i$. So $X_v$, the connected component of $v$ in $G[X_i]$, meets both $A_i, B_i$ and there is at least one path from $v$ to a vertex of $B_i$ in $G[X_i]$. If every path of $G[X_i]$ from $v$ to $B_i$ goes through $A_i$, then $A_i$ is a cutset of $G[X_i]$ that separates $v$ from $B_i$. Thus $A_1 \cup A_2$ is a skew cutset of $G$, so $(X_1, X_2)$ is degenerate, a contradiction. So there is a path $P_b$ as desired, and by the same way, $P_a$ exists.

If $v \in A_i$, then $P_a$ exists and have length 0: put $P_a = v$. The vertex $v$ has a neighbor $w$ in $X_i \setminus A_i$ otherwise $(X_1, X_2)$ is degenerate. By the preceding paragraph, there is a path $Q$ from $w$ to $b \in B_i$ whose interior vertices lie in $X_i \setminus (A_i \cup B_i)$. For $P_b$, consider a shortest path from $v$ to $b$ in $G[V(Q) \cup \{b\}]$. $\square$
A 2-join is said to be *loose* if it has a split $(X_1, X_2, A_1, B_1, A_2, B_2)$ such that:

1. $G[X_1]$ is an outgoing path from $A_1$ to $B_1$. Implicitly we will denote by $a_1$ the unique vertex in $A_1$ and by $b_1$ the unique vertex in $B_1$.

2. There are sets $B_3, B_4$ such that:

* $B_3 \neq \emptyset, B_4 \neq \emptyset, B_3 \cap B_4 = \emptyset, B_3 \cup B_4 = B_2$.

* There are no edges between $B_3$ and $B_4$.

* There is no vertex in $X_2 \setminus B_2$ that is complete to $B_2$.

* Every outgoing path from $B_3$ to $B_3$ (resp. from $B_4$ to $B_4$) has even length.

We say that $X_1$ is the *path-side* of the 2-join. It is clear that some Berge graphs have loose 2-joins. However the following theorem shows that they are not necessary to decompose Berge graphs.

**Lemma 2.11** Let $G$ be a Berge graph. Then either:

* $G$ is basic;

* $G$ has an even skew partition;

* One of $G, \overline{G}$ has a non loose proper 2-join.

**PROOF** — For any graph $G$ let $f(G)$ be the number of loose 2-joins of $G$. Note that when counting 2-joins, we count each 2-join once regardless of the other 2-join one may obtain by swapping the two sides. Let us consider $G$, a counter example to the theorem such that $f(G) + f(\overline{G})$ is minimal. By minimality we have:

(1) For every graph $G'$, if $G'$ is a counter-example to theorem then

$$f(G) + f(\overline{G}) \leq f(G') + f(\overline{G'})$$

Since $G$ is a counter-example and since $G$ is Berge, by Theorem 1.1 and up to a complementation of $G$, we may assume that:

(2) • $G$ is not basic;

* $G$ has no even skew partition;
* None of $G, \bar{G}$ has a non loose proper 2-join;

* $G$ has a loose proper 2-join.

(3) $G$ and $\bar{G}$ have no degenerate proper 2-join and no star cutset.

If one of $G, \bar{G}$ has a degenerate proper 2-join or a star cutset then one of $G, \bar{G}$ has an even skew partition by Lemma 2.9 or by Lemma 2.2. So $G$ has an even skew partition by Lemma 2.1. This contradicts (2). This proves (3).

By (2) we know that $G$ has a loose proper 2-join $(X_1, X_2)$. Up to a symmetry, we may assume that $X_1$ is the path-side of the 2-join. We put $C_2 = X_2 \setminus (A_2 \cup B_2)$. We denote by $\varepsilon \in \{0, 1\}$ the parity of the length of $G[X_1]$. We may assume that $X_2$ is minimal with respect to all the properties above. More precisely:

(4) For every $X'_2 \subsetneq X_2$, the partition $(V(G) \setminus X'_2, X'_2)$ is not a loose proper 2-join of $G$ with $V(G) \setminus X'_2$ as path-side.

We now consider the graph $G'$ obtained from $G$ by deleting $X_1 \setminus \{a_1, b_1\}$. Moreover, we add some new vertices: $c_1, c_2, b_3, b_4$. Then we add every possible edge between $b_3$ and $B_3$, between $b_4$ and $B_4$. We also add edges $a_1c_1, c_2b_3, c_2b_4$. If $\varepsilon = 0$, we consider $c_1 = c_2$. Else we consider $c_1 \neq c_2$ and we add an edge between $c_1$ and $c_2$. Note that in $G'$, $b_1$ has neighbors only in $B_2$. Here are two claims about the connectivity of $G$ and $G'$.

(5) $G[X_2] = G'[X_2]$ is connected.

Suppose not. Let $X'_2$ be any component of $X_2$. Since $(X_1, X_2)$ is proper, the sets $A'_2 = A_2 \cap X'_2$ and $B'_2 = B_2 \cap X'_2$ are not empty. So $(V(G) \setminus X'_2, X'_2)$ is a 2-join of $G$. Let us suppose that $X'_2$ is not an outgoing path length 1 or 2 from $A_2$ to $B_2$. This implies that $(V(G) \setminus X'_2, X'_2)$ is a proper 2-join. So, by (2), we know that $(V(G) \setminus X'_2, X'_2)$ is loose. By (4), $V(G) \setminus X'_2$ cannot be the path side of this 2-join. But $X'_2$ cannot be the path side of this 2-join since for that, one of $A_1, B_1$ would have to be of size at least 2. Hence we know that every component of $X_2$ is an outgoing path length 1 or 2 from $A_2$ to $B_2$. This implies that $G$ is bipartite, contradicting (2). This proves (5).
(6) • For every $A'_2 \subseteq A_2$ the graphs $G'[A'_2 \cup C_2 \cup B_3 \cup B_4 \cup \{b_1\}]$ and $G[A'_2 \cup C_2 \cup B_3 \cup B_4 \cup \{b_1\}]$ are connected.

• For every $B'_2 \subseteq B_2$ the graphs $G'[B'_2 \cup C_2 \cup A_2 \cup \{a_1\}]$ and $G[B'_2 \cup C_2 \cup A_2 \cup \{a_1\}]$ are connected.

• In $G[X_2] = G'[X_2]$, there is an outgoing path from $A_2$ to $B_3$ and an outgoing path from $A_2$ to $B_4$.

By (3) $(X_1, X_2)$ is a non degenerated 2-join of $G$. So, by Lemma 2.10 there is a path from any vertex $v$ of $A'_2 \cup C_2$ to $B_2$ in $G[A'_2 \cup C_2 \cup B_2]$. Since $b_1$ is complete to $B_2$, the first item holds. The second item holds similarly. The third item is clear since $(X_1, X_2)$ is a proper 2-join of $G$. This proves (6).

Here are six claims about the parity of various kinds of paths and antipaths in $G'$.

(7) Every outgoing path of $G'$ from $B_2$ to $A_2$ has length of parity $\varepsilon$.

If such a path contains one of $a_1, b_3, b_4, c_1, c_2$ then it has length $4 + \varepsilon$. Else such a path may be viewed as an outgoing path of $G$ from $B_2$ to $A_2$. By Lemma 2.3 it has parity $\varepsilon$. This proves (7).

(8) Every outgoing path of $G'$ from $B_2$ to $B_2$ has even length.

For suppose there is such a path $P = b-\cdots-b'$, $b, b' \in B_2$. If $P$ goes through $b_1$ then it has length 2. If $P$ goes through $b_3$ and $b_4$ it has length 4. If $P$ goes through only one of $b_3, b_4$ then either $P$ has length 2 or we may assume up to a symmetry that $P = b-b_3-c_2-c_1-a_1-a-\cdots-b'$ where $a \in A_2$. So, $a-P-b'$ is an outgoing path from $A_2$ to $B_2$ and by (7) it has parity $\varepsilon$. So, $P$ has even length. If $P$ goes through $c_2$ or $c_1$ then it must goes through at least one of $b_3, b_4$, and by the discussion above it must have even length. So we may assume that $P$ goes through none of $c_1, c_2, b_1, b_3, b_4$.

If $P$ goes through $a_1$ but through none of $\{b_3, b_4\}$, then we must have $P = b-\cdots-a-a_1-a'-\cdots-b'$. Then $a-P-b$ and $a-P-b$ are both outgoing paths from $A_2$ to $B_2$, so they both have parity $\varepsilon$ by (7). Once again, $P$ has even length.

So we may assume that $P$ is entirely contained in $X_2$. Thus, $P$ has even length by Lemma 2.4.

In every cases, $P$ has even length. This proves (8).

(9) Every outgoing path of $G'$ from $A_2$ to $A_2$ has even length.

For suppose there is such a path $P = a-\cdots-a'$, where $a, a' \in A_2$. If $P$ goes through $a_1$ then it has length 2. So we may assume that $P$ does not go
through $a_1$. Note that if $c_1 \neq c_2$ then $P$ does not go through $c_1$.

If $P$ goes through $b_3, b_4$ and not through $c_2$ then we may assume $P = a-\cdots-b'_3-b_3-b''_3-\cdots-b'_4-b_4-b''_4-\cdots-a'$ where $b'_3, b''_3 \in B_3$ and $b'_4, b''_4 \in B_4$. By (7), $a-P-b'_3$ and $b''_4-P-a'$ have both parity $\varepsilon$ and by (8) $b''_3-P-b'_4$ has even length. Thus $P$ has even length. If $P$ goes through both $b_3, b_4$ and through $c_2$ then we may assume $P = a-\cdots-b-b_3-c_2-b_4-b'-\cdots-a'$ where $b \in B_3$ and $b' \in B_4$. By (7) $b-P-a$ and $a'-P-b'$ have both parity $\varepsilon$. Thus, $P$ has even length. If $P$ goes through $B_3, b_1$ and $B_4$ then we prove that it has even length by the same way. So we may assume that $P$ neither goes through $c_2$ nor through both $b_3, b_4$ nor through $B_3, b_1$ and $B_4$.

If $P$ goes through exactly one of $b_3, b_4$, say $b_3$ up to a symmetry, then just like above $P = a-\cdots-b-b_3-b'-\cdots-a'$, where both $b-P-a$ and $a'-P-b'$ are outgoing paths from $B_2$ to $A_2$. So by (7), they both have parity $\varepsilon$. Thus, $P$ has even length. If $P$ goes through $b_1$ and exactly one of $B_3, B_4$, then we prove that it has even length by the same way. So we may assume that $P$ goes through none of $b_1, b_3, b_4$.

Now $P$ goes through none of $a_1, c_1, c_2, b_1, b_3, b_4$, so $P$ may be viewed as an outgoing path of $G$ from $A_2$ to $A_2$. It has even length by Lemma 2.4.

In every cases, $P$ has even length. This proves (9).

(10) Every antipath of $G'$ with length at least 2, with its end vertices in $V(G') \setminus A_2$, and all its interior vertices in $A_2$ has even length.

Let $Q$ be such an antipath. We may assume that $Q$ has length at least 3. So each end vertex of $Q$ must have a neighbor in $A_2$ and a non neighbor in $A_2$. So none of $a_1, c_1, c_2, b_1, b_3, b_4$ can be an end vertex of $Q$, and $Q$ may be viewed as an antipath of $G$. Its union with $a_1$ is an antihole of $G$ that must have even length. So $Q$ has even length. This proves (10).

(11) Every antipath of $G'$ with length at least 2, with its end vertices in $V(G') \setminus B_2$, and all its interior vertices in $B_2$ has even length.

Let $Q$ be such an antipath. We may assume that $Q$ has length at least 3. So each end vertex of $Q$ must have a neighbor in $B_2$ and a non neighbor in $B_2$. So none of $a_1, b_1, c_1, c_2$ can be an end vertex of $Q$. If $b_3$ is an end vertex of $Q$, then the other end vertex must be adjacent to $b_3$ while not being in $B_2 \cup \{a_1, b_1, c_1, c_2\}$, a contradiction. So $b_3$ is not an end-vertex of $Q$ and by a similar proof, neither $b_4$ is. So none of $a_1, c_1, c_2, b_1, b_3, b_4$ is in $Q$ and $Q$ may be viewed as an antipath of $G$. Its union with $b_1$ is an antihole of $G$ that must have even length. So $Q$ has even length. This proves (11).
(12) • Every antipath of $G'$ with length at least 2, with its end vertices in $V(G') \setminus B_3$, and all its interior vertices in $B_3$ has even length.

• Every antipath of $G'$ with length at least 2, with its end vertices in $V(G') \setminus B_4$, and all its interior vertices in $B_4$ has even length.

Let us prove the first item (the second is similar). Let $Q$ be such an antipath. We may assume that $Q$ has length at least 3. So each end vertex of $Q$ must have a neighbor in $B_3$. So no vertex of $B_4$ can be an end-vertex of $Q$. Thus (11) applies and $Q$ has even length. This proves (12).

(13) Let $Q$ be an antipath of $G'$ of length at least 4. Then $Q$ does not go through $c_1, c_2$. Moreover $Q$ goes through at most one of $a_1, b_1, b_3, b_4$.

In an antipath of length at least 4, each vertex either is in a square of the antipath or in a triangle of the antipath. So, $c_1, c_2$ are not in $Q$ since they are not in any triangle or square of $G'$. In an antipath of length at least 4, for any pair $x, y$ of non adjacent vertices, there must be a third vertex adjacent to both $x, y$. Thus, $Q$ goes through at most one vertex among $a_1, b_3, b_4$. Suppose now that $Q$ also goes through $b_1$. Then it does not go through $a_1$ since $a_1, b_1$ have no common neighbours. So, up to a symmetry we may assume that $Q$ goes through $b_3$ and $b_1$. There is no vertex in $G' \setminus c_2$ seeing $b_3$ and missing $b_1$. So $b_1$ is an end of $Q$. Along $Q$, after $b_1$ we meet $b_3$. The next vertex along $Q$ must be in $B_4$. The next one, in $B_3$. The next one must see $b_3$ and must have a neighbor in $B_4$, a contradiction. This proves (13).

(14) $G'$ is Berge.

Let $H$ be a hole of $G'$. Suppose first that $H$ goes through $a_1$. If $H$ does not go through $c_1$, then $H \setminus a_1$ is a path of even length by (9), so $H$ has even length. If $H$ goes through $c_1$ then $H$ goes through exactly one of $b_3, b_4$, say $b_3$ up to symmetry, and $H \setminus \{a_1, c_1, c_2, b_3\}$ is a path $P$. If $P$ does not go through $b_1$ then it has parity $\varepsilon$ by (7). If $P$ goes through $b_1$, then $P = b-b_1-b'-\dots-a$ where $b'-P-a$ is outgoing from $B_4$ to $A_2$. So, again $P$ has parity $\varepsilon$ by (7). So $H$ has even length. So we may assume that $H$ does not go through $a_1$. So if $c_1 \neq c_2$ then $H$ does not go through $c_1$. If $H$ goes through $c_2$ then the path $H \setminus \{b_3, c_2, b_4\}$ has even length by (8), so $H$ is even. If $H$ goes through $b_1$ then the path $H \setminus \{b_1\}$ has even length by (8), so $H$ is even. So we may assume that $H$ does not go through $b_1, c_2$. If $H$ goes through both $b_3, b_4$ then $H \setminus \{b_3, b_4\}$ is partitionned into two outgoing paths from $B_2$ to $B_2$ that both have even length by (8). Thus $H$ has even length. If $H$ goes through $b_3$ and not through $b_4$, then $H \setminus b_3$ is an outgoing path from $B_3$ to $B_3$. By
the definition of loose 2-joins it has even length, so $H$ is even. If $H$ goes through $b_4$ and not through $b_3$ then $H$ is even by a similar proof. So we may assume that $H$ goes through none of $b_3, b_4$. Now, $H$ goes through none of $a_1, c_1, c_2, b_1, b_3, b_4$. So $H$ may be viewed as a hole of $G$, and so it is even. So every hole of $G'$ is even.

Let us now consider an antihole $H$ of $G'$. Since the antihole on 5 vertices is isomorphic to $C_5$, we may assume that $H$ has at least 7 vertices. Let $v$ be a vertex of $H$ that is not in $\{a_1, c_1, c_2, b_1, b_3, b_4\}$. By (13) applied to $H \setminus \{x\}$, $H$ does not go through $c_1, c_2$ and goes through at most one vertex of $\{a_1, b_1, b_3, b_4\}$. If $H$ goes through $a_1$, the antipath $H \setminus a_1$ has all its interior vertices in $A_2$ and by (10), $H \setminus a_1$ has even length, thus $H$ is even. If $H$ goes through $b_1$ then the antipath $H \setminus b_1$ has all its interior vertices in $B_2$ and by (11), $H \setminus b_1$ has even length, thus $H$ is even. If $H$ goes through one of $b_3, b_4$, say $b_3$ up to a symmetry, the antipath $H \setminus b_3$ has all its interior vertices in $B_3$ and by (12), $H \setminus b_3$ has even length, thus $H$ is even. If $H$ goes through none of $a_1, c_1, c_2, b_1, b_3, b_4$ then $H$ may be viewed as an antihole of $G$. So every antihole of $G'$ has even length. This proves (14).

(15) $G'$ is not basic.

If $G'$ is bipartite then all the vertices of $A_2$ are of the same color because of $a_1$. Because of $b_1$ all the vertices of $B_2$ have the same color. By (6), there is an outgoing path from $A_2$ to $B_2$ that has partity $\varepsilon$ by (7). So, the number of colors in $A_2 \cup B_2$ is equal to $1 + \varepsilon$, implying that $G$ is bipartite and contradicting (2). Hence $G'$ is not bipartite.

The graph $\overline{G'}[a_1, b_3, b_4]$ is a triangle, so $\overline{G'}$ is not bipartite. One of the graphs $G'[c_2, c_1, b_3, b_4]$, $G'[a_1, c_1, b_3, b_4]$ is a claw, so $G'$ is not the line-graph of a bipartite graph. For any $b \in B_3$, $b' \in B_4$, the graph $\overline{G'}[a_1, c_1, b, b']$ is a diamond, so $\overline{G'}$ is not the line-graph of a bipartite graph. In a double split graph with at least nine vertices, every vertex has degree at least 4, so $G'$ is not a double split graph because of $c_2$, or $G'$ has height vertex. If $G'$ has height vertex while being a double split graph then $G'$ must be the double diamond or $L(K - 3, 3 \setminus \{e\})$. In both cases this a contradiction since in both these peculiar graphs, a vertex of degree 3 must have an edge in his neighborhood. This proves (15).

(16) $G'$ has no even skew partition.

Suppose $G'$ has an even skew partition. Let $F'$ be an even skew cutset of $G'$ that separates $E'_1$ from $E'_2$. Let $(F'_1, F'_2)$ be a partition of $F'$ such that $F'_1$ is complete to $F'_2$. Starting from $F'$, we shall build an even skew cutset $F$ of $G$ which contradicts (2).
Let us first suppose $c_1 \neq c_2$ and $c_1 \in F'$. Then, $F'$ must contain at least a neighbor of $c_1$. If $F'$ contains $a_1$ and not $c_2$, then $F'$ is a star cutset of $G'$ centered at $a_1$. But this contradicts (6). If $F'$ contains $c_2$ and not $a_1$, then $F'$ is a star cutset of $G'$ centered at $c_2$. But this again contradicts (6). So, $F'$ must contain $a_1$ and $c_2$. Since $a_1, c_2$ have no common neighbors we have $F' = \{a_1, c_1, c_2\}$. This is a contradiction since $G \setminus \{a_1, c_1, c_2\}$ is connected by (6). So if $c_1 \neq c_2$ then $c_1 \notin F'$.

Suppose $c_2 \in F'$. By (6), no subset of $\{c_2, b_3, b_4\}$ can be a cutset of $G$. So, $F'$ must be a star cutset centered at one of $b_3, b_4$. This again contradicts (6). So $c_2 \notin F'$. Not both $b_3, b_4$ can be in $F'$ since they have no common neighbors in $F'$. So we assume $b_4 \notin F'$.

Up to a symmetry, we may assume $\{c_1, c_2, b_4\} \subset E'_1$. Also, $\{a_1, b_3\} \cap E' \subset E'_1$. We claim that $\{b_1\} \cap E' \subset E'_1$. Else, $F'$ separates $b_1$ from $c_2$. Since $F'$ separates $b_1$ from $c_2$ we must have $B_4 \subset F'$. Now $b_3 \in F'$ is impossible since there is no vertex seeing $b_3$ and having a neighbor in $B_4$. So, $B_3 \subset F'$. Since there is no edge between $B_3$ and $B_4$, there must be a vertex in $F'$ that is complete to $B_3 \cup B_4 = B_2$. The only place to find such a vertex is in $X_2 \setminus B_2$. But this contradicts the definition of loose 2-joins.

We proved $\{a_1, b_1, b_3\} \cap E' \subset E'_1$.

Let $v$ be any vertex of $E'_2$. Since $\{a_1, c_1, c_2, b_1, b_3\} \cap E' \subset E'_1$, we have $v \in X_2$. If $b_3$ is in $F$, put $B'_1 = \{b_1\}$, else put $B'_1 = \emptyset$. Now $F = (F' \setminus \{b_3\}) \cup B'_1$ is a skew cutset of $G$ that separates $v$ from the interior vertices of the path induced by $X_1$. Indeed, either $F = F'$, or $F'$ is obtained by deleting $b_3$ and adding $b_1$. Since $N(b_3) \cap X_2 \subset N(b_1) \cap X_2$, $F$ is not anticonnected and is a skew cutset. It suffices now to prove that $F$ is an even skew cutset of $G$.

Let $P$ be an outgoing path of $G$ from $F$ to $F$. We shall prove that $P$ has even length.

If $a_1, b_1 \notin F$, then $F \subset X_2$ and the end vertices of $P$ are both in $X_2$. So Lemma 2.5 applies to $P$. Suppose that the first outcome of Lemma 2.5 is satisfied: $V(P) \subseteq X_2 \cup \{a_1, b_1\}$. Note that by the definition of $F$, $b_1 \notin F$ implies $b_1 \notin F'$. Hence, $P$ may be viewed as an outgoing path from $F'$ to $F'$, so $P$ have even length since $F'$ is an even skew cutset of $G'$. Suppose now that the second outcome of Lemma 2.5 is satisfied. Put $i = 3$ if $b_2 \in B_3$ and $i = 4$ if $b_2 \in B_4$. Put $P' = c-P-a_2-a_1-c_1-c_2-b_i-b_2-P-c'$. Note that by the definition of $F$, $b_1 \notin F$ implies $b_3 \notin F'$. The paths $P$ and $P'$ have the same parity and $P'$ is an outgoing path of $G'$ from $F$ to $F$. So $P'$ and $P$ have even length since $F$ is an even skew cutset of $G'$.

If $a_1 \in F$, note that $b_1 \notin F$ since $a_1, b_1$ are non adjacent with no common neighbors (in both $G, G'$). We have $F \subset X_2 \cup \{a_1\}$, the end vertices of $P$ are both in $X_2 \cup \{a_1\}$ and no interior vertex of $P$ is in $\{a_1\}$ since $a_1 \in N$. So Lemma 2.6 applies. If Outcome 1 of the lemma holds, then $P$ has even
length. If Outcome 2 of the lemma holds, then just like in the preceding
paragraph, we can build a path $P'$ of $G'$ that is outgoing from $F$ to $F$ and
that has a length with the same parity than $P$. So $P$ has even length. If
Outcome 3 of the lemma holds, the proof is again similar to the preceding
paragraph.

If $b_1 \in F$, the proof is like in preceding paragraph. In every cases, $P$ has even length.

Now, let $Q$ be an antipath of $G$ of length at least 2 with all its interior
vertices in $F$ and with its end vertices outside of $F$. We shall prove that
$Q$ has even length. Note that we may assume that $Q$ has length at least 5,
because if $Q$ has length 3, it may be viewed as an outgoing path from $F$ to
$F$, that have even length by the discussion above on paths.

If both $a_1, b_1 \notin F$, then $N \subset X_2$ and the interior vertices of $Q$ are all in $X_2$. So Lemma 2.7 applies: $V(Q) \subseteq X_2 \cup \{a\}$ where $a \in \{a_1, b_1\}$. So $Q$ may be viewed as an antipath of $G'$ that has even length because $F'$ is an even skew cutset of $G'$.

If $a_1 \in F$, let us remind that $b_1 \notin F$. We have $F \subset X_2 \cup \{a_1\}$, the interior vertices of $Q$ are in $X_2 \cup \{a_1\}$ and the end vertices of $Q$ are not in $\{a_1\}$ since $a_1 \in F$. So Lemma 2.8 applies. We may assume that Outcome 2 holds. Once again, $Q$ may be viewed as an outgoing path of $G'$ that has even length because $F'$ is even.

If $B'_1 = B_1$, the proof is like in preceding paragraph. In every cases, $Q$
has even length. This proves (16).

(17) $G'$ and $\overline{G}'$ have no degenerate 2-join and no star cutset.

If one of $G'$, $\overline{G}'$ has a degenerate proper 2-join or a star cutset then $G'$ has an even skew partition by Lemma 2.9 or by Lemma 2.2. So $G$ has an even skew partition by (16). This contradicts (2). This proves (17).

(18) Let $i$ be in $\{3, 4\}$. Suppose $|B_i| \ge 2$. Then there exist no sets $Y, Z$ such that:

* $Y \cup Z = C_2 \cup A_2$;

* $Y \cap Z = \emptyset$;

* There are every possible edges between $Y$ and $B_i$ and no edge between $Z$ and $B_i$.

Up to a symmetry, suppose $i=3$. Suppose such a pair of sets $Y, Z$ exists.
Let $b, b'$ be in $B_3$. Then the set $\{b\} \cup N(b) \setminus b'$ is a star cutset of $G'$ separating
$b'$ from $a_1$, contradicting (17). This proves (18).
(19) There exist no sets $Y_1, Z_1, Y_2, Z_2$ such that:

• $Y_1, Z_1, Y_2, Z_2$ are pairwise disjoint and $Y_1 \cup Z_1 \cup Y_2 \cup Z_2 = X_2$;

• There are every possible edges between $Y_1$ and $Y_2$, and these edges are the only edges between $Y_1 \cup Z_1$ and $Y_2 \cup Z_2$;

• $A_2 \subset Y_1 \cup Z_1$ and $B_2 \subset Y_2 \cup Z_2$.

Suppose such sets exist. Note that $Y_1 \neq \emptyset$ and $Y_2 \neq \emptyset$ since by (5), $G[X_2]$ is connected. Note that $Z_1, Z_2$ can be empty. Suppose $Y_2 \cap B_2 \neq \emptyset$ and pick a vertex $b \in Y_2 \cap B_2$. Up to a symmetry we assume $b \in B_3$ and we pick a vertex $b' \in B_4$. Since $B_2 \subset Y_2 \cup Z_2$ we have $b' \in Y_2 \cup Z_2$. Now $\{b\} \cup N(b)$ is a star cutset of $G$ that separates $a_1$ from $b'$, contradicting (3). Thus $Y_2 \cap B_2 = \emptyset$. Hence $(Y_2 \cup Z_2, V(G) \setminus (Y_2 \cup Z_2))$ is a 2-join of $G$. This 2-join is proper (the check of connectivity relies on the fact that $(X_1, X_2)$ is connected and on Lemma 2.10). By (2) this 2-join has to be loose. By (4), $Y_2 \cup Z_2$ is the path-side of the 2-join. This is impossible because $|B_2| \ge 2$. This proves (19).

We now give four claims describing the proper 2-joins of $G'$. Implicitly, when $(X'_1, X'_2)$ is 2-join we use the usual notation: there are set $A'_1, A'_2, B'_1, B'_2$ like in the definition. We also put $C'_1 = X'_1 \setminus (A'_1 \cup B'_1)$ and $C'_2 = X'_2 \setminus (A'_2 \cup B'_2)$. (20) If $G'$ has a proper 2-join $(X'_1, X'_2)$ then either $\{c_1, c_2\} \subset X'_1$ or $\{c_1, c_2\} \subset X'_2$.

Suppose not. We may assume that there is a 2-join $(X'_1, X'_2)$ such that $c_1 \in X'_2$ and $c_2 \in X'_1$. In particular, $c_1 \neq c_2$. Up to a symmetry, we assume $c_1 \in A'_2$ and $c_2 \in A'_1$. Then, $a_1 \in X'_2$ for otherwise $c_1$ is isolated in $X'_2$, contradicting $(X'_1, X'_2)$ being proper. Also one of $b_3, b_4$ must be in $X'_1$ for otherwise $c_2$ is isolated in $X'_1$. Up to a symmetry we assume $b_3 \in X'_1$.

By (6) there is an outgoing path $P = h_1 - \cdots - h_k$ from $A_2$ to $B_3$ with $h_1 \in A_2, h_k \in B_3$. We denote by $H$ the hole induced by $V(P) \cup \{a_1, c_1, c_2, b_3\}$. Note that $H$ has an edge whose ends are both in $X'_1$ (it is $c_2b_3$) and an edge whose ends are both in $X'_2$ (it is $a_1c_1$). So $H$ is vertex-wise partitionned into an outgoing path from $A'_1$ to $B'_1$ whose interior is in $X'_1$ and outgoing path from $B'_2$ to $A'_2$ whose interior is in $X'_2$. Hence, starting from $c_1$, then going to $a_1$ and continuing along $H$, one will first stay in $X'_2$, then will meet a vertex in $B'_2$, immediatley after that a vertex in $B'_1$, and after that will stay in $X'_1$ and reach $c_2$. We now discuss several cases according to the unique vertex $x$ in $H \cap B'_2$.

If $x = a_1$ then $a_1 \in B'_2$. So $b_3 \in C'_1$. This implies step by step $B_3 \subset X'_1$, $B_3 \subset C'_1$, $b_1 \in X'_1$, $b_1 \in C'_1$, $B_4 \subset X'_1$, $B_4 \subset C'_1$, $b_4/inX'_1$. Let $v$ a vertex in $C_2$.
Then by (6) there is a path $Q$ from $v$ to $B_2$ with no vertex in $A_2$. If $v \in X'_2$, then $Q$ must contain a vertex in $A'_1 \cup B'_1$. This is impossible since no vertex in $C_2 \cup B_2$ sees $a_1$ or $c_1$. So, $C_2 \subset C'_1$. Let $v$ be a vertex in $A_2$. Note that by (6), $v$ must have a neighbor in $C_2 \cup B_2$. So, $v \in X'_1$ since $C_2 \cup B_2 \subset C'_1$. Finally, we proved $X'_2 = \{a_1, c_1\}$. This is impossible since $(X'_1, X'_2)$ is proper.

If $x = h_i$ with $1 \le i < k$, then $h_i \in B'_2 \cap C_2$ and $h_{i+1} \in B'_1$. Note that $b_3 \in C'_1$ since $b_3$ misses $c_1$ and $h_1$. So, $B_3 \subset X'_1$. By the definition of $x$, we know that $a_1 \in C'_2$. So, $A_2 \subset X'_2$. We consider now two cases.

First case: $b_4 \in X'_1$. Since there are no edges between $\{b_3, b_4\}$ and $\{c_1, h_1\}$ we know that $\{b_3, b_4\} \subset C'_1$. This implies $B_3 \cup B_4 \subset X'_1$. Also, $b_1 \in X'_1$ for otherwise $b_1$ is isolated in $X'_2$. Now, $A'_1 \cup B'_1 \subset (B_2 \cup C_2)$. Let us put: $Y_1 = B'_2$, $Z_1 = (X'_2 \cap X_2) \setminus Y_1$, $Y_2 = B'_1$, $Z_2 = (X'_1 \cap X_2) \setminus Y_2$. These four sets yield a contradiction to (19).

Second case: $b_4 \in X'_2$. Then $b_4 \in A'_2$. If there is a vertex $v$ of $X'_1$ in $B_4$ then $v \in A'_1$. This is impossible since $v$ misses $c_1 \in A'_2$. So, $B_4 \subset X'_2$. Hence, if $b_1 \in X'_1$ then $b_1 \in A'_1 \cup B'_1$. But this is impossible since $b_1$ misses $c_1$ and $h_1$. So, $b_1 \in X'_2$. Since $B_3 \subset X'_1$, we know $B_3 = B'_1$ and $b_1 \in B'_2$. Let $v$ be a vertex of $C_2$. By (6), there is an outgoing path from $v$ to $A_2$. So, if $v \in X'_1$ then there is a vertex of $(A'_1 \cup B'_1)$ in $C_2$. This is impossible since $v$ misses $b_1, c_1$. So, $C_2 \subset X'_2$. Finally, we proved $X'_1 = B_3 \cup \{c_2, b_3\}$. If $|B_3| = 1$ then $(X'_1, X'_2)$ is not proper contradicting our assumptions. So, $|B_3| \ge 2$. Let us now put $Y = B'_2$ and $Z = (C_2 \cup A_2) \setminus Y$. The sets $Y, Z$ contradict (18).

If $x = h_k$ then $a_1 \in C''_2$ and $A_2 \subset X'_2$. Let $v$ be a vertex of $C_2 \cup B_3 \cup B_4 \cup \{b_1, b_4\}$. By (6) there is a path $Q$ from $v$ to $A_2$ with no interior vertex in $B_3 \cup A_2$. If $v \in X'_1$, then $Q$ must have a vertex $u \ne v$ in $A'_2 \cup B'_2$. Note $u \notin B_3$. This is impossible because $u$ misses $c_2$ and $b_3$. So, $v \in X'_2$. Hence, $X'_1 = \{c_2, b_3\}$ contradicting $(X'_1, X'_2)$ being proper. This proves (20).

(21) If $G'$ has a 2-join $(X'_1, X'_2)$ then either $\{c_1, c_2, b_3, b_4\} \subset X'_1$ or $\{c_1, c_2, b_3, b_4\} \subset X'_2$.

Suppose not. By (20), we may assume that there is a 2-join $(X'_1, X'_2)$ such that $c_1, c_2 \in X'_1$ and $b_3 \in X'_2$. Up to a symmetry, we assume $c_2 \in A'_1$ and $b_3 \in A'_2$. At least one vertex of $B_3$ is in $X'_2$ for otherwise $b_3$ is isolated in $X'_2$. So let $b$ be a vertex of $X'_2 \cap B_3$. We claim that there is a hole $H$ that goes through $b_3, c_2, c_1, a_1, h_1 \in A_2, \dots, h_k = b$, with at least an edge in $X'_1$ and at least an edge in $X'_2$. If $c_1 \ne c_2$ the our claim hold trivially: $c_1c_2 \in X'_1$ and $b_3b \in X'_2$. If $c_1 = c_2$, suppose that our claim fails. Then $a_1 \in X'_2$, implying $A'_1 = \{c_2\}$ and $a_1 \in A'_2$. We have $b_4 \in X'_1$ for otherwise $c_2$ is isolated in $X'_1$. If $b_4 \in B'_1$ then $(X'_1, X'_2)$ is degenerate since $b_4$ is complete to $A'_1$. So, $b_4 \in C'_1$ implying $B_4 \subset X'_1$. If $b_1 \in X'_1$ then $b \in B'_1$ since $b \in X'_2$. So $B'_2 \subset B_3$ and $b_3$
is a vertex of $A'_2$ that is complete to $B'_2$, implying $(X'_1, X'_2)$ being degenerate, a contradiction. So $b_1 \in X'_2$. Hence $B'_1 = B_4$ because no vertex of $B'_1$ can be in $B_3$ since $b_3 \in A'_2$. If there is a vertex in $X'_1 \setminus (\{c_2, b_4\} \cup B'_1)$ then $\{c_1\} \cup B_4$ is a star cutset of $G'$ separating $c_2$ from $v$. So, $X'_1 = \{c_2, b_4\} \cup B_4$. If $|B_4| \ge 2$, there is a contradiction with (18). If $|B_4| = 1$ then $(X'_1, X'_2)$ is not proper, contradicting our assumptions. Thus our claim holds: $H$ has an edge in $X'_1$ and an edge in $X'_2$. So there is a unique vertex $x$ in $H \cap B'_2$. We now discuss according to the place of $x$.

If $x = a_1$ then by the discussion above $c_1 \neq c_2$. Also, $a_1 \in B'_2$ and $c_1 \in B'_1$. Suppose that $X'_1 \cap X_2$ and $X'_2 \cap X_2$ are both non-empty. The vertices of $A'_2 \cup B'_2$ are not in $X_2$ because they have to see either $c_1$ or $c_2$. So there are no edges between $X'_1 \cap X_2$ and $X'_2 \cap X_2$. Hence, $G'[X_2]$ is not connected, contradicting (5). So either $X_2 \subset X'_1$ or $X_2 \subset X'_2$. If $X_2 \subset X'_1$ then $X'_2 \subset \{a_1, b_1, b_3, b_4\}$, so $X'_2$ is a stable set, contradicting being $(X'_1, X'_2)$ proper. If $X_2 \subset X'_2$ then $b_1$ is in $X'_2$ for otherwise it is isolated in $X'_1$. So, $X'_1 \subset \{c_1, c_2, b_4\}$. This is a contradiction since by checking every cases, we see that no subset of $\{c_1, c_2, b_4\}$ can be a side of a proper 2-join of $G'$.

If $x = h_1$ then $h_1 \in B'_2$ and $a_1 \in B'_1$. If $b_4 \in X'_1$ then $b_4 \in C'_1$ because of $b_3$ and $h_1$. So, $B_4 \subset X'_1$. But in fact, by the same way, $B_4 \subset C'_1$, and $b_1 \in C'_1$. So, $B_3 \subset X'_1$, contradicting $h_k \in X'_2$. We proved $b_4 \in X'_2$ implying $A'_1 = \{c_2\}$. If a vertex $v$ of $X_2 \cup \{b_1\}$ is in $X'_1$, then by Lemma 2.10 applied to $(X'_1, X'_2)$ there is a path of $X'_1$ from $v$ to $A'_1 = \{c_2\}$ with no interior vertex in $B'_1$, a contradiction. So $X_2 \cup \{b_1\} \subset X'_2$. We proved $X'_1 = \{a_1, c_1, c_2\}$ contradicting $(X'_1, X'_2)$ being proper.

If $x = h_i$, $2 \le i \le k$ then $h_i \in B'_2$, $h_{i-1} \in B'_1$. Since $a_1 \in C'_1$ we have $A_2 \subset X'_1$. If $b_4 \in X'_1$ then $b_4 \in C'_1$ implying $B_4 \subset X'_1$. If $b_1 \in X'_2$ then $b_1$ must be in $A'_2 \cup B'_2$, a contradiction since $b_1$ misses $c_2$ and $h_{i-1}$. So, $b_1 \in X'_1$. Since $h_k \in X'_2$, we know $b_1 \in B'_1$. Thus $B'_2 \subset B_3$. Hence $b_3$ is a vertex of $A'_2$ that is complete to $B'_2$, implying $(X'_1, X'_2)$ being degenerate, a contradiction. We proved $b_4 \in X'_2$. Now $A'_2 = \{b_3, b_4\}$. Suppose that there is a vertex $v$ of $X'_1$ in $B_3 \cup B_4$. Then $v$ must be in $A'_1$ since $v$ sees one of $b_3, b_4$. But this is a contradiction since $v$ misses one of $b_3, b_4$. We proved $B_3 \cup B_4 \subset X'_2$. also, $b_1 \in X'_2$ for otherwise, $b_1$ is isolated in $X'_1$. Let us put: $Y_1 = B'_1$, $Z_1 = (X'_1 \cap X_2) \setminus Y_1$, $Y_2 = B'_2$, $Z_2 = (X'_2 \cap X_2) \setminus Y_2$. These four sets yield a contradiction to (19). This proves (21).

(22) If $G'$ has a proper 2-join $(X'_1, X'_2)$ then either $\{c_1, c_2, b_1, b_3, b_4\} \subset X'_1$ or $\{c_1, c_2, b_1, b_3, b_4\} \subset X'_2$.

Suppose not. By (21), we may assume that there is a 2-join $(X'_1, X'_2)$ of $G'$ such that $c_1, c_2, b_3, b_4 \in X'_1$ and $b_1 \in X'_2$. If $\{b_3, b_4\} \cap (A'_1 \cup B'_1) = \emptyset$ then
$\{b_3, b_4\} \subset C'_1$, so $B_3 \cup B_4 \subset X'_1$. Hence $b_1$ is isolated in $X'_2$, a contradiction.

If $|\{b_3, b_4\} \cap (A'_1 \cup B'_1)| = 1$, then up to a symmetry we may assume $b_3 \in A'_1$ and $b_4 \in C'_1$. Thus $B_4 \subset X'_1$. Since $b_2 \in X'_2$, we have $B_4 \subset A'_1 \cup B'_1$. But no vertex $x$ of $B_4$ can be in $A'_1$ because $x$ and $b_3$ have no common neighbors, so $B_4 \subset B'_1$. Thus $b_1 \in B'_2$. Because of $b_3$, $A'_2 \subset B_3$. So $b_1$ is a vertex of $B'_2$ that is complete to $A'_2$, implying $(X'_1, X'_2)$ being degenerate, a contradiction. We proved $\{b_3, b_4\} \subset (A'_1 \cup B'_1)$.

Since $b_3, b_4$ have no common neighbors in $X'_2$, we may assume up to a symmetry that $b_3 \in A'_1$ and $b_4 \in B'_1$. So $b_2$ have non-neighbors in both $A'_1, B'_1$. This implies $b_2 \in C'_2$, and $B_3 \cup B_4 \subset X'_2$. Hence $A'_2 = B_3$ and $B'_2 = B_4$. Let $v$ be a vertex in $C_2 \cup A_2 \cup \{a_1\}$. By (6), there is a path $Q$ from $v$ to $c_1$ with no vertex in $B_3 \cup B_4$. Thus if $v \in X'_2$, $Q$ must have a vertex in $A'_2 \cup B'_2$, a contradiction. We proved $X'_2 = B_3 \cup B_4 \cup \{b_1\}$. If $|B_3| \ge 2$ then putting $Y = A'_1 \cap X_2$ and $Z = (C_2 \cup A_2) \setminus A'_1$ we find a contradiction to (18). So $|B_3| = 1$. Similarly $|B_4| = 1$. This implies that $(X'_1, X'_2)$ is not proper, a contradiction. This proves (22).

(23) If $G'$ has a proper 2-join $(X'_1, X'_2)$, then $(X'_1, X'_2)$ is a loose 2-join of $G'$ and exactly one of $(X'_1, V(G) \setminus X'_1)$, $(V(G) \setminus X'_2, X'_2)$ is a loose proper 2-join of $G$.

By (22), we may assume $\{c_1, c_2, b_1, b_3, b_4\} \subset X'_2$. If $b_3 \notin C'_2$ and $b_4 \notin C'_2$ then up to a symmetry we may assume $b_3 \in A'_2$, $b_4 \in B'_2$ since $b_3, b_4$ have no common neighbors in $X'_1$. So, there is a vertex of $A'_1$ in $B_3$ and a vertex of $B'_1$ in $B_4$ implying $b_1 \in A'_2 \cap B'_2$, a contradiction. We proved $b_3 \in C'_2$ or $b_4 \in C'_2$. Up to a symmetry we assume $b_3 \in C'_2$, implying $B_3 \subset X'_2$. Note that $X'_1$ is a subset of $V(G)$. If $A'_1 \cap B_4, B'_1 \cap B_4$ are both non empty then $b_1$ must be in $A'_2 \cap B'_2$, a contradiction. Thus we may assume $A'_1 \cap B_4 = \emptyset$. If $a_1 \in X'_1$ and $B'_1 \cap B_4 \neq \emptyset$ then $a_1 \notin B'_1$ since $a_1$ misses $b_1$. Thus we may assume $B'_1 \cap \{a_1\} = \emptyset$.

Let us now put: $X_1'' = X'_1$, $X_2'' = V(G) \setminus X_1''$, $A_1'' = A'_1$, $B_1'' = B'_1$, $B_2'' = B'_2 \setminus \{b_4\}$. If $a_1 \in A'_1$ then $A_2'' = (A'_2 \cap X_2) \cup (N_G(a_1) \cap X_1)$ else $A_2'' = A'_2$. Note that $A_2'' \cap B_2'' = \emptyset$ for otherwise $a_1$ sees $b_1$. Also, if $b_4 \in B'_2$ then $b_1 \in B'_2$ and $b_1 \in B_2''$. From the definitions it follows that $(X_1'', X_2'')$ is a partition of $V(G)$, that $A_1'', B_1'' \subset X_1'', A_2'', B_2'' \subset X_2''$, that $A_1''$ is complete to $A_2'',$ that $B_1''$ is complete to $B_2''$ and that there are no other edges between $X_1''$ and $X_2'$. So, $(X_1'', X_2'') = (X'_1, V(G) \setminus X'_1)$ is a 2-join of $G$. Note that $(V(G) \setminus X_2', X_2'')$ is not a 2-join of $G$ since it is not a partition of $V(G)$.

Let us put $D = (V(G) \setminus V(G')) \cup B_3 \cup \{b_1\}$. By the properties above, $D \subset X_2'' \subset V(G)$. Since $b_1$ is complete to $B_3$, $G[D]$ is connected. We claim that $(X_1'', X_2'')$ is a proper 2-join of $G$. Every component of $X_1''$ meets $A_1'', B_1''$: this
follows from $A_1'' = A_1', B_1'' = B_1'$ and from the fact that $(X_1', X_2')$ is a proper 2-join of $G'$. Let $E$ be a connected component of $X_2''$. If $E \cap D = \emptyset$ then $E$ is a component of $G[(X_2 \cup \{a_1\}) \cap X_2''] = G'[(X_2 \cup \{a_1\}) \cap X_2'']$, so $E$ meets $A_2'' \cap A_2'$ and $B_2'' \cap B_2'$ because $(X_1', X_2')$ is a proper 2-join of $G'$. If $E \cap D \neq \emptyset$ then $D \subset E$ since $G[D]$ is connected. We put $E' = (E \setminus D) \cup \{c_1, c_2, b_1, b_3, b_4\} \cup B_3$. Since $E'$ is a component of $X_2'$ it meets $A_2'$, $B_2'$ because $(X_1', X_2')$ is proper. This implies that $E$ meets $A_2''$ and $B_2''$. Note that $G[X_1'']$ is not an outgoing path of length 2 or 3 from $A_1''$ to $B_1''$, because $(X_1', X_2')$ is a proper 2-join of $G'$. Also $G[X_2'']$ is not an outgoing path from $A_2''$ to $B_2''$ because $b_1$ has at least 2 neighbors in $X_2''$ (one in $X_1$, one in $B_3$) while having degree at least 3 because of $B_4$. This proves our claim.

Since $(X_1'', X_2'')$ is proper, we know by (2) that $(X_1'', X_2'')$ is a loose 2-join of $G$. We claim that $(X_1', X_2')$ is a loose 2-join of $G'$. If $X_2''$ is the path-side of $(X_1'', X_2'')$ then $b_1$ is an interior vertex of this path while having degree at least 3, a contradiction. Hence, $X_1''$ is the path-side of $(X_1'', X_2'')$. We have two cases to consider:

**Case 1:** $(X_1'', X_2'')$ is loose because there are disjoint sets $B_3'', B_4''$ included in $B_2''$ satisfying all the requirements of the definition of loose 2-joins. If $b_1$ is in one of $B_3'', B_4''$ then we assume up to a symmetry $b_1 \in B_3''$ and we put $B_3' = B_3'' \cup \{b_4\}$, else we put $B_3' = B_3''$. Also we put $B_4' = B_4''$. There are no edges between $B_3'$ and $B_4'$. Also, $B_3' \cup B_4' = B_2'$. There is no vertex in $X_2'$ that is complete to $B_2'$ since such a vertex would be a vertex of $X_2''$ complete to $B_2''$. Also every outgoing path from $B_3'$ to $B_3'$ has even length. For suppose there is such a path $P$. If $P$ has ends $b_1, b_4$ then it has length 2 or 4. Else, after possibly replacing $b_4$ by $b_1$ and vertices of $\{c_1, c_2, b_3\}$ by vertices of $X_1$ without changing the parity of the length of $P$, $P$ may be viewed as a an outgoing path from $B_3''$ to $B_3''$. Thus $P$ has even length because $(X_1'', X_2'')$ is loose. Similarly, every outgoing path from $B_4'$ to $B_4'$ has even length. Hence, $(X_1', X_2')$ is loose as claimed.

**Case 2¹:** $(X_1'', X_2'')$ is loose because there are disjoint sets $A_3'', A_4''$ included in $A_2''$ satisfying all the requirements of the definition of loose 2-joins (up to a swap of “A” and “B” in the definition of loose 2-joins). The proof is similar to the previous case. This proves (23).

(24) $\overline{G'}$ has no proper 2-join.

In the proof of (24), the word “neighbor” refers to the neighborhood in $\overline{G'}$.

<footnote n="1">¹One might believe that loose 2-joins are just an uninteresting generalization of cutting 2-joins. This might be true, but an attempt to prove directly Theorem 2.13 by simply following the lines of the proof of Lemma 2.11 will fail here, at this Case 2. Indeed it may happen that the 2-join $(X_1'', X_2'')$ is cutting while $(X_1', X_2')$ is not. This is why we need loose 2-joins.</footnote>
Suppose $c_1 \neq c_2$. In $\overline{G'}$, $c_1$ has degree $n-3$, so up to a symmetry we may assume $c_1 \in A'_1$. In $B'_2$ there must be a non neighbor of $c_1$. Also, since $(X'_1, X'_2)$ cannot be a degenerate 2-join of $G'$, vertex $c_1$ must have a non neighbor in $B'_1$. So we have 2 cases to consider. Case 1: $a_1 \in B'_1$, $c_2 \in B'_2$. Then $c_2$ must have a non neighbor in $B'_2$ for otherwise $(X'_1, X'_2)$ is degenerate. This non-neighbor must be one of $b_3, b_4$. But this is impossible since $b_3, b_4$ both see $a_1$ in $\overline{G'}$. Case 2: $a_1 \in B'_2$, $c_2 \in B'_1$. Then one of $A'_2 \subset \{b_3, b_4\}$. So, $a_1 \in B'_2$ is complete to $A'_2$. Again, $(X'_1, X'_2)$ is degenerate.

Suppose $c_1 = c_2$. In $\overline{G'}$, $c_1$ has degree $n-4$. Up to a symmetry we assume $c_1 \in X'_1$. If $c_1 \in C'_1$ then the only possible vertices in $X'_2$ are $a_1, b_3, b_4$, so $\overline{G'}[X'_2]$ induces a triangle. So, any vertex of $A'_2$ is complete to $B'_2$ and $(X'_1, X'_2)$ is degenerate, a contradiction. So, $c_1 \notin C'_1$. Up to a symmetry, we assume $c_1 \in A'_1$. So, $B'_2 \subset \{a_1, b_3, b_4\}$. Thus, at least one of $a_1, b_3, b_4$ (say $x$) must be in $B'_2$. Since $(X'_1, X'_2)$ is not degenerate, $c_1$ must have a non neighbor in $B'_1$. So, one of $a_1, b_3, b_4$ (say $y$) must be in $B'_1$. Since $(X'_1, X'_2)$ is not degenerate, $x$ must have a non neighbor $z$ in $A'_2$. But $z$ must also be a non neighbor of $y$. This is impossible because in $G' \setminus c_1, N(a_1), N(b_3), N(b_4)$ are disjoint. This proves (24).

$$ (25) \quad f(G') + f(\overline{G'}) < f(G) + f(\overline{G}). $$

By (23) there is a map $\varphi$ that maps every loose proper 2-join of $G'$ to a loose proper 2-join of $G$. Moreover, $\varphi$ is injective because the 2-join in $G'$ shares a side with its image by $\varphi$. We proved $f(G') \le f(G)$. But in fact $f(G') < f(G)$ because $\varphi$ cannot map a 2-join of $G'$ to $(X_1, X_2)$ because $(V(G') \setminus X_2, X_2)$ is not a 2-join of $G'$. By (24) we know $0 = f(\overline{G'}) \le f(\overline{G})$. We can add these two inequalities. This proves (25).

Let us now finish the proof. By (14), $G'$ is a Berge. By (15), $G'$ is not basic. By (16), $G'$ has no even skew partition. By (23), $G'$ has no proper non loose 2-join. By (24) $\overline{G'}$ has no proper non loose 2-join. So, $G'$ is a counter example to the theorem we are proving now. Hence there is a contradiction between (1) and (25). $\square$

A 2-join $(X_1, X_2)$ is said to be *cutting* if:

1. $G[X_1]$ is an outgoing path from $A_1$ to $B_1$.

2. $G[X_2 \setminus A_2]$ is disconnected.

**Lemma 2.12** Let $G$ be a Berge graph. Let $(X_1, X_2)$ be a proper cutting 2-join of $G$. Then either $G$ has an even skew partition or $(X_1, X_2)$ is a loose proper 2-join of $G$.
PROOF — Up to a symmetry, we assume that $X_1$ is the path-side of $(X_1, X_2)$. Suppose first that in $G[X_2 \setminus A_2]$ there is a component disjoint from $B_2$. Thus $A_2$ is a cutset of $G[X_2]$, implying that $A_1 \cup A_2$ being a skew cutset of $G$, implying $(X_1, X_2)$ being degenerate. Thus by Lemma 2.9, $G$ has an even skew partition. So we may assume every component of $G[X_2 \setminus A_2]$ meets $B_2$. Let $Y$ be one of these components, and put $B_3 = B_2 \cap Y$. Also put $Z = X_2 \setminus (A_2 \cup Y)$ and $B_4 = B_2 \cap Z$. We shall prove that $B_3, B_4$ satisfy the definition of loose 2-join or that $G$ has an even skew partition.

Suppose that there is a vertex $v \in X_2 \setminus B_2$ that is complete to $B_2$. Then $v$ must be in $A_2$, implying $(X_1, X_2)$ being degenerate. Thus by Lemma 2.9, $G$ has an even skew partition. Thus we may assume that there is no vertex of $X_2 \setminus B_2$ that is complete to $B_2$.

Now we claim that every outgoing path of $G'$ from $B_3$ to $B_3$ (resp. from $B_4$ to $B_4$) has even length. For suppose there is such a an outgoing path $P = b-\cdots-b'$ from $B_3$ to $B_3$ (the case with $B_4$ is similar). Note that $P$ may have vertices in $B_4$, so Lemma 2.4 does not apply to $P$. If $P$ goes through $B_1$ it has length 2. So we may assume that $P$ does not go through $B_1$. If $P$ has no vertex in $A_2$, then $P$ have no interior vertices in $B_4$ since $B_3$ and $B_4$ are in distinct components of $G \setminus (B_1 \cup A_2)$. So, Lemma 2.4 applies and $P$ has even length.

So we may assume that $P$ has at least a vertex in $A_2$. Let us then call *B-segment of P* every subpath of $P$ whose end vertices are in $B_2$ and whose interior vertices are not in $B_2$. Note that $P$ is edgewise partitioned into its *B-segment*. Similarly, let us call *A-segment of P* every subpath of $P$ whose end vertices are in $A_2$ and whose interior vertices are not in $A_2$. By Lemma 2.4, every *A-segment* has even length or has length 1. An *A-segment* of length 1 is called an *A-edge*. Suppose that $P$ has odd length. Let $b, b' \in B_2$ be the end vertices of $P$. Along $P$ from $b$ to $b'$, let us call $a$ the first vertex in $A_2$ after $b$, and $a'$ the last vertex in $A_2$ before $b'$. So $b-P-a$ and $a'-P-b'$ are both outgoing paths from $B_2$ to $A_2$, and by Lemma 2.3 they have same parity. So $a-P-a'$ is a path of odd length that is edgewise partitioned into its *A-segment*, and that contains all the *A-segments* of $P$. Thus $P$ has an odd number of *A-edges*. Since $P$ is edgewise partitioned into its *B-segments*, there is a *B-segment* $P'$ of $P$ with an odd number of *A-edges*. Let $\beta, \beta'$ be the end vertices of $P'$. Along $P'$ from $\beta$ to $\beta'$, let us call $\alpha$ the first vertex in $A_2$ after $\beta$, and $\alpha'$ the last vertex in $A_2$ before $\beta'$. So $P'' = \alpha-P'-\alpha'$ is a path that is edgewise partitioned into its *A-segment* with an odd number of *A-edge*. Thus $P''$ has odd length. Since $\beta-P-\alpha$ and $\alpha'-P-\beta'$ are both outgoing paths from $B_2$ to $A_2$, they have same parity by Lemma 2.3. Finally, $P'$ is of odd length, with length at least 2, and contradicts Lemma 2.4. Thus $P$ has even length.
We proved that $(X_1, X_2)$ is loose.

☐

**Theorem 2.13** Let $G$ be a Berge graph. Then either:

* $G$ is basic;

* $G$ has an even skew partition;

* One of $G, \overline{G}$ has a non cutting proper 2-join.

**PROOF** — By Lemma 2.11, we may assume that $G$ has a non loose proper 2-join $(X_1, X_2)$. By Lemma 2.12, $(X_1, X_2)$ is non cutting or $G$ has an even skew partition. ☐

## References

[1] C. Berge. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung). Technical report, Wiss. Z. Martin Luther Univ. Math.-Natur. Reihe (Halle-Wittenberg), 1961.

[2] M. Chudnovsky. *Berge trigraphs and their applications*. PhD thesis, Princeton University, 2003.

[3] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. *Annals of Math*. To appear.

[4] V. Chvátal. Star-cutsets and perfect graphs. *J. Combin. Ser. B*, 39:189–199, 1985.

[5] M. Conforti, G. Cornuéjols, and K. Vušković. Square-free perfect graphs. *Jour. Comb. Th. Ser. B*, 90:257–307, 2004.

[6] G. Cornuéjols and W. H. Cunningham. Composition for perfect graphs. *Disc. Math.*, 55:245–254, 1985.