# Decomposing Berge graphs

Nicolas Trotignon

► To cite this version:

Nicolas Trotignon. Decomposing Berge graphs. 2006. halshs-00082823

HAL Id: halshs-00082823

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

Submitted on 28 Jun 2006

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

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

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

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

UNIVERSITÉ PARIS 1
-PANTHÉON - SORBONNE -

Centre d'Economie de la Sorbonne

UMR 8174

Cahiers de la MSE

Decomposing Berge graphs

Nicolas TROTIGNON

2006.02

<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
# Decomposing Berge graphs

Nicolas Trotignon*

January 11, 2006

## 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 and another theorem where some decompositions were restricted while other decompositions were extended. We prove here a theorem stronger than all these previously known results. Our proof uses at an essential step one of the theorems of Chudnovsky.

AMS Mathematics Subject Classification: 05C17, 05C75

## 1 Definitions and known theorems

In this paper graphs are simple and finite. A *hole* in a graph is an induced cycle of length at least 4. An *antihole* is the complement of a hole. A graph is said to be Berge if it has no odd hole and no odd antihole. A graph $G$ is said to be *perfect* if for every induced subgraph $G'$ the chromatic number of $G'$ is equal to the maximum size of a clique of $G'$. In 1961, Berge [1] conjectured that every Berge graph is perfect. This was known as the *Strong Perfect Graph Conjecture*, was the object of much research

<footnote>*Université Paris I Panthéon-Sorbonne, CERMSEM,
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>
and was finally proved by Chudnovsky, Robertson, Seymour and Thomas in
2002 [4]. In fact, they proved a stronger result: a decomposition theorem,
first conjectured by Conforti, Cornuéjols and Vušković [7], stating that every
Berge graph is either in a well understood basic class of perfect graph, or has
a structural fault that cannot occur in a minimum counter-example to Strong
Perfect Graph Conjecture. Before stating this decomposition theorem, we
need some definitions.

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 a path *P* we say that *P* is *from a to b*. The other vertices are the *interior* vertices of the path. We denote by $v_1-\cdots-v_n$ the path whose edge set is $\{v_1v_2, \ldots, v_{n-1}v_n\}$. 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 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 of *G* 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$.

If $X, Y \subset V(G)$ are disjoint, we say that $X$ is *complete* to $Y$ if every vertex in $X$ is adjacent to every vertex in $Y$. We also say that $(X, Y)$ is a *complete pair*. We say that $X$ is *anticomplete* to $Y$ if there are no edges between $X$ and $Y$. We also say that $(X, Y)$ is an *anticomplete pair*. We say that a graph $G$ is *anticonnected* if its complement $\bar{G}$ is connected.

Skew partitions were first introduced by Chvátal [5]. 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. When *A*₁, *A*₂, *B*₁, *B*₂ are non-empty sets such that (*A*₁, *A*₂) partitions *A*, (*A*₁, *A*₂), (*B*₁, *B*₂) partitions *B*, and (*B*₁, *B*₂) is complete, we say that (*A*₁, *A*₂, *B*₁, *B*₂) is a *split* of the skew partition (*A*, *B*). An *even skew partition* (first defined in [4]) 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*. Note that Chudnovosky et al. [4] proved that no minimum non-perfect graph have an even skew partition.

We call *double split graph* (first defined in [4]) any graph *G* that may be constructed as follows. Let *m*, *n* ≥ 2 be integers. Let *A* = {*a*₁, ..., *a*<sub>*m*</sub>}, *B* = {*b*₁, ..., *b*<sub>*m*</sub>}, *C* = {*c*₁, ..., *c*<sub>*n*</sub>}, *D* = {*d*₁, ..., *d*<sub>*n*</sub>} be four disjoint sets. Let *G* have vertex set *A* ∪ *B* ∪ *C* ∪ *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 j \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.

Note that $C \cup D$ is a non-even skew cutset of $G$ and that $\bar{G}$ is a double split graph. Note that in a double split graph, the vertices in $A \cup B$ all have degree $n+1$ and vertices in $C \cup D$ all have degree $2n+m-2$. Since $n \ge 2, m \ge 2$ implies $2n-2+m > 1+n$, it is clear that given a double split graph it is relevant to consider the *matching edges*, that have an end in $A$ and an end in $B$, independantly of the choice of the sets $A, B, C, D$. Figure 1 are depicted 2 examples of double split graphs.

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

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

The 2-join was first defined by Cornuéjols and Cunningham [9]. 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. When sets $A_i$'s $B_i$'s are like in the definition we say that $(X_1, X_2, A_1, B_1, A_2, B_2)$ is a *split* of $(X_1, X_2)$. Implicitly, for $i=1,2$, 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.

A 2-join is said to be a *path 2-join* if it has a split $(X_1, X_2, A_1, B_1, A_2, B_2)$ such that $G[X_1]$ is an outgoing path from $A_1$ to $B_1$. Implicitly we will then denote by $a_1$ the unique vertex in $A_1$ and by $b_1$ the unique vertex in $B_1$. We say that $X_1$ is the *path-side* of the 2-join. Note that when $G$ is not a hole then this path-side is unique. A *non-path 2-join* is a 2-join that is not a path 2-join.

The *homogeneous pair* was first defined by Chvátal and Sbihi [6]. The definition that we give here is a slight variation used in [4]. An homogeneous pair is a partition of $V(G)$ into six non-empty sets $(A, B, C, D, E, F)$ such that:

* every vertex in $A$ has a neighbor in $B$ and a non-neighbor in $B$, and vice versa;

* the pairs $(C, A)$, $(A, F)$, $(F, B)$, $(B, D)$ are complete;

* the pairs $(D, A)$, $(A, E)$, $(E, B)$, $(B, C)$ are anticomplete.

$G$ is *path-cobipartite*<fnref n="1" /> if it is a Berge graph obtained by subdividing an edge between the two cliques that partitionned a cobipartite graph. More accurately, a graph is path-cobipartite if its vertex set can be partitionned into three sets $A, B, P$ where $A$ and $B$ are non-empty cliques and $P$ consist of vertices of degree 2, each of which belongs to the interior of a unique path of odd length with one end $a$ in $A$, the other one $b$ in $B$. Moreover, $a$ has neighbors only in $A \cup P$ and $b$ has neighbors only in $B \cup P$. Note that a path-cobipartite graph such that $P$ is empty is the complement of bipartite graph.

A *cutset* is a graph $G$ is a set $C \subset V(G)$ such that $G \setminus C$ is disconnected ($G \setminus C$ means $G[V(G) \setminus C]$). A *double star* in a graph is a subset $D$ of the vertices such that there is an edge $ab$ in $G[D]$ satisfying: $D \subset N(a) \cup N(b)$.

Now we can state the known decomposition theorems of Berge graphs. The first decomposition theorem for Berge graph ever proved is the following:

**Theorem 1.1 (Conforti, Cornuéjols and Vušković, 2001, [8])** Every graph with no odd hole is either basic or has a proper 2-join or has a double star cutset.

<footnote n="1">¹Our path-cobipartite graphs are simply the complement of the path-bipartite graphs defined by Chudnovsky in [2]. For convenience, we prefer to think about them in the complement as we do.</footnote>
It could be thought that this theorem is useless to prove the Strong Perfect Graph Theorem since there are minimal imperfect graphs that have double star cutset: the odd antiholes of length at least 7. However, by the Strong Perfect Graph Theorem, we know that the following fact is true: for any minimal non-perfect graph $G$, one of $G, \bar{G}$ has no double star cutset. A direct proof of this — of which we have no idea — would yield together with Theorem 1.1 a new proof of the Strong Perfect Graph Theorem.

The following theorem was first conjectured in a slightly different form by Conforti, Cornuéjols and Vušković, who proved it in the particular case of square-free graphs [7]. A corollary of it is the Strong Perfect Graph Theorem.

**Theorem 1.2 (Chudnovsky, Robertson, Seymour and Thomas, 2002, [4])**

Let $G$ be a Berge graph. Then either $G$ is basic or $G$ has an homogeneous pair, of $G$ has an even skew partition or one of $G, \bar{G}$ has a proper 2-join.

The two theorems that we state now are due to Chudnovsky who proved them from scratch, that is without assuming Theorem 1.2. Her proof uses the notion of *trigraph*. The first theorem shows that homogeneous pairs are not necessary to decompose Berge graphs. Thus it is a result stronger than Theorem 1.2. The second one shows that path 2-joins are not necessary to decompose Berge graphs, but at the price of exending even skew partitions to general skew partitions and introducing a new basic class. Note that a third theorem can be obtained by viewing the second one in the complement of $G$.

**Theorem 1.3 (Chudnovsky, 2003, [3, 2])** Let $G$ be a Berge graph.

Then either $G$ is basic, or one of $G, \bar{G}$ has a proper 2-join or $G$ has an even skew partition.

**Theorem 1.4 (Chudnovsky, 2003, [3, 2])** Let $G$ be a Berge graph.

Then either $G$ is basic, or one of $G, \bar{G}$ is path-bipartite, or $G$ has a proper 2-join that is not a path 2-join, or $\bar{G}$ has a proper 2-join or $G$ has a skew partition.

## Main results and Motivation

Our main result is Theorem 1.5, that easily implies Theorems 1.2, 1.3 and 1.4. We expect algorithmic applications that will be given in a work in preparation. Note that our proof of Theorem 1.5 is not a new proof of the previously known decomposition theorems for Berge graphs, since it
uses at an essential step Theorem 1.3. Before going further we need more definitions.

We call *flat path of a graph G* any path whose interior vertices all have degree 2 in G and whose ends have no common neighbors outside of the path.

We call *path-double split graph* any graph obtained from a double split graph *G* by subdivising matching edges of *G* into paths of odd length. Note that a double split graph is a path-double split graph. More accurately, a path-double split graph is any graph *G* that may be constructed as follows. Let *m*, *n* ≥ 2 be integers. Let *A* = {*a*₁, ..., *a*_m}, *B* = {*b*₁, ..., *b*_m}, *C* = {*c*₁, ..., *c*_n}, *D* = {*d*₁, ..., *d*_n} be four disjoint sets. Let *E* be another possibly empty set. Let *G* have vertex set *A* ∪ *B* ∪ *C* ∪ *D* ∪ *E* and edges in such a way that:

* for every vertex *v* in *E*, *v* has degree 2 and there exists *i* ∈ {1, ..., *m*} such that *v* lies on path of odd length from *a*ᵢ to *b*ᵢ;

* for 1 ≤ *i* ≤ *m*, there is a unique path of odd length (possibly 1) between *a*ᵢ and *b*ᵢ whose interior is in *E*. There are no edges between {*a*ᵢ, *b*ᵢ} and {*a*ᵢ', *b*ᵢ'} for 1 ≤ *i* < *i'* ≤ *m*;

* *c*<sub>j</sub> is non-adjacent to *d*<sub>j</sub> for 1 ≤ *j* ≤ *m*. There are all four edges between {*c*<sub>j</sub>, *d*<sub>j</sub>} and {*c*<sub>j'</sub>, *b*<sub>j'</sub>} for 1 ≤ *j* < *j'* ≤ *n*;

* there are exactly two edges between {*a*<sub>i</sub>, *b*<sub>i</sub>} and {*c*<sub>j</sub>, *d*<sub>j</sub>} for 1 ≤ *i* ≤ *m* and 1 ≤ *j* ≤ *n* and these two edges are disjoint.

An *homogeneous 2-join* is a partition of $V(G)$ into six non-empty sets $(A, B, C, D, E, F)$ such that:

* $(A, B, C, D, E, F)$ is an homogeneous pair.

* Every vertex in *E* has degree 2 and belongs to a flat path of odd length with an end in *C*, an end in *D* and whose interior is in *E*.

Our main result is the following:

**Theorem 1.5** Let $G$ be a **Berge graph**. Then either $G$ is **basic**, or one of $G, \bar{G}$ is a **path-cobipartite graph**, or one of $G, \bar{G}$ is a **path-double split graph**, or one of $G, \bar{G}$ has an **homogeneous 2-join**, or one of $G, \bar{G}$ has a **non-path proper 2-join**, or $G$ has an **even skew partition**.
This theorem is stronger than Theorems 1.2, 1.3 and 1.4 because path-cobipartite graphs may be seen either as graphs having a proper path 2-join (Theorems 1.2 and 1.3) or as a new basic class (Theorem 1.4). Path-double split graphs may be seen as graphs having a proper path 2-join (Theorems 1.2 and 1.3) or as graphs having a non-even skew partition (Theorem 1.4). And graphs having an homogeneous 2-join may be seen as graph having an homogeneous pair (Theorems 1.4 and perhaps 1.2) or as graphs having a proper path 2-join (Theorems 1.3 and perhaps 1.2). Formally all these remarks are not always true: it may happen in special cases that path-cobipartite graphs and path-double split graphs have no proper 2-join. But such graphs are established in Lemma 2.3 to be basic or to have an even skew partition.

## 2 Lemmas

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 in a graph is a set of vertices $B$ such that there is a vertex $x$ in $B$, called a center of the star, 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 either $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** — We may assume that $G$ has size at least 4 and at least one edge. 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. Thus up to a symmetry $|A_1| \ge 2$ since $G$ has at least 4 vertices. There is no edge between $B$ and $A_1$ for otherwise such an edge would be a cutset contradicting $|B|$ being maximum. There is no edge in $A_2$ since such an edge would be a cutset of $G$. If there is no edge in $A_1$, any edge of $G$ is a cutset of $G$. So, there is an edge $e$ in $A_1$. So, $|A_1| = 2$ and $B$ is complete to $A_2$ for otherwise, $e$ is a cutset of $G$. So, $|A_2| = 1$ for otherwise, any edge between $B$ and $A_2$ is a cutset edge of $G$. Now, we observe that $G$ is the complement of $C_4$.
If $B$ has size at least 2 then $B$ is a skew cutset of $G$. Let $x$ be a 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 a 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$. $\square$

The following lemma is useful to establish formally that Theorem 1.5 really implies Theorems 1.2, 1.3 and 1.4. But we also need it at several places in the next section.

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

* If $G$ has a flat path $P$ of length at least 3 then either $G$ is bipartite, or $G$ has an even skew partition or $P$ is the path-side of a proper path 2-join of $G$.

* If $G$ is a path-cobipartite graph, a path-double split graph or has an homogeneous 2-join, then either $G$ has a proper 2-join or $G$ has an even skew partition or $G$ is a bipartite graph, the complement of a bipartite graph, or a double-split graph.

**PROOF** — Let us prove the first item. Let $P$ be a flat path of $G$ of length at least 3. So $(P, V(G) \setminus P)$ is a path 2-join of $G$. Let $(P, X_2, \{a_1\}, \{b_1\}, A_2, B_2)$ be a split of this 2-join. If $(P, X_2)$ is not proper, then either there is a component of $X_2$ that does not meet one of $A_2$, $B_2$, or $X_2$ induces a path of length 1 or 2. In the last case, $G$ is bipartite, and in the first one, we may assume that there is a component $C$ of $X_2$ that does not meet $B_2$. But then, $\{a_1\} \cup (A_2 \setminus C)$ is a star cutset of $G$ that separates $C$ from $B_2$, and so by Lemma 2.2, $G$ has an even skew partition.

The second item follows easily: if $G$ is a path-cobipartite graph, then we may assume that $G$ is not the complement of a bipartite graph. If $G$ is a path-double split graph then we may assume that $G$ is not a double split graph. In both cases, $G$ has a flat path of length at least 3. If $G$ has an homogeneous 2-join then it also has a flat path of length at least 3. In every cases, the conclusion follows from the first item. $\square$

## Paths and antipaths overlapping 2-joins

**Lemma 2.4** 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$. The paths $P_1, P_2$ have same parity because $P_1 \cup P_2$ induces a hole. Let $P$ be an outgoing path from $A_1$ to $B_1$ (the proof is the same for an outgoing path from $A_2$ to $B_2$). Let $P^*$ be the interior of $P$. Then one of $P \cup P_2, P^* \cup P_2$ induces a hole. Hence, $P, P_1, P_2$ have same parity. □

**Lemma 2.5** 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. Every antipath of length at least 2 whose interior is in $A_i$ (resp. $B_i$) and whose ends are outside $A_i$ (resp. $B_i$) has even length.

**PROOF** — Note that we do not suppose $(X_1, X_2)$ being connected, so Lemma 2.4 does not apply. Let $P$ be an outgoing path from $A_1$ to $A_1$ (the other cases are 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\}$ 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.

Let $Q$ be an antipath of length at least 2 whose interior is in $A_1$ and whose ends are outside $A_1$ (the other cases are similar). If $Q$ has length at least 3, then the ends of $Q$ must have a neighbor in $A_1$ and a non-neighbor in $A_1$. Hence these ends are in $X_1$. Thus, $Q \cup \{a\}$, where $a$ is any vertex of $A_2$ is an antihole of $G$. Thus, $Q$ has even length. □

**Lemma 2.6** 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$. Vertices $a_2, a, b_1, b_2$ show that the second outcome holds. $\square$

**Lemma 2.7** 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, c \in X_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, c \in X_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 that the end-vertices of $P$ are in $A_1 \cup X_2$ (the case when the end-vertices of $P$ are all in $B_1 \cup X_2$ is similar).

If $P$ has its two end-vertices in $A_1$, then by Lemma 2.5, $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.6 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.6 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. $\square$
**Lemma 2.8** Let $G$ be a graph with a 2-join $(X_1, X_2)$. Let $Q$ be an antipath of $G$ of length at least 4 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.9** 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** — We suppose 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-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'$. Hence, either all the interior vertices of $Q$ are in $A_1$ and by Lemma 2.5, $Q$ has even length, or $c, c' \in B_1$ and $Q$ has interior vertices in $B_2$. But in this last case, the interior of $Q$ is an antipath of length at least 3 with vertices in both $A_1, B_2$, which are anticomplete to one another, a contradiction.

If $Q$ has exactly one vertex $a$ in $A_1$ then by assumption, $a$ is an interior vertex of $Q$. Let $c, c'$ be the ends of $Q$. Suppose $c \in X_1$. Since $Q$ has length at least 5, $c$ must have a neighbor in the interior $Q$ that is different of $a$, hence $c \in B_1$. Since $Q$ has length at least 5, $a$ and $c$ must have a common neighbor, that must be $c'$ since it must be in $X_1$. Hence $c' \in X_1$, implying $c' \in B_1$. Now the non-neighbor of $c'$ along $Q$ is not $a$, so it must be a vertex
of $X_2$ while seeing $c$ and missing $c'$, a contradiction. We proved $c \in X_2$, and similarly $c' \in X_2$. Hence $V(Q) \subset X_2 \cup \{a\}$.

If $Q$ has no vertex in $A_1$ then Lemma 2.8 applies: there is a vertex $a \in A_1 \cup B_1$ such that $V(Q) \subseteq X_2 \cup \{a\}$. $\square$

## Even skew partitions overlapping 2-joins

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 exists $i \in \{1, 2\}$ and a vertex in $C_i$ that is complete to $A_i \cup B_i$.

**Lemma 2.10** 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. Hence, in $\bar{G}$ there is a star cutset of center $v$, and by Lemma 2.2 and 2.1, $G$ has an even skew partition. The cases with $A_2, B_1, B_2$ are similar.

If $A_1 \cup A_2$ is a skew cutset of $G$ then let us check that this skew cutset is even (the case when $B_1 \cup B_2$ is a skew cutset is similar). Since $A_1$ is complete to $A_2$, any outgoing path from $A_1 \cup A_2$ to $A_1 \cup A_2$ is either outgoing from $A_1$ to $A_1$ or outgoing from $A_2$ to $A_2$. Thus, such a path has even length by Lemma 2.5. If there is an antipath $Q$ of length at least 5 with its interior in $A_1 \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. Thus, such an antipath has even length by Lemma 2.5. The case with $B_1 \cup B_2$ is similar.
If there is a vertex $a \in A_1$ that is complete to $B_1$ (the other cases are symmetric) then suppose first $|A_1| > 1$. Consider $a' \neq a$ in $A_1$. Hence $(\{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 $A_1 = \{a\}$. If $|B_1| > 1$, consider $b \neq b'$ in $B_1$. Hence, $(\{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, X_2)$ is proper, $|X_1| \ge 3$, and 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 a vertex $c$ complete to $A_i \cup B_i$ then we may assume $C_i = \{c\}$ for otherwise there is another vertex $c'$ in $C_i$ and $\{c\} \cup A_i \cup B_i$ is a star cutset separating $c'$ from the rest of the graph. By the preceding paragraph, we may assume that there is a vertex $a \in A_1$ and a vertex $b \in B_1$ missing $a$. Then $a-c-b$ is an outgoing path of even length from $A_i$ to $B_i$. Thus by Lemma 2.4, there is no edge between $A_i$ and $B_i$. If there are two vertices $a \neq a' \in A_i$ then $\{a\} \cup N(a) \setminus \{a'\}$ is a star cutset of $G$ separating $a'$ from $B_{3-i}$. Thus may assume $|A_i| = 1$, and similarly $|B_i| = 1$. Thus, $X_i$ is an outgoing path of length 2 from $A_i$ to $B_i$ contradicting $(X_1, X_2)$ being proper.
□

**Lemma 2.11** 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)$. So $P_b$ exists: consider a shortest path from $v$ to $b$ in $G[V(Q) \cup \{b\}]$. $\square$
**Lemma 2.12** Let $G$ be a Berge graph with a non-degenerate and connected 2-join $(X_1, X_2)$. Let $F$ be an even skew cutset of $G$. Then for some $i \in \{1, 2\}$ either:

* $F \subsetneq X_i$;

* $F \cap X_i \subsetneq X_i$ and one of $(F \cap X_i) \cup A_{3-i}$, $(F \cap X_i) \cup B_{3-i}$ is an even skew cutset of $G$;

**PROOF** — We consider three cases:

**Case 1:** $F \cap A_1, F \cap A_2, F \cap B_1, F \cap B_2$ are all non-empty.

If there is a vertex $a \in A_1 \cap F$ non-adjacent to a vertex $b \in B_1 \cap F$ then there is an antipath of length at most 3 between any vertex of $F$ and $a$, contradicting $\overline{G}[F]$ being disconnected. Thus $A_1 \cap F$ is complete to $B_1 \cap F$, and similarly $A_2 \cap F$ is complete to $B_2 \cap F$. Similarly, we prove $F \cap C_1 = F \cap C_2 = \emptyset$. If $A_1 \subset F$ then there is a vertex in $B_1$ that is complete to $A_1$, contradicting $(X_1, X_2)$ being non-degenerate. Thus $A_1 \setminus F \neq \emptyset$, and similarly $A_2 \setminus F \neq \emptyset$, $B_1 \setminus F \neq \emptyset$, $B_2 \setminus F \neq \emptyset$.

Let $E_1$ be the component of $G \setminus F$ that contains $(A_1 \setminus F) \cup (A_2 \setminus F)$. Let $E_2$ be another component of $G \setminus F$. Up to a symmetry we assume $E_2 \cap X_2 \neq \emptyset$. We claim that $F' = (F \cap X_2) \cup A_1$ is a skew cutset of $G$ that separates $E_1 \cap X_2$ from $E_2 \cap X_2$. For suppose not. This means that there is a path $P$ of $G \setminus F'$ with an end in $E_1 \cap X_2$ and an end in $E_2 \cap X_2$. If $P$ has no vertex in $X_1$ then $P \subset G \setminus F$ and $P$ contradicts $E_1, E_2$ being components of $G \setminus F$. If $P$ has a vertex in $X_1$ then this vertex $b$ is unique and is in $B_1$ because $A_1 \subset F'$. By replacing $b$ by any vertex of $B_1 \setminus F$, we obtain again a path that contradicts $E_1, E_2$ being components of $G \setminus F$. Thus $F'$ is a skew cutset of $G$. Note that this skew cutset is included in $A_1 \cup A_2 \cup B_2$. Let us prove that this skew cutset is even.

Let $P$ be an outgoing path from $F'$ to $F'$. Let us apply Lemma 2.7 to $P$. If Outcome 1 of the lemma holds then $P$ has even length. If Outcome 2 of the lemma holds then $V(P) \subset X_2 \cup \{a, b\}$. Let $a_1$ be a vertex of $A_1 \cap F$ and $b_1$ be a vertex of $B_1 \setminus F$ such that $a_1$ misses $b_1$. Note that $b_1$ exists for otherwise $(X_1, X_2)$ is a degenerate 2-join of $G$. After possibly replacing $a$ by $a_1$ and $b$ by $b_1$, we obtain an outgoing path from $F$ to $F$ that has same length than $P$. Thus, $P$ has even length since $F$ is an even skew cutset. If Outcome 3 of the lemma holds then $P$ has one end in $A_1$ and one end in $B_2$ and $P$ is an outgoing path from $A_1$ to $B_1$ plus one edge. Note that there is an edge between $A_2$ and $B_2$ so by Lemma 2.4 every outgoing path from $A_1$ to $B_1$ has odd length. Hence in every cases $P$ has even length.
Let $Q$ be an antipath with both ends in $G \setminus F'$ and interior in $F'$. If $Q$ has length 3 then $Q$ may be seen as an outgoing path from $F'$ to $F'$, so we may assume that $Q$ has length at least 5. By Lemma 2.9 applied to $Q$, either $Q$ has even length or $V(Q) \subset X_2 \cup \{a\}$. If $a \in A_1$ let us replace $a$ by a vertex of $F \cap A_1$ and if $a \in B_1$ let us replace $a$ by a vertex of $B_1 \setminus F$. We obtain an antipath that have same length than $Q$, that has both ends outside of $F$ and interior in $F$. Thus $Q$ has even length because $F$ is an even skew cutset.

**Case 2:** one of $F \cap A_1$, $F \cap A_2$, $F \cap B_1$, $F \cap B_2$ is empty and $F \cap X_1$, $F \cap X_2$ are both non-empty.

We assume up to a symmetry that one of $B_1 \cap F$, $B_2 \cap F$ is empty. Since $F \cap X_1$ and $F \cap X_2$ are both non-empty, there is a least an edge between $F \cap X_1$ and $F \cap X_2$ because $\overline{G}[F]$ is disconnected. Thus we know that $F \cap A_1$ and $F \cap A_2$ are both non-empty. If $(F \cap X_1) \setminus A_1$ and $(F \cap X_2) \setminus A_2$ are both non-empty then there is a vertex of $F$ in one of $C_1, C_2$ since one of $B_1 \cap F$, $B_2 \cap F$ is empty. Up to a symmetry, suppose $C_1 \cap F \neq \emptyset$. Then $\overline{G}[F]$ is connected since every vertex in it can be linked to a vertex of $C_1$ by an antipath of length at most 2, a contradiction. Hence one of $(F \cap X_1) \setminus A_1$ and $(F \cap X_2) \setminus A_2$ is empty. Thus we may assume $F \subset X_2 \cup A_1$. Suppose $B_2 \subset F$. Then $B_2$ and $F \cap A_1$ are in the same component of $\overline{G}[F]$, thus there must be a vertex $v$ in $F$ that is complete to $B_2 \cup (F \cap A_1)$. So, $v$ is in $A_2$, and $v$ is complete to $B_2$, contradicting $(X_1, X_2)$ being non-degenerate. We proved that there is at least a vertex $u$ in $B_2 \setminus F$. In particular, $F \cap X_2 \subsetneq X_2$. By Lemma 2.11 there is a path from every vertex of $X_1 \setminus F$ to $u$, thus there is a component $E_1$ of $G \setminus F$ that contains $X_1 \setminus F$ and $u$. There is another component $E_2$ included in $X_2$. Thus $(F \cap X_2) \cup A_1$ is a skew cutset of $G$ that separates $B_1$ from $E_2$. We still have to prove that the skew cutset $(F \cap X_2) \cup A_1$ is even.

Let $P$ be an outgoing path from $(F \cap X_2) \cup A_1$ to $(F \cap X_2) \cup A_1$. Let us apply Lemma 2.7 to $P$. If Outcome 1 of the lemma holds then $P$ has even length. If Outcome 2 of the lemma holds then $V(P) \subset X_2 \cup \{a, b\}$. Let $a_1$ be a vertex of $A_1 \cap F$ and $b_1$ be a vertex of $B_1$ such that $a_1$ misses $b_1$. Note that $b_1$ exists for otherwise $(X_1, X_2)$ is a degenerate 2-join of $G$. After possibly replacing $a$ by $a_1$ and $b$ by $b_1$ then we obtain an outgoing path from $F$ to $F$ that has the same length than $P$. Thus, $P$ has even length since $F$ is an even skew cutset. If Outcome 3 of the lemma holds then $P = a \cdots b - b_2 - \cdots - c$. Let $a_1$ be in $A_1 \cap F$. By Lemma 2.11 there is a path $P_1$ of $G[X_1]$ from $a_1$ to a vertex $b_1 \in B_1$. Moreover, $P_1$ is outgoing from $A_1$ to $B_1$. Note that by Lemma 2.4, $P_1$ and $a-P-b$ have same parity. Thus $a_1-P_1-b_1-b_2-P-c$ is an outgoing path from $F$ to $F$ that has the same parity that $P$. Thus $P$
has even length.

If $\mathcal{Q}$ is an antipath with both ends in $G \setminus ((F \cap X_2) \cup A_1)$ and its interior in $(F \cap X_2) \cup A_1$, we prove that $\mathcal{Q}$ has even length like in Case 1.

**Case 3:** One of $F \cap X_1$, $F \cap X_2$ is empty.

Since $F \subsetneq X_2$ is an output of the lemma, we may assume up to a symmetry $F = X_2$. If there is an outgoing path of odd length from $A_2$ to $B_2$, then there is by Lemma 2.4 an outgoing path $P$ from $A_1$ to $B_1$ of odd length. Hence $A_2$ is complete to $B_2$ because a pair of non-adjacent vertices yields together with $P$ an outgoing path of odd length from $F$ to $F$, contradicting $F$ being an even skew cutset. In particular, there is a vertex of $A_2$ that is complete to $B_2$, implying $(X_1, X_2)$ being degenerate, a contradiction. If there is an outgoing path of even length from $A_2$ to $B_2$ then by Lemma 2.4 there are no edges between $A_2$ and $B_2$. Since $X_2 = F$ is not anticonnected, there is a vertex in $C_2$ that is complete to $A_2 \cup B_2$, implying again $(X_1, X_2)$ being degenerate, a contradiction. $\square$

Now we turn our attention to types of 2-join whose contraction may create even skew partitions:

* A 2-join $(X_1, X_2)$ is said to be *cutting of type 1* 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$.

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

* A 2-join is said to be *cutting of type 2* if it has a split $(X_1, X_2, A_1, B_1, A_2, B_2)$ such that there exist sets $A_3, B_3$ satisfying:

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

2. $A_3 \neq \emptyset, B_3 \neq \emptyset, A_3 \subset A_2, B_3 \subset B_2$;

3. $A_3$ is complete to $B_3$;

4. every outgoing path from $B_3 \cup \{a_1\}$ to $B_3 \cup \{a_1\}$ (resp. from $A_3 \cup \{b_1\}$ to $A_3 \cup \{b_1\}$) has even length;

5. every antipath with its ends outside of $B_3 \cup \{a_1\}$ (resp. $A_3 \cup \{b_1\}$) and its interior in $B_3 \cup \{a_1\}$ (resp. $A_3 \cup \{b_1\}$) has even length.

6. $G \setminus (X_1 \cup A_3 \cup B_3)$ is disconnected;

* A 2-join is said to be *cutting* if it is either cutting of type 1 or cutting of type 2.
Let $G$ be a Berge graph and $(X_1, X_2, A_1, B_1, A_2, B_2)$ be a split of a proper 2-join of $G$. The pieces of $G$ with respect to $(X_1, X_2, A_1, B_1, A_2, B_2)$ are the two graphs $G_1, G_2$ that we describe now. We obtain $G_1$ by replacing $X_2$ by a flat path $P_2$ from a vertex $a_2$ complete to $A_1$, to a vertex $b_2$ complete to $B_1$. This path has the same parity than an outgoing path from $A_1$ to $B_1$. The length of $P$ is decided as follows: if $(X_1, X_2)$ is a path 2-join then $P$ has length 1 or 2, else it has length 3 or 4. The piece $G_2$ is obtained similarly by replacing $X_1$ by a flat path.

**Lemma 2.13** Let $G$ be a Berge graph and $(X_1, X_2)$ be a non-cutting, non-degenerate and proper 2-join of $G$. Then $G$ has an even skew partition if and only if one of the pieces of $G$ has an even skew partition.

**PROOF** — Suppose first that $G$ has an even skew partition $(E, F)$. By Lemma 2.12 and up to a symmetry either $F \subsetneq X_2$, or $(F \cap X_2) \subsetneq X_2$ and $A_1 \subset F$ (after possibly replacing $F$ by $(F \cap X_2) \cup A_1$).

If $F \subsetneq X_2$ then we claim that $F$ is an even skew cutset of $G_2$. Note that there is at least a component $E$ of $G \setminus F$ that has some vertex in $X_2$ but no vertex in $A_2 \cup B_2$. Else every component of $G \setminus F$ has neighbors in $A_1$ and $B_1$ (because $(X_1, X_2)$ is proper) or in $A_2 \cup B_2$, implying $G \setminus F$ being connected, a contradiction. Thus, $F$ is a skew cutset of $G_2$ that separates $E$ from $V(G_2) \setminus X_2$. Let $P$ be an outgoing path of $G_2$ from $F$ to $F$. Let us apply Lemma 2.6 to $P$. If Outcome 1 of the Lemma holds then after possibly replacing $a$ be $a_1$ and $b$ by $b_1$, $P$ may be viewed as an outgoing of $G$ from $F$ to $F$, thus $P$ has even length. If Outcome 2 of the lemma holds, then $P = c \cdots a_2 - a_1 - \cdots - b_1 - b_2 - \cdots - c'$. Let $P'$ be any outgoing path from $A_1$ to $B_1$ whose interior is in $X_1$. Then $c \cdots a_2 - P' - b_2 - \cdots - c'$ is an outgoing path of $G$ from $F$ to $F$ that has same parity than $P$ by Lemma 2.4. Thus $P$ has even length. Let $Q$ be an antipath of $G_2$ with its ends out of $F$ and its interior in $F$. Let us apply Lemma 2.8 to $Q$: $V(Q) \subseteq X_2 \cup \{a\}$. Thus, after possibly replacing $a$ by a vertex in $A_1 \cup B_1$, $Q$ may be seen as an antipath of $G$ that has same length than $Q$. Thus $Q$ has even length.

If $(F \cap X_2) \subsetneq X_2$ and $A_1 \subset F$ then we put $F' = (F \cap X_2) \cup \{a_1\}$. We claim that $F'$ is an even skew cutset of $G_2$. Exactly as above, we prove that $F'$ is a skew cutset of $G_2$ that separates $b_1$ from a component of $G \setminus F$ that has vertices in $X_2$ but no vertex in $B_2$. Let $P$ be an outgoing path from $F'$ to $F'$. As above we prove that $P$ has even length by Lemma 2.7. Let $Q$ be an antipath of $G_2$ with its ends out of $F'$ and its interior in $F'$. As above, we prove that $Q$ has even length by Lemma 2.9.
Let us suppose conversely that one of $G_1, G_2$ (say $G_2$ up to a symmetry)
has an even skew cutset $F'$. We denote by $P_1 = a_1 - \dots - b_1$ the path induced
by $V(G_2) \setminus X_2$. Note that $G_2$ has an obvious connected path 2-join: $(P_1, X_2)$.

(1) Either:

• $F' \subsetneq X_2$;

• $F' \cap X_2 \subsetneq X_2$ and one of $(F' \cap X_2) \cup \{a_1\}$, $(F \cap X_2) \cup \{b_1\}$ is an even skew cutset of $G$;

If $P_1$ has length 3 or 4, then $(P_1, X_2)$ is proper. It is non-degenerate because $(X_1, X_2)$ is non-degenerate. Let us apply Lemma 2.12. The conclusion $F' \subsetneq X_1$, is impossible by Lemma 2.11. Also $(F' \cap P_1) \cup A_2$ and $(F' \cap P_1) \cup B_2$ cannot be skew cutsets of $G_2$, because $a_1, b_1$ cannot be both in a skew cutset of $G_2$ since they are non adjacent with no common neighbors. Hence, Lemma 2.11 proves that $(F' \cap P_1) \cup A_2$ and $(F' \cap P_1) \cup B_2$ are not cutsets of $G_2$. Thus (1) is simply the only possible conclusion of Lemma 2.12.

If $P_1$ has length 2 then $P_1 = a_1 - c_1 - b_1$. If $a_1, b_1$ are both in $F'$, then $F' = \{a_1, c_1, b_1\}$ because $c_1$ is the only common neighbor of $a_1, b_1$ in $G_2$. This means that $G_2[X_2] = G[X_2]$ is disconnected, implying that $(X_1, X_2)$ is a cutting 2-join of type 1, a contradiction. By Lemma 2.11 applied to $G_2[X_2] = G[X_2]$, none of $a_1, b_1$ can be the center of a star cutset of $G$. Hence, $c_1 \notin F'$. Thus, $F \cap X_2 \subsetneq X_2$ because any induced subgraph of $P_1$ containing $c_1$ is connected. We proved (1) when $P_1$ has length 2.

We are left with the case when $P_1 = a_1 - b_1$. If $a_1, b_1$ are both in $F'$ then $F' \subset \{a_1, b_1\} \cup A_2 \cup B_2$. If $F' \cap A_2 \neq \emptyset$ and $F' \cap B_2 \neq \emptyset$ then putting $A_3 = F' \cap A_2$ and $B_3 = F' \cap B_2$ then we see that $(X_1, X_2)$ is a cutting 2-join of type 2 of $G$. If at least one of $F' \cap A_2$ and $F' \cap B_2$ is empty then we see that $(X_1, X_2)$ is a cutting 2-join of type 1. Both cases contradict $(X_1, X_2)$ being non-cutting. Thus we know that at most one of $a_1, b_1$ is in $F$. Also $F' \cap X_2 \subsetneq X_2$ because every induced subgraph of $P_1$ is connected. This proves (1).

By (1), we may assume that not both $a_1, b_1$ are in $F'$. Up to a symmetry,
we assume $b_1 \notin F'$. If $a_1 \in F'$, put $A'_1 = A_1$, else put $A'_1 = \emptyset$. Now
$F = (F' \cap X_2) \cup A'_1$ is a skew cutset of $G$ that separates a vertex of $X_2$ from
$X_1 \setminus A'_1$. The proof that $F'$ is an even skew cutset of $G$ is entirely similar
to the similar proofs above: we consider a an outgoing path of $G$ from $F'$
to $F'$. Lemma 2.6 or Lemma 2.7 shows that $P$ has the same parity than
an outgoing path of $G_2$ from $F'$ to $F'$. We consider an antipath $Q$ of $G$ of
length at least 2 with all its interior vertices in $N$ and with its end-vertices
outside of $N$. Lemma 2.8 or Lemma 2.9 shows that $Q$ has the same parity
than an outgoing path of $G_2$ from $F'$ to $F'$.
$\square$

Even skew partitions overlapping homogeneous 2-joins

**Lemma 2.14** Let $G$ be a Berge graph with an homogeneous 2-join $(A, B, C, D, E, F)$. Let $c \in C, d \in D$ be two vertices such that there is path whose interior is in $E$ between them. Then $F \subset N(c) \cup N(d)$. Moreover, if $c, d$ are not adjacent then $N(c) \cap N(d) \cap F = \emptyset$.

**PROOF** — Let $P$ be a path whose interior is in $E$ joinning $c, d$. If a vertex $f \in F$ misses both $c, d$, then consider a pair $a \in A, b \in B$ of non-adjacent vertices. Then $\{a, b, f\} \cup P$ induces an odd hole. Thus $F \subset N(c) \cup N(d)$. If $c, d$ are not adjacent, suppose that a vertex $f \in F$ sees both $c, d$. Since there is at least an edge $a'b'$ with $a' \in A, b' \in B$, $P$ has odd length for otherwise $P \cup \{a', b'\}$ induces an odd hole. But since there is a non-edge $ab$ with $a \in A, b \in B$, $P \cup \{a, b, f\}$ is an odd hole. Hence $N(c) \cap N(d) \cap F = \emptyset$. $\square$

An homogeneous 2-join $(A, B, C, D, E, F)$ is said to be *degenerate* if either:

* there is a vertex $x \in C$ such that $N(x) \subset A \cup D \cup E$ or a vertex $y \in D$ such that $N(y) \subset B \cup C \cup E$;

* there is a vertex $x \in C$ with no neighbor in $E \cup D$ or a vertex $y \in D$ with no neighbor in $E \cup C$;

**Lemma 2.15** Let $G$ be a Berge graph with a degenerate homogeneous 2-join. Then $G$ has a proper non-path 2-join or $G$ has an even skew partition.

**PROOF** — Suppose first that there exists $x \in C$ be such that $N(x) \subset A \cup D \cup E$ (when there exists $y \in D$ such that $N(y) \subset B \cup C \cup E$, the proof is similar). Let $N_x$ be the set containing $x$ plus the vertices of $E$ that lie on a path from $x$ to a vertex of $D$. Note that by Lemma 2.14, for every $d \in D$ that is the end of such a path, $d$ is complete to $F$ since $x$ has no neighbor in $F$. Thus, for any $f \in F$, $\{f\} \cup N(F) \setminus B$ is a star cutset of $G$ that separates $N_x$ from $B$. Thus, by Lemma 2.2, $G$ has an even skew partition.

Suppose now that there exists a vertex $x \in C$ with no neighbor in $E \cup D$. Then, $(A \cup C \cup F) \setminus \{x\}$ is a skew cutset that separates $x$ from the rest of the graph. Thus, $\bar{G}$ has a star cutset centered at $x$. By Lemma 2.2, $\bar{G}$ has an even skew partition and by Lemma 2.1 so is $G$. $\square$
The following is needed twice in the next section:

**Lemma 2.16** Let $G$ be a Berge graph. Suppose that $G$ has a vertex $u$ of degree 3 whose neighborhood induces a stable set. Moreover, $G$ has a stable set $\{x, y, z\}$ such that $x, y, z$ all have degree at least 3. Then $G$ is not a path-cobipartite graph, not a path-double split graph and $G$ has no non-degenerate homogeneous 2-join.

**PROOF** — In a path-cobipartite graph the vertices of degree at least 3 partition into 2 cliques. Since $\{x, y, z\}$ contradicts this property, $G$ is not a path-cobipartite

In a path-double split graph, every vertex of degree exactly 3 must have
an edge in his neighborhood. Since $u$ contradicts this property, $G$ is not a
path-double split graph

If $G$ has a non-degenerate homogeneous 2-join $(A, B, C, D, E, F)$, then every vertex in $F$ has degree at least 4. Every vertex in $A, B$ has an edge in his neighborhood. Every vertex in $C$ has a neighbor in $C$ or $F$ for otherwise, $(A, B, C, D, E, F)$ is degenerated. Thus, every vertex in $C$, and by the same way every vertex in $D$, has an edge in his neighborhood. Every vertex in $E$ has degree 2. Hence, $u$ is in none of $A, B, C, D, E, F$, a contradiction. $\square$

**3 Proof of Theorem 1.5**

For any graph $G$ that is not a hole, let $f(G)$ be the number of maximal flat paths of $G$. Let us consider $G$, a counter-example to Theorem 1.5 such that $f(G) + f(\bar{G})$ is minimal.

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

a. $G$ is not basic;

b. None of $G, \bar{G}$ is a path-cobipartite graph;

c. None of $G, \bar{G}$ is a path-double split graph;

d. $G$ has no even skew partition;

e. None of $G, \bar{G}$ has a non-path proper 2-join;

f. None of $G, \bar{G}$ has an homogeneous 2-join;

g. $G$ has a path proper 2-join.
Since $G$ has a path proper 2-join, $G$ has flat path of length at least 3, implying $f(G) \ge 1$. We choose such a flat path $X_1$ inclusion-wise maximal. Note that by Lemma 2.3, $(X_1, V(G) \setminus X_1)$ is a proper 2-join of $G$ since $G$ is not basic and has no even skew partition. Let us consider $(X_1, X_2, A_1, B_1, A_2, B_2)$ a split of this 2-join. Note that $G[X_2]$ is not a path since $G$ is not bipartite. We denote by $a_1$ the only vertex in $A_1$ and by $b_1$ the only vertex in $B_1$. We put $C_1 = X_1 \setminus \{a_1, b_1\}$, and $C_2 = X_2 \setminus (A_2 \cup B_2)$. Since $X_1$ is a maximal flat path we know:

h. $a_1, b_1$ both have degree at least 3 in $G$.

If one of $G, \bar{G}$ has a degenerate proper 2-join, a degenerate homogeneous 2-join or a star cutset then one of $G, \bar{G}$ has an even skew partition by Lemma 2.10, Lemma 2.15 or Lemma 2.2. So $G$ has an even skew partition by Lemma 2.1. This contradicts $G$ being a counter-example. Thus:

i. $G$ and $\bar{G}$ have no degenerate proper 2-join, no degenerate homogeneous 2-join and no star cutset.

Let us study the connectivity of $G$. If $G[X_2]$ is disconnected, then let $X'_2$ be any component of $G[X_2]$. Since $(X_1, X_2)$ is proper, the sets $A_2 \cap X'_2$ and $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 since $G$ is a counter example, we know that $(V(G) \setminus X'_2, X'_2)$ is a path 2-join of $G$. Since $X_1$ is a maximal flat path of $G, V(G) \setminus X'_2$ cannot be the path side of this 2-join. Thus $G[X'_2]$ is the path side of this 2-join. Hence we know that every component of $X_2$ is an outgoing path from $A_2$ to $B_2$. This implies that $G$ is bipartite contradicting $G$ being a counter example. Hence:

j. $G[X_2]$ is connected.

Since by property i, $(X_1, X_2)$ is non-degenerate, the following is a direct consequence of Lemma 2.11:

k. In $G[X_2]$, there exists an outgoing path from $A_2$ to $B_2$. Moreover, for every $A'_2 \subseteq A_2$, $B'_2 \subseteq B_2$ the graphs $G[A'_2 \cup C_2 \cup B_2 \cup \{b_1\}]$, $G[B'_2 \cup C_2 \cup A_2 \cup \{a_1\}]$ are connected.

The eleven properties listed above will be refered as the *properties of G* in the rest of proof. We denote by $\epsilon \in \{0, 1\}$ the parity of the length of
$G[X_1]$. We now consider three cases according to the properties of $(X_1, X_2)$. In every case, we will consider a graph $G'$ obtained from $G$ by detroying the path 2-join $(X_1, X_2)$, and we will show that $G'$ is a counter-example that contradicts $f(G) + f(\bar{G})$ being minimal.

**Case 1:** $(X_1, X_2)$ is cutting of type 1.

Up to a symmetry we assume that $G[X_2 \setminus A_2]$ is disconnected. Let $X$ be a component of $G[X_2 \setminus A_2]$. If $X$ is disjoint from $B_2$ then $\{a_1\} \cup A_2$ is a star cutset of $G$ separating $X$ from $X_2 \setminus X$, contradicting the properties of $G$. Thus $X$ intersects $B_2$, and by the same proof so is any component of $X_2 \setminus X$. Hence, there are two non-empty sets $B_3 = B_2 \cap X$ and $B_4 = B_2 \setminus X$. Also we put $C_3 = C_2 \cap X$, $C_4 = C_2 \setminus X$. Possibly, $C_3, C_4$ are empty. There are no edges between $B_3 \cup C_3$ and $B_4 \cup C_4$.

We consider the graph $G'$ obtained from $G$ by deleting $X_1 \setminus \{a_1, b_1\}$. Moreover, we add 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 for convenience $c_1 = c_2$, so that $c_1$ is always a vertex of $G'$. 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 seven claims about the parity of various kinds of paths and antipaths in $G'$.

(1) 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.4 it has parity $\varepsilon$. This proves (1).

(2) 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 (1) 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$. Hence $P$ may be viewed as a path of $G$. Thus, $P$ has even length by Lemma 2.5. In every cases, $P$ has even length. This proves (2).

(3) 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 $c_2$ or through both $b_3, b_4$ 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 (1) $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 (1), 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.5.

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

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

Suppose that there is 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 interior vertices in $B_4$, so (2) 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$ has 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 (2) 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 (3), 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 (1) 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 (1). Finally, $P'$ is of odd length, outgoing from $B_2$ to $B_2$, and contradicts (2). Thus P has even length. This proves (4).

(5) 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$. So $Q$ has even length by Lemma 2.5. This proves (5).

(6) 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$. So $Q$ has even length by Lemma 2.5. This proves (6).

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

Let $Q$ be such an antipath whose interior is in $B_3$ (the case with $B_4$ is similar). 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 (6) applies and $Q$ has even length. This proves (7).

(8) 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 (8).

(9) $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 (3), 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 (1). 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 (1). So $H$ has even length and we may assume that $H$ does not go through $a_1$. 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 (2), so $H$ is even. If $H$ goes through $b_1$ then the path $H \setminus \{b_1\}$ has even length by (2), 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 (2). 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 (4) 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 (8) 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 (5), $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 (6), $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 (7), $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 (9).

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

Let $(F', E')$ be an even skew partition of $G'$ with a split $(E'_1, E'_2, F'_1, F'_2)$. Starting from $F'$, we shall build an even skew cutset $F$ of $G$ which contradicts the properties of $G$.

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 the property $k$ of $G$. 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 the property $k$ of $G$. 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 the property $k$ of $G$. So if $c_1 \neq c_2$ then $c_1 \notin F'$.

Suppose $c_2 \in F'$. By the property $k$ of $G$, 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 the property $k$ of $G$. 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 $A_2$. But this implies $(X_1, X_2)$ being degenerate, contradicting the properties of $G$.

We proved $\{c_1, c_2, b_4\} \subset E'_1$ and $\{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, b_4\} \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 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.6 applies to $P$. Suppose that the first outcome of Lemma 2.6 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$ has even length since $F'$ is an even skew cutset of $G'$. Suppose now that the second outcome of Lemma 2.6 is satisfied: $P = c-\cdots-a_2-a_1-X_1-b_1-b_2-\cdots-c'$. 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 same parity and $P'$ is an outgoing path of $G'$ from $F'$ to $F'$. So $P'$ and $P$ has 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' = 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 F$. So Lemma 2.7 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$ then $a_1 \notin F$, $F \subset X_2 \cup \{b_1\}$, and Lemma 2.7 applies. If Outcome 1 of the lemma holds, then $P$ has even length. If Outcome 2 of the lemma holds, we may assume that $b_1$ that is in $F \setminus F'$ and that $b_1$ is an end of $P$, for otherwise the proof works like in the paragraph above. Then we build a path $P'$ of $G'$ that is outgoing from $F'$ to $F'$ and that has a length with same parity than $P$, by replacing $\{b_1\}$ by $\{b_3\}$ (if $P$ goes through $B_3$) or by $\{b_3, c_2, b_4\}$ (if $P$ goes through $b_4$). So $P$ has even length. If Outcome 3 of the lemma holds then $P = b_1-X_1-a_1-a_2-\cdots-c$ where $a_2 \in A_2, c \in X_2$. Note that one of $b_1, b_3$ is in $F'$. If $b_3 \in F'$, then we put $P' = b_3-c_2-c_1-a_1-a_2-P-c$. If $b_3 \notin F'$ then up to a symmetry, we assume $V(a-P-c) \subset A_2 \cup C_3$. Note that $b_1 \in F'$. We put $P' = b_1-b-b_4-c_2-c_1-a_1-a_2-P-c$ where $b$ is any vertex in $B_4$. It may happen that $P'$ is not a path of $G'$ because of the chord $a_2b$. But then we put $P' = b_1-b-a_2-P-c$. In every cases, $P'$ is outgoing from $F'$ to $F'$, and has same parity than $P$. Hence, $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 $F \subset X_2$ and the interior vertices of $Q$ are all in $X_2$. So Lemma 2.8 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.9 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 \in F$, we have to consider the case when $b_1 \notin F'$ (else the proof is like in the paragraph above). Since $b_1 \notin F'$, we have $b_3 \in F'$. Note that $B_4 \cap F' = B_4 \cap F = \emptyset$ since there are no edges between $b_3, B_4$ and no vertex seeing $b_3$ while having a neighbor in $B_4$. So, if $Q$ is an antipath whose interior is in $F$, then $Q$ does not go through $B_4$. Hence, if we replace $b_1$ by $b_3$, we obtain an antipath $Q'$ whose interior is in $F'$ and whose ends are not. Hence, $Q$ has even length.

In every cases, $Q$ has even length. This proves (10).

(11) $G'$ and $\overline{G'}$ have no degenerate proper 2-join, no degenerate homogeneous 2-join and no star cutset.

If one of $G', \overline{G'}$ has a degenerate proper 2-join, a degenerate homogeneous 2-join or a star cutset then one of $G', \overline{G'}$ has an even skew partition by Lemma 2.10, 2.15 or 2.2. This contradicts (10). This proves (11).

(12) $G'$ is not basic, not a path-cobipartite graph, not a path-double split graph and has no homogeneous 2-join.

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 the property $k$ of $G$, there is an outgoing path from $A_2$ to $B_2$ that has partity $\varepsilon$ by (1). So, the number of colors in $A_2 \cup B_2$ is equal to $1+\varepsilon$, implying that $G$ is bipartite and contradicting the properties of $G$. Hence $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.

Let us choose $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. Note that $b, b'$ both have degree at least 3 in $G'$ because since $(X_1, X_2)$ is not degenerate, $b, b'$ have neighbors in $A_2 \cup C_2$. Also $a_1$ has degree at least 3 in $G'$ by the property $h$ of $G$. So, there exist in $G'$ a stable set of size 3 containing vertices of degree at least 3 $(\{a_1, b, b'\})$, and a vertex of degree 3 whose neighborhood induces a stable set ($c_1$). Hence, by Lemma 2.16, $G'$ is not a path-cobipartite graph (and in particular, it is not the complement of a bipartite graph), not a
path-double split graph (and in particular, it is not a double split graph)
and $G'$ has no non-degenerate homogeneous 2-join. Hence by (11), $G'$ has
no homogeneous 2-join. This proves (12).

(13) 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 the property j of $G$, $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 the properties of $G$. 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.11). By the properties of $G$, this 2-join has to be a path 2-join. Since $X_1$ is a maximal flat path of $G$, $Y_2 \cup Z_2$ is the path-side of the 2-join. This is impossible because $|B_2| \ge 2$. This proves (13).

We now give four claims describing the proper 2-joins of $G'$. Implicitly,
when $(X'_1, X'_2)$ is a 2-join, we consider a split $(X'_1, X'_2, A'_1, B'_1, A'_2, B'_2)$. We
also put $C'_1 = X'_1 \setminus (A'_1 \cup B'_1)$ and $C'_2 = X'_2 \setminus (A'_2 \cup B'_2)$.
(14) 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 the property k of $G$ 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$, 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 \in X'_1$. Let $v$ a vertex in $C_2$ (if any). Then by the property $k$ of $G$ 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 the property $k$ of $G$, $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 (A_2 \cup 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 (13).

Second case: $b_4 \in X'_2$. Then $b_4 \in A'_2$ and $A'_1 = \{c_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$. So $b_3$ is a vertex of $C'_1$ complete to $A'_1 \cup B'_1$, implying $(X'_1, X'_2)$ being degenerate, a contradiction.

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 the property $k$ of $G$ 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 \neq 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 (14).

(15) 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 (14), 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 \neq c_2$ then our claim hold trivially: $c_1 c_2 \in X'_1$ and
$b_3 b \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'_2$ 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$. So $b_4 \in C'_1$ is complete to $A'_1 \cup B'_1$,
implying $(X'_1, X'_2)$ being degenerate, a contradiction. 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 the property j of $G$. 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 $(X'_1, X'_2)$ being 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.11 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 (13). This proves (15).
(16) 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 (15), 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$. Now, $b_1 \in C'_2$ is complete to $A'_2 \cup B'_2$, implying $(X'_1, X'_2)$ being degenerate, a contradiction. This proves (16).

(17) $G'$ has no proper non-path 2-join.

Let $(X'_1, X'_2)$ be a proper 2-join of $G'$. By (16), 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$. 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'')$ is a 2-join of $G$.

Let us put $D = B_3 \cup X_1 \setminus \{a_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_2''$ 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 the properties of $G$ that $(X_1'', X_2'')$ is a path 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 by the properties of $G$, a contradiction. Hence, $X_1''$ is the path-side of $(X_1'', X_2'')$. Since $X_1'' = X_1'$, $(X_1', X_2')$ is a path 2-join of $G'$. This proves (17).

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

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

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 $\overline{G'}$, vertex $c_1$ must have a non-neighbor in $B_1'$. So we have two 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 imposible 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 $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$. 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 imposible because in $G' \setminus c_1$, $N(a_1)$, $N(b_3)$, $N(b_4)$ are disjoint. This proves (18).

(19) $\overline{G'}$ is not path-cobipartite, not a path-double split graph, has no homogeneous 2-join and has no flat path of length at least 3.
Else, by Lemma 2.3 there is a contradiction with one of (12), (10) or (18). This proves (19).

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

Every vertex in {$a_1$} $\cup$ $B_3$ $\cup$ $B_4$ has degree at least 3 in $G'$. For $a_1$, this is a property of $G$ and for vertices in $B_3$ $\cup$ $B_4$, this is because $(X_1, X_2)$ is not degenerate. Hence no vertex in {$a_1$} $\cup$ $B_3$ $\cup$ $B_4$ can be an interior vertex of a flat path of $G'$, and no vertex in {$c_1, c_2, b_3, b_4, b_1$} can be in a maximal flat path of $G'$ of length at least 3. Hence, every maximal flat path of $G'$ of length at least 3 is a maximal flat path of $G$, implying $f(G') \le f(G)$. But in fact $f(G') < f(G)$ because $X_1$ is a flat path of $G$ that is no more a flat path in $G'$. By (19) we know $0 = f(\overline{G'}) \le f(\overline{G})$. We add these two inequalities. This proves (20).

Let us now finish the case. By (9), $G'$ is Berge. By (12), $G'$ is not basic, not path-cobipartite, not a path-double split graph, and has no homogeneous 2-join. By (10), $G'$ has no even skew partition. By (17), $G'$ has no proper non-path 2-join. By (18) $\overline{G'}$ has no proper 2-join. By (19), $\overline{G'}$ is not a path-cobipartite graph, a path-double split graph and has no homogeneous 2-join. So, $G'$ is a counter-example to the theorem we are proving now. Hence there is a contradiction between the initial choice of $G$ and (20). This completes the proof in Case 1.

**Case 2:** There are sets $A_3$, $B_3$ satisfying the items 1–5 of the definition of cutting 2-joins of type 2.

The frame of the proof is very much like in Case 1, but the details differ. We consider the graph $G'$ obtained from $G$ by deleting $X_1 \setminus \{a_1, b_1\}$. Moreover, we add new vertices: $c_1, c_2, a_3, b_3$. Then we add every possible edge between $a_3$ and $A_3$, between $b_3$ and $B_3$. We also add edges $a_1c_1, c_1c_2, c_2b_1, a_3b_3, c_1a_3, c_2b_3$. Here are two claims about the connectivity of $G$ and $G'$.

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

(21) Every outgoing path of $G'$ from $B_2$ to $A_2$ has odd length.

If such a path contains one of $a_1, b_1, a_3, b_3, c_1, c_2$ then it has length 3 or 5. Else such a path may be viewed as an outgoing path of $G$ from $B_2$ to $A_2$. By Lemma 2.4 it has odd length. This proves (21).

(22) Every outgoing path of $G'$ from $A_2$ to $A_2$ (resp. from $B_2$ to $B_2$) has even length.
For suppose there is such a path $P$ from $A_2$ to $A_2$ (the case with $B_2$ is similar). If $P$ goes through $a_1$ then it has length 2. If $P$ goes through at least one of $c_1, c_2, a_3, b_3, b_1$ then $P$ is the union of two edge-wise-disjoint outgoing paths from $A_2$ to $B_2$. Thus $P$ has even length by (21). Else, $P$ may be viewed as an outgoing path of $G$ from $A_2$ to $A_2$, that has even length by Lemma 2.5. In every cases, $P$ has even length. This proves (22).

(23) Every outgoing path of $G'$ from $A_3$ to $A_3$ (resp. from $B_3$ to $B_3$) has even length.

For suppose there is such a path $P$ from $A_3$ to $A_3$ (the case with $B_3$ is similar). If $P$ goes through $a_1$ or $a_3$ then it has length 2. Also, $P$ cannot go through $c_1$. From now on, we assume that $P$ goes through none of $a_1, a_3, c_1$.

If $P$ goes through $c_2$ then $P = a-b-b_3-c_2-b_1-b'-\cdots a'$ where $a, a' \in A_3$, $b \in B_3$ and $b' \in B_2 \setminus B_3$. Also, $b_1-P-a'$ may be viewed as an outgoing path of $G$ from $A_3 \cup \{b_1\}$ to $A_3 \cup \{b_1\}$. By the definition of cutting 2-joins of type 2, this path has even length, thus $P$ has length. From now on we assume that $P$ does not go through $c_2$.

If $P$ goes through $b_3$ it has length 4. If $P$ goes through $b_1$ then $P$ is the edge-wise-disjoint union of two outgoing paths of $G$ from $A_3 \cup \{b_1\}$ to $A_3 \cup \{b_1\}$. Thus $P$ has even length by the definition of cutting 2-joins of type 2. Thus we may assume that $P$ goes through none of $b_3, b_1$.

Now $P$ may be viewed as an outgoing path of $G$ from $A_3$ to $A_3$, that does not go through $b_1$. Thus $P$ is outgoing from $A_3 \cup \{b_1\}$ to $A_3 \cup \{b_1\}$, it has even length by the definition of cutting 2-joins of type 2. This proves (23).

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

Let $Q$ be such an antipath whose interior is in $A_2$ (the case with $B_2$ is similar). 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$ can be an end-vertex of $Q$. If $a_3$ is an end of $Q$ then the other end of $Q$ must be a neighbor of $a_3$, a contradiction. Thus $Q$ may be viewed as an antipath of $G$. By Lemma 2.5. So $Q$ has even length. This proves (24).

(25) Every antipath of $G'$ with length at least 2, with its end vertices in $V(G') \setminus A_3$ (resp. $V(G') \setminus B_3$), and all its interior vertices in $A_3$ (resp. $B_3$) has even length.
Let $\mathcal{Q}$ be such an antipath whose interior is in $A_3$ (the case with $B_3$ is similar). We may assume that $\mathcal{Q}$ has length at least 3. So each end-vertex of $\mathcal{Q}$ must have a neighbor in $A_3$ and a non-neighbor in $A_3$. So none of $a_1, a_3, c_1, c_2, b_1, b_3$ can be an end-vertex of $\mathcal{Q}$. Thus $\mathcal{Q}$ may be viewed as an antipath of $G$. It has even length by the definition of cutting 2-joins of type 2. This proves (25).

(26) Let $\mathcal{Q}$ be an antipath of $G'$ of length at least 5. Then $\mathcal{Q}$ does not go through $c_1, c_2$. Moreover one of $V(\mathcal{Q}) \cap \{a_1, a_3\}, V(\mathcal{Q}) \cap \{b_1, b_3\}$ is empty.

Let $\mathcal{Q}$ be such an antipath. In an antipath of length at least 5, each vertex is in a triangle of the antipath. So, $c_1, c_2$ are not in $\mathcal{Q}$ since they are not in any triangle of $G'$.

Suppose $V(\mathcal{Q}) \cap \{a_1, a_3\}, V(\mathcal{Q}) \cap \{b_1, b_3\}$ are both non-empty. In an antipath of length at least 6, for every pair $u, v$ of vertices, there is a vertex $x$ seeing both $u, v$. Thus $\mathcal{Q}$ has length 5 because no vertex of $G'$ have neighbors in both $\{a_1, a_3\}, \{b_1, b_3\}$. Let $q_1, \dots, q_6$ be the vertices of $\mathcal{Q}$ in there natural order. Since $V(\mathcal{Q}) \cap \{a_1, a_3\}, V(\mathcal{Q}) \cap \{b_1, b_3\}$ are both non-empty there are two vertices of $\mathcal{Q}$ that have no common neighbors in $G'$. These vertices must be $q_2$ and $q_5$, and up to a symmetry we must have $q_2 = a_3, q_5 = b_3$. Thus $q_3$ must be a vertex of $B_3$ and $q_4$ must be a vertex of $A_3$. There is a contradiction since by the definition of cutting 2-joins of type 2, $A_3$ is complete to $B_3$. This proves (26).

(27) $G'$ is Berge.

Let $H$ be a hole of $G'$.

If $H$ goes through both $c_1, c_2$ then $H$ has length 4 or it must contains one of $\{a_1, b_1\}, \{a_1, b_3\}, \{b_1, a_3\}$. In the first case, $H$ is edge-wise partitionned into two paths outgoing from $A_2$ to $B_2$. Thus $H$ has even length by (21). In the second case $H$ is edge-wise partitionned into two paths outgoing from $B_3 \cup \{a_1\}$ to $B_3 \cup \{a_1\}$, one of them of length 4, the other one included in $V(G)$. Thus $H$ has even length by the definition of cutting 2-joins of type 2. The third case is similar. From now on, we assume that $H$ goes through none of $c_1, c_2$.

If $H$ goes through both $a_1, a_3$ then it has length 4. If $H$ goes through $a_2$ and not through $a_3$ then $H$ has even length by (22). If $H$ goes through $a_3$ and not through $a_2$ then $H$ has even length by (23). Thus, we may assume that $H$ goes through none of $a_1, a_3$. Similarly, we may assume that $H$ goes through none of $b_1, b_3$.

Now $H$ may be viewed as a hole of $G$. In every case, $H$ has even length.
Let us now consider an antihole $H$ of $G'$. We may assume that $H$ has length at least 7. Let $v$ be a vertex of $V(H) \setminus \{a_1, b_1, c_1, c_2, a_3, b_3\}$. By (26) the antipath $V(H) \setminus v$ does not go through $c_1, c_2$ and we may assume up to a symmetry that $V(Q) \cap \{b_1, b_3\}$ is empty. If $H$ goes through both $a_1, a_3$ then $H$ must contains a vertex that sees $a_3$ and misses $a_1$, a contradiction. If $H$ goes through $a_1$ and not through $a_3$ then $H$ has even length by (24). If $H$ goes through $a_3$ and not through $a_1$ then $H$ has even length by (25). If $H$ goes through none of $a_1, a_3$ then $H$ may be viewed as an antihole of $G$. In every case, $H$ has even length. This proves (27).

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

Suppose that $G'$ has an even skew partition $(E', F')$ with a split $(E'_1, E'_2, F'_1, F'_2)$. Starting from $F'$, we shall build an even skew cutset $F$ of $G$ which contradicts the properties of $G$.

By the property k of $G$, $F'$ cannot be a star cutset centered at one of $a_1, b_1, c_1, c_2, a_3, b_3$. For the same reason, $F'$ cannot be a subset of one of $\{c_1, c_2, a_3, b_3\}, \{a_1, c_1, a_3\} \cup A_3, \{b_1, c_2, b_3\} \cup B_3$. Thus, $c_1 \notin F'$ and $c_2 \notin F'$. Since $a_1, b_1$ are non-adjacent with no common neighbors, they are not both in $F'$. Similarly $a_1, b_3$ are not both in $F'$ and $a_3, b_1$ are not both in $F'$. From now on we assume $b_1 \notin F'$. Up to symmetry we may assume $\{c_1, c_2, b_1\} \subset E'_1$, implying $\{a_1, a_3, c_1, c_2, b_1, b_3\} \cap E' \subset E'_1$.

Let $v$ be any vertex of $E'_2$. Since $\{a_1, a_3, c_1, c_2, b_1, b_3\} \cap E' \subset E'_1$, we have $v \in X_2$. If one of $a_1, a_3$ is in $F$, put $A'_1 = \{a_1\}$, else put $A'_1 = \emptyset$. Now $F = A'_1 \cup F' \setminus \{a_3, b_3\}$ is a skew cutset of $G$ that separates $v$ from the interior vertices of the path induced by $X_1$. 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 \notin F$, then $F \subset X_2$ and the end-vertices of $P$ are both in $X_2$. So Lemma 2.6 applies to $P$. Suppose that the first outcome of Lemma 2.6 is satisfied: $V(P) \subseteq X_2 \cup \{a_1, b_1\}$. Hence, $P$ may be viewed as an outgoing path from $F'$ to $F'$, so $P$ has even length since $F'$ is an even skew cutset of $G'$. Suppose now that the second outcome of Lemma 2.6 is satisfied: $P = c-\cdots-a_2-a_1-X_1-b_1-b_2-\cdots-c'$. Put $P' = c-P-a_2-a_1-c_1-c_2-b_1-b_2-P-c'$. The paths $P$ and $P'$ have same parity and $P'$ is an outgoing path of $G'$ from $F'$ to $F'$. So $P'$ and $P$ has even length since $F'$ is an even skew cutset of $G'$.

If $a_1 \in F$ then $F \subset X_2 \cup \{a_1\}$ and Lemma 2.7 applies. If Outcome 1 of the lemma holds, then $P$ has even length. If Outcome 2 of the lemma holds then we may assume $a_1 \in F \setminus F'$ and $a_1$ is an end of $P$, since otherwise the
proof works like in the paragraph above. This implies $a_3 \in F'$. We build a path $P'$ of $G'$ that is outgoing from $F'$ to $F'$ with same parity than $P$, by replacing $\{a_1\}$ by $\{a_3, c_1, a_1\}$. So $P$ has even length. If Outcome 3 of the lemma holds then $P = a_1-X_1-b_1-b_2-\cdots-c$ where $b_2 \in B_2$, $c \in X_2$. Note that one of $a_1, a_3$ is in $F'$. If $a_3 \in F'$, then we put $P' = a_3-c_1-c_2-b_1-b_2-P-c$. If $a_3 \notin F'$ then $a_1 \in F'$ and we put $P' = a_1-c_1-c_2-b_1-b_2-P-c$. In every cases $P$ has even length.

Now, let $Q$ be an antipath of $G$ of length at least 5 with all its interior vertices in $F$ and with its end-vertices outside of $F$. We shall prove that $Q$ has even length.

If $a_1 \notin F$, then $F \subset X_2$ and the interior vertices of $Q$ are all in $X_2$. So Lemma 2.8 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$, we assume $a_1 \notin F'$ (else the proof is like in the paragraph above). Since $a_1 \notin F'$, we have $a_3 \in F'$. Note that $(A_2 \setminus A_3) \cap F' = (A_2 \setminus A_3) \cap F = \emptyset$. For otherwise consider a vertex $a$ in $(A_2 \setminus A_3) \cap F'$. Then $a-a_1-c_1-a_3$ is an outgoing path from $F'$ to $F'$ of odd length, contradicting $F'$ being an even skew cutset. So, if $Q$ is an antipath whose interior is in $F$, then $Q$ does not go through $A_2 \setminus A_3$. Hence, if we replace $a_1$ by $a_3$, we obtain an antipath $Q'$ whose interior is in $F'$ and whose ends are not. Hence, $Q$ has even length.

In every cases, $Q$ has even length. This proves (28).

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

If one of $G'$, $\overline{G'}$ has a degenerate proper 2-join, a degenerate homogeneous 2-join or a star cutset, then $G'$ has an even skew partition by Lemma 2.10, 2.15 or 2.2. This contradicts (28). This proves (29).

(30) $G'$ is not basic, not a path-cobipartite graph, not a path-double split graph and has no homogeneous 2-join.

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 the property k of $G$, there is an outgoing path from $A_2$ to $B_2$ that has odd length by (21). Thus $G$ is bipartite, contradicting the properties of $G$. Hence $G'$ is not bipartite.

The graph $G'[c_2, c_1, a_1, a_3]$ is a claw, so $G'$ is not the line-graph of a bipartite graph. $\overline{G'}[a_1, b_1, a_3, b_3]$ is a diamond, so $\overline{G'}$ is not the line-graph of
a bipartite graph.

Note that $b_1$ has degree at least 3 in $G'$ by the property h of $G$. So, there exist in $G'$ a stable set of size 3 containing vertices of degree at least 3 ($\{b_1, b_3, c_1\}$), and a vertex of degree 3 whose neighborhood induces a stable set ($c_1$). Hence, by Lemma 2.16, $G'$ is not a path-cobipartite graph (and in particular, it is not the complement of a bipartite graph), not a path-double split graph (and in particular, it is not a double split graph) and $G'$ has no non-degenerate homogeneous 2-join. Hence by (29), $G'$ has no homogeneous 2-join. This proves (30).

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

Suppose not. Up to a symmetry, we have five cases to consider according to $X'_1 \cap \{c_1, c_2, a_3, b_3\}$. Each of them leads to a contradiction:

• $\{c_1\} \subset X'_1$ and $\{c_2, a_3, b_3\} \subset X'_2$

Up to a symmetry, we assume $c_1 \in A'_1$ and $c_2, a_3 \in A'_2$. Note that $A'_1 = \{c_1\}$ because $c_1$ is the only vertex in $X'_1$ that sees both $c_2, a_3$. Note that $a_1$ is in $X'_1$ for otherwise $c_1$ is isolated in $X'_1$. Also if a vertex $x$ of $A_3$ is in $X'_1$ then $x$ must be in $A'_1$ since it sees $a_3$. This is impossible since $x$ misses $c_2$. Thus $x \in X'_2$. Since $x$ sees $a_1 \in X'_1$, $x$ must be in $B'_2$ and $a_1$ must be in $B'_1$. So, $a_1$ is a vertex of $B'_1$ that is complete to $A'_1$, implying $(X'_1, X'_2)$ being degenerate, contradicting (29).

• $\{a_3\} \subset X'_1$ and $\{c_1, c_2, b_3\} \subset X'_2$

This case is like the previous one, we just sketch it. We assume $a_3 \in A'_1$, implying $c_1, b_3 \in A'_2$. Thus $A'_1 = \{a_3\}$. There is a $x$ vertex of $X'_1$ in $A_3$. Also, $a_1 \in X'_2$ for otherwise $a_1 \in A'_1$ while missing $b_3$, a contradiction. Thus $x \in B'_1$, and $x$ is a vertex of $B'_1$ that is complete to $B'_1$, a contradiction.

• $\{c_1, c_2\} \subset X'_1$ and $\{a_3, b_3\} \subset X'_2$

Up to a symmetry, we assume $c_1 \in A'_1$, $a_3 \in A'_2$, $c_2 \in B'_1$, $b_3 \in B'_2$. Since by (29) $(X'_1, X'_2)$ is not degenerate, $a_3$ must have a non-neighbor $x$ in $B'_2$. Since $x$ must see $c_2$ we have $x = b_1$ and $b_1 \in B'_2$. Similarly, $b_3$ must have a non-neighbor in $A'_2$, implying $a_1 \in A'_2$. Now put $Y_1 = X_2 \cap X'_1$ and $Y_2 = X_2 \cap X'_2$. Note that $Y_1 \neq \emptyset$ for otherwise $X'_1 = \{c_1, c_2\}$ and $(X'_1, X'_2)$ is not proper. Also $Y_2 \neq \emptyset$ for otherwise, $a_1$ is isolated in $X'_2$. If there is an edge of $G'$ with an end in $Y_1$ and an end $y$ in $Y_2$, then $y_2$ must be in one of $A'_2, B'_2$. This is a contradiction
since $y$ misses both $c_1, c_2$. Thus there is no edge with an end in $Y_1$ and an end $Y_2$. This contradicts the property j of $G$.

• $\{c_1, a_3\} \subset X'_1$ and $\{c_2, b_3\} \subset X'_2$

Up to a symmetry, we assume $c_1 \in A'_1$, $a_3 \in B'_1$, $c_2 \in A'_2$, $b_3 \in B'_2$. Since by (29) $(X'_1, X'_2)$ is not degenerate, $a_3$ must have a non-neighbor $x$ in $A'_1$. Since $x$ must see $c_2$ we have $x = b_1$ and $b_1 \in A'_1$. Similarly, $b_3$ must have a non-neighbor in $A'_2$, implying $a_1 \in A'_2$. So, $b_1 \in A'_1$, $a_1 \in A'_2$ and $a_1b_1 \notin E(G')$, a contradiction.

• $\{c_1, b_3\} \subset X'_1$ and $\{c_2, a_3\} \subset X'_2$

Up to a symmetry, we assume $c_1 \in A'_1$, $a_3 \in A'_2$, $c_2 \in A'_2$, $b_3 \in A'_1$. There is a vertex $x$ of $X'_1$ in $B_3$ for otherwise $b_3$ is isolated in $X'_1$. Also, $b_1 \in X'_2$ for otherwise $c_2$ is isolated in $X'_2$. But $b$ sees $x$. Since $b_1 \in A'_2$ is impossible because $b_1$ misses $c_1$ we have $b_1 \in B'_2$. Similarly, we prove $a_1 \in B'_1$. So, $b_1 \in B'_2$, $a_1 \in B'_1$ and $a_1b_1 \notin E(G')$, a contradiction.

This proves (31).

(32) $G'$ has no non-path proper 2-join.

By (31), we may assume $\{c_1, c_2, a_3, b_3\} \subset X'_2$. We claim that at most one of $c_1, c_2, a_3, b_3$ is in $A'_2 \cup B'_2$. For otherwise, up to a symmetry there are three cases. First case, $a_3 \in A'_2$, $b_3 \in B'_2$, implying $A'_1 \subset A_3$ and $B'_1 \subset B_3$, implying $(X'_1, X'_2)$ being degenerate because any vertex of $A'_1$ is complete to $B'_1$, contradicting (29). Second case, $a_3 \in A'_2$, $c_1 \in B'_2$ implying $A'_1 \subset A_3$, $a_1 \in B'_1$, implying $(X'_1, X'_2)$ being degenerate because $a_1 \in B'_1$ is to complete to $A'_1$, contradicting (29). Third case, $a_3 \in A'_2$, $c_2 \in B'_2$ implying $b_1 \in B'_1$. Also $b_3 \in C'_2$ because $b_3, c_2$ (resp. $b_3, a_3$) have no common neighbors in $X'_1$. So $B_3 \subset X'_2$ and because of $b_1, B_3 \subset B'_2$. Because of $a_3$ there is a vertex $a$ of $A'_1$ in $A_3$. Hence $a$ is a vertex of $A'_1$ that has a neighbor in $B'_2$, a contradiction. The three cases yield a contradiction, so our claim is proved. Thus up to a symmetry we assume that we are in one of the three cases that we describe below:

• $a_3 \in A'_2$. Moreover, $a_1 \in X'_2$ because $c_1 \in C'_2$. Because of $a_3$ there is a vertex of $X'_1$ in $A_3$, implying $a_1 \in A'_2$ and $B_3 \subset A'_2$.

• $c_1 \in A'_2$. This implies $a_1 \in A'_1$. Since $a_3 \in C'_2$, we have $A_3 \subset X'_2$ and $A_3 \subset A'_2$ because of $a_1$. Note that $A'_1 = \{a_1\}$ because $a_1$ is the only neighbor of $c_1$ in $X'_1$.
• $a_2 \notin A'_2$ and $c_1 \notin A'_2$. Moreover, $a_1 \in X'_2$ and $A_3 \subset X'_2$.

In either cases, $c_2, b_3 \in C'_2$, implying $\{b_1\} \cup B_3 \subset X'_2$. Note that $X'_1 \subset V(G)$. 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$. If $c_1 \in A'_2$ then put $A_2'' = (A'_2 \cap X_2) \cup (N_G(a_1) \cap X_1)$. If $c_1 \notin A'_2$ then put $A_2'' = A'_2 \setminus \{a_3\}$. 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$.

Let us put $D = B_3 \cup X_1 \cup \{a_1\}$. By the properties above, $D \subset X_2'' \subset V(G)$ and $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, a_3, b_3, b_1\} \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_2'']$ 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''$ ($c_2$ and one in $B_3$) while having degree at least 3 by the property h of $G$. This proves our claim.

Since $(X_1'', X_2'')$ is proper, we know by the properties of $G$ that $(X_1'', X_2'')$ is a path 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'')$. Thus $(X_1'', X_2'')$ is a path 2-join of $G$ because $X_1'' = X'_1$. This proves (32).

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

In the proof of (33), the word “neighbor” refers to the neighborhood in $\overline{G'}$. Let $(X'_1, X'_2)$ be a proper 2-join of $\overline{G'}$.

If $c_1 \in C'_1$ then $X'_2 \subset \{a_1, a_3, c_2\}$ implying $(X'_1, X'_2)$ being degenerate or non-proper, contradicting (29). Thus, we may assume $c_1 \in A'_1$. Similarly $c_2$ must be in one of $A'_1, A'_2, B'_1, B'_2$. But $c_2 \in A'_2$ is impossible because $c_2$ is not a neighbor of $c_1$. Also $c_1 \in A'_1$ is impossible because otherwise $B'_2 = \emptyset$ since no vertex of $\overline{G'}$ can be a non-neighbor of both $c_1, c_2$. Thus $c_2$ is in one of $B'_1, B'_2$.

If $c_2 \in B'_1$ then $A'_2 \subset \{b_1, b_3\}$ because of $c_2$ and $B'_2 \subset \{a_1, a_3\}$ because of $c_1$. But $b_1$ must be in $A'_2$ because it is a common neighbor of $c_1, a_1, a_3$.
Thus $b_1$ is a vertex of $A'_2$ that is complete to $B'_2$, implying $(X'_1, X'_2)$ being degenerate, contradicting (29).

If $c_2 \in B'_2$ then there is a non-neighbor of $c_2$ in $A'_2$ for otherwise $(X'_1, X'_2)$ is degenerate. Thus at least one of $b_1, b_3$ is in $A'_2$. Similarly, because of $c_1$, at least one of $a_1, a_3$ must be in $B'_1$. But since there is no edge of $\overline{G}'$ between $B'_1, A'_2$, we have $a_3 \in B'_1, b_3 \in A'_2$. Since $a_3, b_3, c_2$ are neighbors of $a_1$, we know $a_1 \in B'_2$. Now $b_1$ is a neighbor of $c_1 \in A'_1, a_3 \in B'_1, a_1 \in B'_2, b_3 \in A'_2$, a contradiction. This proves (33).

(34) $\overline{G}'$ is not path-cobipartite, not a path-double split graph, has no homogeneous 2-join and has no flat path of length at least 3.

Else, by Lemma 2.3 there is a contradiction with one of (30), (28) or (33). This proves (34).

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

Every vertex in $\{a_1, b_1\} \cup A_3 \cup B_3$ has degree at least 3 in $G'$. For $a_1$, this is a property of $G$ and for vertices in $A_3 \cup B_3$, this is clear. Hence no vertex in $\{a_1, b_1\} \cup A_3 \cup B_3$ can be an interior vertex of a flat path of $G'$, and no vertex in $\{c_1, c_2, a_3, b_3\}$ can be in a maximal flat path of $G'$ of length at least 3. Hence, every maximal flat path of $G'$ of length at least 3 is a maximal flat path of $G$, implying $f(G') \le f(G)$. But in fact $f(G') < f(G)$ because $X_1$ is a flat path of $G$ that is no more a flat path in $G'$. By (34) we know $0 = f(\overline{G}') \le f(\overline{G})$. We add these two inequalities. This proves (35).

Let us now finish the case. By (27), $G'$ is Berge. By (30), $G'$ is not basic, not path-cobipartite, not a path-double split graph, and has no homogeneous 2-join. By (28), $G'$ has no even skew partition. By (32), $G'$ has no proper non-path 2-join. By (33) $\overline{G}'$ has no proper 2-join. By (34), $\overline{G}'$ is not a path-cobipartite graph, a path-double split graph and has no homogeneous 2-join. So, $G'$ is a counter-example to the theorem we are proving now. Hence there is a contradiction between the initial choice of $G$ and (35). This completes the proof in Case 2.

**Case 3:** We are neither in Case 1 nor in Case 2. In particular, $(X_1, X_2)$ is not a cutting 2-join.

We consider the graph $G'$ obtained from $G$ by replacing $X_1$ by a path of length $2 - \varepsilon$ from $a_1$ to $b_1$. Possibly, this path has length 2. In this case we denote by $c_1$ its unique interior vertex. Else, this path has length 1, and for convinience we put $c_1 = a_1$ (thus $c_1$ is a vertex of $G'$ whatever $\varepsilon$). Note that $(V(G') \setminus X_2, X_2)$ is not a proper 2-join of $G$ since $V(G') \setminus X_2$ is a path of length 1 or 2 from $a_1$ to $b_1$. Note that $a_1-c_1-b_1$ a flat path of $G'$ (possibly
of length 1 when $a_1 = c_1$) because if there is a common neighbor $c$ of $a_1, b_1$, or if $c_1 \neq a_1$ has degree at least 3, then $(X_1, X_2)$ is not a 2-join of $G$. Note that $G'$ is what we call in section 2 the piece $G_2$ of $G$ with respect to the 2-join $(X_1, X_2)$.

(36) $G'$ has no even skew partition, and none of $G, \overline{G}'$ has a star cutset, a degenerate proper 2-join or a degenerate homogeneous 2-join.

Since $G'$ is a piece of $G$, and since $(X_1, X_2)$ is not cutting, by Lemma 2.13, if $G'$ has an even skew partition then so is $G$, contradicting the properties of $G$. By Lemma 2.2, 2.10 and 2.15, $G, \overline{G}$ have no star cutset, no degenerate 2-join and no degenerate homogeneous 2-join. This proves (36).

(37) $G'$ is Berge.

Any hole $H'$ of $G'$ yield a hole of $G$ of the same parity after possibly subdividing the flat path $a_1-c_1-b_1$. Also, $a_1, b_1$ cannot both be in an antihole of $G'$ because in an antihole of length at least 7, any pair of vertex have a common neighbor. Also, if $c_1 \neq a_1$ then $c_1$ does not lie in an antihole of $G'$ of length at least 7 because $c_1$ has degree 2. Thus, any antihole of $G'$ may be viewed as an antihole of $G$. Thus, every holes and every antiholes in $G'$ are even. This proves (37).

(38) $G'$ has no proper non-path 2-join.

Let $(X'_1, X'_2, A'_1, B'_1, A'_2, B'_2)$ be a split of a proper non-path 2-join of $G'$. If $a_1 \in X'_1$, $b_1 \in X'_1$ then $c_1 \in X'_1$ since otherwise $c_1$ is isolated in $X'_2$. If $c_1 \neq a_1$ then $c_1 \in C'_1$ because $c_1$ has degree 2. So, by subdividing $a_1-c_1-b_1$ we obtain a non-path proper 2-join of $G$, contradicting the properties of $G$. Thus, since $a_1-c_1-b_1$ is a flat path of $G'$, up to a symmetry, we may assume $c_1 \in B'_1$, $b_1 \in B'_2$.

Suppose $|B'_2| = 1$. Then no vertex of $A'_2$ has a neighbor in $B'_2$ for otherwise, $(X_1, X_2)$ is degenerate. Thus, $(X'_1 \cup B'_2, X'_2 \setminus B'_2)$ is a non-path proper 2-join of $G'$, and by subvising $a_1b_1$, we obtain a non-path proper 2-join of $G$, contradicting the properties of $G$. Thus, $|B'_2| \ge 2$. In particular, $c_1 = a_1$, and similarly $|B'_1| \ge 2$.

In $G$, $a_1$ is complete to $B'_2 \setminus \{b_1\}$, and $b_1$ is complete to $B'_1 \setminus \{a_1\}$. We put $A_3 = B'_2 \setminus \{b_1\}$, $B_3 = B'_1 \setminus \{a_1\}$. In $G$, $X_1$ is a path from $a_1$ to $b_1$, $A_3 \subset A_2$ and $B_3 = \subset B_2$ and $A_3$ is complete to $B_3$. We claim that every path of $G$ outgoing from $A_3 \cup \{b_1\}$ to $A_3 \cup \{b_1\}$ has even length. Note that after possibly deleting $c_1, c_2$, such a path may be view as a path $P'$ of $G'$ that has same parity than $P$. In $G'$, $P'$ is an outgoing path from $B'_1$ to $B'_1$ and by Lemma 2.5, $P$ has even length as claimed. We claim that every outgoing
antipath of $G$ whose interior is in $A_3 \cup \{b_1\}$ and whose ends are outside of $A_3 \cup \{b_1\}$ has even length. Let $Q$ be such an antipath of length at least 5. Note that $c_1, c_2$ are not in $Q$ since every vertex in $Q$ have degree at least 3. Thus $Q$ is an outgoing path of $G'$ whose interior is in $B'_1$ and whose ends are not in $B'_1$ and by Lemma 2.5, $P$ has even length as claimed. The same properties hold with $B_3 \cup \{a_1\}$. Now, $A_3, B_3$ show that $(X_1, X_2)$ satisfies the items 1–5 of the definition of cutting 2-joins of type 2, contradicting that we are not in Case 2 of the proof of our theorem. This proves (38).

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

Let us consider a proper 2-join of $\overline{G}'$ with a split $(X'_1, X'_2, A'_1, B'_1, A'_2, B'_2)$. If $c_1 \neq a_1$ then $c_1$ has degree $n-2$ in $\overline{G}'$. Thus, up to a symmetry, we may assume $c_1 \in B'_1$. Since $(X'_1, X'_2)$ is not degenerate, $c_1$ must have a non-neighbor in $A'_1$. Thus, up to a symmetry, we may assume $a_1 \in A'_1$, $b_1 \in A'_2$. Now, since $(X'_1, X'_2)$ is not degenerate, there exists a vertex of $B'_2$ that is a common neighbor of $a_1, b_1$ in $G$, contradicting $a_1-c_1-b_1$ being a flat path of $G$. We proved $a_1=c_1$.

Since $a_1, b_1$ form a flat edge of $G'$, they must be non-adjacent in $\overline{G}'$ with no common non-neighbor. Thus, up to a symmetry we have to deal with three cases:

* $a_1 \in C'_1, b_1 \in X'_2$.

Since in $G'$ $a_1b_1$ is flat, in $\overline{G}'$ $a_1$ is complete to $A'_1 \cup B'_1$ or up to a symmetry $b_1 \in A'_2$ while being complete to $B'_2$. Thus, $(X'_1, X'_2)$ is a degenerate 2-join, a contradiction.

* $a_1 \in A'_1, b_1 \in B'_2$.

Since in $G'$, $a_1b_1$ is flat, in $\overline{G}'$, $a_1$ must be complete to $(A'_1 \cup C'_1) \setminus \{a_1\}$.

Suppose first $C'_1 \neq \emptyset$. There is at least a vertex of $C'_1$ that has a neighbor in $B'_1$ for otherwise $A'_1 \cup A'_2$ is a skew cutset of $\overline{G}'$, implying $(X'_1, X'_2)$ being degenerate. If $a_1$ has a neighbor in $B_1$ then by Lemma 2.4 every outgoing path from $A'_1$ to $B'_1$ has odd length. Thus, $a_1$ must see every vertex of $B'_1$ that has a neighbor in $C'_1$. This implies that $A'_1 \cup (N(a_1) \cap B'_1)$ is a star cutset of $G'$, centered at $a_1$ and separating $C'_1$ and separarting from $X'_2$. Thus, $a_1$ has no neighbor in $B_1$. Hence, there is at least an outgoing path of even length from $A'_1$ to $B'_1$, implying that no vertex in $A'_1$ has a neighbor in $B'_1$. If $|A'_1| \ge 2$ then $\{a_1\} \cup C'_1 \cup B'_2$ is a star cutset centered at $a_1$ that separates $A'_1 \setminus \{a_1\}$ from $B'_2$. Thus, $|A'_1| = 1$. Since, every outgoing path from $A'_1$ to $B'_1$
has even length, we know that every outgoing path from $A'_2$ to $B'_2$
has even length. Thus, $C'_2 \neq \emptyset$. By the same proof than above, this
implies $B'_2 = \{b_1\}$. Note that every vertex in $C'_1$ has a neighbor in $B'_1$
because a vertex of $C'_1$ with no neighbor in $B'_1$ can be separated from
the rest of the graph by a star cutset centered at $a_1$. Every vertex in
$C'_1$ has a non-neighbor in $B'_1$ because a vertex of $C'_1$ complete to $B'_1$
would imply $(X'_1, X'_2)$ being degenerate. Note also that every vertex
in $B'_1$ has a neighbor in $C'_1$ for otherwise $(X'_1, X'_2)$ is degenerate. Ev-
ery vertex in $B'_1$ has a non-neighbor in $C'_1$ because if there is a vertex
$b \in B'_1$ complete to $C'_1$ then $|B'_1| \ge 2$ implyies that $\{b\} \cup C'_1 \cup B'_2$ is
a star cutset separating $B'_1 \setminus \{b\}$ from $A'_2$, and $|B'_1| = 1$ implies that
every vertex in $C'_1$ is complete to $A'_1 \cup B'_1$, a case already treated. Let
us come back to $G$: in $G$, $X_1$ is a path from $a_1$ to $b_1$. Let us denote
by $E$ its interior. We observe that $(C'_1, B'_1, \{b_1\}, \{a_1\}, E, A'_2 \cup C'_2)$ is
an homogeneous 2-join of $G$, contradicting the properties of $G$.

We proved $C'_1 = \emptyset$. By the same way, $C'_2 = \emptyset$. Thus, $(A'_1 \cup B'_2, A'_2 \cup B'_1)$
is a non-path proper 2-join of $G'$, contradicting (38).

$$
\bullet \ a_1 \in A'_1, b_1 \in B'_1.
$$

Since $a_1 - b_1$ is a flat edge of $G'$, $C'_2 = \emptyset$. If $C'_1 = \emptyset$, then just like
above ($A'_1 \cup B'_2$, $A'_2 \cup B'_1$) is a non-path proper 2-join of $G'$, contradict-
ing (38). So, $C'_1 \neq \emptyset$. Hence, ($A'_2$, $B'_2$, $B'_1$, $A'_1$, $X_1 \setminus \{a_1, b_1\}$, $C'_1$)
is an homogeneous 2-join of $G'$, contradicting the properties of $G'$.

This proves (39).

(40) $G'$ is neither a bipartite graph nor the line-graph of a bipartite graph.

Subdivising flat paths of a line-graph of a bipartite graph (resp. of a bipartite
graph) into a path of the same parity yields a line-graph of a bipartite graph
(resp. a bipartite graph). Thus, if $G'$ is the line-graph of a bipartite graph
or a bipartite graph, then so is $G$, contradicting the properties of $G$. This
proves (40).

(41) $\overline{G}'$ is not the line-graph of a bipartite graph.

Suppose that $\overline{G}'$ is the line-graph of bipartite graph. If $c_1 \neq a_1$ then by the
properties of $G$ there exists an outgoing path of even length from $A_2$ to $B_2$
whose interior is in $C_2$. Thus, there is a vertex $c \in C_2$. Since $(X_1, X_2)$ is not
degenerate, $c_2$ has at least a non-neighbor $b$ in one of $A_2, B_2$, say $B_2$ up to
symmetry. Now $\{a_1, c_1, c, b\}$ induces a diamond of $\overline{G}'$, a contradiction. We
prove $a_1 = c_1$.
Let $B$ be a bipartite graph such that $G = \overline{L(B)}$. Let $(X, Y)$ be a bipartition of $B$. So, $a_1, b_1$ may be seen as edges of $B$. Let us suppose $a_1 = a_X a_Y$ and $b_1 = b_X b_Y$ where $a_X, b_X \in X$ and $a_Y, b_Y \in Y$. Note that these four vertices of $B$ are pairwise distinct since in $L(B) = \overline{G'}$, $a_1$ misses $b_1$. Since $a_1 b_1$ is flat in $G'$, every edge of $B$ is either adjacent to $a_X, a_Y, b_X$ or $b_Y$. Thus, the vertices of $L(B) = \overline{G'}$ different of $a_1, b_1$ partition into six sets:

* $A_X$, the sets of the edges of $B$ being $a_X$ and missing $b_Y$;

* $A_Y$, the sets of the edges of $B$ being $a_Y$ and missing $b_X$;

* $B_X$, the sets of the edges of $B$ being $b_X$ and missing $a_Y$;

* $B_Y$, the sets of the edges of $B$ being $b_Y$ and missing $a_X$;

* possibly a single vertex $c$ representing the edge $a_X b_Y$;

* possibly a single vertex $d$ representing the edge $a_Y b_X$.

Suppose $|A_X| \ge 2$. Then, $|B_X| \ge 1$ for otherwise one of $\{a_1\}$, $\{a_1, c\}$ is a star cutset of $\overline{G'}$ separating $A_X$ from $b_1$. We observe that $(A_X \cup B_X, V(G') \setminus (A_X \cup B_X))$ is a 2-join of $\overline{G'}$. By (39), this 2-join is not proper. Since $|A_X| \ge 2$, since $V(G') \setminus (A_X \cup B_X)$ does not induce a path of $\overline{G'}$ of length at most 2, there is either a component of $A_X \cup B_X$ that does not meet $A_X$ and $B_X$ or a component of $V(G') \setminus (A_X \cup B_X)$ that does not meet $a_1$ and $b_1$. In both cases, there is a star cutset of $\overline{G'}$ centered at one of $a_1, b_1$, a contradiction. Thus, $|A_X| \le 1$, and similarly $|B_X| \le 1$, $|A_X| \le 1$, $|B_Y| \le 1$. In the case when $|A_X| = |B_X| = |A_Y| = |B_Y| = 1$ and when $c, d$ are both vertices of $G'$, we observe that $\overline{G'}$ is the self-complementary graph $L(K_{3,3} \setminus \{e\})$. Hence, $G'$ is an induced subgraph of the line-graph of a bipartite graph, and $G'$ is the line-graph of a bipartite graph, contradicting (40). This proves (41).

(42) *G'* is not a path-cobipartite graph.

If $G'$ is a path-cobipartite graph then it is partitioned into two cliques $A$ and $B$ and a path $P$ joining, like in the definition, a vertex $a$ of $A$ to a vertex $b$ of $B$. Suppose first $P = \emptyset$. If $a_1 \in A, b_1 \in A$, then since $a_1 b_1$ is a flat edge of $G'$ we have $|A| = 2$. If a vertex $c$ of $B$ sees none of $a_1, b_1$ then $B \setminus c$ is a star-cutset of $G'$ separating $c$ from $a_1 b_1$. Thus $\{a_1\} \cup N(a_1)$ and $\{b_1\} \cup N(b_1)$ are two cliques of $G'$ that partition $V(G')$. Thus, we may always assume that $a_1 \in A, b_1 \in B$. So, $G$ is obtained by subdividing $a_1 b_1$
implying $G$ being a path-cobipartite graph, contradicting the properties of $G$.

Thus $P \neq \emptyset$. Note that $(P \cup \{a, b\}, A \setminus \{a\} \cup B \setminus \{b\})$ is a 2-join of $G'$. Also, $G'[A \setminus \{a\} \cup B \setminus \{b\}]$ is connected because otherwise, any vertex of $P$ is a star cutset of $G'$, contradicting. Also, $G'[A \setminus \{a\} \cup B \setminus \{b\}]$ is not a single edge, for otherwise $G'$ is bipartite, a case already treated. Thus this 2-join is proper, and so it is not degenerate. In particular, every vertex in $A \setminus \{a\}$ has a neighbor and a non-neighbor in $B \setminus \{b\}$, implying $|A| \ge 3$, $|B| \ge 3$. If at least one $a_1, b_1$ is on $P$ then the graph $G$ obtained by subdividing $a_1b_1$ is again a path-cobipartite graph, contradicting the properties of $G$. Thus since $a_1b_1$ is a flat edge of $G'$, we may assume $a_1 \in A \setminus \{a\}$, $b_1 \in B \setminus \{b\}$. The graph $G$ is obtained by subdividing $a_1b_1$ into a path $Q$. Now $(P \cup Q \cup \{a, b\}, V(G') \setminus (P \cup Q \cup \{a, b\})$ is a 2-join of $G$. By the properties of $G$ this 2-join must be either a path 2-join or a non-proper 2-join, meaning that $V(G') \setminus (P \cup Q \cup \{a, b\})$ is a single edge. Now we observe that $G$ is the line-graph of a bipartite graph (it is in fact a graph called *prism* in [4]), contradicting the properties of $G$. This proves (42).

(43) $G'$ is not a path-double split graph.

Suppose that $G'$ is a path-double split graph. 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\}$ and $E'$ be sets of vertices of $G'$ that are like in the definition. If $a_1 \in A' \cup E'$ and $b_1 \in B' \cup E'$, then $G$ is obtained from $G'$ by subdividing the flat path $a_1-c_1-b_1$. If this yields a path of even length between a vertex $a'_i$ and $b'_i$, then this path together with a neighbor of $a'_i$ in $C' \cup D'$ and a neighbor of $b'_i$ in $C' \cup D'$ that are adjacent, yields an odd hole of $G$. Thus every path with an end in $A'$, and end in $B'$ and interior in $E$ has odd length, and $G$ is a path-double split graph contradicting the properties of $G$. The case when $a_1 \in B' \cup E$, $b_1 \in A' \cup E$ is symmetric. Since $a_1-c_1-b_1$ is a flat path of $G'$, there is only one case left up to a symmetry: $a_1 = c_1$, $|C'| = |D'| = 2$, $a_1 = c'_1$, $b_1 = c'_2$ and for every $i \in \{1, \dots, m\}$, $a'_i$ sees $c'_1$, $d'_2$ and $b'_i$ sees $d'_1$, $c'_2$. So, $G$ is obtained by subdividing $c'_1c'_2$ into a path $P$. We see that $(P \cup \{d'_1, d'_2\}, A' \cup B')$ is a proper non-path 2-join of $G$, contradicting the properties of $G$. This proves (43).

(44) $G'$ has no homogeneous 2-join.

Suppose that $G'$ has an homogeneous 2-join $(A, B, C, D, E, F)$. If $c_1 \neq a_1$ then since $c_1$ has degree 2, $c_1$ must be in $E$. Thus, by subdividing $a_1-c_1-b_1$ we obtain a graph $G$ with an homogeneous 2-join. If $c_1 = a_1$ then $a_1b_1$ is a flat edge of $G'$, thus, up to a symmetry, either $a_1 \in C$, $b_1 \in E \cup D$
or $a_1 \in C$, $b_1 \in A$. But the last case is impossible since $a_1b_1$ being flat implies $N(a_1) \subset A \cup D \cup E$, implying $(A, B, C, D, E, F)$ being degenerate, contradicting (36). Hence, $a_1 \in C$ and $b_1 \in D \cup E$. So, by subdivising $a_1b_1$ we obtain a graph $G$ that has an homogeneous 2-join. This proves (44).

(45) $\overline{G'}$ is not a path-cobipartite graph, not a path-double split graph, has no homogeneous 2-join and no flat path of length at least 3.

Else, by Lemma 2.3 either $\overline{G'}$ has a proper 2-join, contradicting (39) or $\overline{G'}$ has an even skew partition contradicting (36), or $\overline{G'}$ is bipartite contradicting (42), or $G'$ is bipartite contradicting (40), or $\overline{G'}$ is a double split graph and so is $G'$, contradicting (43). This proves (45).

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

Every flat path of $G'$ is a flat path of $G$ thus $f(G') \le f(G)$. But in fact $f(\overline{G'}) < f(G)$ since $X_1$ is a flat path of $G$ and not of $G'$. By (45) $0 = f(\overline{G'}) \le f(\overline{G})$. We add these two inequalities. This proves (46).

Let us now finish the proof. By (37), $G'$ is Berge. By (36), $G'$ has no even skew partition. By (38), $G'$ has no proper non-path 2-join. By (39) $\overline{G'}$ has no proper 2-join. By (40, 41), none of $G'$, $\overline{G'}$ is the line-graph of a bipartite graph and $G'$ is not bipartite. By (42) $G'$ is not a path-cobipartite graph. By (43) $G'$ is not a path-double split graph. By (44) $G'$ has no homogeneous 2-join. By (45), $\overline{G'}$ is not a path-cobipartite graph, not a path-double split graph and has no homogeneous 2-join. So, $G'$ is a counter-example to the theorem we are proving now. Hence there is a contradiction between the initial choice of $G$ and (46). This completes the proof.

## 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. Berge trigraphs. To appear in J. of Graph Theory, 2004.

[4] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. *Annals of Math*. To appear.
[5] V. Chvátal. Star-cutsets and perfect graphs. *J. Combin. Ser. B*, 39:189–199, 1985.

[6] V. Chvátal and N. Sbihi. Bull-free Berge graphs are perfect. *Graphs and Combinatorics*, 3:127–139, 1987.

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

[8] M. Conforti, G. Cornuéjols, and K. Vušković. Decomposition of odd-hole-free graphs by double star cutsets and 2-joins. *Discete Applied Math.*, 141:41–91, 2004.

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