# Pseudo-Cographs, Polar-Cats and Level-1 Network Explainable Graphs

Marc Hellmuth  Department of Mathematics, Faculty of Science, Stockholm
University, SE-10691 Stockholm, Sweden
<EMAIL_ADDRESS>corresponding author  Guillaume E. Scholz
Bioinformatics Group, Department of Computer Science & Interdisciplinary
Center for Bioinformatics, Universität Leipzig, Härtelstraße 16–18, D-04107
Leipzig, Germany.

( )

###### Abstract

We characterize graphs $G$ that can be explained by rooted labeled level-1
networks $(N,t)$, i.e., $N$ is equipped with a binary vertex-labeling $t$ such
that $\\{x,y\\}\in E(G)$ if and only if the lowest common ancestor
$\operatorname{lca}_{N}(x,y)$ of $x$ and $y$ has label “$1$”. This generalizes
the concept of graphs that can be explained by labeled trees, that is,
cographs. We provide three novel graph classes: _polar-cats_ are a proper
subclass of _pseudo-cographs_ which forms a proper subclass of
_$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$_.
In particular, every cograph is a pseudo-cograph and
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ is
precisely the class of graphs the can be explained by a labeled level-1
network. The class
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ is
defined in terms of the modular decomposition of graphs and the property that
all prime modules “induce” polar-cats. We provide a plethora of structural
results and characterizations for graphs of these new classes and give linear-
time algorithms to recognize them and to construct level-1 networks to explain
them.

Keywords:  cographs; modular decomposition; prime modules; recognition
algorithms; prime vertex replacement; phylogenetic networks

##  1 Introduction

Cographs are among the best-studied graph classes. They are characterized by
the absence of induced simple paths $P_{4}$ on four vertices [14, 74, 71] and
can be represented by a unique rooted tree $(T,t)$, called cotree, whose leaf
set is $V(G)$ and whose non-leaf vertices $v$ obtain a binary label
$t(v)\in\\{0,1\\}$. Every cograph $G$ is _explained_ by its cotree, i.e.,
$\\{x,y\\}\in E(G)$ if and only if the lowest common ancestor
$\operatorname{lca}_{T}(x,y)$ has label “$1$”. Several linear-time algorithms
to recognize cographs and to compute the underlying cotrees have been
established see e.g. [15, 38, 9, 21, 33]. Cographs are of particular interest
in computer science because many combinatorial optimization problems that are
NP-complete for arbitrary graphs become polynomial-time solvable on cographs
[15, 7, 30]. Recent advances in mathematical biology have shown that cographs
are intimately linked to pairwise relationships between genes [40, 41, 46, 45,
31, 43, 69, 61, 59, 60]. By way of example, the orthology relation, a key term
in evolutionary biology, collects all pairs of genes whose last common
ancestor in their evolutionary history was a speciation event (or,
equivalently has label “$1$”) and thus forms a cograph.

In many applications, however, graphs $G$ usually violate the property of
being a cograph and thus, cannot be represented by a tree $(T,t)$ whose binary
labeling $t$ uniquely determines the structure of $G$. This motivates the
investigation of generalizations. While trees are an excellent model of many
evolutionary systems or hierarchical data in general, they are often
approximations and sometimes networks are a better model of reality, in
particular, in phylogenomics [55]. In the case of distance-based
phylogenetics, this naturally connects with theory of split-decomposable
metrics [2] and their natural representations, the Buneman graphs [22, 49].
The latter form a subclass of median graphs and it has been shown by Bruckmann
et al. [10] that every graph can be explained by a rooted binary-labeled
median graph.

In this contribution, we are interested in the characterization of graphs that
can be explained by rooted level-1 networks $N$ with binary labeling $t$. We
present the formal definition for this type of network in the next section
but, essentially, level-1 networks are directed acyclic graphs with a single
root and in which any two “cycles” [48] (also known as blocks [28] or galls
[29]) are edge disjoint. We provide two generalizations of cographs: the class
of _pseudo-cographs_ and the class
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$.
Pseudo-cographs have the appealing property that they “behave” nearly like a
cograph up to a single vertex. Note, however, that the existence of a single
vertex $v$ such that $G-v$ is a cograph is not enough to define pseudo-
cographs $G$. Every pseudo-cograph can be explained by a labeled level-1
network. We distinguish here between weak and strong level-1 networks; a
property that is defined in terms of the cycles a level-1 network contains. In
weak networks, all cycles can be locally replaced by trees and one obtains a
phylogenetic tree that still explains the same graph. In other words, labeled
weak networks do not contain more information than a labeled tree. In strong
networks, however, none of the cycles can be removed. Pseudo-cographs are
restrictive in the sense that they can only be explained by strong level-1
networks that contain at most one cycle. To circumvent this restriction, we
provide the class
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ and
_polar-cats_. Polar-cats are particular pseudo-cographs that can be explained
by so-called elementary networks and
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ is
precisely the class of graphs that can be explained by a labeled level-1
network. Graphs in
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ are
defined by means of the modular decomposition; a general technique to
decompose a graph into smaller building blocks [27, 26, 68, 62, 36]. Roughly
speaking a module in a graph is a subset $M$ of vertices which share the same
neighbourhood outside $M$. A module $M$ of $G$ is prime if the subgraph $G[M]$
of $G$ induced by the vertices in $M$ and its complement $\overline{G[M]}$ are
both connected. A graph $G$ is contained in
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ if
the underlying “quotient of” $G[M]$ is a polar-cat for all non-trivial prime
modules $M$ . We build upon the ideas provided by Bruckmann et al. [10] and
show that prime modules in the modular decomposition tree can be replaced by
elementary networks to obtain a level-1 network that explains a given graph
$G\in\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$.
In addition, we provide linear-time algorithms for the recognition of pseudo-
cographs, polar-cats as well as graphs in
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ and
for the construction of level-1 networks to explain them.

After introducing the notation and some preliminary results, we give an
overview of the main concepts and results in Section 3.

##  2 Preliminaries

### Miscellaneous

Let $\Pi(A)=\\{A_{1},\dots,A_{k}\\}$ be a collection of subsets of a non-empty
set $A$. Then, $\Pi(A)$ is a _quasi-partition_ of $A$, if
$\cup_{i=1}^{k}A_{i}=A$ and $A_{i}\cap A_{j}=\emptyset$ for all distinct
$A_{i},A_{j}\in\Pi(A)$. If all elements $A_{i}\in\Pi(A)$ are non-empty, then
$\Pi(A)$ is a _partition_. A _bipartition_ is a partition consisting of two
elements.

### Graphs

We consider graphs $G=(V,E)$ with vertex set $V(G)\coloneqq V$ and edge set
$E(G)\coloneqq E$. A graph $G$ is _undirected_ if $E$ is a subset of the set
of two-element subsets of $V$ and $G$ is _directed_ if $E\subseteq V\times V$.
Thus, edges $e\in E$ in an undirected graph $G$ are of the form $e=\\{x,y\\}$
and in directed graphs of the form $e=(x,y)$ with $x,y\in V$ being distinct.
An undirected graph is _connected_ if, for every two vertices $u,v\in V$,
there is a path connecting $u$ and $v$. A directed graph is _connected_ if its
underlying undirected graph is connected. Moreover, (directed) paths
connecting two vertices $x$ and $y$ are also called _$xy$ -paths_. We write
$H\subseteq G$ if $H$ is a subgraph of $G$ and $G[W]$ for the subgraph in $G$
that is induced by some subset $W\subseteq V$. Moreover $G-v$ denotes the
induced subgraph $G[V\setminus\\{v\\}]$. _For here on, we will call undirected
graphs simply _graph_._

Let $G=(V,E)$ be a graph. The set $N_{G}(v)\coloneqq\\{w\in V\mid\\{v,w\\}\in
E\\}$ denotes the set of neighbors of $v$ in $G$. The complement
$\overline{G}$ of $G=(V,E)$ has vertex $V$ and edge set
$\\{\\{x,y\\}\mid\\{x,y\\}\notin E,x,y\in V\text{distinct}\\}$. The join of
two vertex-disjoint graphs $H=(V,E)$ and $H^{\prime}=(V^{\prime},E^{\prime})$
is defined by $H\operatorname{\otimes}H^{\prime}\coloneqq(V\cup
V^{\prime},E\cup E^{\prime}\cup\\{\\{x,y\\}\mid x\in V,y\in V^{\prime}\\})$,
whereas their disjoint union is given by
$H\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}H^{\prime}\coloneqq(V\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}V^{\prime},E\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}E^{\prime})$.
The intersection of two not necessarily vertex-disjoint graphs $H$ and
$H^{\prime}$ is $H\cap H^{\prime}\coloneqq(V\cap V^{\prime},E\cap
E^{\prime})$. A graph $G$ admits a _graph-bipartition_ , if there is a
bipartition $\\{V_{1},V_{2}\\}$ of $V$ such that $\\{u,v\\}\in E$ implies
$u\in V_{i}$ and $v\in V_{j}$, $\\{i,j\\}=\\{1,2\\}$.

A _star_ is a graph that has a single vertex (called _center_) that is
adjacent to all other vertices and no further edges. Complete graphs $G=(V,E)$
are denoted by $K_{|V|}$ and a path with $n$ vertices by $P_{n}$. We often
write, for simplicity, $x_{1}-x_{2}-\cdots-x_{n}$ for a path $P_{n}$ with
vertices $x_{1},\dots,x_{n}$ and edges $\\{x_{i},x_{i+1}\\}$, $1\leq i<n$. The
distance $\operatorname{dist}_{G}(x,y)$ of two vertices $x,y\in V$ is the
length, i.e. the number of edges, of a shortest $xy$-path in $G$. Moreover,
the _diameter $\operatorname{diam}(G)$_ of $G$ is $\max_{x,y\in
V}(\operatorname{dist}_{G}(x,y))$.

### Networks and Trees

We consider rooted, (not necessarily binary) phylogenetic trees and networks,
called trees or networks for short (see e.g. [72, 54] for an overview of
phylogenetic trees and networks). To be more precise, a network $N=(V,E)$ on
$X$ is a directed acyclic graph (DAG) such that either

  1. (N0)

$V=X=\\{x\\}$ and, thus, $E=\emptyset$.

or $N$ satisfies the following three properties

  1. (N1)

There is a unique _root_ $\rho_{N}$ with indegree 0 and outdegree at least 2;
and

  2. (N2)

$x\in X$ if and only if $x$ has outdegree 0 and indegree 1; and

  3. (N3)

Every vertex $v\in V^{0}\coloneqq V\setminus X$ with $v\neq\rho_{N}$ has

    1. (a)

indegree 1 and outdegree at least 2 (_tree-vertex_) or

    2. (b)

indegree 2 and outdegree at least 1 (_hybrid-vertex_).

If a network $N=(V,E)$ does not contain hybrid-vertices, then $N$ is a _tree_.
The set $X$ is the _leaf set_ of $N$ and $V^{0}$ the set of _inner_ vertices.
The set $E^{0}\subset E$ denotes the set of _inner_ edges, i.e., edges
consisting of inner vertices only. A graph is _biconnected_ if it contains no
vertex whose removal disconnects the graph. A _biconnected component_ of a
graph is a maximal biconnected subgraph. If such a biconnected component is
not a single vertex or an edge, then it is called a _cycle_ [48] (or _block_
[28] or _gall_ [29]). A network $N$ is a _level-k_ network, if each bi-
connected component of $N$ contains at most $k$ hybrid-vertices [12]. Thus,
every tree is a level-$k$ network, $k\geq 0$.

A _caterpillar_ is a tree $T$ such that each inner vertex has exactly two
children and the subgraph induced by the inner vertices is a path with the
root $\rho_{T}$ at one end of this path. A subset $\\{x,y\\}\subseteq X$ is a
_cherry_ if the two leaves $x$ and $y$ are adjacent to the same vertex in $T$.
In this case, we also say that $x$, resp., $y$ is _part of a cherry_. Note
that a caterpillar on $X$ with $|X|\geq 2$ contains precisely two vertices
that are part of a cherry.

Let $N=(V,E)$ be a network on $X$. A vertex $u\in V$ is called an _ancestor_
of $v\in V$ and $v$ a _descendant_ of $u$, in symbols $v\preceq_{N}u$, if
there is a directed path (possibly reduced to a single vertex) in $N$ from $u$
to $v$. We write $v\prec_{N}u$ if $v\preceq_{N}u$ and $u\neq v$. If
$u\preceq_{N}v$ or $v\preceq_{N}u$ then $u$ and $v$ are _comparable_ and
otherwise, _incomparable_. Moreover, if $(u,v)\in E$, vertex
$\operatorname{par}(v)\coloneqq u$ is called a _parent of $v$_ and vertex $v$
is a _child of $u$_. The set of children of a vertex $v$ in $N$ is denoted by
$\operatorname{child}_{N}(v)$. Note that in a network $N$ the root is an
ancestor of all vertices in $N$. For a non-empty subset of leaves $A\subseteq
V$ of $N$, we define $\operatorname{lca}_{N}(A)$, or a _lowest common ancestor
of $A$_, to be a $\preceq_{N}$-minimal vertex of $N$ that is an ancestor of
every vertex in $A$. Note that in trees and level-1 networks the
$\operatorname{lca}_{N}$ is uniquely determined [48]. For simplicity we write
$\operatorname{lca}_{N}(x,y)$ instead of $\operatorname{lca}_{N}(\\{x,y\\})$.
For a vertex $v$ of $N$, the _subnetwork $N(v)$ of $N$ rooted at $v$_, is the
network obtained from the subgraph $N[W]$ induced by the vertices in
$W\coloneqq\\{w\in V(N)\mid w\preceq_{N}v\\}$ and by suppression of $w$ if it
has indegree 0 and outdegree 1 in $N[W]$ or hybrid-vertices of $N$ that have
in- and outdegree 1 in $N[W]$. Clearly, $N(v)$ remains a level-1 network in
case that $N$ is a level-1 network.

Following [48], we call by slight abuse of notation, a biconnected component
of a level-1 network $N$ a _cycle of $N$,_ if it is not a single vertex or a
single edge. We remark that a cycle $C$ of $N$ is composed of two directed
paths $P^{1}$ and $P^{2}$ in $N$ with the same start-vertex $\rho_{C}$ and
end-vertex $\eta_{C}$, and whose vertices distinct from $\rho_{C}$ and
$\eta_{C}$ are pairwise distinct. These two paths are also called _sides of
$C$_. The _length_ of $C$ is the number of vertices it contains. A cycle
$C\subseteq N$ is _weak_ if either (i) $P^{1}$ or $P^{2}$ consist of
$\rho_{C}$ and $\eta_{C}$ only or (ii) both $P^{1}$ and $P^{2}$ contain only
one vertex distinct from $\rho_{C}$ and $\eta_{C}$. A cycle $C\subseteq N$
that is not weak is called _strong_. A network $N$ is _weak_ if all cycles of
$N$ are weak. Networks that do not contain weak cycles are _strong_. Since
trees do not contain cycles, they are trivially both, weak and strong
networks.

By definition, different cycles in level-1 networks may share a common vertex
but never edges and if a hybrid vertex $\eta_{C}$ of some cycle $C$ belongs to
a further cycle $C^{\prime}$, then $\eta_{C}=\rho_{C^{\prime}}$ must hold. A
level-1 network $N$ on $X$ is _elementary_ if it contains a single cycle $C$
of length $|X|+1$ with root $\rho_{N}\in V(C)$, a hybrid-vertex $\eta_{N}\in
V(C)$ and additional edges $\\{v_{i},x_{i}\\}$ such that every vertex
$v_{i}\in V(C)\setminus\\{\rho_{N}\\}$ is adjacent to unique vertex $x_{i}\in
X$. In this case, we say that $v_{i}$ is the vertex in $C$ that _corresponds_
to $x_{i}$. An example of an elementary network $(N,t)$ is shown in Fig. 1.

### Labeled networks and Trees

We consider networks $N=(V,E)$ on $X$ that are equipped with a
_(vertex-)labeling_ $t$ i.e., a map $t\colon V\to\\{0,1,\odot\\}$ such that
$t(x)=\odot$ if and only if $x\in X$. Hence, every inner vertex $v\in V^{0}$
must have some _binary_ label $t(v)\in\\{0,1\\}$. The labeling of the leaves
$x\in X$ with $t(x)=\odot$ is just a technical subtlety to cover the special
case $V=X=\\{x\\}$. A network $N$ with such a “binary” labeling $t$ is called
_labeled network_ and denoted by $(N,t)$.

######  Definition 2.1.

Given a labeled level-1 network $(N,t)$ we denote with
$\mathscr{G}(N,t)=(X,E)$ the undirected graph with vertex $X$ and edges
$\\{x,y\\}\in E$ precisely if $t(\operatorname{lca}_{N}(x,y))=1$. An
undirected graph $G=(X,E)$ is _explained_ by $(N,t)$ on $X$ if
$G\simeq\mathscr{G}(N,t)$.

A network $(N,t)$ is _least-resolved for $G$_ if $(N,t)$ explains $G$ and
there is no labeled network $(N^{\prime},t^{\prime})$ that explains $G$ where
$N^{\prime}$ is obtained from $N$ by a series of edge contractions (and
removal of possible multi-edges and suppression of vertices with indegree 1
and outdegree 1) and $t^{\prime}$ is some labeling of $N^{\prime}$.

A labeling $t$ (or equivalently $(N,t)$) is _discriminating_ if $t(u)\neq
t(v)$ for all $(u,v)\in E^{0}$. A labeling $t$ (or equivalently $(N,t)$) is
_quasi-discriminating_ if $t(u)\neq t(v)$ for all $(u,v)\in E^{0}$ with $v$
not being a hybrid-vertex. The latter implies that every quasi-discriminating
tree $(T,t)$ is discriminating. In networks $(N,t)$, however, $t(u)=t(v)$ is
possible if $v$ is a hybrid-vertex; see Fig. 1 for an illustrative example.

Figure 1: Shown are three labeled level-1 networks $(N,t)$,
$(N^{\prime},t^{\prime})$ and $(N^{\prime\prime},t^{\prime\prime})$ on
$X=\\{1,\dots,7\\}$. While $(N,t)$ is elementary, the networks
$(N^{\prime},t^{\prime})$ and $(N^{\prime\prime},t^{\prime\prime})$ are not.
Moreover, $(N,t)$ is neither discriminating nor quasi-discriminating;
$(N^{\prime},t^{\prime})$ is discriminating and thus, quasi-discriminating;
and $(N^{\prime\prime},t^{\prime\prime})$ is quasi-discriminating but not
discriminating. Note, $(N^{\prime},t^{\prime})$ and
$(N^{\prime\prime},t^{\prime\prime})$ can be obtained from $(N,t)$ by
contraction of edges whose vertices have the same label. In this example, we
have
$\mathscr{G}(N,t)\simeq\mathscr{G}(N^{\prime\prime},t^{\prime\prime})\not\simeq\mathscr{G}(N^{\prime},t^{\prime})$,
since $\mathscr{G}(N^{\prime},t^{\prime})$ does not contain the edge
$\\{1,4\\}$. This example, in particular, shows that edges that lie on a cycle
$C$ in $(N,t)$ and are incident to the hybrid-vertex $\eta_{C}$ can, in
general, not be contracted to obtain a network that still explains the same
graph $\mathscr{G}(N,t)$ which is one of the reasons to consider quasi-
discriminating networks instead of discriminating ones.

######  Remark.

In all drawings that show labeled networks, the leaf-label “$\odot$” is
omitted and inner vertices with label “$1$”, resp., “$0$” are drawn as
“$\bullet$”, resp., “$\square$”. The label of the hybrid-vertices can often be
chosen arbitrarily and is sometimes marked as “$\times$”.

### Cographs

_Cographs_ form a class of undirected graphs that play an important role in
this contribution. They are defined recursively [14]: the single vertex graph
$K_{1}$ is a cograph and the join $H\operatorname{\otimes}H^{\prime}$ and
disjoint union
$H\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}H^{\prime}$
of two cographs $H$ and $H^{\prime}$ is a cograph. Many characterizations of
cographs have been established in the last decades from which we summarize a
few of them in the following

######  Theorem 2.2 ([14, 74, 71]).

Given a graph $G$, the following statements are equivalent:

  1. 1.

$G$ is a cograph.

  2. 2.

$G$ does not contain induced $P_{4}$s.

  3. 3.

For every subset $W\subseteq V(G)$ with $|W|>1$ it holds that $G[W]$ is
disconnected or $\overline{G[W]}$ is disconnected.

  4. 4.

Every connected induced subgraph of $G$ has diameter $\leq 2$.

  5. 5.

Every induced subgraph of $G$ is a cograph.

It is well-known that a graph $G$ can be explained by a labeled tree $(T,t)$,
called _cotree_ , if and only if $G$ is a cograph [14]. In particular, we have

######  Theorem 2.3.

For every cograph $G=(V,E)$ there is a unique (up to isomorphism)
discriminating cotree $(\widehat{T},\widehat{t})$ such that
$G\simeq\mathscr{G}(\widehat{T},\widehat{t})$. In particular, the recognition
of cographs $G$ and, in the affirmative case, the construction of the
discriminating cotree $(\widehat{T},\widehat{t})$ that explains $G$ can be
done in $O(|V|+|E|)$ time.

A cograph is _(strict) caterpillar-explainable_ if its unique discriminating
cotree is a caterpillar.

### Modular Decomposition

The concept of _modular decomposition (MD)_ is defined for arbitrary graphs
$G$ and allows us to present the structure of $G$ in the form of a tree that
generalizes the idea of cotrees [27]. However, in general much more
information needs to be stored at the inner vertices of this tree if the
original graph has to be recovered. We refer to [36] for an excellent overview
about MDs.

The MD is based on the notion of modules. These are also known as autonomous
sets [67, 66], closed sets [27], clans [26], stable sets, clumps [3] or
externally related sets [35]. A _module_ $M$ is a subset $M\subseteq V$ such
that for all $x,y\in M$ it holds that $N_{G}(x)\setminus M=N_{G}(y)\setminus
M$. Therefore, the vertices within a given module $M$ are not distinguishable
by the part of their neighborhoods that lie “outside” $M$. The singletons and
$X$ are the _trivial_ modules of $G$ and thus, the set $\mathbb{M}(G)$ of all
modules of $G$ is not empty. A graph $G$ is called _primitive_ [24, 25, 23]
(or _prime_ [17, 36] or _indecomposable_ [18, 56, 70]) if it has at least four
vertices and contains trivial modules only. The smallest primitive graph is
the path $P_{4}$ on four vertices. In particular, every primitive graph
$G=(V,E)$ must contain an induced $P_{4}$ and thus, cannot be a cograph [73].

A module $M$ of $G$ is _strong_ if $M$ does not _overlap_ with any other
module of $G$, that is, $M\cap M^{\prime}\in\\{M,M^{\prime},\emptyset\\}$ for
all modules $M^{\prime}$ of $G$. In particular, all trivial modules of $G$ are
strong. We write $\mathbb{M}_{\mathrm{str}}(G)\subseteq\mathbb{M}(G)$ for the
set of all strong modules of $G$. Every strong module
$M\in\mathbb{M}_{\mathrm{str}}(G)$ is of one of the following three types:

  * •

_series_ , if $\overline{G[M]}$ is disconnected;

  * •

_parallel_ , if $G[M]$ is disconnected;

  * •

_prime_ , otherwise, i.e., $\overline{G[M]}$ and $G[M]$ are connected.

The set $\mathbb{M}_{\mathrm{str}}(G)$ of strong modules is uniquely
determined [45, 26]. While there may be exponentially many modules, the
cardinality of the set of strong modules is in $O(|X|)$ [26]. Since strong
modules do not overlap, the set $\mathbb{M}_{\mathrm{str}}(G)$ forms a
hierarchy and gives rise to a unique tree representation $\mathscr{T}_{G}$ of
$G$, known as the _modular decomposition tree_ (_MDT_) of $G$. The vertices of
$\mathscr{T}_{G}$ are (identified with) the elements of
$\mathbb{M}_{\mathrm{str}}(G)$. Adjacency in $\mathscr{T}_{G}$ is defined by
the maximal proper inclusion relation, that is, there is an edge
$(M^{\prime},M)$ between $M,M^{\prime}\in\mathbb{M}_{\mathrm{str}}(G)$ if and
only if $M\subsetneq M^{\prime}$ and there is no
$M^{\prime\prime}\in\mathbb{M}_{\mathrm{str}}(G)$ such that $M\subsetneq
M^{\prime\prime}\subsetneq M^{\prime}$. The root of $\mathscr{T}_{G}$ is
(identified with) $X$ and every leaf $v$ corresponds to the singleton
$\\{v\\}$, $v\in X$. Hence,
$\mathbb{M}_{\mathrm{str}}(G)=\\{L(\mathscr{T}_{G}(v))\mid v\in
V(\mathscr{T}_{G})\\}$.

To present the structure of $G$ in the form of a tree that generalizes the
idea of cotrees a labeling is needed. Since every strong module
$M\in\mathbb{M}_{\mathrm{str}}(G)$ corresponds to a unique vertex in
$\mathscr{T}_{G}$ and is either a serial, parallel or prime module, we can
establish a labeling $\tau_{G}\colon
V(\mathscr{T}(G))\to\\{0,1,\mathrm{prime},\odot\\}$ defined by setting for all
$M\in\mathbb{M}_{\mathrm{str}}(G)=V(\mathscr{T}_{G})$

$\tau_{G}(M)\coloneqq\begin{cases}0&\text{, if }M\text{ is a parallel
module}\\\ 1&\text{, else if }M\text{ is a series module}\\\
\mathrm{prime}&\text{, else if }M\text{ is a prime module and }|M|>1\\\
\odot&\text{, else, i.e., }|M|=1\end{cases}$

In this way, we obtain a labeled tree $(\mathscr{T}_{G},\tau_{G})$ that, at
least to some extent, encodes the structure of $G$. In particular,
$\tau_{G}(\operatorname{lca}(x,y))=1$ implies $\\{x,y\\}\in E(G)$ and
$\tau_{G}(\operatorname{lca}(x,y))=0$ implies $\\{x,y\\}\notin E(G)$. The
converse, however, is not satisfied in general, since
$\tau_{G}(\operatorname{lca}(x,y))=p$ is possible. Note that, if $G$ is a
cograph, then $(\mathscr{T}_{G},\tau_{G})$ coincides with the unique
discriminating cotree $(\widehat{T},\widehat{t})$ of $G$ [7, 14, 40]. In other
words, $G$ is a cograph if and only it its cotree does not contain _prime
vertices_ , i.e., vertices with label “$\mathrm{prime}$”. Hence, $G$ is a
cograph if and only it does not contain prime modules $M$ of size at least
two.

The first polynomial time algorithm to compute the modular decomposition is
due to Cowan _et al._ [19], and it runs in $O(|V|^{4})$. Improvements are due
to Habib and Maurer [35], who proposed a cubic time algorithm, and to Müller
and Spinrad [68], who designed a quadratic time algorithm. The first two
linear time algorithms appeared independently in 1994 [17, 63]. Since then a
series of simplified algorithms has been published, some running in linear
time [20, 64, 75], and others in almost linear time [20, 65, 39, 37].

##  3 Main Ideas and Results

The following type of graphs will play a central role in this contribution.

######  Definition 3.1 (Pseudo-Cographs).

A graph $G$ is a _pseudo-cograph_ if $|V(G)|\leq 2$ or if there are induced
subgraphs $G_{1},G_{2}\subseteq G$ and a vertex $v\in V(G)$ such that

  1. (F1)

$V(G)=V(G_{1})\cup V(G_{2})$, $V(G_{1})\cap V(G_{2})=\\{v\\}$ and
$|V(G_{1})|,|V(G_{2})|>1$; and

  2. (F2)

$G_{1}$ and $G_{2}$ are cographs; and

  3. (F3)

$G-v$ is either the join or the disjoint union of $G_{1}-v$ and $G_{2}-v$.

In this case, we also say that $G$ is a _$(v,G_{1},G_{2})$ -pseudo-cograph_.

Illustrative examples of pseudo-cographs are provided in Fig. 2. As argued in
Section 4, none of the conditions (F1), (F2) and (F3) is dispensable. Pseudo-
cographs generalize the class of cographs (cf. Lemma 4.2). Moreover, the
property of being a pseudo-graph is hereditary (Lemma 4.3) and pseudo-cographs
are closed under complementation (Lemma 4.6). Every connected induced subgraph
$H$ of a pseudo-cograph $G$ must have diameter less or equal than four (Lemma
4.4) and thus, $G$ cannot contain induced paths of length larger than $5$
(Cor. 4.5). The latter properties, however, do not characterize pseudo-
cographs.

If $G$ is a $(v,G_{1},G_{2})$-pseudo-cograph, then $G-v$ or $\overline{G-v}$
must be disconnected and, in particular, $G-v$ must be a cograph (cf. Obs.
4.1). As shown in Lemma 4.7, every connected component of the disconnected
graph in $\\{G-v,\overline{G-v}\\}$ must be entirely contained in either
$G_{1}$ or $G_{2}$. Moreover, if there are two connected components $H$ and
$H^{\prime}$ such that subgraph induced by $V(H)\cup V(H^{\prime})\cup\\{v\\}$
contains an induced $P_{4}$, then $H$ must be contained in $G_{i}$ and
$H^{\prime}$ in $G_{j}$ with $i,j\in\\{1,2\\}$ being distinct. The latter two
results provide the foundation for further characterizations of pseudo-
cographs by means of the connected components of the disconnected graph in
$\\{G-v,\overline{G-v}\\}$, see Prop. 4.8 and Thm. 4.9.

After investigating further properties of pseudo-cographs in Section 4 we
provide a quite simple construction of level-1 networks to explain a
$(v,G_{1},G_{2})$-pseudo-cograph $G$. This construction is based on the two
cotrees $(T_{1},t_{1})$ and $(T_{2},t_{2})$ that explain $G_{1}$ and $G_{2}$,
respectively (Def. 4.14). Roughly speaking, $(T_{1},t_{1})$ and
$(T_{2},t_{2})$ are joined under a common root and the edges
$(\operatorname{par}(v),v)$ of the vertex $v$ that is common in both graphs
$G_{1}$ and $G_{2}$ are identified, see Fig. 3 for an illustrative example.
Hence, every pseudo-cograph can be explained by a level-1 network (Prop.
4.15). In particular, pseudo-cographs are characterized in terms of level-1
networks $(N,t)$ that contain precisely one cycle that is rooted at $\rho_{N}$
and whose hybrid-vertex has a unique leaf-child, see Thm. 5.5. However, not
all level-1 networks that explain a pseudo-cograph do necessarily satisfy
latter property as shown in Fig. 3. This, in particular, shows that different
non-isomorphic level-1 networks can explain the same graph. As argued at the
end of Section 4, not all graphs that can be explained by a level-1 network
are pseudo-cographs.

To gain a deeper understanding into graphs that can be explained by a level-1
network, we first investigate the structure of level-1 networks in some more
detail in Section 5. In particular, we show in Lemma 5.2 that for every
level-1 network $(N,t)$ there is a quasi-discriminating “version”
$(\widehat{N},\widehat{t})$ of $(N,t)$ (obtained from $(N,t)$ by contraction
of certain edges whose endpoint have the same label $t$) such that
$\mathscr{G}(N,t)=\mathscr{G}(\widehat{N},\widehat{t})$. Moreover, as shown in
Lemma 5.3, every level-1 network that contains weak cycles can be
‘transformed” into a strong level-1 network that explains the same graph by
replacing all weak cycles locally by trees. As a consequence, a graph $G$ is a
cograph if and only if $G$ can be explained by weak level-1 networks (Thm.
5.4). Different weak level-1 networks that explain a given cograph are shown
in Fig. 7. The latter results allow us to consider quasi-discriminating strong
networks only which simplifies many of the proofs.

In Section 6, we continue to investigate the structure of graphs that can be
explained by elementary networks which leads to the concept of polar-cats.

######  Definition 3.2 (Polar-Cat).

Let $G$ be a $(v,G_{1},G_{2})$-pseudo-cograph with $|V(G)|\geq 3$. Then, $G$
is _polarizing_ if $G_{1}$ and $G_{2}$ are connected (resp., disconnected) and
$G-v$ is the disjoint union (resp., join) of $G_{1}-v$ and $G_{2}-v$.
Moreover, if $|V(G)|\geq 4$ and $G_{1}$ and $G_{2}$ are caterpillar-
explainable such that $v$ is part of a cherry in both caterpillars explaining
$G_{1}$, resp, $G_{2}$ then $G$ is _cat_. If $G$ is both, polarizing and cat,
it is a _polar-cat_ 111Not to be confused with their living counterparts:
https://marc-hellmuth.github.io/polarCat. The class of polar-cats is denoted
by  .

We first provide in Prop. 6.2 a characterization of polar-cats in terms of an
ordering of their vertex sets. Moreover, polar-cats are closed under
complementation (Lemma 6.3), are always connected and never cographs (Cor.
6.7). In particular, polar-cats are primitive graphs, i.e., they have at least
four vertices and consist of trivial modules only (Lemma 6.6 and 6.8). Polar-
cats are precisely those graphs that can be explained by a strong elementary
quasi-discriminating network (Lemma 6.4). As a main results, Thm. 6.5 shows
that a graph can be explained by quasi-discriminating elementary network if
and only if it is a caterpillar-explainable cograph on at least two vertices
or a polar-cat. Taking the latter results together, a graph $G$ is a polar-cat
if and only if it is primitive and can be explained by a (strong quasi-
discriminating elementary) level-1 network (see Thm. 6.9 and 6.10).

So far, we have only investigated the structure of graphs that can be
explained by particular level-1 networks that contain at most one cycle.
Nevertheless, these results will help us to define the class of graphs that
can be explained by general level-1 networks. As explained in much more detail
in Section 7, for every prime module $M$ in the MDT
$(\mathscr{T}_{G},\tau_{G})$ of $G$ one can compute a quotient graph
$G[M]/\mathbb{M}_{\max}(G[M])$ which is always a primitive graph. This
observation leads to the following

######  Definition 3.3.

$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$
denotes the class of all graphs $G$ for which
$G[M]/\mathbb{M}_{\max}(G[M])\in\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}$
for all prime modules $M$ of $G$.

Note that
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$
includes the class of cographs, since they do not contain prime modules at
all. Our aim is now to replace every prime module $M$ in the MDT of $G$ by a
suitable choice of labeled networks (in particular, elementary networks that
explain the polar-cat $G[M]/\mathbb{M}_{\max}(G[M])$) to obtain labeled
level-1 networks that explains $G$ (cf. Def. 7.3). The latter is based on the
concept of prime-vertex replacement (pvr) graphs as established in [10]. These
results allow us to show that
$G\in\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$
if and only if $G$ can be explained by a level-1 network $(N,t)$, see Thm.
7.5. Many examples show that level-1 networks that explain a given graph $G$
can differ in their topology and their label. Nevertheless, we show in Thm.
7.8 that there is a 1-to-1 correspondence between prime modules of $G$ and
strong cycles in $N$. This eventually shows that every strong quasi-
discriminating level-1 network $(N,t)$ that explains $G$ can be obtained from
some pvr graph $(N^{*},t^{*})$ of $(\mathscr{T}_{G},\tau_{G})$ after a
(possibly empty) sequence of edge contractions. Note, in this way, we can
derive distinct networks that differ, in particular, in the cycles that are
used to replace prime vertices in the MDT. Nevertheless, there is a unique
least-resolved strong level-1 network $(N,t)$ that explains $G$ provided that
every primitive graph $G[M]/\mathbb{M}_{\max}(G[M])$ is a “well-proportioned”
polar-cat (cf. Def. 6.11 and Thm. 7.9).

In Section 8 we provide linear-time algorithms for the recognition of pseudo-
cographs, polar-cats as well as graphs in
$\vbox{\hbox{\includegraphics[scale={0.01}]{./cat.png}}}^{\textit{prime}}$ and
for the construction of level-1 networks to explain them.

##  4 Pseudo-Cographs and Level-1 Networks

In this section we investigate the structural properties of pseudo-cographs.
We first argue that none of the conditions in Def. 3.1 is dispensable. It is
easy to see that (F2) together with (F3) does not imply (F1) in general (just
consider a cograph $G=G_{1}\star G_{2}$ with
$\star\in\\{\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}},\operatorname{\otimes}\\}$
where $V(G_{1})\cap V(G_{2})=\emptyset$). Now assume that only (F1) and (F2)
holds and consider the graph $G$ that consists of two disjoint copies
$P=1-2-3-4$ and $P^{\prime}=1^{\prime}-2^{\prime}-3^{\prime}-4^{\prime}$ of an
induced $P_{4}$. Now we can choose $G_{1}$ and $G_{2}$ in an arbitrary way as
long as $G_{1}$ and $G_{2}$ are cographs that additionally satisfy (F1). In
fact, putting $G_{1}=G[\\{2,1,1^{\prime}\\}]$ and
$G_{2}=G[\\{2,3,4,2^{\prime},3^{\prime},4^{\prime}\\}]$ shows that such a
choice with $v=2$ is possible. Now consider the graph $G-v$. Both vertices $1$
and $1^{\prime}$ are contained $G_{1}-v$. However, vertex $1$ is not adjacent
to any vertex in $G_{2}-v$ while vertex $1^{\prime}$ is adjacent to vertex
$2^{\prime}$ in $G_{2}-v$. Hence, $G-v$ can neither be the join nor the
disjoint union of $G_{1}-v$ and $G_{2}-v$ which implies that (F3) is violated.
To see that (F1) and (F3) do not imply (F2) in general, consider the graph
$G\simeq P_{7}=1-2-\cdots-7$. To satisfy (F3), we can choose
$v\in\\{2,3,\dots,6\\}$. For every choice of $v$, $G-v$ is the disjoint union
of the two paths. To satisfy (F3) and (F1) and, in particular,
$|V(G_{1})|,|V(G_{2})|>1$, $G_{1}-v$ must consist of one path and $G_{2}-v$ of
the other. But then at least one of $G_{1}$ and $G_{2}$ contains an induced
$P_{4}$ and thus, is not a cograph. Hence (F2) is violated.

Consider now a $(v,G_{1},G_{2})$-pseudo-cograph $G$. In this case $G_{1}-v$
and $G_{2}-v$ are cographs, since $G_{1}$ and $G_{2}$ are cographs and the
property of being a cograph is hereditary by Thm. 2.2. This implies that $G-v$
must be a cograph as well, since it is the join or disjoint union of the two
cographs $G_{1}-v$ and $G_{2}-v$. Furthermore, Thm. 2.2 implies that either
$G-v$ its complement $\overline{G-v}$ is disconnected. Now consider a vertex
$v$ of $G$ that is contained in all induced $P_{4}$s of $G$. Then, $G-v$ is a
cograph. Thm. 2.2 implies that $G-v$ or $\overline{G-v}$ is disconnected. The
converse, however, is not satisfied in general. To see this, consider the
graph that consists of the disjoint union of two induced $P_{4}$s. In this
case, for every $v\in V(G)$, the graph $G-v$ is disconnected, but $v$ is not
located on every $P_{4}$. For later reference, we summarize the latter
discussion in the following:

######  Observation 4.1.

If $G$ is graph that contains a vertex $v$ that is contained in all induced
$P_{4}$s of $G$, then $G-v$ or $\overline{G-v}$ is disconnected. The converse
of the latter statement is not satisfied in general as $G-v$ is not
necessarily a cograph. Moreover, if $G$ is a _$(v,G_{1},G_{2})$ -pseudo-
cograph_, then $G-v$ is a cograph and either $G-v$ or its complement
$\overline{G-v}$ is disconnected.

Pseudo-cographs generalize the class of cographs.

######  Lemma 4.2.

Every cograph is a pseudo-cograph.

###### Proof.

Let $G$ be a cograph. If $|V(G)|\leq 2$ we are done. Thus, assume that
$V(G)\geq 3$. Hence, $G$ can be written as $G=H\star H^{\prime}$,
$\star\in\\{\operatorname{\otimes},\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}\\}$
of two cographs $H$ and $H^{\prime}$ with $|V(H)|,|V(H^{\prime})|\geq 1$ and
$|V(H)|+|V(H^{\prime})|\geq 3$. W.l.o.g. assume that
$|V(H)|\geq|V(H^{\prime})|$ and thus, $|V(H)|\geq 2$. Let $v\in V(H)$ and put
$G_{1}=H$ and $G_{2}=G[V(H^{\prime})\cup\\{v\\}]$. By construction (F1) is
satisfied for $G_{1}$ and $G_{2}$. Since $G_{1}$ and $G_{2}$ are induced
subgraphs of $G$, Thm. 2.2 implies that the graphs $G_{1}$ and $G_{2}$ are
cographs and hence, (F2) is satisfied. By construction, $G-v=(H\star
H^{\prime})-v=(H\star(G_{2}-v))-v=(H-v)\star(G_{2}-v)=(G_{1}-v)\star(G_{2}-v)$
and therefore, (F3) is satisfied. In summary, $G$ is a pseudo-cograph. ∎

Note, however, that not every pseudo-cograph $G$ is a cograph. By way of
example, a path $P=1-2-3-4$ on four vertices is not a cograph. Nevertheless,
$G$ is a pseudo-cograph. In fact, for every choice of $v\in\\{1,2,3,4\\}$
there are induced subgraph $G_{1}$ and $G_{2}$ such that $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph. By way of example, $G$ is an
$(1,G_{1},G_{2})$-pseudo-cograph for $G_{1}=G[\\{1,3\\}]$ and
$G_{2}=G[\\{1,2,4\\}]$ as well as a $(2,G_{1},G_{2})$-pseudo-cograph for
$G_{1}=G[\\{1,2\\}]$ and $G_{2}=G[\\{2,3,4\\}]$. In the first case
$G-1=(G_{1}-1)\operatorname{\otimes}(G_{2}-1)$ and in the second case
$G-2=(G_{1}-2)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(G_{2}-2)$.
By symmetry for $v\in\\{3,4\\}$ there are induced subgraphs $G_{1}$ and
$G_{2}$ of $G$ such that $G$ is a $(v,G_{1},G_{2})$-pseudo-cograph.

Figure 2: _Top:_ the generic structure of pseudo-cographs where $G-v$ is
either the disjoint union (I) or the join (II) of $G_{1}-v$ and $G_{2}-v$.
_Panel a):_ A polar-cat and thus, a pseudo-cograph. Note that polar-cats are
always connected and primitive and thus, cannot be cographs (cf. Cor. 6.7).
_Panel b):_ A polarizing pseudo-cograph $G$ that is not a cograph. Here,
$G_{1}$ is not caterpillar-explainable and thus, $G$ is not cat. _Panel c):_ A
cat pseudo-cograph $G$ that is not polarizing, since $G_{1}$ is disconnected
while $G_{2}$ is connected. _Panel d)_ A polarizing pseudo-cograph $G$ that is
a cograph. Although $G_{1}$ and $G_{2}$ are caterpillar-explainable, vertex
$v$ is not part of cherry in their respective cotrees. Thus, $G$ is not a cat.

As the next result shows, the property of being a pseudo-cograph is
hereditary.

######  Lemma 4.3.

A graph $G$ is a pseudo-cograph if and only if every induced subgraph of $G$
is a pseudo-cograph

###### Proof.

If every induced subgraph of $G$ is a pseudo-cograph, then the fact that $G$
is an induced subgraph of $G$ implies that $G$ must be a pseudo-cograph.

Now let $G$ be a $(v,G_{1},G_{2})$-pseudo-cograph. For $V(G)\leq 2$, every
induced subgraph of $G$ contains one or two vertices and is, by definition, a
pseudo-cograph. Thus, assume that $V(G)\geq 3$. Since any induced subgraph of
a graph can be obtained by removing vertices one by one, it is sufficient to
show that the removal of a single vertex from a pseudo-cograph yields a
pseudo-cograph. Let $x\in V(G)$ be chosen arbitrarily and consider the graph
$G-x$. If $x=v$, then by Obs. 4.1, $G-x$ is a cograph and Lemma 4.2 implies
that $G-x$ is a pseudo-cograph.

Hence, assume that $x\neq v$. By (F1), $x$ must be contained in either
$V(G_{1})$ or $V(G_{2})$. W.l.o.g. assume that $x\in V(G_{1})$. If
$V(G_{1})=\\{x,v\\}$ it follows that $G-x=G_{2}$ and, by (F2), $G-x$ is a
cograph and thus, a pseudo-cograph. Assume that
$V(G_{1})\setminus\\{x,v\\}\neq\emptyset$. In this case, $G_{1}-x$ remains a
cograph with at least two vertices. In particular, it holds that
$V(G-x)=V(G_{1}-x)\cup V(G_{2})$, $V(G_{1}-x)\cap V(G_{2})=\\{v\\}$ and
$|V(G_{1}-x)|,|V(G_{2})|>1$. Thus (F1) is satisfied for $G-x$. Since $G_{1}-x$
is a cograph and $G_{2}$ remained unchanged, (F2) is satisfied for $G-x$.
Since $G-v$ satisfies $G-v=(G_{1}-v)\star(G_{2}-v)$,
$\star\in\\{\operatorname{\otimes},\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}\\}$
and since $V(G_{1})\setminus\\{x,v\\}\neq\emptyset$ it is straightforward to
show that $((G-x)-v=((G_{1}-x)-v)\star(G_{2}-v)$ is satisfied and thus (F3)
holds for $G-x$. Hence, $G$ is a pseudo-cograph. ∎

######  Lemma 4.4.

If $G$ is a pseudo-cograph, then $\operatorname{diam}(H)\leq 4$ of every
connected induced subgraph $H$ of $G$.

###### Proof.

Let $G$ be a $(v,G_{1},G_{2})$-pseudo-cograph. There are two cases (1)
$G-v=(G_{1}-v)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(G_{2}-v)$
or (2) $G-v=(G_{1}-v)\operatorname{\otimes}(G_{2}-v)$. Assume first that $G$
satisfies (1). Hence, $G$ can be obtained from $G_{1}$ and $G_{2}$ by taking
copies of $G_{1}$ and $G_{2}$ that are identified on the single common vertex
$v$. Let $H\subseteq G$ be a connected induced subgraph. If $H\subseteq
G_{i}$, $i\in\\{1,2\\}$, then $\operatorname{diam}(H)\leq 2$ since $G_{i}$ is
a cograph and by Thm. 2.2. Assume that $H$ is not entirely in one of $G_{1}$
and $G_{2}$. In this case, $H$ must contain vertex $v$ since $H$ is connected
and
$G-v=(G_{1}-v)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(G_{2}-v)$.
Hence, we can subdivide $H$ into $H_{1}\coloneqq H\cap G_{1}$ and
$H_{2}\coloneqq H\cap G_{2}$. Note, both $H_{1}$ and $H_{2}$ contain vertex
$v$ and, in particular, must be induced connected subgraphs of $G_{1}$ and
$G_{2}$, respectively. Again, since $H_{i}\subseteq G_{i}$ is an induced
connected subgraph of the cograph $G_{i}$, we can apply Thm. 2.2 and conclude
that $\operatorname{diam}(H_{i})\leq 2$, $i\in\\{1,2\\}$. The latter, in
particular, implies that $\operatorname{dist}_{H_{i}}(v,w)\leq 2$ for all
$w\in V(H_{i})$, $i\in\\{1,2\\}$. Since $H_{1}$ and $H_{2}$ have vertex $v$ in
common it follows that for every two vertices $w\in V(G_{1})$ and $u\in
V(G_{2})$ it holds that
$\operatorname{dist}_{H}(w,u)\leq\operatorname{dist}_{H_{1}}(w,v)+\operatorname{dist}_{H_{2}}(v,u)\leq
4$. Hence, $\operatorname{diam}(H)\leq 4$.

Assume now that $G$ satisfies (2). By similar arguments as in the previous
case one show that $\operatorname{diam}(H)\leq 4$ for all connected induced
subgraphs $H$ of $G$ in case $H$ is entirely contained in one of $G_{1}$ and
$G_{2}$. Assume that $H$ is not entirely in one of $G_{1}$ and $G_{2}$ and
thus, it contains vertices of both $G_{1}$ and $G_{2}$. Let $x,y\in H$ be
distinct. Assume first that $x,y\neq v$. If $x\in V(G_{1})$ and $y\in
V(G_{2})$, then $\\{x,y\\}$ is an edge of $G$, by assumption, and thus
$\operatorname{dist}_{H}(x,y)=1$. If $x,y\in V(G_{i})$, $i\in\\{1,2\\}$, then
there exists a vertex $z\in V(H)\cap V(G_{j}-v)$, $j\neq i$, such that both
$\\{x,z\\}$ and $\\{y,z\\}$ are edges of $G$. Therefore,
$\operatorname{dist}_{H}(x,y)\leq 2$. Finally assume that one $x$ and $y$
coincides with $v$, say $x=v$. Since $H$ is connected and $|V(H)|>1$ there is
a vertex $z\in V(H)$ such that $\\{z,v\\}$ is an edge of $G$. If $y=z$, then
$\operatorname{dist}_{H}(x,y)=1$. Otherwise, if $y\neq z$ we can apply the
previous arguments to the vertices $y$ and $z$ to conclude that
$\operatorname{dist}_{H}(y,z)\leq 2$ and, therefore,
$\operatorname{dist}_{H}(x,y)\leq 3$.

In summary, $\operatorname{diam}(H)\leq 4$ for every connected induced
subgraph $H$ of $G$. ∎

######  Corollary 4.5.

A pseudo-cograph does not contain induced paths $P_{n}$ with $n\geq 6$.

The converse of Lemma 4.4 is not satisfied, in general. To see this consider a
cycle $C$ on five vertices. Here $\operatorname{diam}(C)=2$ and thus, in
particular, $\operatorname{diam}(H)\leq 4$ for every connected induced
subgraph $H$ of $C$. However, for all vertices $v\in V(C)$, the graph $C-v$ is
isomorphic to a $P_{4}$ and $C-v$ is not a cograph. Thus (F3) cannot be
satisfied which implies that $C$ is not a pseudo-cograph.

Pseudo-cographs are closed under complementation.

######  Lemma 4.6.

A graph $G=(X,E)$ is a pseudo-cograph if and only if $\overline{G}$ is a
pseudo-cograph. In particular, if $|X|\geq 3$ and $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph, then $\overline{G}$ is
$(v,\overline{G_{1}},\overline{G_{2}})$-pseudo-cograph.

###### Proof.

Since $\overline{\overline{G}}=G$ it suffices to show the _only-if_
-direction. Let $G=(X,E)$ be a pseudo-cograph. If $|X|\leq 2$, then
$\overline{G}$ is trivially a pseudo-cograph. Hence, suppose that $|X|\geq 3$
and that $G$ is a $(v,G_{1},G_{2})$-pseudo-cograph. Since a graph and its
complement have the same vertex sets, (F1) must hold for $\overline{G_{1}}$
and $\overline{G_{2}}$. Moreover, since $G_{1}$ and $G_{2}$ are cographs,
their complements are cographs and thus, (F2) holds for $\overline{G_{1}}$ and
$\overline{G_{2}}$. Since $G$ satisfies (F3), we have
$G-v=(G_{1}-v)\star(G_{2}-v)$, where
$\star\in\\{\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}},\operatorname{\otimes}\\}$.
It remains to show that (F3) holds for $\overline{G}$. To this end note that
$\overline{G}-v=\overline{G-v}$ and
$\overline{G-v}=\overline{(G_{1}-v)\star(G_{2}-v)}=\overline{(G_{1}-v)}\overline{\star}\overline{(G_{2}-v)}=(\overline{G_{1}}-v)\overline{\star}(\overline{G_{2}}-v)$
with
$\overline{\star}\in\\{\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}},\operatorname{\otimes}\\}\setminus\\{\star\\}$.
Hence, (F3) is satisfied for $\overline{G}$. In summary, $\overline{G}$ is
$(v,\overline{G_{1}},\overline{G_{2}})$-pseudo-cograph. ∎

The next lemma provides a key result that we re-use in many of the upcoming
proofs.

######  Lemma 4.7.

Let $G$ be a $(v,G_{1},G_{2})$-pseudo-cograph. Furthermore, let $\mathfrak{C}$
be the set of connected components of $G-v$ (resp., $\overline{G-v}$),
whenever $G-v$ is disconnected (resp. connected). For every $H\in\mathfrak{C}$
it holds that either $H\subsetneq G_{1}$ or $H\subsetneq G_{2}$. Moreover, if
there are two elements $H,H^{\prime}\in\mathfrak{C}$ such that the subgraph of
$G$ induced by $V(H)\cup V(H^{\prime})\cup\\{v\\}$ contains an induced
$P_{4}$, then $H\subsetneq G_{i}$ and $H^{\prime}\subsetneq G_{j}$ with
$i,j\in\\{1,2\\}$ being distinct.

###### Proof.

Let $G$ be a $(v,G_{1},G_{2})$-pseudo-cograph. By Obs. 4.1, $G-v$ is a
cograph. By Thm. 2.2, $G-v$ or its complement is disconnected. In particular,
by (F3), $G-v$ is either the join or the disjoint union of $G_{1}-v$ and
$G_{2}-v$. Note, if $G-v$ is connected (resp. disconnected) it cannot be the
disjoint union (resp. join) of $G_{1}-v$ and $G_{2}-v$. This together with
(F3) implies that if $G-v$ is connected, then
$G-v=(G_{1}-v)\operatorname{\otimes}(G_{2}-v)$ and if $G-v$ is disconnected,
then
$G-v=(G_{1}-v)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(G_{2}-v)$.
In the latter case, it is easy to see that $\mathfrak{C}$ consists of at least
two elements and for every connected component $H\in\mathfrak{C}$ it must hold
that either $H\subsetneq G_{1}$ or $H\subsetneq G_{2}$. Assume that $G-v$ is
connected and thus, $G-v=(G_{1}-v)\operatorname{\otimes}(G_{2}-v)$. In this
case, we consider the connected components of
$\overline{G-v}=\overline{(G_{1}-v)\operatorname{\otimes}(G_{2}-v)}=(\overline{G_{1}-v})\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(\overline{G_{2}-v})$.
Again, for every connected component $H\in\mathfrak{C}$ it must hold that
either $V(H)\subsetneq V(\overline{G_{1}})=V(G_{1})$ or $V(H)\subsetneq
V(\overline{G_{2}})=V(G_{2})$.

Finally, by (F2), the graphs $G_{1}$ and $G_{2}$ are cographs. Thus, whenever
the subgraph induced by $V(H)\cup V(H^{\prime})\cup\\{v\\}$ contains an
induced $P_{4}$, it cannot be entirely contained in either $G_{1}$ and $G_{2}$
and, therefore, $H\subsetneq G_{i}$ and $H^{\prime}\subsetneq G_{j}$ with
$i,j\in\\{1,2\\}$ being distinct. ∎

We are now in the position to provide several characterizations of pseudo-
cographs in terms of the connected components of $G-v$, resp.,
$\overline{G-v}$.

######  Proposition 4.8.

A graph $G$ is a pseudo-cograph if and only if $|V(G)|\leq 2$ or there is a
vertex $v\in V(G)$ for which the following two conditions are satisfied:

  1. (A1)

$G-v$ or $\overline{G-v}$ is disconnected with set of connected components
$\mathfrak{C}$; and

  2. (A2)

there is a bipartition $\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ of
$\mathfrak{C}$ such that $G[V_{1}]$ and $G[V_{2}]$ are cographs where
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$i\in\\{1,2\\}$.

In this case, $G$ is a $(v,G[V_{1}],G[V_{2}])$-pseudo-cograph.

###### Proof.

Let $G$ be a pseudo-cograph. If $|V(G)|\leq 2$, we are done. Hence assume that
$|V(G)|\geq 3$ and that $G$ is a $(v,G_{1},G_{2})$-pseudo cograph. By Obs.
4.1, $G-v$ is a cograph. Thm. 2.2 implies that either $G-v$ or
$\overline{G-v}$ is disconnected. Thus, (A1) is satisfied. Let us denote with
$\mathfrak{C}$ the set of connected components of the respective disconnected
graph $G-v$ or $\overline{G-v}$. If $G$ is a cograph, then we put
$\mathfrak{C}_{1}=\\{H\\}$ for some $H\in\mathfrak{C}$ and
$\mathfrak{C}_{2}=\mathfrak{C}\setminus H$ to obtain a bipartition of
$\mathfrak{C}$. Put $V_{1}=V(H)\cup\\{v\\}$ and
$V_{2}=\\{v\\}\cup(\cup_{H\in\mathfrak{C}_{2}}V(H))$. Both graphs $G[V_{1}]$
and $G[V_{2}]$ are induced subgraphs of $G$ and, by Thm. 2.2, $G[V_{1}]$ and
$G[V_{2}]$ are cographs. Hence, (A2) is satisfied. If $G$ is not a cograph, we
can apply Lemma 4.7 to conclude that for every $H\in\mathfrak{C}$ it holds
that either $V(H)\subsetneq V(G_{1})$ or $V(H)\subsetneq V(G_{2})$. Hence,
there is a quasi-bipartition
$\mathfrak{C}_{1}\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}\mathfrak{C}_{2}$
of $\mathfrak{C}$ defined by putting $H\in\mathfrak{C}_{i}$ whenever
$V(H)\subsetneq V(G_{i})$, $i\in\\{1,2\\}$. By construction
$V(G_{i})=V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$
and thus, $G[V_{i}]=G_{i}$, $i\in\\{1,2\\}$ is a cograph. Since $G$ is not a
cograph, it follows that neither $G[V_{1}]\simeq G$ nor $G[V_{2}]\simeq G$,
which implies that $\mathfrak{C}_{1}\neq\emptyset$ and
$\mathfrak{C}_{2}\neq\emptyset$. Therefore,
$\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ is a bipartition of $\mathfrak{C}$
that satisfies (A2).

For the converse, if $|V(G)|\leq 2$, then we are done. Hence, assume that
$|V(G)|\geq 3$ and that there is a vertex $v\in V(G)$ such that (A1) and (A2)
are satisfied. By (A1), $G-v$ or its complement is disconnected and we denote
with $\mathfrak{C}$ the set of connected components of the respective
disconnected graph. Since (A2) is satisfied, there is a bipartition
$\mathfrak{C}_{1}\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}\mathfrak{C}_{2}$
of $\mathfrak{C}$ such that $G_{1}\coloneqq G[V_{1}]$ and $G_{2}\coloneqq
G[V_{2}]$ are cographs where
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$i\in\\{1,2\\}$. Therefore, $G_{1}$ and $G_{2}$ satisfy (F2). Moreover, since
$\mathfrak{C}_{1}\neq\emptyset$ and $\mathfrak{C}_{2}\neq\emptyset$ and by
construction of $V_{1}$ and $V_{2}$ it follows that (F1) is satisfied. We
continue with showing (F3). If $G-v$ is disconnected, then
$G-v=\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}}H=(\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}_{1}}H)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}_{2}}H)=(G_{1}-v)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(G_{2}-v)$
and (F3) is satisfied. Assume now that $G-v$ is connected, in which case
$\overline{G-v}$ is disconnected and, in particular,
$\overline{G-v}=\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}}H$.
Hence,
$G-v=\overline{\overline{G-v}}=\overline{\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}}H}=\overline{(\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}_{1}}H)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}_{2}}H)}=\overline{(\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}_{1}}H)}\operatorname{\otimes}\overline{(\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}_{H\in\mathfrak{C}_{2}}H)}=(G_{1}-v)\operatorname{\otimes}(G_{2}-v)$.
Hence, (F3) is satisfied.

In summary, $G$ and $v$ satisfy (F1), (F2) and (F3) and, therefore, $G$ is a
$(v,G[V_{1}],G[V_{2}])$-pseudo-cograph. ∎

######  Theorem 4.9.

The following statements are equivalent for every graph $G$.

  1. 1.

$G$ is a pseudo-cograph.

  2. 2.

Either $G$ is a cograph or there is a vertex $v\in V(G)$ that satisfies the
following conditions:

    1. (B1)

$G-v$ or $\overline{G-v}$ is disconnected with set of connected components
$\mathfrak{C}$; and

    2. (B2)

$G[V(H)\cup\\{v\\}]$ is a cograph for all $H\in\mathfrak{C}$; and

    3. (B3)

all edges of the graph $\Gamma(G,v)$ are incident to the same vertex, where
$\Gamma(G,v)$ is the undirected graph whose vertex set is $\mathfrak{C}$ and
that contains all edges $\\{H,H^{\prime}\\}$ for which the subgraph of $G$
induced by $V(H)\cup V(H^{\prime})\cup\\{v\\}$ contains an induced $P_{4}$.

  3. 3.

Either $G$ is a cograph or there is a vertex $v\in V(G)$ that satisfies the
following conditions:

    1. (C1)

$G-v$ or $\overline{G-v}$ is disconnected with set of connected components
$\mathfrak{C}$; and

    2. (C2)

there are at most two components $H_{1},H_{2}\in\mathfrak{C}$ such that
$G[V(H_{i})\cup\\{v\\}]$ and $G[W_{i}]$ are cographs, where $W_{i}\coloneqq
V(G)\setminus V(H_{i})$, $i\in\\{1,2\\}$.

In this case, $G$ or $\overline{G}$ is a
$(v,G^{\prime},G^{\prime\prime})$-pseudo-cograph with
$G^{\prime}=G[V(H_{i})\cup\\{v\\}]$ and $G^{\prime\prime}=G[W_{i}]$,
$i\in\\{1,2\\}$.

###### Proof.

We start with showing that (1) implies (2). Hence, let $G$ be a pseudo-
cograph. If $G$ is a cograph, we are done. Thus, assume that $G$ is not a
cograph and hence, $|V(G)|\geq 4$. In particular, $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph for some $v\in V(G)$ and some
$G_{1},G_{2}\subset G$. By Obs. 4.1, $G-v$ is a cograph and, by Thm. 2.2,
either $G-v$ or $\overline{G-v}$ is disconnected, i.e., Condition (B1) holds
and therefore, $\Gamma(G,v)$ is well-defined. Let $\mathfrak{C}$ be the set of
connected components of the disconnected graph in $\\{G-v,\overline{G-v}\\}$.
By Lemma 4.7, either $H\subsetneq G_{1}$ or $H\subsetneq G_{2}$ for all
$H\in\mathfrak{C}$. Hence, $G[V(H)\cup\\{v\\}]$ is an induced subgraph of
either $G_{1}$ or $G_{2}$ and thus, $G[V(H)\cup\\{v\\}]$ must be a cograph by
Thm. 2.2. Therefore (B2) is satisfied.

We continue with showing that (B3) holds. In the following, we assume first
that $G-v$ is disconnected. If $|\mathfrak{C}|=2$, then $\Gamma(G,v)$ contains
at most one edge and the statement is vacuously true. Let $|\mathfrak{C}|\geq
3$. By Prop. 4.8 there is a there is a bipartition
$\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ of $\mathfrak{C}$ such that
$G[V_{1}]$ and $G[V_{2}]$ are cographs where
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$i\in\\{1,2\\}$. This immediately implies that $\Gamma(G,v)$ can only contain
edges $\\{H,H^{\prime}\\}$ with $H\in V_{1}$ and $H^{\prime}\in V_{2}$ and
thus, $\Gamma(G,v)$ must be bipartite. Assume, for contradiction, that not all
edges of $\Gamma(G,v)$ are incident to the same vertex. Since $\Gamma(G,v)$ is
bipartite, there must be two vertex disjoint edges, say $\\{H_{1},H_{2}\\}$
and $\\{H^{\prime}_{1},H^{\prime}_{2}\\}$ in $\Gamma(G,v)$. W.l.o.g. we
assume, by Lemma 4.7, that $H_{1}\subset G_{1}$ and $H_{2}\subset G_{2}$.
Since $H_{1}\cup H_{2}\subseteq G-v$ is a cograph and since
$\\{H_{1},H_{2}\\}$ is an edge in $\Gamma(G,v)$, there is an induced $P_{4}$
in $G$ that contains $v$ and three further vertices $x,y$ and $z$ such that
two of these vertices are contained in $H_{i}$ and one vertex is contained in
$H_{j}$, $\\{i,j\\}=\\{1,2\\}$. W.l.o.g. assume that $x,y\in V(H_{1})$ and
$z\in V(H_{2})$. Since there are no edges between vertices of $H_{1}$ and
$H_{2}$ in $G$, we can assume w.l.o.g. that the edges of this $P_{4}$ are
$\\{v,x\\}\\{x,y\\}$ and $\\{v,z\\}$. By similar arguments and since
$H^{\prime}_{1}\cup H^{\prime}_{2}\subseteq G-v$ is a cograph and
$\\{H^{\prime}_{1},H^{\prime}_{2}\\}\in E(\Gamma(G,v))$, there is an induced
$P_{4}$ that contains $v$ and three further vertices $x^{\prime},y^{\prime}$
and $z^{\prime}$ (that are all distinct from $x,y$ and $z$) and that has edges
$\\{v,x^{\prime}\\}\\{x^{\prime},y^{\prime}\\}$ and $\\{v,z^{\prime}\\}$.
Moreover, $x^{\prime},y^{\prime}\in V(H^{\prime}_{i})$ and $z^{\prime}\in
V(H^{\prime}_{j})$, $\\{i,j\\}=\\{1,2\\}$. It is now straightforward to verify
that the subgraph $\Gamma(G,v)$ induced by $H_{1},H_{2}$ and $H^{\prime}_{i}$
must be a $K_{3}$ since all subgraphs of $G$ induced by $V(H_{1})\cup
V(H_{2})\cup\\{v\\}$, $V(H_{1})\cup V(H^{\prime}_{i})\cup\\{v\\}$ and
$V(H_{2})\cup V(H^{\prime}_{i})\cup\\{v\\}$ contain an induced $P_{4}$; a
contradiction to bipartiteness of $\Gamma(G,v)$. Hence, all edges must be
incident to the same vertex and thus, Statement (2) holds in case that $G-v$
is disconnected. Assume that $G-v$ is connected. Since $G-v$ is a cograph,
$\overline{G-v}=\overline{G}-v$ is disconnected. Moreover, Lemma 4.6 implies
that $\overline{G}$ is a $(v,\overline{G_{1}},\overline{G_{2}})$-pseudo-
cograph and we can apply analogous arguments to $\overline{G}$ and
$\overline{G}-v$ to conclude that statement (2) holds.

We continue with showing that (2) implies (3). If $G$ is a cograph, there is
nothing to show. Hence, assume that $G$ is not a cograph and that there is a
vertex $v\in V(G)$ such that (B1), (B2) and (B3) are satisfied. Note, (B1) and
(C1) are equivalent. Hence, it remains to show that (C2) is satisfied. Let
$\mathfrak{C}$ be the set of connected components of the disconnected graph in
$\\{G-v,\overline{G-v}\\}$. By (B3), there is a connected component
$H\in\mathfrak{C}$ to which all edges of $\Gamma(G,v)$ are incident. By (B2),
$G[V(H^{\prime})\cup\\{v\\}]$ is a cograph for all
$H^{\prime}\in\mathfrak{C}$. Hence, $G[V(H)\cup\\{v\\}]$ is a cograph and
moreover, every component $H^{\prime}\in\mathfrak{C}$ is a cograph, since they
are induced subgraphs of the cographs $G[V(H^{\prime})\cup\\{v\\}]$ (cf. Thm.
2.2). This implies that $G-v$ is a cograph since $G-v$ or $\overline{G-v}$ is
disconnected whose connected components are cographs. Hence, if there is any
induced $P_{4}$ of $G$, then it must contain vertex $v$. Now put $G[W]$, where
$W\coloneqq V(G)\setminus V(H)$. Note that $v\in W$. By (B3), the subgraph of
$\Gamma(G,v)$ induced by the vertex set $\mathfrak{C}\setminus\\{H\\}$ does
not contain any edges. This together with the fact that $v$ is contained in
every induced $P_{4}$ of $G$ implies that $G[W]$ must be a cograph.

So-far, we have shown that there is one component $H\in\mathfrak{C}$ such that
$G[V(H)\cup\\{v\\}]$ and $G[W]$ are cographs. Since $G$ is not a cograph and
$G-v$ is a cograph and since every induced $P_{4}$ in $G$ contains vertex $v$,
we can conclude that $\Gamma(G,v)$ contains at least one edge
$\\{H,H^{\prime}\\}$. It is easy to see that if $\Gamma(G,v)$ contains only
the edge $\\{H,H^{\prime}\\}$, then all of the previous arguments hold also
for $G^{\prime}_{1}\coloneqq G[V(H^{\prime})\cup\\{v\\}]$ and
$G^{\prime}_{2}=G[W^{\prime}]$, where $W^{\prime}\coloneqq V(G)\setminus
V(H^{\prime})$. Hence, there are at least two components in $\mathfrak{C}$ for
which (B2) is satisfied. Now assume that $\Gamma(G,v)$ contains at least two
edges $\\{H,H^{\prime}\\}$ and $\\{H,H^{\prime\prime}\\}$. Assume, for
contradiction, that there is a further
$H^{\prime\prime\prime}\in\mathfrak{C}$, $H\neq H^{\prime\prime\prime}$ such
that $G[V(H^{\prime\prime\prime})\cup\\{v\\}]$ and $G[W^{\prime\prime\prime}]$
are cographs where $W^{\prime\prime\prime}\coloneqq V(G)\setminus
V(H^{\prime\prime\prime})$. Hence, $H$ must be contained in
$G[W^{\prime\prime\prime}]$ and at least one of $H^{\prime}$ and
$H^{\prime\prime}$ must be contain in $G[W^{\prime\prime\prime}]$ as well. But
since $H$ is incident both $H^{\prime}$ and $H^{\prime\prime}$ one of the
induced subgraphs $G[V(H)\cup V(H^{\prime})\cup v]$ or $G[V(H)\cup
V(H^{\prime\prime})\cup v]$ is an induced subgraph of
$G[W^{\prime\prime\prime}]$ and contains induced $P_{4}$s. Hence,
$G[W^{\prime\prime\prime}]$ is not a cograph; a contradiction. Therefore, (C2)
is satisfied.

We finally show that (3) implies (1). If $G$ is a cograph, then it is a
pseudo-cograph by Lemma 4.2. Assume that $G$ is not a cograph and thus
$|X|\geq 4$. Let $v\in V(G)$ be a vertex satisfying (C1) and (C2). Let
$\mathfrak{C}$ be the set of connected components of the disconnected graph in
$\\{G-v,\overline{G-v}\\}$. By assumption, there is a component
$H\in\mathfrak{C}$ such that $G[V(H)\cup\\{v\\}]$ and $G[W]$ are cographs with
$W\coloneqq V(G)\setminus V(H)$. If $G-v$ is disconnected, then put
$G_{1}\coloneqq G[V(H)\cup\\{v\\}]$ and $G_{2}\coloneqq G[W]$, and otherwise,
put $G_{1}\coloneqq\overline{G[V(H)\cup\\{v\\}}]$ and
$G_{2}\coloneqq\overline{G[W]}$. We show that $G$ is $(v,G_{1},G_{2})$-pseudo-
cograph. By construction and the latter arguments (F1) and (F2) are satisfied.
Moreover, if $G-v$ is disconnected it is, by construction, the disjoint union
of $G_{1}-v$ and $G_{2}-v$ and, if $G-v$ is connected, then
$\overline{G-v}=G[V(H)]\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}G[W\setminus\\{v\\}]$
and thus,
$G-v=\overline{\overline{G-v}}=\overline{G[V(H)]\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}G[W\setminus\\{v\\}]}=\overline{G[V(H)]}\operatorname{\otimes}\overline{G[W\setminus\\{v\\}]}=G_{1}-v\operatorname{\otimes}G_{2}-v$.
Hence, (F3) is satisfied, which completes the proof. ∎

######  Corollary 4.10.

Let $G$ be a pseudo-cograph and $v\in V(G)$ be a vertex that is contained in
every induced $P_{4}$ of $G$. Then, $\Gamma(G,v)$ is either edge-less (in
which case $G$ is a cograph) or it contains precisely one connected component
that is isomorphic to a star while all other remaining components (if there
are any) are single vertex graphs (in which case $G$ is not a cograph).

###### Proof.

Let $G$ be a pseudo-cograph and $v\in V(G)$ be a vertex that is contained in
every induced $P_{4}$ of $G$. In this case, $G-v$ must be a cograph. If
$|V(G-v)|\in\\{0,1\\}$, then $\Gamma(G,v)$ is trivially edge-less. Assume that
$|V(G-v)|\geq 2$. By Thm. 2.2, either $G-v$ or $\overline{G-v}$ must be
disconnected. Thus, $\Gamma(G,v)$ is well-defined and has as vertex set
$\mathfrak{C}$ the connected components of the disconnected graph in
$\\{G-v,\overline{G-v}\\}$. In particular, $|\mathfrak{C}|\geq 2$ and thus,
$\Gamma(G,v)$ has at least two vertices. If $G$ is a cograph, then $G$ does
not contain any induced $P_{4}$ and one easily verifies that $\Gamma(G,v)$ is
edge-less. Assume now that $G$ contains induced $P_{4}$s. By Thm. 4.9(B3), all
edges of the graph $\Gamma(G,v)$ are incident to the same vertex and thus,
$\Gamma(G,v)$ contains precisely one connected component that is isomorphic to
a star while all other remaining components are $K_{1}$s. ∎

We investigate now in some detail to what extent the choice of the vertices
$v$ and subgraphs $G_{1}$ and $G_{2}$ are unique for $(v,G_{1},G_{2})$-pseudo-
cographs.

######  Lemma 4.11.

Let $G$ be a $(v,G_{1},G_{2})$-pseudo-cograph. Then, every induced
$P_{4}\subseteq G$ must contain vertex $v$ and, if $G$ is not a cograph, there
are at most four vertices $v^{\prime}\in V$ such that $G$ is a
$(v^{\prime},G^{\prime}_{1},G^{\prime}_{2})$-pseudo-cograph. In particular, if
$\\{P^{1},\dots,P^{k}\\}$, $k\geq 1$ is the set of all induced $P_{4}$s in
$G$, then, the number $\ell$ of choices for $v$ is
$1\leq\ell=|\cap_{i=1}^{k}V(P^{i})|\leq 3$ Moreover, if $G$ contains a $P_{5}$
$x_{1}-x_{2}-x_{3}-x_{4}-x_{5}$ or its complement $\overline{P_{5}}$ as an
induced subgraph, then $v=x_{3}$ is uniquely determined.

###### Proof.

If $G$ is a cograph, the statement is vacuously true. Assume that $G$ is not a
cograph. Thus, $G$ contains an induced $P_{4}$. By Obs. 4.1, $G-v$ is a
cograph which immediately implies that every $P_{4}$ must contain $v$. Since,
for a given induced $P_{4}$ there are four possible choices for $v\in
V(P_{4})$, there are at most four vertices $v\in V$ such that $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph. Clearly the number $|V(P)\cap
V(P^{\prime})|$ of vertices in the intersection of distinct induced $P_{4}$s
$P$ and $P^{\prime}$ must be less than four and restrict the number of
possible choices for $v$ such that $G$ is $(v,G_{1},G_{2})$-pseudo-cograph.

Now assume that $G$ is a $(v,G_{1},G_{2})$-pseudo-cograph that contains an
induced $P_{5}$ $x_{1}-x_{2}-x_{3}-x_{4}-x_{5}$. Clearly neither $v=x_{1}$ nor
$v=x_{5}$ is possible since, otherwise, $G-v$ contains still an induced
$P_{4}$; violating Obs. 4.1. Now assume that $v=x_{4}$. By Obs. 4.1, $G-v$ is
a cograph and, by Thm. 2.2, either $G-v$ or $\overline{G-v}$ must be
disconnected. Assume first that $G-v$ is disconnected. In this case, there is
one connected component $H$ of $G-v$ that contains the vertices
$x_{1},x_{2},x_{3}$. By Lemma 4.7, $H\subset G_{i}$ for one $i\in\\{1,2\\}$.
By (F1), both $G_{i}$ contains vertex $v=x_{4}$ and thus, the particular graph
$G_{i}$ contains all vertices $x_{1},\dots,x_{4}$ and therefore, an induced
$P_{4}$; a contradiction to (F2). Hence, $G-v$ must connected, in which case
$\overline{G-v}$ must be disconnected. In particular, $\overline{G}$ contains
the complement $\overline{P_{5}}$ as an induced subgraph. Note that
$\overline{P_{5}}$ has edges $\\{x_{1},x_{3}\\}$, $\\{x_{3},x_{5}\\}$ and
$\\{x_{2},x_{5}\\}$ (among others). Hence, $\overline{P_{5}}-v$ is contained
in a connected component $H$ of $\overline{G-v}$. Lemma 4.7 implies that
$H\subset G_{i}$ for one $i\in\\{1,2\\}$. Since $v\in V(G_{i})$, the graph
$\overline{G_{i}}$ contains an induced $\overline{P_{5}}$ and thus, in
particular, the induced $P_{4}$ $x_{3}-x_{1}-x_{4}-x_{2}$. Therefore,
$\overline{G_{i}}$ and thus, $G_{i}$ cannot be a cograph and (F2) is violated;
a contradiction. Therefore, $v=x_{4}$ is not possible. By analogous arguments,
one shows that $v=x_{4}$ is not possible in case that $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph that contains the complement
$\overline{P_{5}}$ as an induced subgraph. By the same arguments, $v=x_{2}$ is
not possible. Hence, if $G$ is a $(v,G_{1},G_{2})$-pseudo-cograph that
contains such an induced $P_{5}$, then $v=x_{3}$ is uniquely determined. ∎

######  Lemma 4.12.

If $G$ is a cograph with at least three vertices, then $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph for every $v\in V(G)$ and all graphs $G_{1}$
and $G_{2}$ that satisfy $G_{1}=G[V_{1}]$ and $G_{2}=G[V_{2}]$ with
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$i\in\\{1,2\\}$ for an arbitrary bipartition
$\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ of the vertex set $\mathfrak{C}$ of
$\Gamma(G,v)$, i.e., the connected components in the disconnected graph in
$\\{G-v,\overline{G-v}\\}$.

###### Proof.

Let $G$ be a cograph with at least three vertices and $v\in V(G)$ be an
arbitrary vertex. By Thm. 2.2, $G-v$ is a cograph and either $G-v$ or
$\overline{G-v}$ must be disconnected. Thus, $\Gamma(G,v)$ is well-defined and
has as vertex set $\mathfrak{C}$ the connected components of the disconnected
graph in $\\{G-v,\overline{G-v}\\}$. In particular, since $G-v$ has at least
two vertices, it holds that $|\mathfrak{C}|\geq 2$. By Cor. 4.10,
$\Gamma(G,v)$ is edge-less. Let $\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ be
any bipartition of $\mathfrak{C}$ and put
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$1\leq i\leq 2$ and $G_{1}\coloneqq G[V_{1}]$ and $G_{2}\coloneqq G[V_{2}]$.
By construction, $G_{1}$ and $G_{2}$ satisfy (F1) and $G-v$ is still the
disjoint union of join of $G_{1}-v$ or $G_{2}-v$ and thus, (F3) is satisfied.
Since both $G_{1}$ and $G_{2}$ are induced subgraphs of $G$, Thm. 2.2 implies
that $G_{1}$ and $G_{2}$ are cograph. Therefore, (F2) is satisfied. ∎

######  Lemma 4.13.

If $G$ is a $(v,G^{\prime},G^{\prime\prime})$-pseudo-cograph, then $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph for all graphs $G_{1}$ and $G_{2}$ that
satisfy $G_{1}=G[V_{1}]$ and $G_{2}=G[V_{2}]$ with
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$1\leq i\leq 2$ for an arbitrary graph-bipartition
$\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ of the vertex set $\mathfrak{C}$ of
$\Gamma(G,v)$.

In particular, if $G$ is $(v,G_{1},G_{2})$-pseudo-cograph but not a cograph,
then the center $H$ of the star in $\Gamma(G,v)$ is in $G_{i}$; all
$H^{\prime}\in\mathfrak{C}$ that are adjacent to $H$ are in $G_{j}$,
$\\{i,j\\}=\\{1,2\\}$; and every $K_{1}\in\mathfrak{C}$ is in either $G_{1}$
or $G_{2}$. If $\Gamma(G,v)$ is connected, then $G_{1}$ and $G_{2}$ are
uniquely determined.

###### Proof.

Assume that $G$ is a $(v,G^{\prime},G^{\prime\prime})$-pseudo-cograph. By
(F3), $G-v$ is the join or disjoint union $G^{\prime}-v$ and
$G^{\prime\prime}-v$ and thus, $\Gamma(G,v)$ is well-defined and has as vertex
set $\mathfrak{C}$ the connected components of the disconnected graph in
$\\{G-v,\overline{G-v}\\}$. If $G$ is a cograph, then the assertion follows
from Lemma 4.12. Assume that $G$ is not a cograph. Since $G-v$ is a cograph,
the vertex $v$ must be contained in contained in every induced $P_{4}$ of $G$.
Hence, we can apply Cor. 4.10 to conclude $\Gamma(G,v)$ has at least two
vertices and contains precisely one connected component that is isomorphic to
a star while all other remaining components (if there are any) are single
vertex graphs.

In particular $\Gamma(G,v)$ is bipartite. Let
$\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ be any graph-bipartition of
$\mathfrak{C}$. Let $H\in\mathfrak{C}$ be the component that is contained in
every edge of $\Gamma(G,v)$ and assume w.l.o.g. that $H\in\mathfrak{C}_{1}$.
Thus for every edge $\\{H,H^{\prime}\\}$ in $\Gamma(G,v)$ it must hold that
$H^{\prime}\in\mathfrak{C}_{2}$. Now assign every remaining component in
$\mathfrak{C}$ that is isomorphic to a $K_{1}$ in an arbitrary way to either
$\mathfrak{C}_{1}$ or $\mathfrak{C}_{2}$. Finally put
$V_{i}\coloneqq\\{v\\}\cup\left(\bigcup_{H\in\mathfrak{C}_{i}}V(H)\right)$,
$1\leq i\leq 2$ and $G_{1}\coloneqq G[V_{1}]$ and $G_{2}\coloneqq G[V_{2}]$.
By construction $G_{1}$ and $G_{2}$ satisfy (F1) and $G-v$ is still the
disjoint union or join of $G_{1}-v$ or $G_{2}-v$ and thus, (F3) is satisfied.
It remains to show that both $G_{1}$ and $G_{2}$ are cographs. By construction
of $V_{1}$ and since $\\{\mathfrak{C}_{1},\mathfrak{C}_{2}\\}$ is any graph-
bipartition of $\mathfrak{C}$, it follows that $H^{\prime\prime}$ and
$H^{\prime\prime\prime}$ cannot be adjacent for all
$H^{\prime\prime},H^{\prime\prime\prime}\in\mathfrak{C}_{1}$ and thus,
$G[V(H^{\prime\prime})\cup V(H^{\prime\prime})\cup\\{v\\}]$ does not contain
any induced $P_{4}$. Since the latter holds for all
$H^{\prime\prime},H^{\prime\prime\prime}\in\mathfrak{C}_{1}$ it follows that
$G[V_{1}]=G_{1}$ must be a cograph. Analogously, $G_{2}$ is a cograph and
therefore, (F2) is satisfied.

In summary, $G$ is a $(v,G_{1},G_{2})$-pseudo-cograph. By the latter
construction and arguments, it is easy to verify that last part of the
statement is satisfied. ∎

An example that shows the different construction of subgraphs $G_{1}$ and
$G_{2}$ based on $\Gamma(G,v)$ such that $G$ is a $(v,G_{1},G_{2})$-pseudo-
cograph is provided in Fig 3.

Figure 3:  _Upper Row:_ Shown is a pseudo-cograph $G$. The connected
components $H_{1},\dots,H_{4}$ of $G-v$ are the vertices of the graph
$\Gamma(G,v)$. Here, $\Gamma(G,v)$ has two connected components, one is a star
with center $H_{3}$ and the other a single vertex. _2nd and 3rd Upper Row:_
There are two possible graph-bipartitions of $\Gamma(G,v)$ (shown left) which
yield two different ways to write $G$ as a $(v,G_{1},G_{2})$\- and
$(v,G^{\prime}_{1},G^{\prime}_{2})$-pseudo-cograph. The different networks
$(N(v,G_{1},G_{2}),t(v,G_{1},G_{2}))$ and
$(N(v,G^{\prime}_{1},G^{\prime}_{2}),t(v,G^{\prime}_{1},G^{\prime}_{2}))$ are
constructed as specified in Def. 4.14. _Bottom Row:_ The quasi-discriminating
versions $(\widehat{N},\widehat{t})$ of $(N(v,G_{1},G_{2}),t(v,G_{1},G_{2}))$
and $(N(v,G^{\prime}_{1},G^{\prime}_{2}),t(v,G^{\prime}_{1},G^{\prime}_{2}))$
i.e., the network obtained after contracting the edge
$(\rho_{N},\operatorname{par}_{N}(6))$ are identical (shown right). Left:
shown is an additionally quasi-discriminating level-1 network $(N,t)$ that
explains $G$ but that cannot be obtained by means of the construction in Def.
4.14 since the root of $N$ is not part of a cycle and the hybrid vertex of $N$
has two children. We explain in Section 7 how $(N,t)$ can be constructed.

There is a quite simple construction to obtain a labeled level-1 network on
$X$ that explains a $(v,G_{1},G_{2})$-pseudo-cograph $G=(X,E)$. To this end,
consider the cotrees $(T_{1},t_{1})$ and $(T_{2},t_{2})$ for the cographs
$G_{1}=(X_{1},E_{1})$ and $G_{2}=(X_{2},E_{2})$, respectively. Note that, by
definition of pseudo-cographs, $X_{1}\cap X_{2}=\\{v\\}$, $X_{1}\cup X_{2}=X$
and $|X_{1}|,|X_{2}|>1$. Thus, $T_{1}$ is a tree on $X_{1}$, $T_{2}$ is a tree
on $X_{2}$ and both trees contain $v$ as a leaf. Based on this we provide

######  Definition 4.14.

Let $G$ be $(v,G_{1},G_{2})$-pseudo-cograph and $(T_{i},t_{i})$ be a cotree
for $G_{i}$, $i\in\\{1,2\\}$. We construct now a directed graph
_$N(v,G_{1},G_{2})$ with labeling $t(v,G_{1},G_{2})$_ as follows:

  1. 1.

Modify the trees $T_{1}$ and $T_{2}$ by adding a new vertex $\eta_{i}$ along
the edge $(\textrm{parent}_{T_{i}}(v),v)$ in $T_{i}$, $i\in\\{1,2\\}$.

  2. 2.

Take these modified trees, add a root $\rho_{N}$ and two new edges
$(\rho_{N},\rho_{T_{1}})$ and $(\rho_{N},\rho_{T_{2}})$.

  3. 3.

identify $\eta_{1}$ and $\eta_{2}$ to obtain the vertex $\eta_{N}$ in $N$.

  4. 4.

remove one copy of the leaf $v$ and its incident edge.

The labeling $t\coloneqq t(v,G_{1},G_{2})$ of $N(v,G_{1},G_{2})$ is defined as
follows:

  1. 1.

Put $t(u)\coloneqq t_{i}(u)$ for all $u\in V^{0}(T_{i})$ with $i\in\\{1,2\\}$.

  2. 2.

Choose $t(\eta_{N})\in\\{0,1\\}$ arbitrarily.

  3. 3.

Put $t(\rho_{N})=\begin{cases}1,&\text{if $G-v$ is the join of $G_{1}-v$ and
$G_{2}-v$}\\\ 0,&\text{otherwise}\end{cases}$

Examples for such networks $(N(v,G_{1},G_{2}),t(v,G_{1},G_{2}))$ are provided
in Fig. 3 and Fig. 8.

######  Proposition 4.15.

Every pseudo-graph $G$ can be explained by the labeled level-1 network
$(N(v,G_{1},G_{2}),t(v,G_{1},G_{2}))$.

###### Proof.

Let $G=(X,E)$ be a pseudo-cograph. If $|X|\leq 3$, then $G$ is a cograph and
it can be explained by a tree on $X$. Thus, let $|X|\geq 4$ and assume that
$G$ is $(v,G_{1},G_{2})$-pseudo-cograph. Consider the two cotrees
$(T_{1},t_{1})$ and $(T_{2},t_{2})$ of $G_{1}=(X_{1},E_{1})$ and
$G_{2}=(X_{2},E_{2})$, respectively. By definition of pseudo-cographs,
$X_{1}\cap X_{2}=\\{v\\}$, $X_{1}\cup X_{2}=X$ and $|X_{1}|,|X_{2}|>1$. Thus,
$T_{1}$ is a tree on $X_{1}$, $T_{2}$ is a tree on $X_{2}$ and both trees
contain $v$ as a leaf.

Consider now the network $(N,t)$ with $N\coloneqq N(v,G_{1},G_{2})$ and
$t\coloneqq t(v,G_{1},G_{2})$. It is straightforward to see that $N$ is a
level-1 network whose single cycle $C$ consists of sides $P^{1}$ and $P^{2}$
that are composed of $\rho_{N},\eta_{N}$ and the $\rho_{T_{1}}v$-path in
$T_{1}$ and the $\rho_{T_{2}}v$-path in $T_{2}$, respectively. Moreover, since
$V^{0}(T_{1})\cup V^{0}(T_{2})=V^{0}(N)\setminus\\{\rho_{N},\eta_{N}\\}$ and
$V^{0}(T_{1})\cap V^{0}(T_{2})=\emptyset$, the labeling $t$ is well-defined.

It remains to show that $G=\mathscr{G}(N,t)$. To this end let $x,y\in X$ be
chosen arbitrarily. Consider first the case that $x,y\in X_{1}$. Since $G_{1}$
is explained by $(T_{1},t_{1})$, it holds that
$t_{1}(\operatorname{lca}_{T_{1}}(x,y))=1$ if and only if $\\{x,y\\}\in E$. It
is straightforward to verify that
$\operatorname{lca}_{T_{1}}(x,y)=\operatorname{lca}_{N}(x,y)$ and thus, by
construction of $t$, that $t(\operatorname{lca}_{N}(x,y))=1$ if and only if
$\\{x,y\\}\in E$. Note, the latter covers also that case that one of $x$ or
$y$ is $v$, since $v\in X_{1}$. Similarly, the case $x,y\in X_{2}$ is shown.
Suppose now that $x\in X_{1}\setminus\\{v\\}$ and $y\in
X_{2}\setminus\\{v\\}$. The latter arguments together with the fact that the
paths in $N$ from $\rho_{T_{1}}$ to $x$ and $\rho_{T_{2}}$ to $y$ are vertex
disjoint and $\rho_{N}$ is the only vertex that is adjacent to both
$\rho_{T_{1}}$ and $\rho_{T_{2}}$ imply that
$\operatorname{lca}_{N}(x,y)=\rho_{N}$. By (F3), $G-v$ is either the join or
disjoint union of $G_{1}-v$ or $G_{2}-v$. By construction, $(\rho_{N})=1$ if
$G-v$ is the join of $G_{1}-v$ or $G_{2}-v$ and, otherwise, $t(\rho_{N})=0$.
Hence, $t(\rho_{N})=1$ if and only if $G-v$ is the join of $G_{1}-v$ and
$G_{2}-v$, if and only if $\\{x,y\\}\in E$. In summary, $\\{x,y\\}\in E$ if
and only if $t(\operatorname{lca}_{N}(x,y))=1$ for all $x,y\in X$ which
implies that $G=\mathscr{G}(N,t)$. Hence, $(N,t)$ is a labeled level-1 network
that explains the pseudo-cograph $G$. ∎

We emphasize that not all graphs that can be explained by a level-1 network
are pseudo-cographs. To see this consider a graph $G$ that is the disjoint
union of two induced $P_{4}$s. Each $P_{4}$ can be explained by a level-1
network as shown in Fig. 7. A level-1 network that explains $G$ can be
obtained by joining the two networks that explain the individual $P_{4}$s
under a common root with label “$0$”. However, $G$ is not a pseudo-cograph,
since for every choice of the vertex $v$, the graph $G-v$ is not a cograph and
thus, by Obs. 4.1, $G$ is not a pseudo-cograph. In particular, pseudo-cographs
are characterized in terms of level-1 networks $(N,t)$ that contain one cycle
that is rooted at $\rho_{N}$, and whose hybrid vertex has a unique child which
is a leaf, see Thm. 5.5. A characterization of general graphs that can be
explained by level-1 networks is provided in Thm. 7.5.

##  5 Cographs, Quasi-discriminating Strong and Weak Networks

To recap, a network $(N,t)$ is _quasi-discriminating_ if for all $(u,v)\in
E^{0}$ with $v$ not being a hybrid-vertex we have $t(u)\neq t(v)$. Of course,
not all labeled level-1 networks $(N,t)$ are quasi-discriminating. Suppose
that $(N=(V,E),t)$ is not quasi-discriminating. In this case, there must exist
some edge $e=(u,v)\in E^{0}$ such that $t(u)=t(v)$ and where $v$ is not a
hybrid-vertex. Let $v_{e}$ denote the vertex in $N$ obtained by contracting
the edge $e$. Then, the directed graph
$N^{\prime}_{e}=(V^{\prime}_{e},E^{\prime}_{e})$ with vertex set
$V^{\prime}_{e}=V\setminus\\{u,v\\}\cup\\{v_{e}\\}$, edge set
$E^{\prime}_{e}=E\setminus\\{e\\}\cup\\{(v_{e},w)\colon(v,w)\in E\text{ or
}(u,w)\in E\\}\\}\cup\\{(w,v_{e})\colon(w,v)\in E\text{ or }(w,u)\in E\\}$ is
a directed graph on $X$. Now suppress all vertices with indegree 1 and
outdegree 1 in $N^{\prime}_{e}$ to obtain the directed graph
$N_{e}=(V_{e},E_{e})$. To obtain a labeling of $N_{e}$, we defined the map
$t_{e}\colon V_{e}\to\\{0,1,\odot\\}$ by putting, for all $w\in V_{e}$,

$t_{e}(w)=t(w)\textrm{ if }w\neq v_{e}\textrm{ and }t(v_{e})=t(u)$ (1)

Clearly, this construction can be repeated, with $(N_{e},t_{e})$ now playing
the role of $(N,t)$, until a directed graph
$\widehat{N}=(\widehat{V},\widehat{E})$ on $X$ is obtained together with a
quasi-discriminating map $\widehat{t}$ on $\widehat{N}$; see Fig. 4 for an
example of such a construction. In the following, we will refer to
$(N_{e},t_{e})$ as the directed graph that is _obtained from $(N,t)$ by
contraction of $e$_ without explicitly mentioning each time that in addition
possible multi-edges have been removed or that indegree 1 and outdegree 1
vertices have been suppressed.

######  Lemma 5.1.

For every labeled level-1 network $(N,t)$ on $X$, the labeled directed graph
$(\widehat{N},\widehat{t})$ is a quasi-discriminating level-1 network on $X$.

###### Proof.

Clearly if (N0) holds, i.e., $|V(N)|=1$ then $|\widehat{V}(N)|=1$ and we are
done. Thus, assume that $|V(N)|>1$. By construction, the labeled directed
graph $(\widehat{N},\widehat{t})$ is quasi-discriminating. To prove that
$(\widehat{N},\widehat{t})$ is a level-1 network, it suffices to show that for
$e=(u,v)\in E^{0}(N)$ such that $t(u)=t(v)$ and $v$ is not a hybrid-vertex of
$N$, the labeled directed graph $(N_{e},t_{e})$ obtained by contraction of $e$
remains a level-1 network on $X$, since
$(\widehat{N},\widehat{t})=(\widehat{N_{e}},\widehat{t_{e}})$.

Clearly, $N_{e}$ is a DAG, as the contraction of an edge of a DAG does not
induce a directed cycle. Now, let $v_{e}$ be the vertex obtained by
contraction of $e=(u,v)$. By assumption, $v$ is not a hybrid-vertex of $N$.
Moreover, $v$ is not a leaf of $N$, as $e\in E^{0}(N)$. In particular, $v$ has
indegree 1 and outdegree at least $2$ in $N$. By construction, all children of
$v$ in $N$ become the children of $v_{e}$ after contraction of $e$. It follows
that $v_{e}$ has outdegree at least $2$ in $N_{e}$. In particular, $v_{e}$ is
not an indegree 1 and outdegree 1 vertex, i.e., $v_{e}$ will not be suppressed
and thus, $v_{e}\in V(N_{e})$. Moreover, since $v$ has indegree 1 in $N$ and
is, therefore, only adjacent to $u$, it follows that all in-neighbors of $u$
in $N$ are precisely the in-neighbors of $v_{e}$ in $N_{e}$. Consequently, the
indegree of $v_{e}$ in $N_{e}$ is precisely the indegree of $u$ in $N$.

To see that (N1) holds, assume first that $u\neq\rho_{N}$. In this case,
$\rho_{N}\in V(N_{e})$ and $\rho_{N}$ is the only vertex of indegree 0 in
$N_{e}$. Moreover, the outdegree of $\rho_{N}$ remains unchanged and thus,
(N1) is satisfied. Assume that $u=\rho_{N}$. In this case, $v_{e}$ is the only
vertex of indegree $0$ in $N_{e}$. Moreover, as argued above, the outdegree of
$v_{e}$ in $N_{e}$ is at least $2$. Hence, (N1) is satisfied. Moreover, since
$v$ is not a leaf and since contraction of the edge $e$ does not create new
leaves in $N_{e}$ it follows that the leaf set of $N_{e}$ must be $X$. It is
now easy to verify that (N2) holds.

We continue with showing that (N3) is satisfied. To this end, let $w\in
V^{0}(N_{e})$ such that $w\neq\rho_{N_{e}}$. Assume first that $w=v_{e}$. As
already argued, $w$ has outdegree at least $2$ in $N_{e}$. Moreover, the
indegree of $w$ in $N_{e}$ is precisely the indegree of $u$ in $N$. Since $w$
is distinct from $\rho_{N_{e}}$, vertex $u$ must be distinct from $\rho_{N}$
and, therefore, the indegree of $u$ in $N$ is at least 1. It follows that (N3)
is satisfied for $w$. Now, assume that $w\neq v_{e}$. In this case, $w$ must
be a vertex of $N$ that is distinct from $u$ and $v$ since $w\in
V(N_{e})\setminus\\{v_{e}\\}\subseteq V(N)\setminus\\{u,v\\}$. If $w$ has
indegree $1$ in $N_{e}$, then $w$ has outdegree at least $2$ in $N_{e}$, since
vertices with indegree 1 and outdegree $1$ are suppressed when constructing
$N_{e}$. Moreover, contraction of $e$ does not increase the indegree of
vertices of $N$ distinct from $u$ and $v$, so $w$ has indegree at most $2$ in
$N_{e}$. Hence, (N3) is satisfied. In summary, $N_{e}$ is a phylogenetic
network on $X$.

It remains to show that $N_{e}$ is a level-1 network. To this end, we must
show that every biconnected component in $N_{e}$ contains at most one hybrid-
vertex. If $e=(u,v)$ is not part of a cycle in $N$, then it is easy to see
that $N_{e}$ remains a level-1 network. Assume that $e$ is contained in a
cycle $C$ in $N$ and let $C_{e}$ be the biconnected component in $N_{e}$ that
contains $v_{e}$. There are cases in which $C_{e}$ is not a cycle in $N_{e}$,
in particular if $u=\rho_{C}$ and both $(u,\eta_{C})$ and $(v,\eta_{C})$ are
edges of $N$. If $C_{e}$ is not a cycle, then it cannot contain any hybrid-
vertex. Now assume that $C_{e}$ remains a subgraph in $N_{e}$ that is distinct
from a single vertex or an edges. In this case, _none_ of the vertices of $N$
that are distinct from $u$ and $v$ have been suppressed and thus, are still
present in $N_{e}$. This, in particular, implies that $C$ and $C_{e}$ differ
only in the edge $e$ and the vertex $v_{e}$, that is, the topology of $C$ and
$C_{e}$ remains the same up to the single contraction of $e$. Note that
$v\neq\eta_{C}$ by assumption. Moreover, since $v\prec_{N}u$, we also have
$u\neq\eta_{C}$. Hence, the only remaining case we need to show is that
$v_{e}$ is not a hybrid-vertex of $C_{e}$. If $v_{e}$ has indegree 1 in
$N_{e}$ we are done. Thus, assume $v_{e}$ has indegree 2 in $N_{e}$. Assume
for contradiction $C_{e}$ has $v_{e}$ and $\eta_{C}$ as hybrid-vertices. Note,
removal of any vertex $w$ in $C_{e}$ keeps $C_{e}-w$ connected in $N_{e}$.
Hence, removal of any vertex $w$ in $C$ keeps $C-w$ connected. This together
with the facts that the topology of $C$ and $C_{e}$ remains the same up to the
single contraction of $e$ and that $v$ has indegree 1 in $N$ implies that
$u\neq\eta_{c}$ must be a hybrid-vertex of $C$ in $N$; a contradiction. In
summary, every biconnected components of $N_{e}$ contains at most one hybrid-
vertex and thus, $N_{e}$ is a level-1 network. ∎

Figure 4: A level-1 network $(N,t)$ and the resulting quasi-discriminating
level-1 network $(\widehat{N},\widehat{t})$. Here, $(\widehat{N},\widehat{t})$
is weak. Note, although $\widehat{N}$ contains only one cycle $C$, it is not
elementary since there are inner vertices adjacent to more than one leaf and
vertex $5$ is adjacent to the root. Observe that the edge
$(\rho_{\widehat{N}},\eta_{\widehat{N}})$ satisfies
$\widehat{t}(\rho_{\widehat{N}})=\widehat{t}(\eta_{\widehat{N}})$ but will not
be contracted since $\eta_{\widehat{N}}$ is a hybrid-vertex.

We continue with showing that $(N,t)$ and $(\widehat{N},\widehat{t})$ explain
the same graph.

######  Lemma 5.2.

If $(N,t)$ is a labeled level-1 network, then it holds that
$\mathscr{G}(N,t)=\mathscr{G}(\widehat{N},\widehat{t})$.

###### Proof.

Let $(N,t)$ be a labeled level-1 network on $X$ and $e=(u,v)\in E^{0}(N)$ be
an edge of $N$ that satisfies $t(u)=t(v)$ and where $v$ is not a hybrid-
vertex. Consider the directed graph $(N_{e},t_{e})$ that is obtained from
$(N,t)$ by contraction of $e$ and let $v_{e}$ be the vertex in $N_{e}$ that
corresponds to the contracted edge $e$. As shown in the proof of Lemma 5.1,
$(N_{e},t_{e})$ is a labeled level-1 network on $X$. By construction all
vertices of $N_{e}$ that are contained in $N$ obtained the same label as in
$N$, while $v_{e}$ obtained label $t(v_{e})=t(u)=t(v)$.

We show first that $\mathscr{G}(N,t)=\mathscr{G}(N_{e},t_{e})$. It suffices to
verify that, for all distinct $x,y\in X$, we have
$t(\operatorname{lca}_{N}(x,y))=t_{e}(\operatorname{lca}_{N_{e}}(x,y))$. Let
$x,y\in X$ be distinct and $w=\operatorname{lca}_{N}(x,y)$. Note, since
$w=\operatorname{lca}_{N}(x,y)$ there must be two directed paths $P$ and
$P^{\prime}$ from $w$ to $u$, resp., $v$ in $N$ that have only vertex $w$ in
common.

Assume first that $w\notin\\{u,v\\}$. By the latter arguments, $w$ has
outdegree at least 2 in $N$. In particular, $w$ still has outdegree at least
$2$ after contraction of $e$, since such a contraction does not affect the
outdegree of vertices of $N$ distinct from $u$ and $v$. As a consequence, $w$
has not been suppressed and is, therefore, still a vertex of $N_{e}$. Now
consider the two paths $P$ and $P^{\prime}$ in $N$. Since $v$ is not a hybrid-
vertex in $N$, there are still directed (sub)paths of $P$ and $P^{\prime}$ in
$N_{e}$ that have only vertex $w$ in common. This together with the fact that
$N_{e}$ is a level-1 network implies that
$w=\operatorname{lca}_{N_{e}}(x,y)=\operatorname{lca}_{N}(x,y)$ and,
therefore,
$t(\operatorname{lca}_{N}(x,y))=t_{e}(\operatorname{lca}_{N_{e}}(x,y))$.

Now assume that $w\in\\{u,v\\}$. Note that $v_{e}$ remains an ancestor of both
$x$ and $y$ in $N_{e}$. Again, consider the two paths $P$ and $P^{\prime}$ in
$N$. Note that there are, in particular, two children $w_{u}$ and $w_{v}$ of
$w$ such $w_{u}$ is located on $P$ and $w_{v}$ is located on $P^{\prime}$.
After contraction of $e$, this two vertices $w_{u}$ and $w_{v}$ are now the
children of $v_{e}$. Hence, there are still directed (sub)paths of $P$ and
$P^{\prime}$ in $N_{e}$ that have now only vertex $v_{e}$ in common. Thus,
$v_{e}=\operatorname{lca}_{N_{e}}(x,y)$. By construction,
$t_{e}(v_{e})=t(u)=t(v)$ and since
$w=\operatorname{lca}_{N}(x,y)\in\\{u,v\\}$, we
$t(\operatorname{lca}_{N}(x,y))=t_{e}(\operatorname{lca}_{N_{e}}(x,y))$.

In summary, $\mathscr{G}(N,t)=\mathscr{G}(N_{e},t_{e})$. The latter arguments
can be repeated, with $(N_{e},t_{e})$ now playing the role of $(N,t)$, until
we eventually obtain $(\widehat{N},\widehat{t})$, which completes the proof. ∎

Figure 5: The left network $(N,t)$ is discriminating but not least-resolved,
since the right network $N^{\prime}$ can be obtained from $N$ by a single edge
contraction and there is a labeling $t^{\prime}$ such that
$\mathscr{G}(N,t)=\mathscr{G}(N^{\prime},t^{\prime})$.

We emphasize that discriminating or quasi-discriminating networks are not
necessarily least-resolved, see Fig. 5. We show now that every level-1 network
that contains weak cycles can be ‘transformed” into a strong level-1 network
that explains the same graph by replacing all weak cycles locally by trees.

######  Lemma 5.3.

Let $(N,t)$ be a level-1 network that contains $l$ cycles for which $k$ of
them are weak. Then, there is a strong level-1 network
$(N^{\prime},t^{\prime})$ on $X$ that contains $l-k$ cycles and such that
$\mathscr{G}(N^{\prime},t^{\prime})=\mathscr{G}(N,t)$.

###### Proof.

Let $(N,t)$ be a level-1 network that contains $l$ cycles. Assume that $C$ is
a weak cycle of $N$. Hence, we either have that (a) $(\rho_{C},\eta_{C})$ is
an edge of $N$, or (b) there exists two vertices $u$ and $v$ in $N$ and edges
$(\rho_{C},u)$, $(u,\eta_{C})$, $(\rho_{C},v)$, $(v,\eta_{C})$. We continue
with showing that we can “locally replace” $C$ by a tree to obtain a level-1
network $(N^{\prime},t^{\prime})$ on $X$ such that
$\mathscr{G}(N^{\prime},t^{\prime})=\mathscr{G}(N,t)$. In this case,
$(N^{\prime},t^{\prime})$ contains contains $l-1$ weak cycles and the
statement follows by induction.

Consider first Case (a) and let $N^{\prime}$ be the network obtained from $N$
by removing the edge $(\rho_{C},\eta_{C})$, and suppressing $\rho_{C}$, resp.,
$\eta_{C}$ in case they have now indegree 1 and outdegree 1 or indegree 0 and
outdegree 1. Note, these are the only vertices in $N$ that may have a
different indegree and outdegree than in $N^{\prime}$. It is now easy to
verify that $N^{\prime}$ remains a level-1 network with
$V(N^{\prime})\subseteq V(N)$. If $\rho_{C}$ has been suppressed in
$N^{\prime}$, then we define $\rho^{\prime}$ as the unique child $c$ of
$\rho_{C}$ that is located on $C$ and distinct from $\eta_{C}$ which is
feasible, since $c$ was not suppressed. In all other cases, we put
$\rho^{\prime}\coloneqq\rho_{C}$. In either case, $\rho^{\prime}\in
V(N^{\prime})$, however, $\rho^{\prime}\neq\rho_{N^{\prime}}$ may be possible.
The latter arguments also imply that, for all distinct $x.y\in X$, the vertex
$\operatorname{lca}_{N}(x,y)$ is not suppressed in $N^{\prime}$ whenever
$\operatorname{lca}_{N}(x,y)\neq\rho_{C},\eta_{C}$, $x,y\in X$. Moreover, if
$\operatorname{lca}_{N}(x,y)=\rho_{C}$, then at least one of the vertices $x$
and $y$ must be incomparable to every vertex in $C$ which implies that, after
the removal of the edge $(\rho_{C},\eta_{C})$, vertex $\rho_{C}$ must have
outdegree at least two and thus, was not suppressed. By similar arguments, if
$\operatorname{lca}_{N}(x,y)=\eta_{C}$, then $\eta_{C}$ must have outdegree at
least two $N^{\prime}$ and thus, was not suppressed in $N^{\prime}$. Hence, in
all cases the vertex $\operatorname{lca}_{N}(x,y)\in V(N)$ is present in
$N^{\prime}$ for all distinct $x.y\in X$.

We show now that for all distinct $x,y\in X$, we have indeed
$\operatorname{lca}_{N^{\prime}}(x,y)=\operatorname{lca}_{N}(x,y)$. Let
$x,y\in X$, $x\neq y$ be chosen arbitrarily. If $\operatorname{lca}_{N}(x,y)$
and $\rho_{C}$ are incomparable in $N$, then it is easy to verify that
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{N^{\prime}}(x,y)$ since we
only changed the topology of $N$ “below” $\rho_{C}$. Thus, assume that
$\operatorname{lca}_{N}(x,y)$ and $\rho_{C}$ are comparable in $N$. We
distinguish the following case:
$\operatorname{lca}_{N}(x,y)\prec_{N}\rho_{C}$,
$\rho_{C}\prec_{N}\operatorname{lca}_{N}(x,y)$ and
$\rho_{C}=\operatorname{lca}_{N}(x,y)$.

Assume first that $\operatorname{lca}_{N}(x,y)\prec_{N}\rho_{C}$. Since we
only removed $(\rho_{C},\eta_{C})$ and since the $\rho_{C}\eta_{C}$-path in
$N$ that is distinct from the single edge $(\rho_{C},\eta_{C})$ defines a
$\rho^{\prime}\eta_{C}$-path in $N^{\prime}$, we still have
$\operatorname{lca}_{N^{\prime}}(x,y)\prec_{N^{\prime}}\rho^{\prime}$ in case
$\rho^{\prime}=\rho_{C}$ and
$\operatorname{lca}_{N^{\prime}}(x,y)\preceq_{N^{\prime}}\rho^{\prime}$ if
$\rho_{C}$ was suppressed. Moreover, since the topology along all vertices $v$
with $v\prec_{N}\rho_{C}$ remained unchanged, it holds that
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{N^{\prime}}(x,y)$.

Assume now that $\rho_{C}\prec_{N}\operatorname{lca}_{N}(x,y)$. If neither $x$
and $y$ are not descendants of $\rho_{C}$ in $N$, then the paths from
$\operatorname{lca}(x,y)$ to $x$ and $y$ respectively remain unchanged in
$N^{\prime}$. In particular,
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{N^{\prime}}(x,y)$ holds.
Otherwise, we can assume w.l.o.g. that $x\prec_{N}\rho_{C}$ and that $y$ and
$\rho_{C}$ are incomparable in $N$ and thus,
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{N}(\rho_{C},y)$. Since we
have only removed the edge $(\rho_{C},\eta_{C})$, the vertices $y$ and
$\rho^{\prime}$ remain incomparable in $N^{\prime}$ and
$x\prec_{N^{\prime}}\rho^{\prime}$. Therefore,
$\operatorname{lca}_{N^{\prime}}(x,y)=\operatorname{lca}_{N^{\prime}}(\rho^{\prime},y)=\operatorname{lca}_{N}(\rho_{C},y)=\operatorname{lca}_{N}(x,y)$.

Finally assume that $\rho_{C}=\operatorname{lca}_{N}(x,y)$, in which case
$\rho^{\prime}=\rho_{C}$. In this case, at least one of the vertices $x$ and
$y$ must be incomparable to every vertex in $C$ and $\rho^{\prime}=\rho_{C}$
since, otherwise, $\operatorname{lca}_{N}(x,y)\preceq_{N}c$ where
$c\neq\eta_{N}$ denotes the unique child of $\rho_{C}$ that is located on a
$\rho_{C}\eta_{C}$-path in $N$. It is easy to verify that $\rho^{\prime}$
remains the $\preceq_{N^{\prime}}$-minimal ancestor of $x$ and $y$, since we
did not create new paths in $N^{\prime}$. Hence,
$\rho^{\prime}=\operatorname{lca}_{N^{\prime}}(x,y)$ and therefore,
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{N^{\prime}}(x,y)$.

In summary, for all vertices $x,y\in X$, we have
$\operatorname{lca}_{N^{\prime}}(x,y)=\operatorname{lca}_{N}(x,y)$. Let
$t^{\prime}$ be the restriction of $t$ to $V(N^{\prime})$, that is,
$t^{\prime}(v)=t(v)$ for all $v\in V(N^{\prime})\subseteq V(N)$. Since
$\operatorname{lca}_{N^{\prime}}(x,y)=\operatorname{lca}_{N}(x,y)$ and
$t^{\prime}$ retains the vertex labels for all such vertices, it follows that
$(N^{\prime},t^{\prime})$ is a labeled level-1 network such that
$\mathscr{G}(N^{\prime},t^{\prime})=\mathscr{G}(N,t)$ and that has one weak
cycle less than $N$.

Consider now Case (b). By Lemma 5.2, we can assume w.l.o.g. that $(N,t)$ is
quasi-discriminating and thus, $t(u)\neq t(\rho_{C})$ and $t(v)\neq
t(\rho_{C})$. Let $N^{\prime}$ be the network obtained from $N$ by applying
the following steps: Remove the edges $(\rho_{C},u)$, $(\rho_{C},v)$,
$(u,\eta_{C})$ and $(v,\eta_{C})$; add new vertices $\rho^{\prime}$ and
$w_{0}$; add the edges $(\rho_{C},\rho^{\prime})$, $(\rho^{\prime},\eta_{C})$,
$(\rho^{\prime},w_{0})$, $(w_{0},u)$ and $(w_{0},v)$; and suppress resulting
vertices of indegree and outdegree 1. By construction we have
$V(N^{\prime})\setminus\\{w_{0},\rho^{\prime}\\}\subseteq V(N)$. Moreover, we
have $\rho_{C}\in V(N^{\prime})$ if and only if $\rho_{C}$ has outdegree three
or more in $N$. We next define $t^{\prime}$ by putting
$t^{\prime}(w_{0})=t(\rho_{C})$, $t^{\prime}(\rho^{\prime})=t(v)$ and
$t^{\prime}(w)=t(w)$ for all $w\in
V(N^{\prime})\setminus\\{w_{0},\rho^{\prime}\\}$. Note,
$t^{\prime}(\rho^{\prime})=t(v)=t(u)$, since $(N,t)$ is quasi-discriminating.
Note that a vertex $w\in\\{\rho_{C},u,v\\}$ is suppressed if and only if $w$
has outdegree exactly two in $N$, while $\eta_{C}$ is suppressed if it has
outdegree one in $N$. All other vertices $w\in
V(N)\setminus\\{\rho_{C},u,v,\eta_{C}\\}$ remain vertices of $N^{\prime}$.

We next show that $\mathscr{G}(N^{\prime},t^{\prime})=\mathscr{G}(N,t)$. To
this end, we must verify that
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$
holds for all $x,y\in X$. Let $x,y\in X$ be two arbitrarily chosen vertices.
If $\operatorname{lca}_{N}(x,y)$ and $\rho_{C}$ are incomparable in $N$, then
the subnetwork of $N$ rooted at $\operatorname{lca}_{N}(x,y)$ remained
unchanged in $N^{\prime}$. In particular, we have
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{N^{\prime}}(x,y)$ and,
therefore,
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$
by definition of $t^{\prime}$. By similar arguments, if
$\operatorname{lca}_{N}(x,y)\prec_{N}\rho_{C}$ with
$\operatorname{lca}_{N}(x,y)\notin\\{u,v\\}$, then
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$.
If $\rho_{C}\prec_{N}\operatorname{lca}_{N}(x,y)$, then the path from
$\operatorname{lca}_{N}(x,y)$ to the parent $p$ of $\rho_{C}$ (possibly of
length 0) is preserved in $N^{\prime}$. In particular,
$\operatorname{lca}_{N^{\prime}}(x,y)=\operatorname{lca}_{N}(x,y)$ holds in
this case and thus,
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$
by definition of $t^{\prime}$.

It remains to consider the cases
$\operatorname{lca}_{N}(x,y)\in\\{\rho_{C},v,u\\}$. Assume first that
$\operatorname{lca}_{N}(x,y)=\rho_{C}$, then two cases can occur: (i) at least
one of $x,y$ is not a descendant of $u$ and $v$ in $N$, and (ii) $x$ is a
descendant of $u$ and $y$ is a descendant of $v$ in $N$ or _vice versa_. In
Case (i), $\rho_{C}$ has outdegree at least three in $N$, so $\rho_{C}\in
V(N^{\prime})$. By construction, $x$ and $y$ are descendant of distinct
children of $\rho_{C}$ in $N^{\prime}$, so
$\operatorname{lca}_{N^{\prime}}(x,y)=\rho_{C}=\operatorname{lca}_{N}(x,y)$.
By definition of $t^{\prime}$ it holds that
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$.
In Case (ii), we first remark that neither $x$ nor $y$ are descendant of
$\eta_{C}$ in $N$, since then $\operatorname{lca}_{N}(x,y)\prec_{N}\rho_{C}$;
a contradiction. This means that $x$ (resp., $y$) is descendant of one child
of $u$ (resp., $v$) that is distinct from $\eta_{C}$. Note, that these
particular children cannot be located on $C$ since $(u,\eta_{C})$ and
$(v,\eta_{C})$ are edges of $C$. Hence, by construction, $x$ and $y$ are
descendants of two distinct children of $w_{0}$ in $N^{\prime}$ and thus,
$\operatorname{lca}_{N^{\prime}}(x,y)=w_{0}$. Since
$t^{\prime}(w_{0})=t(\rho_{C})$ it follows that
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$.

Finally, if $\operatorname{lca}_{N}(x,y)\in\\{u,v\\}$, then two cases may
occur: (i’) None of $x$ and $y$ is a descendant of $\eta_{C}$ and (ii’)
exactly one of $x,y$, say $x$, is a descendant of $\eta_{C}$ in $N$. In Case
(i’), $\operatorname{lca}_{N}(x,y)$ has outdegree three or more in $N$. In
particular, $\operatorname{lca}_{N}(x,y)$ has outdegree two or more in
$N^{\prime}$, so $\operatorname{lca}_{N}(x,y)\in V(N^{\prime})$. It follows
that $\operatorname{lca}_{N^{\prime}}(x,y)=\operatorname{lca}_{N}(x,y)$ and
thus,
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$.
In Case (ii’), $x$ remains a descendant of $\eta_{C}$ in $N^{\prime}$ if
$\eta_{C}$ was not suppressed and, otherwise, a descendant of a child of
$\rho^{\prime}$ in $N^{\prime}$ that is distinct from $w_{0}$. Moreover, $y$
is a descendant of $w_{0}$ in $N^{\prime}$ . Hence,
$\operatorname{lca}_{N^{\prime}}(x,y)=\rho^{\prime}$. Since
$t^{\prime}(\rho^{\prime})=t(v)=t(u)$, we have
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$.

In summary, $N^{\prime}$ contains one weak cycle less than $N$ and
$t^{\prime}(\operatorname{lca}_{N^{\prime}}(x,y))=t(\operatorname{lca}_{N}(x,y))$
for all $x,y\in X$ which implies that
$\mathscr{G}(N^{\prime},t^{\prime})=\mathscr{G}(N,t)$. ∎

As a direct consequence of Lemma 5.3, we obtain a new characterization of
cographs.

######  Theorem 5.4.

A graph $G$ is a cograph if and only if $G$ can be explained by a weak labeled
level-1 network $(N,t)$.

###### Proof.

If $G$ is a cograph, then $G$ can be explained by a labeled phylogenetic tree
$(N,t)$ which is trivially a weak level-1 network since it does not contain
cycles.

Conversely, if $G$ can be explained by a weak labeled level-1 network $(N,t)$,
then all $l$ cycles of $N$ are weak and, by Lemma 5.3, there is a strong
level-1 network $(N^{\prime},t^{\prime})$ that contains no cycles and still
explains $G$. Hence, $(N^{\prime},t^{\prime})$ is a tree and thus, $G$ is a
cograph. ∎

Based on the latter results we can provide an additional characterization of
pseudo-cographs.

######  Theorem 5.5.

A graph $G$ is a pseudo-cograph if and only if $|V(G)|\leq 2$ or $G$ can be
explained by a level-1 network $(N,t)$ that contains precisely one cycle $C$
such that $\rho_{C}=\rho_{N}$ and $\operatorname{child}_{N}(\eta_{C})=\\{x\\}$
with $x\in L(N)$.

###### Proof.

Assume first that $G$ is a pseudo-cograph. If $|V(G)|\leq 2$ there is nothing
to show. Assume that $|V(G)|\geq 3$. In this case there is a vertex $v$ and
subgraphs $G_{1}$ and $G_{2}$ of $G$ such that $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph. By Prop. 4.15, $G$ can be explained by the
level-1 network $(N(v,G_{1},G_{2}),t(v,G_{1},G_{2}))$. This network contains
precisely one cycle $C$ with $\rho_{C}=\rho_{N}$, and
$\operatorname{child}_{N}(\eta_{C})=\\{v\\}$ and $v\in L(N)$.

Conversely, if $|V(G)|\leq 2$, then $G$ is a pseudo-cograph by definition.
Assume that $G$ can be explained by a level-1 network $(N,t)$ that contains
precisely one cycle $C$ with $\rho_{C}=\rho_{N}$. If $C$ is weak, then $N$ is
weak and Thm. 5.4 implies that $G$ is a cograph. By Lemma 4.2, $G$ is a
pseudo-cograph. Thus, assume that $C$ is strong. Since $N$ is level-1, there
is a unique hybrid-vertex $\eta_{C}$ in $C$. Consider the two sides $P^{1}$
and $P^{2}$ of $C$. Since $C$ is strong we have, in particular, that
$1\leq|V(P^{1})\setminus\\{\rho_{C},\eta_{C}\\}|,|V(P^{2})\setminus\\{\rho_{C},\eta_{C}\\}|$.
Let $u$ be the child of $\rho_{C}$ that is contained in $P^{1}$ and let $x$ be
the leaf that is the unique children of $\eta_{C}$. Consider the subnetwork
$(N_{1},t_{1})$ that is rooted at $u$ and where $\eta_{C}$ is suppressed.
Since $N$ contains only one cycle it follows that $(N_{1},t_{1})$ is a labeled
(phylogenetic) tree. Hence, $G_{1}\coloneqq G[L(N_{1})]$ must be a cograph.
Note that $V(G_{1})=L(N_{1})$ and thus, $|V(G_{1})|\geq 2$ since
$|V(P^{1})\setminus\\{\rho_{C}\\}|\geq 2$ and each vertex in $P^{1}-\rho_{C}$
must be an ancestor of at least one leaf in $L(N_{1})$. Consider now the
subnetwork $(N_{2},t_{2})$ that is rooted at $\rho_{C}$ and that contains none
of the vertices of $N_{1}$ except $\eta_{C}$ and $x$ and where $\eta_{C}$ is
finally suppressed and $\rho_{C}$ is removed in case it has outdegree 1 in
$N_{2}$. Roughly speaking, $(N_{2},t_{2})$ consists of the other side $P^{2}$
of $C$ and all vertices that are descendants of the vertices in $P^{2}$ except
for $u$ an its descendants that are different from $\eta_{C}$ and $x$. By
similar arguments as before, $(N_{2},t_{2})$ is a labeled (phylogenetic) tree
that explains the cograph $G_{2}\coloneqq G[L(N_{2})]$ with $|V(G_{2})|\geq
2$. Hence, $|V(G_{1})|,|V(G_{2})|>1$ and, by construction, $V(G_{1})\cup
V(G_{2})=V(G)$ and $V(G_{1})\cap V(G_{2})=\\{x\\}$. Thus, (F1) is satisfied.
Since both $G_{1}$ and $G_{2}$ are cographs (F2) holds. Moreover, for every
$y\in V(G_{1})\setminus\\{x\\}$ and $z\in V(G_{2})\setminus\\{x\\}$ it holds
that $\operatorname{lca}_{N}(y,z)=\rho_{N}$. Hence, depending on the label
$t(\rho_{N})$ it either holds that $\\{y,z\\}\in E$ or $\\{y,z\\}\notin E$ for
all $y\in V(G_{1})\setminus\\{x\\}$ and $z\in V(G_{2})\setminus\\{x\\}$. Thus,
$G-x$ is either the join or disjoint union of $G_{1}-x$ and $G_{2}-x$ which
implies that (F3) is satisfied. Hence, $G$ is a $(x,G_{1},G_{2})$-pseudo-
cograph. ∎

Note that not all graphs that can be explained by level-1 networks are pseudo-
cographs, see Fig. 6. Furthermore, observe that not every level-1 network that
explains a pseudo-cograph contains a cycle $C$ such that $\rho_{C}=\rho_{N}$
and $\operatorname{child}_{N}(\eta_{C})=\\{x\\}$ with $x\in L(N)$ as shown in
Fig. 3. Thus, there can be distinct quasi-discriminating level-1 networks that
explain the same graph $G$. Non-uniqueness of labeled level-1 networks that
explain a given graph is supported by further examples: Consider a network $N$
that contains a hybrid-vertex $\eta$ that has outdegree 1. In this case,
$\eta$ cannot be the lowest common ancestor of any pair of leaves. Hence, the
label of $\eta$ can be chosen arbitrarily. Let $v$ denote the unique child of
$\eta$ in a quasi-discriminating level-1 network $(\widehat{N},\widehat{t})$
and assume that $\widehat{t}(\eta)\neq\widehat{t}(v)$ and that $v$ is not a
leaf. In this case, there is another labeling $t$ of $\widehat{N}$ that keeps
all vertex labels except for $\eta$ where we put $t(\eta)=t(v)$. In this case,
$(\widehat{N},t)$ is not quasi-discriminating any more and we can contract the
edge $e=(\eta,v)$ to obtain a different quasi-discriminating level-1 network
$(N_{e},t_{e})$ for which $\mathscr{G}(N,t)=\mathscr{G}(N_{e},t_{e})$. Further
examples (incl. cographs) that show that different labeled level-1 networks
can explain the same graph are provided in Fig. 7.

Figure 6: Shown is a graph $G$ that is not a pseudo-cograph and thus, not a
polar-cat. To see this, assume for contradiction that $G$ is a
$(v,G_{1},G_{2})$-pseudo-cograph. There are only two choices for $v$ such that
$G-v$ is a cograph, namely $v\in\\{2,5\\}$. By Lemma 4.7, $G_{1}-v$ must
contain one component of $G-v$ and $G_{2}-v$ the other one. In this case,
however, $G_{1}$ or $G_{2}$ is not a cograph; a contradiction to (F2). The
graph $G^{\prime}\simeq G/\mathbb{M}_{\max}(G)$ is a pseudo-cograph and, in
particular, a polar-cat that is obtained from $G$ by identifying the two
vertices $3$ and $4$; see Section 7 for more details. Replacing the prime
vertex in the modular-decomposition tree of $(\mathscr{T}_{G},\tau_{G})$ of
$G$ by a strong quasi-discriminating elementary network that explains
$G^{\prime}$ yields the level-1 network $(N,t)$ that explains $G$. Figure 7:
Three different graphs that can be represented by non-isomorphic quasi-
discriminating elementary level-1 networks.

######  Lemma 5.6.

A graph $G$ can be explained by a weak quasi-discriminating elementary network
if and only if $G$ is a caterpillar-explainable cograph and $|V(G)|\geq 2$.

###### Proof.

Suppose that $G=(X,E)$ can be explained by a weak quasi-discriminating
elementary network $(N,t)$ on $X$. By Thm. 5.4, $G$ is a cograph. Since $N$ is
elementary it contains a cycle and, in particular, more than one leaf. Hence,
$|X|\geq 2$. Let $C$ be the unique cycles in $N$ of length $|X|+1$ and $P^{1}$
and $P^{2}$ be the sides of $C$. Since $N$ is weak, $C$ must be weak. Hence,
either one of $P^{1}$ and $P^{2}$ consists of $\rho_{C}$ and $\eta_{C}$ only
or both $P^{1}$ and $P^{2}$ contain only one vertex that is distinct from
$\rho_{C}$ and $\eta_{C}$.

Assume first that one of $P^{1}$ and $P^{2}$ consists of $\rho_{C}$ and
$\eta_{C}$ only. Now remove $\rho_{C}$ and its two incident edges from
$(N,t)$, suppress $\eta_{C}$ and keep the labels of all remaining vertices to
obtain a tree $(T,t^{\prime})$ on $X$. It is straightforward to verify that
$(T,t^{\prime})$ satisfies
$\operatorname{lca}_{N}(x,y)=\operatorname{lca}_{T}(x,y)$ for all distinct
$x,y\in X$ and therefore, $G=\mathscr{G}(N,t)=\mathscr{G}(T,t^{\prime})$. By
construction and since $N$ is elementary, $T$ is a caterpillar. Moreover,
since $\eta_{C}$ was suppressed in $T$ and since $t$ is a quasi-discriminating
labeling of $N$, the labeling $t^{\prime}$ must be a discriminating labeling
of $T$. Hence, $(T,t^{\prime})$ is the unique discriminating cotree of $G$.
Thus, $G=(X,E)$ is caterpillar-explainable. Assume now that both $P^{1}$,
resp., $P^{2}$ contain only one vertex $u$, resp., $v$ distinct from
$\rho_{C}$ and $\eta_{C}$. Hence, $C$ must be cycle of length $4=|X|+1$ and
thus, $|X|=3$. Since $(N,t)$ is quasi-discriminating it must hold
$t(u)=t(v)\neq t(\rho_{N})$. It is now easy to verify that $G$ is either
isomorphic to a $P_{3}$ or $K_{2}+K_{1}$ whose discriminating cotree is a
caterpillar. Hence, $G=(X,E)$ is caterpillar-explainable.

Suppose now that $G=(X,E)$ is a caterpillar-explainable cograph and $|X|\geq
2$. Let $(T,t)$ be its unique discriminating cotree which is, by definition, a
caterpillar. Since $|X|\geq 2$ the root of $T$ is distinct from the leaves in
$X$ and thus, an inner vertex. Let $\rho_{T}$ be the root of $T$, $x\in X$ be
one of the leaves that is part of the unique cherry in $T$ and $u$ be the
parent of $x$ in $T$. To construct a weak quasi-discriminating elementary
network $(N,t^{\prime})$ take $(T,t)$, remove the edge $(u,x)$, add a vertex
$\eta_{N}$ (the hybrid-vertex in $N$), add a vertex $\rho_{N}$ (the root of
$N$) and add edges $(u,\eta_{N})$, $(\eta_{N},x)$, $(\rho_{N},\rho_{T})$ and
$(\rho_{N},\eta_{N})$. It is straightforward to see that $N$ consists of a
single cycle $C$ for which one side consists of $\rho_{N}$ and $\eta_{N}$
only. Hence, $N$ is a weak elementary network. To obtain a quasi-
discriminating network, we define $t^{\prime}\colon V^{0}(N)\to\\{0,1\\}$ by
putting $t^{\prime}(v)=t(v)$ for all $v\in
V^{0}(N)\setminus\\{\rho_{N},\eta_{N}\\}$ and put $t^{\prime}(\rho_{N})\neq
t(\rho_{T})$ and choose $t^{\prime}(\eta_{N})\in\\{0,1\\}$ arbitrarily. It is
easy to verify that for all distinct $x,y\in X$ the vertex
$\operatorname{lca}_{N}(x,y)$ is located at the non-empty side of $C$ and in
particular, $\operatorname{lca}_{N}(x,y)\neq\rho_{N}$. In other words, for all
distinct $x,y\in X$ the vertex $\operatorname{lca}_{N}(x,y)$ is located in the
copy of $T$. Hence, $G=\mathscr{G}(N,t^{\prime})$. Therefore, $G$ can be
explained by a weak quasi-discriminating elementary network. ∎

##  6 Primitive Graphs, Polar-Cats and Elementary Networks

In this section, we first characterize cographs that are caterpillar-
explainable and polar-cats. These characterizations are based on particular
vertex-orderings. We then show that polar-cats are precisely the primitive
graphs that can be explained by strong quasi-discriminating elementary
networks.

######  Lemma 6.1.

A graph $G=(X,E)$, $|X|=n\geq 1$ can be explained by a discriminating
caterpillar tree $(T,t)$ on $X$ if and only if we can index the vertices of
$X$ from $1$ to $n$ such that one of the following holds:

  * (a)

$G$ is connected and the edges of $G$ are $\\{x_{i},x_{j}\\}$ with $1\leq
i<j\leq n$ and $i$ being odd.

  * (b)

$G$ is disconnected and the edges of $G$ are $\\{x_{i},x_{j}\\}$ with $1\leq
i<j\leq n$ and $i$ being even.

In this case, the indexing of the vertices in $X$ is unique up to permutation
of the indices $n-1$ and $n$. In particular, the vertices $x_{n-1}$ and
$x_{n}$ form the cherry in the underlying caterpillar.

###### Proof.

It is an easy task to verify that the statements are satisfied in case $n\leq
2$. Hence, let us assume that $n\geq 3$.

Assume first that $G$ can be explained by a discriminating caterpillar tree
$(T,t)$ on $X$. W.l.o.g. assume that the inner vertices are indexed in such a
way that the index $i$ in $v_{i}$ implies that
$\operatorname{dist}_{T}(\rho_{T},v_{i})=i-1$. Hence, $\rho_{T}=v_{1}$ and,
since there are $|X|=n$ leaves and $T$ is a caterpillar,
$V^{0}(T)=\\{v_{1},\dots,v_{n-1}\\}$. We index the leaves in such a way that
vertex $v_{i}$ is adjacent to $x_{i}$, $1\leq i\leq n-2$ while $v_{n-1}$ is
adjacent to $x_{n-1}$ and $x_{n}$. We consider now the two different cases:
(i) $t(v_{1})=1$ and (ii) $t(v_{1})=0$. In Case (i) it holds that $t(v_{1})=1$
and thus, $G$ is connected. Moreover, $t(v_{i})=1$ if and only if $i$ is odd
($1\leq i\leq n-1$), since $(T,t)$ is discriminating. By definition of
caterpillars and the choice of respective vertex indices, we have
$\operatorname{lca}(x_{i},x_{j})=v_{i}$, $1\leq i<j\leq n$. The latter two
arguments imply that $\\{x_{i},x_{j}\\}$ is an edge of $G$ if and only if $i$
is odd, $1\leq i\leq n$. Hence, Condition (a) is satisfied. Now consider Case
(ii). The fact that $t(v_{1})=0$ implies that $G$ is disconnected. By
analogous arguments and by interchanging the term “odd” by “even” one shows
that Condition (b) is satisfied as well.

Conversely, assume that we can index the vertices of $X$ from $1$ to $n$ such
that one of the Conditions (a) and (b) holds. We show that there exists a
discriminating caterpillar tree $(T,t)$ on $X$ explaining $G$.

Assume first that Condition (a) is satisfied. Let $M\subseteq X$ be a module
of $G$ with $|M|>1$. Let $x_{i},x_{j}\in M$, $1\leq i<j\leq n$. In this case,
every vertex $x_{k}\in X$ with $i<k<j$ must also be contained in $M$ since
otherwise there are two vertices $a,b\in M$ with $N_{G}(a)\setminus M\neq
N_{G}(b)\setminus M$. Thus, $\\{x_{k}\mid i\leq k\leq j\\}\subseteq M$ with
$1\leq i<j\leq n$. Since $|M|>2$, there are vertices $x_{j},x_{j-1}$ in $M$
and, by definition of the edges in Case (a), one of them is adjacent to
$x_{n}$ while the other is not. This implies that $x_{n}\in M$. Taking the
latter arguments together, every putative module of size at least two must be
of the form $M_{i}\coloneqq\\{x_{k}\mid i\leq k\leq n\\}$, $1\leq i\leq n-1$.
By definition, every $x\in M_{i}$ is adjacent to $x_{\ell}\in X\setminus M$ if
$\ell$ is odd and non-adjacent of $\ell$ is even. Hence, indeed $M_{i}$ is
module for all $i\in\\{1,\dots,n\\}$. It is easy to see that $M_{k}\cap
M_{k^{\prime}}\in\\{M_{k},M_{k^{\prime}}\\}$ and thus these modules do not
overlap. Hence
$\mathbb{M}_{\mathrm{str}}(G)=\\{M_{1}=X,M_{2},\dots,M_{n}\\}\cup(\cup_{x\in
X}\\{x\\})$. Moreover, $G[M_{i}]$ is disconnected if $i$ is even (since
$x_{i}\in M_{i}$ is not connected to any $x_{j}\in M_{i}\setminus\\{x_{i}\\}$)
and $\overline{G[M_{i}]}$ is disconnected if $i$ is odd (since $x_{i}\in
M_{i}$ is connected to all $x_{j}\in M_{i}\setminus\\{x_{i}\\}$). Hence, none
of the modules $M_{i}$ is a prime module. Its now easy to verify that the MDT
for $G$ must be a discriminating caterpillar $(T,t)$. In particular,
$M_{n-1}=\\{x_{n-1},x_{n}\\}$ is the smallest non-trivial module and thus
$x_{n-1}$ and $x_{n}$ form a cheery in $T$. By similar arguments one shows
that $G$ is explained by a discriminating caterpillar $(T,t)$ in case
Condition (b) is satisfied. ∎

######  Proposition 6.2.

Let $G=(X,E)$ be a graph with $|X|\geq 4$. Then, $G$ is a polar-cat if and
only if there exists a vertex $v\in X$ and two ordered sets
$Y=\\{y_{1},\ldots,y_{k-1},y_{k}=v\\}$ and
$Z=\\{z_{1},\ldots,z_{m-1},z_{m}=v\\}$, $k,m\geq 2$ such that $Y\cap
Z=\\{v\\}$, $Y\cup Z=X$, and one of the following conditions hold:

  * (a)

$G[Y]$ and $G[Z]$ are connected and the edges of $G$ are

    * (I)

$\\{y_{i},y_{j}\\}$, where $1\leq i<j\leq k$ and $i$ is odd; and

    * (II)

$\\{z_{i},z_{j}\\}$, where $1\leq i<j\leq m$ and $i$ is odd.

  * (b)

$G[Y]$ and $G[Z]$ are disconnected and the edges of $G$ are

    * (I)

$\\{y_{i},y_{j}\\}$, where $1\leq i<j\leq k$ and $i$ is even; and

    * (II)

$\\{z_{i},z_{j}\\}$, where $1\leq i<j\leq m$ and $i$ is even; and

    * (III)

$\\{y,z\\}$ for all $y\in Y\setminus\\{v\\}$ and $z\in Z\setminus\\{v\\}$

In this case, $G$ is a $(v,G[Y],G[Z])$-polar-cat

###### Proof.

Assume first that $G$ is a $(v,G_{1},G_{2})$-polar-cat. In this case, $G_{1}$
and $G_{2}$ are caterpillar-explainable such that $v$ is part of a cherry. We
can put $Y=V(G_{1})$ and $Z=V(G_{2})$. Since $G_{1}$ and $G_{2}$ intersect
only in vertex $v$ it holds that $G_{1}=G[Y]$ and $G_{2}=G[Z]$. By Lemma 6.1
and since $v$ is part of a cherry in the cotrees of $G_{1}$ and $G_{2}$, we
can order $Y$ and $Z$ such that $Y=\\{y_{1},\ldots,y_{k-1},y_{k}=v\\}$ and
$Z=\\{z_{1},\ldots,z_{m-1},z_{m}=v\\}$ and (a.I) and (a.II), resp., (b.I) and
(b.II) are satisfied. Moreover, since $G$ is polarizing, there are two cases
either (A) $G[Y]$ and $G[Z]$ are connected and
$G-v=(G_{1}-v)\operatorname{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}(G_{2}-v)$