# Clustering Systems of Phylogenetic Networks

Marc Hellmuth  Department of Mathematics, Faculty of Science, Stockholm
University, SE - 106 91 Stockholm, Sweden
<EMAIL_ADDRESS>corresponding author  David Schaller  Bioinformatics
Group, Department of Computer Science & Interdisciplinary Center for
Bioinformatics, Universität Leipzig, Härtelstraße 16–18, D-04107 Leipzig,
Germany.  Peter F. Stadler

( )

###### Abstract

Rooted acyclic graphs appear naturally when the phylogenetic relationship of a
set $X$ of taxa involves not only speciations but also recombination,
horizontal transfer, or hybridization, that cannot be captured by trees. A
variety of classes of such networks have been discussed in the literature,
including phylogenetic, level-1, tree-child, tree-based, galled tree, regular,
or normal networks as models of different types of evolutionary processes.
Clusters arise in models of phylogeny as the sets
$\operatorname{\mathtt{C}}(v)$ of descendant taxa of a vertex $v$. The
clustering system $\mathscr{C}_{N}$ comprising the clusters of a network $N$
conveys key information on $N$ itself. In the special case of rooted
phylogenetic trees, $T$ is uniquely determined by its clustering system
$\mathscr{C}_{T}$. Although this is no longer true for networks in general, it
is of interest to relate properties of $N$ and $\mathscr{C}_{N}$. Here, we
systematically investigate the relationships of several well-studied classes
of networks and their clustering systems. The main results are correspondences
of classes of networks and clustering system of the following form: If $N$ is
a network of type $\mathbb{X}$, then $\mathcal{C}_{N}$ satisfies $\mathbb{Y}$,
and conversely if $\mathscr{C}$ is a clustering system satisfying $\mathbb{Y}$
then there is network $N$ of type $\mathbb{X}$ such that
$\mathscr{C}\subseteq\mathscr{C}_{N}$.This, in turn, allows us to investigate
the mutual dependencies between the distinct types of networks in much detail.

Keywords:  compatibility, level-k, hybrid, evolution, cluster, network,
phylogenetics, least common ancestor

##  1 Introduction

Networks used to model phylogenetic relationships typically are directed
acyclic graphs (DAGs) with a single root, i.e., a unique vertex from which all
other vertices can be reached from. As usual in phylogenetics, the subset $X$
of vertices without descendants (the leaves of the network) represents the
extant taxa, while the remaining vertices model their ancestors. In this
contribution, we are interested in the relationships between the structure of
networks $N$ with leaf set $X$ and their associated clustering systems
$\mathscr{C}_{N}$, which contains, for each vertex $v$ of $N$, the subset
$\operatorname{\mathtt{C}}(v)\subseteq X$ of leaves that can be reached from
$v$ [45, 26]. In the literature on phylogenetic networks, the sets
$C\in\mathscr{C}_{N}$ are often called the “hardwired clusters” of $N$.

As a special case, there is a well-known 1-to-1 correspondence between rooted
phylogenetic trees $T$ and hierarchies $\mathscr{C}$ [48], i.e., clustering
systems that do not contain pairs of overlapping clusters. Therefore, $T$ is
uniquely determined by $\mathscr{C}_{T}=\mathscr{C}$. This simple
correspondence, however, is no longer true for (phylogenetic) networks.
Nevertheless, it is not difficult to find some network $N$ for a given
clustering system $\mathscr{C}$ such that $\mathscr{C}_{N}=\mathscr{C}$: If
suffices to determine the Hasse diagram $N=\mathfrak{H}(\mathscr{C})$ of the
inclusion partial order of the clustering system $\mathscr{C}$ to obtain such
a network. For a phylogenetic trees $T$, the Hasse diagram
$\mathfrak{H}(\mathscr{C}_{T})$ and $T$ are isomorphic. For general networks,
however, the situation is much more complicated [45, 26, 59].

A broad array of different types of networks have been studied in the
literature in order to model different modes of non-tree-like evolution such
as horizontal gene transfer, recombination, or hybridization, see [43] for a
current review. Naturally, the question arises how much information about the
structure of $N$ is contained in the clustering system $\mathscr{C}_{N}$. We
will in particular be concerned with the following, inter-related questions

  1. 1.

Which types of networks $N$ satisfy $N\simeq\mathfrak{H}(\mathscr{C}_{N})$?

  2. 2.

What are necessary properties of the clustering systems $\mathscr{C}_{N}$
obtained for networks $N$ of a given class?

  3. 3.

Which types of networks $N$, if any, can be characterized in terms of
properties of their clustering systems $\mathscr{C}_{N}$?

  4. 4.

When is a network $N$ uniquely determined by $\mathscr{C}_{N}$ or by the
corresponding multiset of clusters $\mathscr{M}_{N}$?

  5. 5.

When is a clustering system $\mathscr{C}$ compatible with a specified type of
network $N$ in the sense that there is network $N$ of given type such that
$\mathscr{C}\subseteq\mathscr{C}_{N}$?

While addressing these questions, we will also consider the implications
between the defining properties of the various network classes. To help the
reader navigate this contribution, we summarize the properties of interest in
Table 1 and point to their formal definitions. Complementarily, properties of
clustering systems are compiled in Table 2. Many of the results established
here are summarized in Table 3.

It is important to note that the literature on phylogenetic networks does not
always utilize the same nomenclature. In particular, properties such as
_binary_ , _separated_ , _conventional_ , or _phylogenetic_ are – more often
than not – taken for granted in a given publication and explicitly or tacitly
included in the definition of “phylogenetic network”. Here, we start from a
very general setting of rooted DAGs, called “networks” throughout. All
additional properties are made explicit throughout. We furthermore strive to
prove all statements as general as possible. The reader will therefore on
occasion find results that are well known in the field, although earlier
proofs pertain to a more restrictive setting.

This paper is organized as follows. In Section 2, we provide the basic
terminology and definitions used throughout this paper. In Section 3, we start
with a closer look at phylogenetic networks (Sect. 3.1) and related concepts
which includes graph modifications such as arc-contractions or expansions
(Sect. 3.2) as well as the structural properties of non-trivial biconnected
components (called blocks) in networks (Sect. 3.3). We then continue in
Section 3.4 to characterize the structure of the Hasse diagram of clustering
systems. In particular, we provide new characterizations of regular networks,
that is, networks that are isomorphic to the Hasse diagram of some clustering
system.

In Section 4, we consider semi-regular networks, i.e., networks that do not
contain so-called shortcuts and satisfy the path-cluster-comparability (PCC)
property as introduced in Section 4.1. (PCC) simply ensures that one of the
clusters $\operatorname{\mathtt{C}}(u)$ and $\operatorname{\mathtt{C}}(v)$ is
subsets of the other one whenever the vertices $u$ and $v$ are connected by a
directed path in $N$. Although this property does not seem to have been
studied so far, it turns out to play a fundamental role in the relationships
between networks and their clustering systems. Regular networks, as it turns
out, are precisely the semi-regular networks that do not contain vertices with
outdegree $1$. In addition, we show how to obtain regular networks
$N^{\prime}$ from networks $N$ that only satisfy (PCC) such that
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. In Section 4.2, we consider
separated networks (networks for which each vertex with indegree greater than
$1$ has outdegree $1$) and cluster networks in the sense of [26] (whose
definition is somewhat more involved). As we shall see, cluster networks are
precisely the networks that are semi-regular, separated, and phylogenetic. We
then show in Section 4.3, that semi-regular networks are uniquely determined
by their multiset of clusters and that, in turn, cluster networks, as a
subclass of regular networks, are uniquely determined by their clustering
systems. Section 5 makes a short excursion to so-called tree-child, normal,
and tree-based networks and their mutual relationships.

In Section 6, we then have a closer look at the concept of least common
ancestors ($\operatorname{lca}$) in networks. In contrast to rooted trees, the
$\operatorname{lca}$ of a pair of leaves (or more generally, a subset of
leaves) is in general not uniquely defined. We introduce in Section 6.1
several classes of networks in which the $\operatorname{lca}$ is unique for at
least certain subsets of leaves. This leads to the cluster-lca property (CL)
which is satisfied by a network $N$ whenever
$\operatorname{lca}(\operatorname{\mathtt{C}}(v))$ is uniquely determined for
all $v\in V(N)$. We shall see that every network that satisfies (PCC), and
this in particular includes all normal networks, also satisfy (CL). In Section
6.2, we consider lca-networks, i.e., networks in which $\operatorname{lca}(A)$
is uniquely determined for all leaf sets $A\subseteq X$. Among other results,
we show that a clustering system $\mathscr{C}$ is closed (under intersection)
if only if it is the clustering systems $\mathscr{C}_{N}$ of an lca-network.
We then consider in Section 6.3 the subclass strong lca-networks, in which,
for all $A\subseteq X$, it holds that
$\operatorname{lca}(A)=\operatorname{lca}(\\{x,y\\})$ for a suitably chosen
pair of leaves $x$ and $y$. These are closely related to weak hierarchies.

A very prominent role in phylogenetics is played by level-1 networks. Section
7 is devoted to establishing structural results for level-1 networks and their
underlying clustering systems. After establishing basic results, we derive in
Section 7.3 a simple condition, called property (L), for clustering systems
that is defined in terms of the intersection of its elements. As a main result
of this contribution, we obtain in Section 7.4 a simple characterization of
the clustering systems of (phylogenetic, separated) level-1 network as the
ones that are closed and satisfy (L). We then show in Section 7.5 that
property (L) is sufficient to ensure that clustering systems are “compatible”
with a (phylogenetic, separated) level-1 network. Moreover, we provide a
polynomial-time algorithm to check if $\mathscr{C}$ is compatible with some
level-1 network and, in the affirmative case, to construct such a network. We
finally consider in Section 8 several subclasses of level-1 networks as e.g.
galled trees or binary, conventional, separated or quasi-binary level-1
networks and characterize their clustering systems. Finally, we show that
quasi-binary level-1 networks are encoded by their multisets of clusters. In
Section 9, we provide a summary of the main results (see also Table 3).

##  2 Preliminaries

The power set of a given set $X$ is denoted by $2^{X}$. Two sets $A$ and $B$
overlap if $A\cap B\notin\\{\emptyset,A,B\\}$.

We consider graphs $G=(V,E)$ with vertex set $V(G)\coloneqq V$ and arc 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)\setminus\\{(v,v)\mid v\in V\\}$. Thus, arcs $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. The _degree_ of a vertex $v\in V$ in an
undirected or directed graph $G$, denoted by $\deg_{G}(v)$, is the number of
arcs that are incident with $v$. If $G$ is directed, we furthermore
distinguish the indegree $\operatorname{indeg}_{G}(v)=|\left\\{u\mid(u,v)\in
E\right\\}|$ and the outdegree $\operatorname{outdeg}_{G}(v)=|\\{u\mid(v,u)\in
E\\}|$. 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\\}]$.

A path $P$ in an undirected (resp. directed) graph $G$ is a subgraph of $k\geq
1$ vertices and arcs $\\{v_{i},v_{i+1}\\}\in E$ (resp. $(v_{i},v_{i+1})\in E$)
for all $1\leq i\leq k-1$. Moreover, (directed) paths connecting two vertices
$x$ and $y$ are also called _$xy$ -paths_. We will often write _undirected
path_ for a subgraph $P$ of a directed graph $G$ that has vertices
$\\{v_{1},v_{2},\dots,v_{k}\\}$, $k\geq 1$, and the _forward arc_
$(v_{i},v_{i+1})$ or the corresponding _backward arc_ $(v_{i+1},v_{i})$ for
all $1\leq i\leq k-1$. The vertices $v_{1}$ and $v_{k}$ in a directed or
undirected path $P$ are the _endpoints_ of $P$ and all other vertices (in $P$)
are its _inner vertices_. A path $P$ with vertices
$\\{v_{1},v_{2},\dots,v_{k}\\}$ in a directed graph G is _induced (in $G$)_ if
$(v_{i},v_{j})\in E(G)$ precisely if $j=i+1$, for all $i\in\\{1,\dots,k-1\\}$.

A directed cycle $K$ in a directed graph $G$ is a subgraph with vertices
$\\{v_{1},v_{2},\dots,v_{k}\\}$, $k\geq 2$, and arcs $(v_{i},v_{i+1})\in E$
for all $1\leq i\leq k-1$ and additionally $(v_{k},v_{1})\in E$. In analogy to
undirected paths, an _undirected cycle_ $K$ in a directed graph $G$ is a
subgraph with $k\geq 3$ vertices that can be ordered in the form
$\\{v_{1},v_{2},\dots,v_{k}\\}$ such that the forward arc $(v_{i},v_{i+1})$ or
the corresponding backward arc $(v_{i+1},v_{i})$ for $1\leq i\leq k-1$, as
well as the forward arc $(v_{k},v_{1})$ or the backward arc $(v_{1},v_{k})$
are exactly the arcs of $K$.

An undirected graph $G=(V,E)$ is _bipartite_ if there is a partition of $V$
into subsets $W$ and $W^{\prime}$ such that every arc in $G$ connects one
vertex in $W$ to one vertex in $W^{\prime}$. If in addition, $x\in W$ and
$x^{\prime}\in W^{\prime}$ implies $\\{x,x^{\prime}\\}\in E$, then $G$ is
_complete bipartite_.

#### Graph connectivity.

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. A connected component of $G$ is a
maximal induced subgraph that is connected. A vertex $v$ is a cut vertex in a
graph $G$ if $G[V(G)\setminus\\{v\\}]$ consists of more connected components
than $G$. Similarly, a directed or undirected arc $(u,v)$ is a cut arc in $G$
if the graph $G^{\prime}$ with vertex set $V(G^{\prime})=V(G)$ and arc set
$E(G^{\prime})=E(G)\setminus\\{(u,v)\\}$ consists of more connected components
than $G$.

An undirected or directed graph is _biconnected_ if it contains no vertex
whose removal disconnects the graph. A _block_ of an undirected or a directed
graph is a maximal biconnected subgraph. A block $B$ is called _non-trivial_
if it contains an (underlying undirected) cycle. Equivalently, a block is non-
trivial if it is not a single vertex or a single arc. An arc that is at the
same time a (trivial) block is a cut arc. For later reference, we state here
the following observations that are immediate consequences of the fact that
two distinct blocks in a graph share at most one vertex [55, Prop. 4.1.19]:

######  Observation 2.1.

If two biconnected subgraphs share two vertices, then their union is contained
in a common block.

######  Observation 2.2.

If $B$ and $B^{\prime}$ are distinct blocks of a directed graph, then $B$ and
$B^{\prime}$ are arc-disjoint.

The latter is justified by the fact that if blocks $B$ and $B^{\prime}$ share
a common arc, then $B\cup B^{\prime}$ is biconnected and thus, $B=B^{\prime}$
since blocks are always _maximal_ biconnected subgraphs. We will frequently
make use of

######  Theorem 2.3.

[55, Thm. 4.2.4] For a graph $G$ with at least three vertices, the following
statements are equivalent:

  1. 1.

$G$ is biconnected.

  2. 2.

For all $x,y\in V(G)$, there are at least two internally vertex-disjoint
(undirected) paths connecting $x$ and $y$.

  3. 3.

For all $x,y\in V(G)$, there is an (undirected) cycle containing $x$ and $y$.

######  Corollary 2.4.

Any two vertices of a non-trivial block $B$ lie on a common (undirected) cycle
in $B$.

The following well-known result will also be useful throughout:

######  Proposition 2.5.

[21, Prop. 3.1.1] Let $H$ be a biconnected subgraph of $G$ and $P$ be a path
in $G$ that only shares its endpoints with $H$. Then the subgraph obtained by
adding $P$ to $H$ is again biconnected.

#### Directed acyclic graphs.

A directed graph $G=(V,E)$ is _acyclic_ if it does not contain a directed
cycle. In particular, every undirected cycle in a directed acyclic graph (DAG)
contains at least one forward and one backward arc. In a DAG $G$, a vertex
$u\in V$ is called an _ancestor_ of $v\in V$ and $v$ a _descendant_ of $u$, in
symbols $v\preceq_{G}u$, if there is a directed path (possibly reduced to a
single vertex) in $G$ from $u$ to $v$. We write $v\prec_{G}u$ if
$v\preceq_{N}u$ and $u\neq v$. If $u\preceq_{N}v$ or $v\preceq_{G}u$, then $u$
and $v$ are _$\preceq_{G}$ -comparable_ and otherwise, _$\preceq_{G}$
-incomparable_. Moreover, if $(u,v)\in E$, we say that $u$ is a _parent_ of
$v$, $u\in\operatorname{par}_{G}(v)$, and $v$ is a _child_ of $u$,
$v\in\operatorname{child}_{G}(u)$. Following [32], we call a vertex $v$ that
is $\preceq_{G}$-minimal in a block $B$ a _terminal vertex_ (of $B$). Note
that every terminal vertex $v$ of a non-trivial block $B$ must always have
indegree at least $2$ since, by Cor. 2.4, $v$ lies on some undirected cycle in
$B$ and, by $\preceq_{G}$-minimality of $v$ in $B$, its two incident vertices
on this cycle must both be in-neighbors. Below we will consider DAGs in which
terminal vertices are a type of so-called hybrid vertices.

An arc $(u,w)$ in a DAG $G$ is a _shortcut_ if there is a vertex
$v\in\operatorname{child}(u)\setminus\\{w\\}$ such that $w\prec_{G}v$ (or,
equivalently, if there is a vertex $v^{\prime}\in V(G)$ such that
$w\prec_{G}v^{\prime}\prec_{G}u$). A DAG without shortcuts is _shortcut-free_.

######  Observation 2.6.

Let $G$ be a DAG. The following statements are equivalent:

  1. 1.

$N$ is shortcut-free.

  2. 2.

For all $u\in V(N)$, $v,w\in\operatorname{child}_{G}(u)$ are
$\preceq_{G}$-comparable if and only if $v=w$.

  3. 3.

For all $u\in V(N)$, $v,w\in\operatorname{par}_{G}(u)$ are
$\preceq_{G}$-comparable if and only if $v=w$.

##  3 Networks and Clustering Systems

###  3.1 Basic Concepts

We define (phylogenetic) networks here as a slightly more general class of
DAGs than what is customarily considered in most of the literature on the
topic.

######  Definition 3.1.

A _(rooted) network_ is a directed acyclic graph $N=(V,E)$ such that

  * (N1)

There is a unique vertex $\rho_{N}$, called the _root_ of $N$, with
$\operatorname{indeg}(\rho_{N})=0$.

A network is _phylogenetic_ if

  * (N2)

There is no vertex $v\in V$ with $\operatorname{outdeg}(v)=1$ and
$\operatorname{indeg}(v)\leq 1$.

A vertex with $v\in V$ is a _leaf_ if $\operatorname{outdeg}(v)=0$, a _hybrid
vertex_ if $\operatorname{indeg}(v)>1$, and _tree vertex_ if
$\operatorname{indeg}(v)\leq 1$. The set of leaves is denoted by $X$.

We note that a leaf $x\in X$ is always either a hybrid vertex or a tree
vertex. A leaf $x\in X$ is a _strict descendant_ of $v\in V$ if every directed
path from the root $\rho_{N}$ to $x$ contains $v$. In contrast to the even
more general definition [37, Def. 3], we use the term “phylogenetic” here to
mean that vertices with indegree $1$ and outdegree $1$ do not appear.
Moreover, the root is either the single leaf or has
$\operatorname{outdeg}(\rho_{N})\geq 2$. Rooted phylogenetic networks thus
generalize rooted phylogenetic trees. Since the root is an ancestor of all
vertices, $N$ is connected. We emphasize that all networks considered here are
rooted and thus, we always use the term “network” instead of “rooted network”.

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]$.

Table 1: Summary of networks considered in this paper. Network $N$ is/satisfies | Ref.
---|---
_tree (level- $0$)_ |  $N$ does not contain hybrid vertices |
_shortcut-free_ |  $N$ does not contain shortcuts |
_phylogenetic_ |  cf. Def. 3.1 (N2) |  Def. 3.1
_separated_ |  all hybrid vertices of $N$ have outdegree $1$. |  Def. 3.2
_binary_ |  every tree vertex $v$ is either a leaf or has $\operatorname{outdeg}(v)=2$, and every hybrid vertex $v$ satisfies $\operatorname{indeg}(v)=2$ and $\operatorname{outdeg}(v)=1$. |  Def. 3.3
_level- $k$_ |  each block $B$ of $N$ contains at most $k$ hybrid vertices (distinct from the “root” of $B$) |  Def. 3.24
_regular_ |  there is a prescribed isomorphism between $N$ and the Hasse diagram $\mathfrak{H}(\mathscr{C}_{N})$ of the clusters in $N$. |  Def. 3.41
_path-cluster-comparability (PCC)_ |  for all $u,v\in V(N)$, $u$ and $v$ are $\preceq_{N}$-comparable if and only if $\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)$ or $\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(u)$. |  Def. 4.1
_semi-regular_ |  $N$ is shortcut-free and satisfies (PCC). |  Def. 4.2
_cluster network_ |  $N$ satisfies (PCC), and, three additional properties based on the clusters and respective vertices in $N$ |  Def. 4.18
_tree-child_ |  for every $v\in V^{0}(N)$, there is a “tree-child”, i.e., $u\in\operatorname{child}(v)$ with $\operatorname{indeg}(u)=1$. |  Def. 5.1
_normal_ |  $N$ is tree-child and shortcut-free. |  Def. 5.4
_tree-based_ |  there is a base tree $T$ of $N$ that can be obtained from $N$ in a prescribed manner |  Def. 5.11
_cluster-lca (CL)_ |  $\operatorname{lca}(\operatorname{\mathtt{C}}(v))$ is defined for all $v\in V(N)$ |  Def. 6.8
_lca-network_ |  $\operatorname{lca}(A)$ is well-defined, i.e., if $|\operatorname{LCA}(A)|=1$ for all non-empty subsets $A\subseteq X$. |  Def. 6.14
_strong lca-network_ |  $N$ is an lca-network and, for every non-empty subset $A\subseteq X$, there are $x,y\in A$ such that $\operatorname{lca}(\\{x,y\\})=\operatorname{lca}(A)$. |  Def. 6.24
_galled tree_ |  every non-trivial block in $N$ is an (undirected) cycle. |  Def. 8.3
_conventional_ |  (i) all leaves have indegree at most $1$ and (ii) every hybrid vertex is contained in a unique non-trivial block. |  Def. 8.17
_quasi-binary_ |  $\operatorname{indeg}_{N}(w)=2$ and $\operatorname{outdeg}_{N}(w)=1$ for every hybrid vertex $w\in V(N)$ and, additionally, $\operatorname{outdeg}_{N}(\max B)=2$ for every non-trivial block $B$ in $N$. |  Def. 8.30
Table 2: Properties of clustering systems considered in this paper. Clustering system $\mathscr{C}$ is/satisfies | Ref.
---|---
_hierarchy_ |  for all $C,C^{\prime}\in\mathscr{C}$, it holds $C\cap C^{\prime}\in\\{\emptyset,C,C^{\prime}\\}$. |  Def. 3.5
_closed_ |  $\mathcal{C}$ is closed under intersection, i.e., $\bigcap_{C\in\mathscr{C}^{\prime}}C\in\mathscr{C}\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}}}}\\{\emptyset\\}$ holds for all $\mathscr{C}^{\prime}\subseteq\mathscr{C}$. |  Def. 3.31
_pre-binary_ |  for every pair $x,y\in X$, there is a unique inclusion-minimal cluster $C$ such that $\\{x,y\\}\subseteq C$ |  Def. 6.6
_binary_ |  pre-binary and, for every $C\in\mathscr{C}$, there is a pair of vertices $x,y\in X$ such that $C$ is the unique inclusion-minimal cluster containing $x$ and $y$. |  Def. 6.25
_weak hierarchy_ |  for all $C_{1},C_{2},C_{3}\in\mathscr{C}$, it holds $C_{1}\cap C_{2}\cap C_{3}\in\\{C_{1}\cap C_{2},C_{1}\cap C_{3},C_{2}\cap C_{3},\emptyset\\}$. |  Def. 6.25
_(L)_ |  $C_{1}\cap C_{2}=C_{1}\cap C_{3}$ for all $C_{1},C_{2},C_{3}\in\mathscr{C}$ where $C_{1}$ overlaps both $C_{2}$ and $C_{3}$. |  Def. 7.15
_(N3O)_ |  $\mathscr{C}$ contains no three distinct pairwise overlapping clusters. |  Def. 8.7
_paired hierarchy_ |  every $C\in\mathscr{C}$ overlaps with at most one other cluster in $\mathscr{C}$. |  Def. 8.14
_(2-Inc)_ |  for all clusters $C\in\mathscr{C}$, there are at most two inclusion-maximal clusters $A,B\in\mathscr{C}$ with $A,B\subsetneq C$ and at most two inclusion-minimal clusters $A,B\in\mathscr{C}$ with $C\subsetneq A,B$. |  Def. 8.22

A network $N$ with leaf set $X$ is often called a _network on $X$_. Two
networks $N_{1}=(V_{1},E_{1})$ and $N_{2}=(V_{2},E_{2})$ on $X$ are _graph
isomorphic_ , in symbols $N_{1}\sim N_{2}$, if there is a _graph isomorphism_
, i.e., a bijection $\varphi\colon V_{1}\to V_{2}$ such that $(u,v)\in E_{1}$
if and only if $(\varphi(u),\varphi(v))\in E_{2}$ for all $u,v\in V_{1}$.
Moreover, if additionally $N_{1}$ and $N_{2}$ are networks on the same leaf
set $X$, we say that $N_{1}$ and $N_{2}$ are _isomorphic_ in symbols
$N_{1}\simeq N_{2}$ if $N_{1}\sim N_{2}$ (via the graph isomorphism $\varphi$)
and $\varphi(x)=x$ for all $x\in X$. We say that a network $N$ on $X$ is
_unique_ w.r.t. some property (or some set of properties), if $N\simeq
N^{\prime}$ for every network $N^{\prime}$ that also satisfies the desired
property (or properties).

Many studies into phylogenetic networks require that reticulation events and
speciation events are separated, i.e., $\operatorname{outdeg}(v)=1$ for all
hybrid vertices.

######  Definition 3.2.

A network $N$ is _separated_ if all hybrid vertices have outdegree $1$.

In particular, all leaves have indegree $1$ in a separated network (or
indegree zero if the network consists of a single vertex).

The properties _phylogenetic_ and _separated_ are part of the definition of
networks in many publications in the field, see e.g. [42, 47, 59]. However, we
opted for the more general definition of networks for several reasons. On the
one hand, we aim to explore which restrictions are actually needed to
establish the relationship of different properties or classes of networks. On
the other hand, separated networks do not include regular networks [5], which
are, as we shall see, a class of networks that is intimately linked with
clustering systems.

An even more restrictive class of networks that is often considered are binary
networks [24, 12, 43]:

######  Definition 3.3.

A network is _binary_ if every tree vertex $v$ is either a leaf or has
$\operatorname{outdeg}(v)=2$, and every hybrid vertex $v$ satisfies
$\operatorname{indeg}(v)=2$ and $\operatorname{outdeg}(v)=1$.

By construction, binary networks are always phylogenetic and separated.

Throughout this paper, several other properties and distinct classes of
networks are considered. For convenience, all these types are listed in Table
1. More formal definitions or more precise explanations are given in the
remainder of the paper. A further essential ingredient to our paper are
clusters and clustering systems as defined next.

######  Definition 3.4.

Let $N$ be a network with vertex set $V$, leaf set $X$ and partial order
$\preceq_{N}$. Then, for each $v\in V$, the associated _cluster_ is
$\operatorname{\mathtt{C}}(v)\coloneqq\operatorname{\mathtt{C}}_{N}(v)\coloneqq\\{x\in
X\mid x\preceq_{N}v\\}$. Furthermore, we write
$\mathscr{C}\coloneqq\mathscr{C}_{N}\coloneqq\\{\operatorname{\mathtt{C}}(v)\mid
v\in V\\}$.

Note, that $\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)$ may be
possible for distinct $v,w\in V$. However, $\mathscr{C}$ is considered as a
_set_ and thus, each cluster appears only once in $\mathscr{C}_{N}$. The
clusters in $\mathscr{C}_{N}$ are usually called the _hardwired clusters_ of
$N$, see e.g. [37].

######  Definition 3.5.

[7, 48] A _clustering system_ on $X$ is a set $\mathscr{C}\subseteq 2^{X}$
such that (i) $\emptyset\notin\mathscr{C}$, (ii) $X\in\mathscr{C}$, and (iii)
$\\{x\\}\in\mathscr{C}$ for all $x\in X$. A clustering system is a _hierarchy_
if it does not contain pairwise overlapping sets.

Figure 1: Three non-isomorphic (binary) level-1 networks with the same
clustering system $\mathscr{C}=\\{\\{a\\},\\{b\\},\\{a,b\\}\\}$. While they
are indistinguishable in terms of their clustering systems, they are encoded
by their multiset of clusters, see Thm. 8.33, i.e., they are distinguished by
the multiplicities of the clusters $\\{a\\}$, $\\{b\\}$, and $\\{a,b\\}$.

We will mainly focus on clustering systems $\mathscr{C}_{N}$ of networks $N$
(cf. Lemma 3.29). As shown in Fig. 1, the information conveyed by
$\mathscr{C}_{N}$ is often insufficient to determine $N$, i.e., there are non-
isomorphic networks $N$ and $N^{\prime}$ for which
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. A natural generalization is to
consider the _multiset of clusters_ $\mathscr{M}_{N}$, in which each cluster
$C\in\mathscr{C}_{N}$ appears once for every vertex $v\in V(N)$ with
$\operatorname{\mathtt{C}}(v)=C$. We say that $\mathscr{M}_{N}$ _encodes_ $N$
__within a given class $\mathbb{P}$ of networks if $N^{\prime}\in\mathbb{P}$
and $\mathscr{M}_{N^{\prime}}=\mathscr{M}_{N}$ implies $N^{\prime}\simeq N$.

As for networks, we will also consider plenty of different types of clustering
systems equipped with certain properties and, for convenience, list them in
Table 2.

###  3.2 Arc-Expansion and Arc-Contraction

As mentioned above, often only separated networks are considered, stipulating
that (1) leaves, i.e., vertices $v$ with $\operatorname{outdeg}(v)=0$ have
$\operatorname{indeg}(v)=1$; (2) hybrid vertices $v$ have
$\operatorname{indeg}(v)\geq 2$ and $\operatorname{outdeg}(v)=1$. Such
networks are obtained from the ones in Def. 3.1 by means of a simple
refinement operation that replaces every “offending” vertex by a pair of
vertices connected by single arc. More precisely, we define the following
operation on a network $N$, which is also part of [37, Alg. 6.4.2]:

$\operatorname{\textsc{expd}}(v)$

Create a new vertex $v^{\prime}$, replace arcs $(u,v)$ by $(u,v^{\prime})$ for
all $u\in\operatorname{par}_{N}(v)$, and add the arc $(v^{\prime},v)$.

It will also useful to consider the reversed operation for arcs
$(v^{\prime},v)$ that are not shortcuts:

$\operatorname{\textsc{cntr}}(v^{\prime},v)$

Replace arcs $(u,v^{\prime})$ by $(u,v)$ for all
$u\in\operatorname{par}_{N}(v^{\prime})\setminus\operatorname{par}_{N}(v)$;
replace arcs $(v^{\prime},w)$ by $(v,w)$ for all
$w\in\operatorname{child}_{N}(v^{\prime})\setminus\operatorname{child}_{N}(v)$;
and finally delete $(v^{\prime},v)$ and $v^{\prime}$.

The notation $\operatorname{\textsc{cntr}}$ is chosen in compliance with the
literature where arc contraction is a commonly used operation. Fur our
purpose, however, it will be useful to have this more formal definition in
order to precisely keep track of the vertex sets upon execution of multiple
operations. Observe that, e.g. since $(u,v^{\prime}),(u,v)\in E$ is possible,
applying first $\operatorname{\textsc{cntr}}(v^{\prime},v)$ and then
$\operatorname{\textsc{expd}}(v)$ does not necessarily yield a network that is
isomorphic to the original network. Furthermore, we remark that the condition
that $(v^{\prime},v)$ is not a shortcut cannot be dropped since otherwise
directed cycles are introduced (cf. Fig. 2(A)).

Figure 2:  Complications arising in the contraction of arcs. The arcs to be
contracted are highlighted in blue. (A) Contraction of a shortcut $(u,w)$
introduced directed cycles. (B) Application of
$\operatorname{\textsc{cntr}}(u,w)$ to a shortcut-free network $N$ can result
in a network $N^{\prime}$ that contains a shortcut (r.h.s., shortcut indicated
by the red arc). (C),(D) Contraction of an arc $(u,w)$ in a phylogenetic
network $N$ can yield a network $N^{\prime}$ that is no longer phylogenetic.
Application of $\operatorname{\textsc{phylo}}(N^{\prime})$ can resolve this
issue.

We are now in the position to define least-resolved networks:

######  Definition 3.6.

A network $N$ is _least-resolved_ (w.r.t. its clustering system
$\mathscr{C}\coloneqq\mathscr{C}_{N}$) if there is no network $N^{\prime}$
with $\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$ that can be obtained from $N$
by a non-empty series of shortcut removal and application of
$\operatorname{\textsc{cntr}}(v^{\prime},v)$ for some arc $(v^{\prime},v)$
that is not a shortcut.

In many applications, phylogenetic networks are considered. However,
$\operatorname{\textsc{cntr}}(w^{\prime},w)$ applied on a phylogenetic network
may result in a non-phylogenetic network. By way of example, see Fig. 2(C), if
$u$ is a tree vertex with parent $u^{\prime}$ and two children $w$ and
$w^{\prime}$ which are leaves, then $\operatorname{\textsc{cntr}}(u,w)$ will
“locally” result in a path with arcs $(u^{\prime},w)$ and $(w,w^{\prime})$,
i.e., $\operatorname{indeg}(w)=\operatorname{outdeg}(w)=1$. Similarly,
$\operatorname{\textsc{cntr}}(u,w)$ in a block that contains a shortcut can
result in a network $N^{\prime}$ that is not phylogenetic, see Fig. 2(D). To
circumvent this issue, we must “suppress” $w$ to obtain a phylogenetic
network. To this end, we define the following operation to make a network $N$
phylogenetic:

$\operatorname{\textsc{phylo}}(N)$

Repeatedly apply $\operatorname{\textsc{cntr}}(u,w)$ for an arc $(u,w)$ such
that $\operatorname{outdeg}(u)=1$ and $\operatorname{indeg}(u)\leq 1$ until no
such operation is possible.

Now contraction of an arcs $(v^{\prime},v)$ that is not a shortcut and
“suppression” of superfluous vertices can be combined in:

$\operatorname{\textsc{cntr}}^{\star}(v^{\prime},v)$

Apply $\operatorname{\textsc{cntr}}(v^{\prime},v)$ to obtain $N^{\prime}$ and
then $\operatorname{\textsc{phylo}}(N^{\prime})$.

######  Definition 3.7.

Let $N$ and $N^{\prime}$ be networks such that $V(N^{\prime})\subseteq V(N)$.
Then, $N$ and $N^{\prime}$ are _$(N,N^{\prime},W)$ -ancestor-preserving_ if
for all $v,v^{\prime}\in W\subseteq V(N^{\prime})$, it holds that
$v\preceq_{N}v^{\prime}$ if and only if $v\preceq_{N^{\prime}}v^{\prime}$. If
$N$ and $N^{\prime}$ are $(N,N^{\prime},V(N^{\prime}))$-ancestor-preserving,
then we say for simplicity that $N$ and $N^{\prime}$ are
$(N,N^{\prime})$-ancestor-preserving.

######  Lemma 3.8.

Let $N$ be a network on $X$ and $(u,w)\in E(N)$ be a shortcut. Then removal of
$(u,w)$ in $N$ results in a network $N^{\prime}$ with leaf set $X$ and
$V(N)=V(N^{\prime})$. In particular,
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
for all $v\in V(N^{\prime})=V(N)$ and thus,
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. Moreover, $N$ and $N^{\prime}$ are
$(N,N^{\prime})$-ancestor-preserving.

###### Proof.

Let $N$ be a network on $X$ and $(u,w)$ be a shortcut in $N$. Since $(u,w)$ is
a shortcut, there is a $w^{\prime}\in\operatorname{child}(u)\setminus\\{w\\}$
such that $w\prec_{N}w^{\prime}$. Hence, there is a $w^{\prime}w$-path $P$ in
$N$. Since $N$ is acyclic and $w^{\prime}\prec_{N}u$, $u$ is not a vertex in
$P$ since otherwise $u\preceq_{N}w^{\prime}$. Therefore, $w$ has indegree
larger than $1$ in $N$. In particular, there is a $uw$-path $P^{\prime}$ in
$N^{\prime}$ formed by the arc $(u,w^{\prime})$ and $w^{\prime}w$-path $P$.
Since removal of $(u,w)$ only decreases the indegree of $w$ and
$\operatorname{indeg}_{N}(w)\geq 2$, $\rho_{N}=\rho_{N^{\prime}}$ is still the
only vertex with indegree $0$ in $N^{\prime}$. Moreover, removal of arcs
clearly preserves acyclicity, and thus $N^{\prime}$ is a rooted network.

Now let $v,v^{\prime}\in V(N)=V(N^{\prime})$. If $v\not\preceq_{N}v^{\prime}$,
then there is no $v^{\prime}v$-path in $N$. Clearly, removal of arcs changes
nothing about this and thus $v\not\preceq_{N^{\prime}}v^{\prime}$. Suppose now
that $v\preceq_{N}v^{\prime}$ and thus let $P_{v^{\prime}v}$ be a
$v^{\prime}v$-path in $N$. If $P_{v^{\prime}v}$ does not contain the arc
$(u,w)$, then $P_{v^{\prime}v}$ is still a $v^{\prime}v$-path in $N^{\prime}$.
Otherwise, the path obtained from $P_{v^{\prime}v}$ by replacing $(u,w)$ by
the $uw$-path $P^{\prime}$ is a $v^{\prime}v$-path in $N^{\prime}$. Hence,
$v\preceq_{N}v^{\prime}$ holds in both cases. In summary, we have
$v\preceq_{N}v^{\prime}$ if and only if $v\preceq_{N^{\prime}}v^{\prime}$.

By the latter arguments, $N^{\prime}$ is a network with leaf set $X$ and we
have $x\preceq_{N}v$ if and only if $x\preceq_{N^{\prime}}v$ for all $x\in X$
and all $v\in V(N)=V(N^{\prime})$. Therefore,
$x\in\operatorname{\mathtt{C}}_{N}(v)$ if and only if
$x\in\operatorname{\mathtt{C}}_{N^{\prime}}(v)$ for all $x\in X$ and all $v\in
V(N)=V(N^{\prime})$, and thus,
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$.
Together with $V(N)=V(N^{\prime})$, this implies
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. ∎

Note that deletion of a shortcut from a phylogenetic network does not
necessarily result in a phylogenetic network.

######  Lemma 3.9.

If a network $N$ is shortcut-free and has no vertex of outdegree $1$, then for
every vertex $w\in V(N)\setminus\\{\rho_{N}\\}$, there is a vertex
$v\in\operatorname{child}_{N}(\operatorname{par}_{N}(w))$ such that $v$ and
$w$ are $\preceq_{N}$-incomparable. In this case, $N$ is phylogenetic.

###### Proof.

Since $N$ is shortcut-free, siblings
$v^{\prime},v^{\prime\prime}\in\operatorname{child}_{N}(u)$, $v^{\prime}\neq
v^{\prime\prime}$ are $\preceq_{N}$-incomparable. Thus there is
$v\in\operatorname{child}_{N}(\operatorname{par}_{N}(w))$ that is
$\preceq_{N}$-incomparable with $w$ if and only if
$\operatorname{par}_{N}(w)\neq\emptyset$ and
$\operatorname{outdeg}(\operatorname{par}_{N}(w))>1$. Both conditions are
satisfied by assumption. ∎

######  Lemma 3.10.

Let $N$ be a network on $X$ and $(u,w)\in E(N)$ be an arc that is not a
shortcut. Then, $\operatorname{\textsc{cntr}}(u,w)$ applied on $N$ results in
a network $N^{\prime}$ with leaf set $X$ or $X\setminus\\{w\\}$ and
$V(N^{\prime})=V(N)\setminus\\{u\\}$. Moreover, for all $v,v^{\prime}\in
V(N^{\prime})$,

  1. 1.

$v\preceq_{N}v^{\prime}$ implies $v\preceq_{N^{\prime}}v^{\prime}$, and

  2. 2.

$v\preceq_{N^{\prime}}v^{\prime}$ implies (i) $v\preceq_{N}v^{\prime}$ or (ii)
$w\preceq_{N}v^{\prime}$ and $v\preceq_{N}w^{\prime}$ for some
$w^{\prime}\in\operatorname{child}_{N}(u)\setminus\\{w\\}$ that is
$\preceq_{N}$-incomparable with $w$.

In particular, $v\prec_{N^{\prime}}v^{\prime}$ always implies
$v\prec_{N}v^{\prime}$ or $v$ and $v^{\prime}$ are $\preceq_{N}$-incomparable.

###### Proof.

The proof is rather lengthy and technical and is, therefore, placed to Section
A.1 in the Appendix. ∎

######  Lemma 3.11.

Let $N$ be a network on $X$ and $(u,w)\in E(N)$ such that
$\operatorname{outdeg}_{N}(u)=1$. Then $\operatorname{\textsc{cntr}}(u,w)$
results in a network $N^{\prime}$ with leaf set $X$ and
$V(N^{\prime})=V(N)\setminus\\{u\\}$ that is $(N,N^{\prime})$-ancestor-
preserving. Moreover,
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
for all $v\in V(N^{\prime})=V(N)\setminus\\{u\\}$ and, in particular,
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$.

###### Proof.

Let $N$ be a network on $X$ and $(u,w)\in E(N)$ such that
$\operatorname{outdeg}_{N}(u)=1$. Since an arc $(u,w)\in E(N)$ with
$\operatorname{outdeg}_{N}(u)=1$ cannot be a shortcut and satisfies
$\operatorname{child}_{N}(u)\setminus\\{w\\}=\emptyset$, and thus condition
(ii) in Lemma 3.10 cannot occur, $N^{\prime}$ is a network with leaf set $X$
or $X\setminus\\{w\\}$ and $(N,N^{\prime})$-ancestor-preserving. Moreover,
since $w$ is the only out-neighbor of $u$, we do not add any out-neighbors for
$w$. Hence, $N^{\prime}$ has leaf set $X$.

By the latter argument, $N^{\prime}$ is a network with leaf set $X$ and we
have $x\preceq_{N}v$ if and only if $x\preceq_{N^{\prime}}v$ for all $x\in X$
and all $v\in V(N^{\prime})=V(N)\setminus\\{u\\}$. Therefore,
$x\in\operatorname{\mathtt{C}}_{N}(v)$ if and only if
$x\in\operatorname{\mathtt{C}}_{N^{\prime}}(v)$ holds for all $x\in X$ and all
$v\in V(N^{\prime})=V(N)\setminus\\{u\\}$. Hence, we have
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
for all $v\in V(N^{\prime})=V(N)\setminus\\{u\\}$. Moreover, since $w$ is the
unique out-neighbor of $u$, one can easily verify that
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(w)$ (cf. Obs.
3.36 for further arguments) and thus
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N^{\prime}}(w)\in\mathscr{C}_{N^{\prime}}$.
Taken together, we obtain $\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. ∎

As an immediate consequence of Lemma 3.8 and 3.11, we obtain

######  Corollary 3.12.

Every least-resolved network $N$ is shortcut-free and does not contain
vertices $v$ with $\operatorname{outdeg}_{N}(v)=1$.

######  Lemma 3.13.

Let $N$ be a network and $N^{\prime}$ be obtained from $N$ by applying
$\operatorname{\textsc{expd}}(w)$ for some $w\in V(N)$. Then $N^{\prime}$ is a
network such that $N$ and $N^{\prime}$ are $(N^{\prime},N)$-ancestor-
preserving. Moreover,
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
for all $v\in V(N)\subseteq V(N^{\prime})$ and, in particular, it holds
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. Moreover, if $N$ is phylogenetic,
then $N^{\prime}$ is phylogenetic if and only if $w$ is a hybrid vertex and
$\operatorname{outdeg}_{N}(w)\neq 1$.

###### Proof.

Let $N$ be a network on $X$. We show first that $N^{\prime}$ is a network. By
construction, $w$ is the only vertex in $N$ whose in-neighborhood changes and
it has the new vertex $u$ as its unique in-neighbor in $N^{\prime}$. If
$w\neq\rho_{N}$, then $w$ has at least one in-neighbor in $N$, which becomes
an in-neighbor of $u$. Hence, $\rho_{N}$ is still the only vertex with
indegree $0$ in $N^{\prime}$. If $w=\rho_{N}$, then it has no in-neighbors in
$N$ and thus $u$ has no in-neighbors in $N^{\prime}$. Together with the fact
that $w$ no longer has indegree $0$, $u$ is the only vertex with indegree $0$
in $N^{\prime}$ in this case. Now assume that $N^{\prime}$ contains a directed
cycle $K$ comprising the vertices $v_{1},v_{2},\dots,v_{k}$, $k\geq 2$, in
this order, i.e., $(v_{i},v_{i+1})$, $1\leq i\leq k-1$ and $(v_{k},v_{1})$ are
arcs in $N^{\prime}$. If all arcs in $K$ are in $N$, then $K$ is a directed
cycle in $N$; a contradiction. If $K$ contains an arc that is not in $N$, then
$K$ must contain the new vertex $u$ since all new arcs are incident with $u$.
Suppose w.l.o.g. that $u=v_{1}$. Since $u$ has a unique out-neighbor $w$ and
exactly the vertices in $\operatorname{par}_{N}(w)$ as in-neighbors, we must
have $v_{2}=w$ and $v_{k}\in\operatorname{par}_{N}(w)$, respectively. In
particular, this implies $v_{2}\neq v_{k}$ and $(v_{k},v_{2})\in E(N)$. Since
$u$ appears in $K$ at most once, $(v_{k},v_{1})$ and $(v_{1},v_{2})$ are the
only arcs in $K$ that are incident with $u$, and thus all other arcs of $K$
are also arcs in $N$. In particular, there is a $v_{2}v_{k}$-path in $N$.
Together with the fact that $(v_{k},v_{2})\in E(N)$, this implies that $N$
contains a directed cycle; a contradiction. Therefore, $N^{\prime}$ must be
acyclic. Since moreover $N^{\prime}$ has a unique root, it is a network.

The operation $\operatorname{\textsc{expd}}(w)$ on a network $N$ creates a
network $N^{\prime}$ with an additional vertex $u$ such that $w$ is the unique
out-neighbor of $u$ and
$\operatorname{par}_{N^{\prime}}(u)=\operatorname{par}_{N}(w)$. Therefore, $N$
is recovered from $N^{\prime}$ by applying
$\operatorname{\textsc{cntr}}(u,w)$. This observation together with Lemma.
3.11 implies that $N$ and $N^{\prime}$ are $(N^{\prime},N)$-ancestor-
preserving.

Suppose now that $N$ is phylogenetic. Assume first that $w$ is a hybrid vertex
and $\operatorname{outdeg}_{N}(w)\neq 1$. Then, by construction, the newly
created vertex $w$ satisfies
$\operatorname{indeg}_{N^{\prime}}(w^{\prime})=\operatorname{indeg}_{N}(w)\geq
2$ and moreover, we have
$\operatorname{outdeg}_{N^{\prime}}(w)=\operatorname{outdeg}_{N}(w)\neq 2$.
The only other vertices whose neighborhoods are affected are the vertices
$u\in\operatorname{par}_{N}(w)$. More precisely, their outneighbor $w$ is
replaced by an outneighbor $w^{\prime}$ and thus
$\operatorname{indeg}_{N^{\prime}}(u)=\operatorname{indeg}_{N}(u)$ for any
$u\in\operatorname{par}_{N}(w)$. Together with the fact that $N$ is
phylogenetic, the latter arguments imply that there is no vertex $v\in
V(N^{\prime})$ with $\operatorname{outdeg}_{N^{\prime}}(v)=1$ and
$\operatorname{indeg}_{N^{\prime}}(v)\leq 1$. Hence, $N^{\prime}$ is
phylogenetic. Now assume that $w$ is a not hybrid vertex or
$\operatorname{outdeg}_{N}(w)=1$. If $w$ is not a hybrid vertex, then
$\operatorname{indeg}_{N^{\prime}}(w^{\prime})=\operatorname{indeg}_{N}(w)\leq
1$. Moreover, $\operatorname{outdeg}_{N^{\prime}}(w^{\prime})=1$ holds by
construction, and thus $N^{\prime}$ is not phylogenetic. If
$\operatorname{outdeg}_{N}(w)=1$, then
$\operatorname{outdeg}_{N^{\prime}}(w)=1$ since the outneighborhood of $w$
does not change. In addition, $w^{\prime}$ is the unique in-neighbor of $w$ in
$N^{\prime}$ by construction. Hence, $N^{\prime}$ is not phylogenetic. In
summary, it holds that $N^{\prime}$ is phylogenetic if and only if $w$ is a
hybrid vertex and $\operatorname{outdeg}_{N}(w)\neq 1$.

By the latter arguments, $N^{\prime}$ is a network with leaf set $X$. The
newly created vertex $w^{\prime}$ has a unique child $w$. The statement
“$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
for all $v\in V(N)\subseteq V(N^{\prime})$ and, in particular,
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$” therefore follows immediately from
Lemma 3.11 and the fact that $N$ is recovered from $N^{\prime}$ by applying
$\operatorname{\textsc{cntr}}(w^{\prime},w)$. ∎

The following result shows that the expansion operation does not introduce
shortcuts and is an immediate consequence of Lemma A.1 in Section A.1.

######  Corollary 3.14.

Let $N$ be a network and $N^{\prime}$ be the network obtained from $N$ by
applying $\operatorname{\textsc{expd}}(w)$ for some $w\in V(N)$. Then $N$ is
shortcut-free if and only if $N^{\prime}$ is shortcut-free.

We remark that an analogue of Cor. 3.14 does not hold for the contraction
operation $\operatorname{\textsc{cntr}}(u,w)$. Fig. 2(B) shows an example
where contraction introduces a shortcut.

###  3.3 Blocks

The blocks of $N$ will play a key role in the following. We first establish
several technical results that will allow us efficiently reason about the
block structure of a network.

######  Lemma 3.15.

Let $N$ be a network and $u,v\in V(N)$ be two $\preceq_{N}$-incomparable
vertices. Then $u$ and $v$ are connected by an undirected path $P$ that
contains at least 3 vertices and of which all inner vertices $w$ satisfy
$u\prec_{N}w$ or $v\prec_{N}w$. In addition, we have $w\not\preceq_{N}u$ and
$w\not\preceq_{N}v$ for every such inner vertex $w$.

###### Proof.

There are directed paths $P_{u}$ and $P_{v}$ from $\rho_{N}$ to both $u$ and
$v$, respectively. Let $w^{*}$ be the $\preceq_{N}$-minimal vertex of $P_{u}$
that is also a vertex of $P_{v}$, which exists since at least $\rho_{N}$ is
contained in both paths. It must hold that $w^{*}\notin\\{u,v\\}$ since
otherwise $u$ and $v$ would be $\preceq_{N}$-comparable. In particular,
$u\prec_{N}w^{*}$ and $v\prec_{N}w^{*}$. Let $P^{\prime}_{u}$ and
$P^{\prime}_{v}$ be the subpaths of $P_{u}$ and $P_{v}$ from $w^{*}$ to $u$
and $v$, respectively. By construction, $P^{\prime}_{u}$ and $P^{\prime}_{v}$
only have vertex $w^{*}$ in common, which moreover is an outer vertex of both
paths. Now consider the path $P$ that is the union of the underlying
undirected version of $P^{\prime}_{u}$ and $P^{\prime}_{v}$. By construction,
$P$ contains at least the three vertices $u$, $v$, and $w^{*}$ and all of its
inner vertices $w$ satisfy $u\prec_{N}w$ or $v\prec_{N}w$. Assume, for
contradiction, that $w\preceq_{N}u$ for some of these inner vertices. Since
$u\prec_{N}w$ is not possible, we must have $v\prec_{N}w$. But then
$v\prec_{N}w$ and $w\preceq_{N}u$ imply that $v$ and $u$ are
$\preceq_{N}$-comparable; a contradiction. Hence, $w\not\preceq_{N}u$ must
hold. One shows analogously that $w\not\preceq_{N}v$. ∎

Paths of the form described in Lemma 3.15 connecting two leaves $u$ and $v$
are called “up-down-paths” in [13].

######  Lemma 3.16.

Let $B$ be a block in a network $N$ and $u,v\in V(B)$ such that
$v\preceq_{N}u$. Then every $uv$-path in $N$ is completely contained in $B$.

###### Proof.

Let $P$ be a $uv$-path in $N$, which exists since $v\preceq_{N}u$. The
statement holds trivially if $B$ is an isolated vertex, $v=u$, or $B$ is the
arc $(u,v)$. Thus suppose $B$ is a non-trivial block. Suppose, for
contradiction, there is a vertex $w\in V(P)\setminus\\{V(B)\\}$. Let $w_{a}$
and $w_{d}$ be the $\preceq_{N}$-minimal ancestor and the
$\preceq_{N}$-maximal descendant, resp., of $w$ in $P$ (both of which exist
since $u,v\in V(P)$). Consider the subpath $P^{\prime}$ of $P$ from $w_{a}$ to
$w_{d}$. By Prop. 2.5, the subgraph of $N$ obtained by adding $P^{\prime}$ to
$B$ is again biconnected. Together with $w\in
V(P^{\prime})\setminus\\{V(B)\\}$, this contradict that $B$ is a block. Hence
such a vertex cannot exist. Therefore and since blocks are always induced
subgraphs, the statement follows. ∎

######  Lemma 3.17.

Every block $B$ in a network $N$ has a unique $\preceq_{N}$-maximal vertex
$\max B$. In particular, for every $v\in V(B)$, there is a directed path from
$\max B$ to $v$ and every such path is completely contained in $B$.

###### Proof.

The statement is trivial for a block that consists only of a single vertex or
arc. Otherwise, suppose there are two distinct $\preceq_{N}$-maximal vertices
$v_{1}$ and $v_{2}$ in $B$. By assumption, $v_{1}$ and $v_{2}$ must be
$\preceq_{N}$-incomparable. By Lemma 3.15, $v_{1}$ and $v_{2}$ are connected
by an undirected path $P$ that contains at least 3 vertices and of which all
inner vertices $w$ satisfy $u\prec_{N}w$ or $v\prec_{N}w$. By
$\preceq_{N}$-maximality of $v_{1}$ and $v_{2}$, none of these inner vertices
can be contained in $B$. By Prop. 2.5, adding $P$ to $B$ preserves
biconnectivity, and thus $B$ is not a maximal biconnected subgraph; a
contradiction. In particular, for every $v\in V(B)$, we have $v\preceq_{N}\max
B$, i.e., there is a path from $\max B$ to $v$ and by Lemma 3.16, each every
such path is completely contained in $B$. ∎

######  Corollary 3.18.

If $B$ is a non-trivial block in network $N$, then $\max B$ has at least two
out-neighbors in $B$.

###### Proof.

Since $B$ is non-trivial, $\max B$ lies on an undirected cycle in $B$ and thus
is incident with two distinct vertices in $B$. By $\preceq_{N}$-maximality of
$\max B$ in $B$, these must be out-neighbors of $\max B$. ∎

######  Lemma 3.19.

Let $N$ be a network and suppose that $v\in V(N)$ is contained in the blocks
$B$ and $B^{\prime}$ of $N$. If $v\notin\\{\max B,\max B^{\prime}\\}$, then
$B=B^{\prime}$.

###### Proof.

Assume that vertex $v$ is contained in the blocks $B$ and $B^{\prime}$ of $N$
but $v\notin\\{\max B,\max B^{\prime}\\}$. By Lemma 3.17, there exists a
directed path $P$ in $B$ from $\max B$ to $v$. Similarly, there is a directed
path $P^{\prime}$ in $B^{\prime}$ from $\max B^{\prime}$ to $v$. Since
$v\notin\\{\max B,\max B^{\prime}\\}$, both $P$ and $P^{\prime}$ contain at
least one arc.

Assume first that $P$ and $P^{\prime}$ share an arc $e$ and thus, that $B$ and
$B^{\prime}$ share the arc $e$. In this case, contraposition of Obs. 2.2
implies that $B=B^{\prime}$. Hence, in the following we assume that $P$ and
$P^{\prime}$ are arc-disjoint.

Consider first the case $\max B^{\prime}\preceq_{N}\max B$. Let $u$ be the
unique $\preceq_{N}$-minimal vertex in $P$ such that $\max
B^{\prime}\preceq_{N}u$. Together with $v\prec_{N}\max B^{\prime}$, this
implies that $u\neq v$. Let $P_{u,v}$ be the subpath of $P$ from $u$ to $v$
and note that $P_{u,v}$ contains at least one arc. Since $\max
B^{\prime}\preceq_{N}u$, we can find a directed path $P_{u,\max B^{\prime}}$
(possible only containing a single vertex $u=\max B^{\prime}$) from $u$ to
$\max B^{\prime}$. The paths $P_{u,v}$ and $P_{u,\max B^{\prime}}$ only have
vertex $u$ in common since $u$ is the unique $\preceq_{N}$-minimal vertex in
$P$ with $\max B^{\prime}\preceq_{N}u$. Since $N$ is acyclic, $P_{u,\max
B^{\prime}}$ and $P^{\prime}$ are arc-disjoint. In summary, $P^{\prime}$,
$P_{u,v}$, and $P_{u,\max B^{\prime}}$ are pairwise arc-disjoint. Hence, $\max
B^{\prime}$ and $v$ are connected by two arc-disjoint undirected paths that
correspond to $P^{\prime}$ and the union of $P_{u,v}$ and $P_{u,\max
B^{\prime}}$. Therefore, $\max B^{\prime}$ and $v$ are contained in a common
block $B^{\prime\prime}$. In particular, $B$ and $B^{\prime\prime}$ share all
arcs in $P_{u,v}$, and thus at least one arc. Similarly, $B^{\prime}$ and
$B^{\prime\prime}$ share all arcs in $P^{\prime}$, and thus at least one arc.
By Obs. 2.2, it follows that $B=B^{\prime\prime}=B^{\prime}$. Similarly, $\max
B\preceq_{N}\max B^{\prime}$ implies $B=B^{\prime}$.

Suppose now that $\max B$ and $\max B^{\prime}$ are
$\preceq_{N}$-incomparable. Recall that $P$ and $P^{\prime}$ are arc-disjoint
and each contain at least one arc. Let $\breve{P}$ be the undirected path
corresponding to the union of $P$ and $P^{\prime}$ and observe that all of its
inner vertices $w$ that satisfy $w\preceq_{N}\max B$ or $w\preceq_{N}\max
B^{\prime}$. Since $\max B$ and $\max B^{\prime}$ are
$\preceq_{N}$-incomparable, Lemma 3.15 implies that they are connected by an
undirected path $\invbreve{P}$ that contains at least 3 vertices and of which
all inner vertices $w^{\prime}$ satisfy $w^{\prime}\not\preceq_{N}\max B$ and
$w^{\prime}\not\preceq_{N}\max B^{\prime}$. As a consequence, $\breve{P}$ and
$\invbreve{P}$ only have their endpoints $\max B$ and $\max B^{\prime}$ in
common. Hence, $\max B$ and $\max B^{\prime}$ are contained in a common block
$B^{\prime\prime}$. In particular, $B$ and $B^{\prime\prime}$ share all arcs
in $P$, and thus at least one arc. Similarly, $B^{\prime}$ and
$B^{\prime\prime}$ share all arcs in $P^{\prime}$, and thus at least one arc.
By Obs. 2.2, it follows that $B=B^{\prime\prime}=B^{\prime}$. ∎

By definition, $N$ is tree if and only if it contains no undirected cycle,
i.e., if all blocks are trivial. Thus $N$ is a tree if and only if there are
no hybrid vertices.

######  Definition 3.20.

Let $N$ be a network and $B$ a non-trivial block in $N$ with terminal vertices
$\\{m_{1},m_{2},\dots,m_{h}\\}$, $h\geq 1$. Then

$B^{0}\coloneqq B\setminus\\{\max B,m_{1},m_{2},\dots m_{h}\\}$ (1)

is the _interior_ of $B$.

As an immediate consequence of Lemma 3.19, we have

######  Observation 3.21.

Let $B_{1}$ and $B_{2}$ be two distinct blocks in $N$. Then $B_{1}^{0}\cap
B_{2}^{0}=\emptyset$.

######  Lemma 3.22.

Let $N$ be a network and $w\in V(N)$ be a hybrid vertex. Then $w$ and all of
its in-neighbors are contained in a non-trivial block $B$.

###### Proof.

Let $w$ be a hybrid vertex, i.e., $\operatorname{indeg}_{N}(w)\geq 2$, and let
$v$ and $v^{\prime}$ be two distinct in-neighbors of $w$. If
$v^{\prime}\prec_{N}v$, then there is a directed path $P$ from $v$ to
$v^{\prime}$ that contains at least one arc. Moreover, $w$ is not a vertex of
$P$ since otherwise $v^{\prime}\preceq_{N}w$ would contradict
$w\prec_{N}v^{\prime}$. Therefore, $P$ together with $w$ and arcs $vw$ and
$v^{\prime}w$ form an undirected cycle. An analogous argument applies if
$v\prec_{N}v^{\prime}$. If $v$ and $v^{\prime}$ are
$\preceq_{N}$-incomparable, then Lemma 3.15 implies that they are connected by
an undirected path $P$ that contains at least 3 vertices and of which all
inner vertices $w^{\prime}$ satisfy $w^{\prime}\not\preceq_{N}v$ and
$w^{\prime}\not\preceq_{N}v^{\prime}$. Together with $w\prec_{N}v,v^{\prime}$,
this implies that $w$ is not contained in $P$. Therefore, $P$ together with
$w$ and arcs $vw$ and $v^{\prime}w$ form an undirected cycle. In summary, in
all cases, $w$ is contained in a non-trivial block $B_{v^{\prime}}$ that, in
particular, also contains $v$, $v^{\prime}$, and the arc $vw$. Since
$v^{\prime}$ was chosen arbitrarily among the in-neighbors of $w$ that are
distinct from $v$ and the blocks $B_{v^{\prime}}$ for all of these vertices
share the arc $vw$, Obs. 2.1 implies that $w$ and all of its in-neighbors are
contained in a non-trivial block $B$. ∎

Following [37], we say that a hybrid vertex $w$ is _properly contained_ in a
block $B$ if all of its in-neighbors are contained in $B$. As an immediate
consequence of Lemma 3.22, every hybrid vertex is properly contained in
exactly one block.

######  Lemma 3.23.

Let $N$ be a network, $w$ a hybrid vertex in $N$, and $B$ be a block of $N$.
Then the following statements are equivalent:

  1. 1.

$w$ is properly contained in $B$, i.e., $w$ and all of its parents are
contained in $B$.

  2. 2.

$w$ and one of its parents $u$ are contained in $B$.

  3. 3.

$w\in V(B)\setminus\\{\max B\\}$.

###### Proof.

(3) $\implies$ (2). Since $\max B$ is the unique $\preceq_{N}$-maximal vertex
in $B$, we have $w\prec_{N}\max B$. By Lemma 3.17, there is a directed path
from $\max B$ to $w$ that is completely contained in $B$. Clearly, $P$
contains a parent of $w$, which is there also contained in $B$. (2) $\implies$
(1). By Lemma 3.22, $w$ and all of its parents are contained in a non-trivial
block $B^{\prime}$. Hence, $B$ and $B^{\prime}$ share the distinct vertices
$w$ and $u$. By Obs. 2.1, $B=B^{\prime}$. (1) $\implies$ (3). If $w$ and all
of its (at least two) parents are contained in $B$, then clearly $w\in
V(B)\setminus\\{\max B\\}$. ∎

As a consequence, if a hybrid vertex $w$ is contained in a block $B$ but not
properly contained, then it must hold $w=\max B$. This motivates the following
definition of level-$k$ networks:

######  Definition 3.24.

A network $N$ is _level- $k$_ if each block $B$ of $N$ contains at most $k$
hybrid vertices distinct from $\max B$.

Equivalently, by Lemma 3.22, $N$ is level-$k$ if each block $B$ of $N$
properly contains at most $k$ hybrid vertices. In [19], level-$k$ networks are
simply defined by having no more than $k$ hybrid vertices within any given
block. We note that this is equivalent to our definition in a setting where
hybrid vertices are restricted to having outdegree $1$. Def. 3.24 also
accommodates the contraction of out-arcs of hybrid vertices $v$ with
$\operatorname{outdeg}(v)=1$, see Fig. 3.

Figure 3: The network $N$ contains a hybrid vertex $v$ with
$\operatorname{outdeg}(v)=1$. Network $N^{\prime}$ is obtained from $N$ by
contraction of the arc $(v,w)$, i.e., the operation
$\operatorname{\textsc{cntr}}(v,w)$ which preserves vertex $w$. Vertex $w$ is
now a hybrid vertex that is contained in two blocks of $N^{\prime}$. However,
only the upper block properly contains it.

The following two lemmas show that neither arc contraction nor expansion
increases the level of a network. Since their proofs are rather lengthy and
technical, they are given in Section A.1 in the Appendix.

######  Lemma 3.25.

Let $N$ be a network, $(w^{\prime},w)\in E(N)$ be an arc that is not a
shortcut, and $N^{\prime}$ be the network obtained from $N$ by applying
$\operatorname{\textsc{cntr}}(w^{\prime},w)$. If $N$ is level-$k$, then
$N^{\prime}$ is also level-$k$.

###### Proof.

See Section A.1 in the Appendix. ∎

Figure 4: The level-$3$ network $N^{\prime}$ is obtained from the level-$6$
network by application of $\operatorname{\textsc{cntr}}(w^{\prime},w)$. The
hybrid vertices are highlighted in orange.

The converse of Lemma 3.25, however, is not true as shown by the example in
Fig. 4. This example also shows that even mitigated versions “ _if
$N^{\prime}$ is level-$k$, then $N$ is level-$(k+1)$_” do not hold. As an
immediate consequence of the definition of $\operatorname{\textsc{phylo}}(N)$,
Lemma 3.11 and 3.25, we obtain

######  Corollary 3.26.

Let $N$ be a level-$k$ network. Then the network $N^{\prime}$ obtained by
operation $\operatorname{\textsc{phylo}}(N)$ is a phylogenetic level-$k$
network such that $\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$.

######  Lemma 3.27.

Let $N$ be a network and $N^{\prime}$ be the network obtained from $N$ by
applying $\operatorname{\textsc{expd}}(w)$ for some $w\in V(N)$. Then $N$ is
level-$k$ if and only if $N^{\prime}$ is level-$k$.

###### Proof.

See Section A.1 in the Appendix. ∎

The definition of $\operatorname{\textsc{phylo}}(N)$ and
$\operatorname{\textsc{cntr}}^{\star}(v^{\prime},v)$ and Lemma 3.25 yield

######  Corollary 3.28.

Let $N$ be a level-$k$ network. If $N^{\prime}$ is the the network obtained
from $N$ by applying $\operatorname{\textsc{phylo}}(N)$ or
$\operatorname{\textsc{cntr}}^{\star}(v^{\prime},v)$ for some arc
$(v^{\prime},v)\in E(N)$ that is not a shortcut, then $N^{\prime}$ is
phylogenetic and level-$k$.

###  3.4 Clusters, Hasse Diagrams, and Regular Networks

In this section we consider general properties of the set of clusters
$\mathscr{C}_{N}$ of a phylogenetic network as specified in Def. 3.4 above.

######  Lemma 3.29.

For all networks $N$ on $X$, the set $\mathscr{C}_{N}$ is a clustering system.

###### Proof.

Every non-leaf vertex $v\in V\setminus X$ has at least one out-neighbor and
$N$ is acyclic and finite. Thus every directed path in $N$ can be extended to
a directed path that eventually ends in a leaf, implying
$\operatorname{\mathtt{C}}(v)\neq\emptyset$. Since
$\operatorname{\mathtt{C}}(v)\neq\emptyset$ for all $v\in V$ and since $N$
contains at least a root $\rho_{N}$ as a vertex, we have
$\emptyset\notin\mathscr{C}_{N}$ and thus Condition (i) holds. Since
$v\preceq_{N}\rho_{N}$ for all $v\in V$, we have
$\operatorname{\mathtt{C}}(\rho_{N})=X$ and (ii) is satisfied. To see that
Condition (iii) holds, observe that for all $x\in X$, we have
$\operatorname{outdeg}(x)=0$ and thus $\operatorname{\mathtt{C}}(x)=\\{x\\}$.
∎

This simple observation connects phylogenetic networks to a host of literature
on clustering systems, which have been studied with motivations often
unrelated to evolution or phylogenetics [41, 7, 38].

A particular difficulty in the characterization of certain types of networks
by means of their clustering systems is that even rather simple clustering
systems such as hierarchies can be explained by very complex networks.

######  Lemma 3.30.

Let $n$ be a positive integer. Then, for all $k\in\\{0,2,\dots,n\\}$, there is
a phylogenetic, shortcut-free level-$k$ network $N$ on $n$ leaves that is not
level-$(k-1)$ such that $\mathscr{C}_{N}$ is a hierarchy.

###### Proof.

If $n=1$, then $k=0$ and the single vertex graphs serves as an example (since
a network contains at least one vertex and thus a level-$(-1)$ cannot exist by
definition). Let $n\geq 2$. For $k=0$, simply take a tree whose root is
adjacent to the $n$ leaves only. Again, this tree is level-$0$ but not
level-$(-1)$. We refer to this tree as a star tree. For $k\geq 2$, take a star
tree $T$ and randomly collect $k$ of its leaves $l_{1},\dots l_{k}$. Now add
new leaves $x_{1},\dots,x_{k}$ and edges such that the induced subgraph
$N[\\{l_{1},\dots l_{k},x_{1},\dots,x_{k}\\}$ is graph isomorphic to a
complete bipartite graphs where one part of the bipartition contains all
$l_{1},\dots,l_{k}$ and the other part all $x_{1},\dots,x_{k}$ (see Fig. 5 for
a generic example). It is easy to verify that $N$ is shortcut-free,
phylogenetic, level-$k$ but not level-$(k-1)$. In all cases, $\mathscr{C}_{N}$
just consist of the clusters $\\{x_{1},\dots,x_{k}\\}$, $X$, and the
singletons $\\{x\\}$, $x\in X$ and is, therefore, a hierarchy. ∎

Figure 5: A generic framework that shows that, for every $n\geq 2$ and
$k\in\\{0,2,\dots,n\\}$, there is a phylogenetic, shortcut-free level-$k$
network $N$ on $n$ leaves that is not level-$(k-1)$ and where
$\mathscr{C}_{N}$ is a hierarchy. The network shown left is level-0 and its
clustering system is trivially a hierarchy. The clustering system
$\mathscr{C}_{N}$ of the level-$k$ network $N$ shown right consists of the
clusters $X^{\prime}\coloneqq\\{x_{1},\dots,x_{k}\\}$ (for which the
corresponding vertices are highlighted in orange),
$X=X^{\prime}\cup\\{l_{k+1},\dots,l_{n}\\}$, and the singletons and,
therefore, $\mathscr{C}_{N}$ is a hierarchy.

As we shall in Lemma 7.3 there is no phylogenetic shortcut-free level-1
network $N$ (that is not a tree) for which $\mathscr{C}_{N}$ is a hierarchy.

For a clustering system $\mathscr{C}$ on $X$ and a subset $A\subseteq 2^{X}$,
we define the _closure operator_ as the map $\operatorname{cl}\colon 2^{X}\to
2^{X}$ defined by

$\operatorname{cl}(A)\coloneqq\bigcap_{\begin{subarray}{c}C\in\mathscr{C}\\\
A\subseteq C\end{subarray}}C.$ (2)

It is well defined, isotonic [$A\subseteq
B\implies\operatorname{cl}(A)\subseteq\operatorname{cl}(B)$], enlarging
[$A\subseteq\operatorname{cl}(A)$], and idempotent
$\operatorname{cl}(\operatorname{cl}(A))=\operatorname{cl}(A)$. For $|X|>1$,
we have $\operatorname{cl}(\emptyset)=\emptyset$.

######  Definition 3.31.

A clustering system $\mathscr{C}$ is _closed_ if, for all _non-empty_ $A\in
2^{X}$, the following condition holds: $\operatorname{cl}(A)=A\iff
A\in\mathscr{C}$.

The following result is well know in the clustering literature.

######  Lemma 3.32.

A clustering system $\mathscr{C}$ is closed if and only if $A,B\in\mathscr{C}$
and $A\cap B\neq\emptyset$ implies $A\cap B\in\mathscr{C}$.

###### Proof.

For completeness, a proof is provided in Section A.2 in the Appendix. ∎

We continue with three simple observations concerning the clusters of
networks.

######  Lemma 3.33.

Let $N$ be a network. Then $v\preceq_{N}w$ implies
$\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(w)$.

###### Proof.

By construction, $x\in\operatorname{\mathtt{C}}(v)$ if and only if $x\in X$
and $v$ lies on a directed path from the root $\rho_{N}$ to $x$. Furthermore,
$v\preceq_{N}w$ implies that $w$ lies on a directed path from $\rho_{N}$ to
$v$. By (N1) and since $N$ is a DAG, there is directed path from $\rho_{N}$ to
$x$ that contains $w$, and thus $x\preceq_{N}w$, i.e.,
$x\in\operatorname{\mathtt{C}}(w)$. ∎

We note in passing that the converse of Lemma 3.33 is not always satisfied
(even in level-$1$ networks): If $v$ is a hybrid vertex with unique child $w$,
we have $\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)$ and thus
$\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(w)$, but
$v\not\preceq_{N}w$, (cf. the network $N$ in Fig. 3). A result similar to
Lemma 3.15 ensures the existence of a path $P$ connecting
$\preceq_{N}$-incomparable vertices $u,v\in V(N)$ that contains only vertices
that are below $u$ or $v$. However, it requires that $u$ and $v$ have at least
one descendant leaf in common, i.e., that
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)\neq\emptyset$:

######  Lemma 3.34.

Let $N$ be a network and $u,v\in V(N)$ be two $\preceq_{N}$-incomparable
vertices such that
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)\neq\emptyset$.
Then, for every
$x\in\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)$, $u$ and
$v$ are connected by an undirected path $P=(w_{1}\coloneqq
u,\dots,w_{h},\dots,w_{k}\coloneqq v)$, $1<h<k$, such that

(i)

$(w_{i},w_{i+1})\in E(N)$ for all $1\leq i<h$, $(w_{i+1},w_{i})\in E(N)$ for
all $h\leq i<k$, and $w_{h}$ is a hybrid vertex satisfying $w_{h}\prec_{N}u$
and $w_{h}\prec_{N}v$.

(ii)

$x\in\operatorname{\mathtt{C}}(w_{h})$,

In particular, $k\geq 3$, all inner vertices $w_{i}$ of $P$ satisfy
$w_{i}\prec_{N}u$ or $w_{i}\prec_{N}v$, and $P$ is a subgraph of a non-trivial
block $B$.

###### Proof.

There are directed paths $P_{u}$ and $P_{v}$ from $u$ and $v$, respectively,
to the leaf $x$. Let $w^{*}$ be the $\preceq_{N}$-maximal vertex of $P_{u}$
that is also a vertex of $P_{v}$, which exists since at least $x$ is contained
in both paths. It must hold that $w^{*}\notin\\{u,v\\}$ since otherwise $u$
and $v$ would be $\preceq_{N}$-comparable. In particular, $w^{*}\prec_{N}u$
and $w^{*}\prec_{N}v$. Let $P^{\prime}_{u}$ and $P^{\prime}_{v}$ be the
subpaths of $P_{u}$ and $P_{v}$ from $u$ and $v$, respectively, to $w^{*}$. By
construction, $w^{*}$ must be a hybrid vertex,
$x\in\operatorname{\mathtt{C}}(w^{*})$, and $P^{\prime}_{u}$ and
$P^{\prime}_{v}$ only have vertex $w^{*}$ in common, which moreover is an
outer vertex of both paths. Now consider the path $P=(w_{1}\coloneqq
u,\dots,w_{h}\coloneqq w^{*},\dots,w_{k}\coloneqq v)$, that is the union of
the underlying undirected version of $P^{\prime}_{u}$ and $P^{\prime}_{v}$. It
is now easy to verify that $P$ satisfies all of the desired properties. Two
see that $P$ is a subgraph of a non-trivial block $B$, observe that, by Lemma
3.15, the two $\preceq_{N}$-incomparable vertices $u$ and $v$ are connected by
an undirected path $\invbreve{P}$ that contains at least 3 vertices and of
which all inner vertices $w^{\prime}$ satisfy $w^{\prime}\not\preceq_{N}u$ and
$w^{\prime}\not\preceq_{N}v$. Hence, $P$ and $\invbreve{P}$ cannot have any
inner vertices in common. Therefore, $u$ and $v$ are connected by two distinct
paths that both have at least 3 vertices and that only have the endpoints $u$
and $v$ in common. Hence, $u$ and $v$ lie on a cycle $K$ and thus in a common
block $B$ of $N$. In particular, $P$ is a subgraph of $K$ and thus of $B$. ∎

######  Lemma 3.35.

Let $N$ be a network and $u,v\in V(N)$. If $\operatorname{\mathtt{C}}_{N}(u)$
and $\operatorname{\mathtt{C}}_{N}(v)$ overlap, then $u$ and $v$ are
$\preceq_{N}$-incomparable and $u,v\in B^{0}$ for a non-trivial block $B$ of
$N$.

###### Proof.

If two clusters $\operatorname{\mathtt{C}}_{N}(u)$ and
$\operatorname{\mathtt{C}}_{N}(v)$ overlap, then Lemma 3.33 implies that $u$
and $v$ are $\preceq_{N}$-incomparable. Lemma 3.34 implies that $u$ and $v$
are contained in a common non-trivial block $B$ of $N$. Since
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(\max B)$ for
all $u\in B$, $\operatorname{\mathtt{C}}(\max B)$ does not overlap any cluster
$\operatorname{\mathtt{C}}(v)$ with $v\in B$, and thus $u,v\neq\max B$. Now
suppose $u$ is a terminal vertex of $B$ and $v\in B$ such that
$\operatorname{\mathtt{C}}(u)$ and $\operatorname{\mathtt{C}}(v)$ overlap. By
Lemma 3.34 there is $w\in B$ in
$x\in\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)$ with
$w\prec_{N}u$, contradicting that $u$ is terminal. Therefore $u,v\in B^{0}$. ∎

Clusters of outdegree-1 vertices $w$ are redundant in the sense that every
directed path from $w$ to one of its descendant leaves necessarily passes
through the unique child $v$ of $w$. Thus we have
$\operatorname{\mathtt{C}}(w)\subseteq\operatorname{\mathtt{C}}(v)$. Moreover,
$v\prec_{N}w$ and Lemma 3.33 imply
$\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(w)$, and thus,
$\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)$. Hence, we have

######  Observation 3.36.

Let $N$ be a network. If $v$ is the unique child of $w$ in $N$, then
$\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)$.

######  Lemma 3.37.

Let $N$ be a network, $B$ a block in $N$ and $u,v\in V(B)$. Moreover, let $H$
be the set of hybrid vertices $h$ that are properly contained in $B$ and
satisfy $h\preceq_{N}u,v$. Then it holds
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)\in\\{\operatorname{\mathtt{C}}(u),\operatorname{\mathtt{C}}(v),\bigcup_{h\in
H}\operatorname{\mathtt{C}}(h)\\}$.

###### Proof.

It suffices to show that
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)\notin\\{\operatorname{\mathtt{C}}(u),\operatorname{\mathtt{C}}(v)\\}$
implies
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)=\bigcup_{h\in
H}\operatorname{\mathtt{C}}(h)\eqqcolon C$. Hence, suppose
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)\notin\\{\operatorname{\mathtt{C}}(u),\operatorname{\mathtt{C}}(v)\\}$.
Then Lemma 3.33 implies that $u$ and $v$ are $\preceq_{N}$-incomparable. If
$x\in C$, then $x\in\operatorname{\mathtt{C}}(h)$ for some $h\in H$. Since
$h\preceq_{N}u,v$, Lemma 3.33 implies
$\operatorname{\mathtt{C}}(h)\subseteq\operatorname{\mathtt{C}}(u)$ and
$\operatorname{\mathtt{C}}(h)\subseteq\operatorname{\mathtt{C}}(v)$ and thus,
$x\in\operatorname{\mathtt{C}}(h)\subseteq\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)$.
Now suppose
$x\in\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)$. By Lemma
3.34, the $\preceq_{N}$-incomparable vertices $u$ and $v$ are connected by an
undirected path $P$ which contains a hybrid vertex $h\prec_{N}u,v$ with
$x\in\operatorname{\mathtt{C}}(h)$ and is a subgraph of a non-trivial block
$B^{\prime}$ of $N$. Since $B$ and $B^{\prime}$ share the two distinct
vertices $u$ and $v$, Obs. 2.1 implies $B=B^{\prime}$. In particular,
$u,v,h\in V(B)$ and $h\prec_{N}u,v$ imply $h\neq\max B$, and thus, $h$ must be
properly contained in $B$ by Lemma 3.22. Hence, we have $h\in H$ and thus
$x\in\operatorname{\mathtt{C}}(h)\subseteq C$. In summary, we have
$x\in\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)$ if and only
if $x\in C$, and thus
$\operatorname{\mathtt{C}}(u)\cap\operatorname{\mathtt{C}}(v)=C$. ∎

Note that $H=\emptyset$ and thus, $C=\bigcup_{h\in
H}\operatorname{\mathtt{C}}(h)=\emptyset$ in Lemma 3.37 is possible.

The _Hasse diagram_ $\mathfrak{H}\coloneqq\mathfrak{H}(\mathscr{C})$ of
$\mathscr{C}$ w.r.t. to set inclusion is a DAG whose vertices are the clusters
in $\mathscr{C}$. There is a directed arc $(C,C^{\prime})\in\mathfrak{H}$ if
$C^{\prime}\subsetneq C$ and there is no $C^{\prime\prime}\in\mathscr{C}$ with
$C^{\prime}\subsetneq C^{\prime\prime}\subsetneq C$. Since $X\in\mathscr{C}$,
the Hasse diagram is connected and has $X$ as its unique root. The singletons
$\\{x\\}$, $x\in X$, are exactly the inclusion-minimal vertices in
$\mathscr{C}$ and thus, they have outdegree $0$ but not necessarily indegree
$1$ in $\mathfrak{H}$. Another simple property of $\mathfrak{H}$ is the
following:

######  Lemma 3.38.

Let $\mathscr{C}$ be a clustering system on $X$. Then every non-singleton set
$C\in\mathscr{C}$ satisfies $\operatorname{outdeg}_{\mathfrak{H}}(C)\geq 2$ in
the Hasse diagram $\mathfrak{H}$ of $\mathscr{C}$.

###### Proof.

Let $C\in\mathscr{C}$ be a non-singleton set, i.e., $|C|\geq 2$. Therefore and
since $\\{x\\}\in\mathscr{C}$ for all $x\in X$, there is a directed path in
$\mathfrak{H}$ from $C$ to some singleton set
$\\{x^{\prime}\\}\in\mathscr{C}$. In particular, this path contains at least
the two distinct clusters $C$ and $\\{x^{\prime}\\}$, and thus, $C$ has a
child $C^{\prime}$ in $\mathfrak{H}$ with $\\{x^{\prime}\\}\subseteq
C^{\prime}\subsetneq C$. Now pick an element $x^{\prime\prime}\in C\setminus
C^{\prime}\neq\emptyset$. Since $\\{x^{\prime\prime}\\}\in\mathscr{C}$ and
$\\{x^{\prime\prime}\\}\subseteq C$, we can argue similarly as before to
conclude that $C$ has a child $C^{\prime\prime}$ in $\mathfrak{H}$ with
$\\{x^{\prime\prime}\\}\subseteq C^{\prime\prime}\subsetneq C$. Since
$x^{\prime\prime}\notin C^{\prime}$, we have $C^{\prime}\neq C^{\prime\prime}$
and thus, $C$ satisfies $\operatorname{outdeg}_{\mathfrak{H}}(C)\geq 2$. ∎

######  Lemma 3.39.

Let $\mathscr{C}$ be a clustering system on $X$ with corresponding Hasse
diagram $\mathfrak{H}$. Then $\mathfrak{H}$ is a phylogenetic network with
leaf set $X_{\mathfrak{H}}\coloneqq\\{\\{x\\}\mid x\in X\\}$.

###### Proof.

Clearly, $\mathfrak{H}$ is a DAG. Since $X\in\mathscr{C}$ and $C\subseteq X$
for all $C\in\mathscr{C}$, $X$ is the unique cluster in $\mathscr{C}$ with
indegree 0, i.e., $X$ is the root in $\mathfrak{H}$ and $\mathfrak{H}$
satisfies (N1). By definition of clustering systems, we have
$X_{\mathfrak{H}}\subseteq\mathscr{C}$. Now consider a cluster $\\{x\\}\in
X_{\mathfrak{H}}$. Since $\emptyset\notin\mathscr{C}$, $\\{x\\}$ has outdegree
zero in $\mathfrak{H}$. Lemma 3.38 implies
$\operatorname{outdeg}_{\mathfrak{H}}(C)\geq 2$ for all $C\in\mathscr{C}$ with
$|C|>1$, i.e., for all $C\in\mathscr{C}\setminus X_{\mathfrak{H}}$. Taken
together, the latter arguments imply that the elements in $X_{\mathfrak{H}}$
are exactly the leaves of $\mathfrak{H}$ and that (N2) is satisfied. ∎

For a given a clustering system $\mathscr{C}$ and a cluster $C\in\mathscr{C}$,
we will moreover make use of the subsets

$\mathcal{D}(C)\coloneqq\\{D\in\mathscr{C}\mid D\subsetneq
C\\}\qquad\text{and}\qquad\overline{\mathcal{D}}(C)\coloneqq\\{D\in\mathscr{C}\mid
D\not\subseteq C\\}.$ (3)

Note that, by definition, we have
$\mathcal{D}(C)\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{\mathcal{D}}(C)\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}}}}\\{C\\}=\mathscr{C}$
for all $C\in\mathscr{C}$, $\mathcal{D}(C)=\emptyset$ if and only if $C$ is a
singleton, and $\overline{\mathcal{D}}(C)=\emptyset$ if and only if $C=X$.

######  Lemma 3.40.

Let $\mathfrak{H}$ be the Hasse diagram of a clustering system $\mathscr{C}$
and $C\in\mathscr{C}$ such that $C$ does not overlap any other set. Then,
there is no undirected cycle in $\mathfrak{H}$ that intersects both
$\mathcal{D}(C)$ and $\overline{\mathcal{D}}(C)$. In particular, if $C\neq X$
and $|C|>1$, then $C$ is a cut vertex in $\mathfrak{H}$.

###### Proof.

Suppose that $C$ does not overlap with any other cluster. If $C=X$ then,
$\overline{\mathcal{D}}(C)=\emptyset$ and if $|C|=1$ then
$\mathcal{D}(C)=\emptyset$ and thus, for any cycle $K$ in $\mathfrak{H}$ we
have $K\cap\overline{\mathcal{D}}(C)=\emptyset$ or
$K\cap{\mathcal{D}}(C)=\emptyset$. Hence, $K$ cannot intersect both. Now,
assume that $C\neq X$ and $|C|>1$. Since $C$ is neither a singleton nor $X$,
both $\mathcal{D}(C)$ and $\overline{\mathcal{D}}(C)$ are non-empty.
Furthermore,
$\mathcal{D}(C)\cup\overline{\mathcal{D}}(C)=\mathscr{C}\setminus\\{C\\}$. Let
$C_{1}\in\mathcal{D}(C)$ and $C_{2}\in\overline{\mathcal{D}}(C)$. By
assumption, we have $C_{1}\subsetneq C$ and either (i) $C_{2}\cap C=\emptyset$
or (ii) $C\subsetneq C_{2}$. In case (i), we have $C_{1}\cap C_{2}=\emptyset$
and in case (ii), it holds $C_{1}\subsetneq C\subsetneq C_{2}$. Therefore and
since $C_{1}\in\mathcal{D}(C)$ and $C_{2}\in\overline{\mathcal{D}}(C)$ were
chosen arbitrarily, $\mathfrak{H}$ contains no arc connecting a cluster in
$\mathcal{D}(C)$ and a cluster in $\overline{\mathcal{D}}(C)$. Together with
$\mathcal{D}(C)\cup\overline{\mathcal{D}}(C)=\mathscr{C}\setminus\\{C\\}$,
this implies that the subgraph of $\mathfrak{H}$ obtained by removing $C$ is
disconnected and thus, $C$ is a cut vertex. In particular, every undirected
path connecting a cluster in $\mathcal{D}(C)$ and a cluster in
$\overline{\mathcal{D}}(C)$ has to pass through $C$ and thus the second
statement of the lemma follows as an immediate consequence. ∎

Figure 6: Both the rooted $K_{2,3}$ (A) and $K_{3,3}$ (B) are a phylogenetic
networks that have only two leaves, denoted $x$ and $y$ here. The clustering
system therefore consists only of $X=\\{x,y\\}$ and the two singletons
$\\{x\\}$ and $\\{y\\}$. The same clustering system can be represented by a
rooted tree with a single root that is adjacent to the two leaves $x$ and $y$.
In particular, both networks do not satisfy (PCC) since the highlighted
vertices are $\preceq_{N}$-incomparable but share the cluster $\\{x,y\\}$. (C)
A network showing that
$\operatorname{\mathtt{C}}(v)\subsetneq\operatorname{\mathtt{C}}(u)$ is also
possible for two $\preceq$-incomparable vertices $u$ and $v$.

Every phylogenetic tree $T$ is isomorphic to the Hasse diagram of its
clustering systems $\mathscr{C}$ by virtue of the map $\varphi\colon
V(T)\to\mathscr{C},\,v\mapsto\operatorname{\mathtt{C}}(v)$, see e.g. [48].
Fig. 6 shows that this is not the case for phylogenetic networks in general.
The rooted networks that share this property with phylogenetic trees have been
introduced and studied in [5, 6, 56].

######  Definition 3.41.

[5] A network $N=(V,E)$ is _regular_ if the map $\varphi\colon V\to
V(\mathfrak{H}(\mathscr{C}_{N}))\colon v\mapsto\operatorname{\mathtt{C}}(v)$
is a graph isomorphism between $N$ and $\mathfrak{H}(\mathscr{C}_{N})$.

The graph isomorphism in Def. 3.41 is quite constrained. In particular, it is
not obvious that an arbitrary graph isomorphism $\varphi$ between the two
networks $N$ and $\mathfrak{H}(\mathscr{C}_{N})$ implies that $N$ is regular,
as $\varphi(v)\neq\operatorname{\mathtt{C}}(v)$ may be possible. As we shall
see in Cor. 4.11, however, $N\sim\mathfrak{H}(\mathscr{C}_{N})$ if and only if
$N$ is regular. Even more, as noted without proof in [5], a rooted network $N$
with leaf set $X$ is regular if and only if it is graph isomorphic to the
Hasse diagram $\mathfrak{H}(\mathscr{C})$ for some clustering system
$\mathscr{C}\subseteq 2^{X}$. This result will be an immediate consequence of
the results established below and will be summarized and proven in Prop. 4.10.

######  Proposition 3.42.

For every clustering system $\mathscr{C}$, there is a unique regular network
$N$ with $\mathscr{C}_{N}=\mathscr{C}$.

###### Proof.

Let $\mathscr{C}$ be a clustering system on $X$. By Lemma 3.39,
$\mathfrak{H}(\mathscr{C})$ is a network with leaf set
$X_{\mathfrak{H}}\coloneqq\\{\\{x\\}\mid x\in X\\}$. Replacing all leaves
$\\{x\\}$ in $\mathfrak{H}(\mathscr{C})$ with the single element $x$ that they
contain clearly yields a network $N$ such that $\mathscr{C}_{N}=\mathscr{C}$
and $\varphi\colon V(N)\to V(\mathfrak{H}(\mathscr{C}))\colon
v\mapsto\operatorname{\mathtt{C}}_{N}(v)$ is an isomorphism between $N$ and
$\mathfrak{H}(\mathscr{C})$. By definition, $N$ is regular.

Now let $N^{\prime}$ be a regular network with
$\mathscr{C}_{N^{\prime}}=\mathscr{C}$, i.e, there is an isomorphism
$\varphi^{\prime}\colon V(N^{\prime})\to V(\mathfrak{H}(\mathscr{C}))\colon
v\mapsto\operatorname{\mathtt{C}}_{N^{\prime}}(v)$ between $N^{\prime}$ and
$\mathfrak{H}(\mathscr{C})$. In particular, we have
$\varphi(x)=\varphi^{\prime}(x)=\\{x\\}$ for all $x\in X$ and thus
$\varphi^{\prime-1}(\varphi(x))=x$. Hence, $\varphi^{\prime-1}\circ\varphi$ is
an isomorphism between $N$ and $N$ that is the identity on $X$. Hence, $N$ is
the unique regular network with $\mathscr{C}_{N}=\mathscr{C}$. ∎

######  Remark 1.

By a slight abuse of notation, we also write $\mathfrak{H}(\mathscr{C})$ for
the unique regular network of a clustering system $\mathscr{C}$ since it is
obtained from the Hasse diagram by relabeling all leaves $\\{x\\}$ with $x$.

The following characterization is a slight rephrasing of Prop. 4.1 in [5]:

######  Proposition 3.43.

A network $N$ is regular if and only if

  * (i)

$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)\iff
u\preceq_{N}v$ for all $u,v\in V$, and

  * (ii)

$N$ is shortcut-free.

###### Proof.

Prop. 4.1 in [5] states that $N$ is regular if and only if the following three
conditions hold: (a) $u\neq v$ implies
$\operatorname{\mathtt{C}}(u)\neq\operatorname{\mathtt{C}}(v)$, i.e.,
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)\implies u=v$; (b)
if $\operatorname{\mathtt{C}}(u)\subsetneq\operatorname{\mathtt{C}}(v)$, then
there is a directed path from $v$ to $u$, i.e., $u\prec_{N}v$; and (c) if
there are two distinct directed paths connecting $u$ and $v$, then neither
path consists of a single arc, i.e., $(u,v)$ is not a shortcut. Clearly,
conditions (ii) and (c) are equivalent. It therefore suffices to show that
condition (i) holds if and only if conditions (a) and (b) are satisfied.
Together, (a), (b) and Lemma 3.33 obviously imply (i). Now suppose (i) is
satisfied. Then $\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$
implies $\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)$
and $\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(u)$ and
thus we have both $u\preceq_{N}v$ and $v\preceq_{N}u$, and hence $u=v$, i.e.,
(a) holds. Assuming
$\operatorname{\mathtt{C}}(u)\subsetneq\operatorname{\mathtt{C}}(v)$, i.e,
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)$ and
$\operatorname{\mathtt{C}}(u)\neq\operatorname{\mathtt{C}}(v)$ implies
$u\preceq_{N}v$ by (i) and $u\neq v$ by (a), and thus $u\prec_{N}v$, i.e., (b)
holds as well. ∎

Prop. 3.42 and 3.43 imply

######  Corollary 3.44.

For every clustering system $\mathscr{C}$ there is a network $N$ with
$\mathscr{C}_{N}=\mathscr{C}$ such that
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)\iff
u\preceq_{N}v$ for all $u,v\in V$.

######  Corollary 3.45.

Every regular network is least-resolved.

###### Proof.

Suppose, for contradiction, that the regular network $N$ is not least-
resolved, i.e., there is a network $N^{\prime}$ with
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$ that can be obtained from $N$ by a
non-empty sequence of shortcut removals and application of
$\operatorname{\textsc{cntr}}(v^{\prime},v)$. By Prop. 3.43, $N$ is shortcut-
free and, therefore, the operation that is applied first must be a
contraction. Therefore and since no new vertices are introduced, it must hold
$|V(N^{\prime})|<|V(N)|$. Since $N$ is regular, it holds
$|V(N)|=|\mathscr{C}_{N}|$. Hence, we have
$|V(N^{\prime})|<|\mathscr{C}_{N}|=|\mathscr{C}_{N^{\prime}}|$; a
contradiction. ∎

The converse of Cor. 3.45, however, is not satisfied, see Fig. 7. The network
$N$ is shortcut-free and satisfies $|V(N)|=|\mathscr{C}_{N}|$. Hence,
$\mathscr{C}_{N}$ is least-resolved. The unique regular network $N^{\prime}$
for $\mathscr{C}_{N}$ on the r.h.s. of Fig. 7 is not isomorphic to $N$. Hence,
we obtain

######  Observation 3.46.

Not every least-resolved network is regular.

Nevertheless, for level-1 networks the terms least-resolved and regular
coincide as shown in Cor. 7.2.

Figure 7: The network $N$ is least-resolved but not isomorphic to
$N^{\prime}\sim\mathfrak{H}(\mathscr{C}_{N})$. Consequently, $N$ is not
regular.

A clustering system $\mathscr{C}$, by definition, is a hierarchy if and only
if, for all $C,C^{\prime}\in\mathscr{C}$ holds $C\cap
C^{\prime}\in\\{\emptyset,C,C^{\prime}\\}$.

######  Corollary 3.47.

A clustering system $\mathscr{C}$ on $X$ is a hierarchy if and only if
$\mathfrak{H}(\mathscr{C})$ is a phylogenetic tree. Moreover, $N$ is a
phylogenetic tree if and only if $\mathfrak{H}(\mathscr{C}_{N})\sim N$ and
$\mathscr{C}_{N}$ is a hierarchy.

###### Proof.

The 1-to-1 correspondence of hierarchies and phylogenetic trees is well known,
see e.g. [48, Thm. 3.5.2]. ∎

##  4 Semi-Regular Networks

###  4.1 Path-Cluster Comparability

Regularity as characterized in Prop. 3.43 is a bit too restrictive for our
purposes. We therefore consider a slightly weaker condition, which we will
call _semi-regularity_. More precisely, we relax condition (i) in Prop. 3.43:

######  Definition 4.1.

A network $N$ has the _path-cluster-comparability (PCC)_ property if it
satisfies, for all $u,v\in V(N)$,

(PCC)

$u$ and $v$ are $\preceq_{N}$-comparable if and only if
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)$ or
$\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(u)$.

######  Definition 4.2.

A network is _semi-regular_ if it is shortcut-free and satisfies (PCC).

We introduce the term “semi-regular” because, as we shall see in Thm. 4.8, it
is a moderate generalization of regularity that preserves many of useful
properties of regular networks. We emphasize that (PCC) is a quite restrictive
property. For instance, the rooted $K_{3,3}$ in Fig. 6(B) violates (PCC). The
example in Fig. 6(C) shows that even
$\operatorname{\mathtt{C}}(v)\subsetneq\operatorname{\mathtt{C}}(u)$ is
possible for two $\preceq_{N}$-incomparable vertices $u$ and $v$.

######  Observation 4.3.

Let $N$ be a network satisfying (PCC) and $u,v\in V(N)$. Then
$\operatorname{\mathtt{C}}(u)\subsetneq\operatorname{\mathtt{C}}(v)$ implies
$u\prec_{N}v$.

###### Proof.

Suppose $\operatorname{\mathtt{C}}(u)\subsetneq\operatorname{\mathtt{C}}(v)$.
Then (PCC) implies that $u$ and $v$ are $\preceq_{N}$-comparable. If
$v\preceq_{N}u$, then Lemma 3.33 implies
$\operatorname{\mathtt{C}}(v)\subseteq\operatorname{\mathtt{C}}(u)$; a
contradiction. Hence, only $u\prec_{N}v$ is possible. ∎

Property (PCC) still allows that distinct vertices are associated with the
same clusters. It requires, however, that such vertices lie along a common
directed path.

######  Lemma 4.4.

Let $N$ be a network. Then
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$ and $u\prec_{N}v$
imply that there is $w\in\operatorname{child}_{N}(v)$ such that
$u\preceq_{N}w\prec_{N}v$ and
$\operatorname{\mathtt{C}}(w)=\operatorname{\mathtt{C}}(v)$.

###### Proof.

Since $u\prec_{N}v$, there is a $vw$-path which passes through some child
$w\in\operatorname{child}_{N}(v)$. Hence, we have $u\preceq_{N}w\prec_{N}v$.
Lemma 3.33 implies
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(w)\subseteq\operatorname{\mathtt{C}}(v)$.
Together with $\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$,
this yields
$\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)=\operatorname{\mathtt{C}}(u)$.
∎

######  Lemma 4.5.

Let $N$ be a semi-regular network and let $v\in V(N)$. Then, there is a vertex
$u\in V(N)$ with $\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$
and $u\prec_{N}v$ if and only if $\operatorname{outdeg}(v)=1$. If, moreover,
$N$ is phylogenetic, then $u$ is the unique child of $v$ in this case.

###### Proof.

Suppose first that $\operatorname{outdeg}(v)=1$ and thus let $u$ be the unique
child of $v$. Thus, it holds $u\prec_{N}v$ and, by Obs. 3.36, we have
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$. Conversely,
suppose that $\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$ and
$u\prec_{N}v$. Lemma 4.4 implies that there is $w\in\operatorname{child}(v)$
with $u\preceq_{N}w\prec_{N}v$ and
$\operatorname{\mathtt{C}}(w)=\operatorname{\mathtt{C}}(v)$. Suppose there is
another child $w^{\prime}\in\operatorname{child}(v)$ with $w^{\prime}\neq w$.
By Lemma 3.33, we have
$\operatorname{\mathtt{C}}(w^{\prime})\subseteq\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)$.
Hence, (PCC) implies that $w$ and $w^{\prime}$ are $\preceq_{N}$-comparable.
But then Obs. 2.6 and $N$ being shortcut-free imply $w=w^{\prime}$; a
contradiction. Hence, $w$ is the unique child of $v$.

Now suppose, in addition, that $N$ is phylogenetic and assume, for
contradiction, that $u\neq w$ and thus $u\prec_{N}w$. We can apply similar
arguments as before to conclude that $w$ has a unique child. Therefore and
since $N$ is phylogenetic, there must be a vertex
$v^{\prime}\in\operatorname{par}_{N}(w)\setminus\\{v\\}$ since otherwise
$\operatorname{indeg}(w)=\operatorname{outdeg}(w)=1$. By Lemma 3.33, we have
$\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)\subseteq\operatorname{\mathtt{C}}(v^{\prime})$.
This together with (PCC) implies that $v$ and $v^{\prime}$ are
$\preceq_{N}$-comparable. But then Obs. 2.6 and $N$ being shortcut-free imply
$v=v^{\prime}$; a contradiction. Therefore, $u=w$ is the unique child of $v$.
∎

As a consequence of Lemmas 3.33 and 4.5, we have

######  Corollary 4.6.

Let $N$ be a semi-regular network and let $v\in V^{0}$. Then
$\operatorname{\mathtt{C}}(u)\subsetneq\operatorname{\mathtt{C}}(v)$ for all
$u\in\operatorname{child}_{N}(v)$ if and only if $\operatorname{outdeg}(v)\geq
2$.

######  Lemma 4.7.

Let $N$ be a semi-regular, $u\in V(N)$, and let $Q(u)\coloneqq\\{u^{\prime}\in
V(N)\mid\operatorname{\mathtt{C}}(u^{\prime})=\operatorname{\mathtt{C}}(u)\\}$.
Then the vertices of $Q(u)$ are pairwise $\preceq_{N}$-comparable and lie
consecutively along an induced directed path in $N$. Moreover, if $|Q(u)|>1$,
either $Q(u)$ is contained in a non-trivial block, or adjacent pairs of
vertices in $Q(u)$ form a trivial block.

###### Proof.

By (PCC), $\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(w)$ and
$v\neq w$ implies $v\prec_{N}w$ or $w\prec_{N}v$ for $v,w\in Q(u)$, i.e., the
vertices in $Q(u)$ are pairwise $\preceq_{N}$-comparable and thus linearly
ordered w.r.t. $\preceq_{N}$. Using Lemma 4.4, one easily verifies that $Q(u)$
forms a directed path in $N$ and there are unique $\preceq_{N}$-minimal and
$\preceq_{N}$-maximal vertices $\min Q(u)$ and $\max Q(u)$. In particular,
since $N$ is acyclic and shortcut-free, this path must be an induced subgraph.

Now suppose $u$ is a hybrid vertex and suppose there is $v\in Q(u)$ with
$(v,u)\in E(N)$, i.e., $u$ has a parent in $Q(u)$. Then there is
$v^{\prime}\in\operatorname{par}(u)\setminus\\{v\\}$. By Lemma 3.33,
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v^{\prime})$,
and thus by (PCC), $v$ and $v^{\prime}$ are $\preceq_{N}$-comparable. However,
since $N$ is shortcut-free, $v$ and $v^{\prime}$ are
$\preceq_{N}$-incomparable by Obs. 2.6; a contradiction. Thus only $\max Q(u)$
can be a hybrid vertex in $Q(u)$. By similar argument, only $\min Q(u)$ can
have outdegree greater that one. Hence, all inner vertices in the directed
path $P$ formed by $Q(u)$ have degree $2$. Therefore, if one arc in $P$ is
contained in an undirected cycle, then all arcs in $P$ are contained in this
cycle, in which case $Q(u)$ is contained in a non-trivial block. Otherwise
$Q(u)$ consists of a sequence of consecutive cut-arcs. ∎

The examples in Fig. 6(A) and (B) show that (PCC) is necessary in Lemma 4.7.
We note, moreover, that the cardinality $|Q(u)|$ equals the multiplicity of
the cluster $\operatorname{\mathtt{C}}(u)$ in $\mathscr{M}_{N}$.

######  Theorem 4.8.

A network is regular if and only if it is semi-regular and there is no vertex
with outdegree $1$.

###### Proof.

If $N$ is regular, it is in particular also semi-regular, and thus satisfies
(PCC). Furthermore, then
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$ implies $u=v$ and
thus there are no two vertices $u,v$ satisfying
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$ and $u\prec_{N}v$.
Lemma 4.5 thus implies that there is no vertex with outdegree $1$. Conversely,
assume that $N$ is semi-regular (and thus shortcut-free) and suppose there is
not vertex with outdegree $1$. Then Lemma 4.5 implies that there is no pair of
vertices $u,v$ with
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$ and $u\prec_{N}v$
or $v\prec_{N}u$, i.e.,
$\operatorname{\mathtt{C}}(u)=\operatorname{\mathtt{C}}(v)$ implies $u=v$.
Therefore and by Lemma 3.33, we have
$\operatorname{\mathtt{C}}(u)\subseteq\operatorname{\mathtt{C}}(v)\iff
u\preceq_{N}v$. By Prop. 3.43, therefore, $N$ is regular. ∎

By Thm. 4.8, every regular network is semi-regular and thus, satisfies (PCC).
This together with Cor. 3.44 and Def. 4.1 implies

######  Corollary 4.9.

For every clustering system $\mathscr{C}$ there is a network $N$ with
$\mathscr{C}_{N}=\mathscr{C}$ that that satisfies (PCC).

######  Proposition 4.10.

Let $N$ be a network on $X$. Then, $N\sim\mathfrak{H}(\mathscr{C})$ for some
clustering system $\mathscr{C}\subseteq 2^{X}$ if and only if $N$ is regular.

###### Proof.

Assume first that $N\sim\mathfrak{H}(\mathscr{C})$. In this case, $N$ is
shortcut-free, satisfies (PCC), and has no vertex with outdegree $1$ (since
$\mathfrak{H}(\mathscr{C})$ has these properties). By Thm. 4.8, $N$ is
regular. Assume now that $N$ is regular. By Def. 3.41,
$N\sim\mathfrak{H}(\mathscr{C_{N}})$. Thus, we can put
$\mathscr{C}=\mathscr{C}_{N}$ and obtain $N\sim\mathfrak{H}(\mathscr{C})$. ∎

It should be noted that $N\sim\mathfrak{H}(\mathscr{C})$ does not necessarily
imply that $\mathscr{C}_{N}=\mathscr{C}$. By way of example, consider a binary
phylogenetic rooted tree $T$ on $X$ with
$\mathscr{C}_{T}=\\{\\{1\\},\\{2\\},\\{3\\},\\{1,2\\},\\{1,2,3\\}\\}$ and the
clustering system
$\mathscr{C}=\\{\\{1\\},\\{2\\},\\{3\\},\\{2,3\\},\\{1,2,3\\}\\}$. It can
easily be verified that $T\sim\mathfrak{H}(\mathscr{C})$ although
$\mathscr{C}_{T}\neq\mathscr{C}$. Nevertheless, Prop. 4.10 together with Def.
3.41 immediately implies

######  Corollary 4.11.

$N\sim\mathfrak{H}(\mathscr{C}_{N})$ if and only if $N$ is regular.

A crucial link between a network and its clustering systems is the ability to
identify the non-trivial blocks. The following result shows that, at least in
semi-regular networks, key information is provided by the overlaps of
clusters.

######  Lemma 4.12.

Let $B$ be a non-trivial block in a semi-regular network $N$. Then for every
$u\in B^{0}$ there is a $v\in B^{0}$ such that $\operatorname{\mathtt{C}}(u)$
and $\operatorname{\mathtt{C}}(v)$ overlap.

###### Proof.

Suppose $u\in B^{0}$ and consider the two disjoint sets $A\coloneqq\\{w\in
V(B)\mid u\prec_{N}w\\}$ and $D\coloneqq\\{w\in V(B)\mid w\prec_{N}u\\}$,
i.e., the ancestors and descendants, resp., of $u$ in $B$. Note that both sets
are non-empty since $u\in B^{0}$. There is no arc connecting a vertex in $A$
with a vertex in $D$. To see this, consider $a\in A$ and $d\in D$. Since
$d\prec_{N}u\prec_{N}a$ and $N$ is acyclic, there is a directed path $P$ from
$a$ to $d$ passing through $u$. Thus an arc $(a,d)$ would be a shortcut,
contradicting that $N$ is semi-regular, and an arc $(d,a)$ would imply
$a\prec_{N}d$ contradicting $d\prec_{N}u\prec_{N}a$. Since $a,d\in V(B)$ and
$B$ is a non-trivial block, $a$ and $d$ lie on an undirected cycle $K$ in $B$.
In particular, they are connected by two undirected paths that do not share
any inner vertices. Thus there is an undirected path
$P=(d=v_{1},v_{2},\dots,a=v_{k})$ that does not contain $u$. Let $v_{i}$ be
the unique vertex in $P$ such that $v_{i}\in D$ and there is no vertex
$v_{j}\in D$ with $i<j\leq k$. Such a vertex exists since $v_{1}\in D$.
Moreover, $v_{k}=a\in A$ implies $i<k$. Thus consider the vertex $v\coloneqq
v_{i+1}$. We have $v\notin D$ by construction and $v\notin A$ since $v_{i}\in
D$ is not adjacent to any vertex in $A$. Since $P$ does not contain $u$ and
$v\in
V(B)\setminus(A\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}}}}D)$,
we see that $u$ and $v$ are $\preceq_{N}$-incomparable. Since $v_{i}\in D$, we
have $v_{i}\prec_{N}u$. Hence, $(v_{i},v_{i+1})$ cannot be an arc in $N$ since
otherwise $v_{i+1}\prec_{N}v_{i}\prec_{N}u$ would imply $v_{i+1}\in D$; a
contradiction. Therefore, it have $(v,v_{i})=(v_{i+1},v_{i})\in E(N)$ and thus
$v_{i}\prec_{N}u,v$. By Lemma 3.33, this implies
$\emptyset\neq\operatorname{\mathtt{C}}_{N}(v_{i})\subseteq\operatorname{\mathtt{C}}_{N}(u)\cap\operatorname{\mathtt{C}}_{N}(v)$.
Together with (PCC) and the fact that $u$ and $v$ are
$\preceq_{N}$-incomparable, this yields that $\operatorname{\mathtt{C}}(u)$
and $\operatorname{\mathtt{C}}(v)$ overlap. In particular, $v\neq\max B$ since
$u$ and $v$ are $\preceq_{N}$-incomparable and $v$ is not a terminal vertex
since $v_{i}\prec_{N}v$. Therefore, we have $v\in B^{0}$. ∎

We note that semi-regularity cannot be omitted in Lemma 4.12, since the
statement is not true for the rooted $K_{3,3}$ of Fig. 6. Lemma 3.35 and Lemma
4.12 together show that in semi-regular networks all vertices in the interior
of non-trivial blocks are identified by the fact their clusters overlap. It
remains an open question, however, whether the information of cluster overlaps
is sufficient to identify the non-trivial blocks.

We continue by showing that, whenever (PCC) is satisfied, least-resolved
networks are precisely the regular network, To this end, we consider first the
implications given by the operations $\operatorname{\textsc{expd}}$ and
$\operatorname{\textsc{cntr}}$, and by the removal of short-cuts,
respectively.

######  Lemma 4.13.

Let $N$ be a network, $w\in V(N)$, and $N^{\prime}$ the network obtained from
$N$ by applying $\operatorname{\textsc{expd}}(w)$. Then $N$ satisfies (PCC) if
and only if $N^{\prime}$ satisfies (PCC).

###### Proof.

By Lemma 3.13, $N$ and $N^{\prime}$ are $(N^{\prime},N)$-ancestor-preserving,
i.e., $v\preceq_{N}v^{\prime}$ if and only if $v\preceq_{N}v^{\prime}$ holds
for all $v,v^{\prime}\in V(N)$. By Lemma 3.13,
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
for all $v\in V(N)\subseteq V(N^{\prime})$. Let $w^{\prime}$ be the unique
vertex in $V(N^{\prime})\setminus V(N)$. By construction, $w$ is the unique
child of $w^{\prime}$ in $N^{\prime}$ and thus, by Obs. 3.36,
$\operatorname{\mathtt{C}}_{N}(w)=\operatorname{\mathtt{C}}_{N^{\prime}}(w)=\operatorname{\mathtt{C}}_{N^{\prime}}(w^{\prime})$.

Suppose first $N^{\prime}$ satisfies (PCC), i.e., for all $u,v\in
V(N^{\prime})$, it holds that $u$ and $v$ are
$\preceq_{N^{\prime}}$-comparable if and only if
$\operatorname{\mathtt{C}}_{N^{\prime}}(u)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
or
$\operatorname{\mathtt{C}}_{N^{\prime}}(v)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(u)$.
To see that $N$ also satisfies (PCC), consider $u,v\in V(N)\subseteq
V(N^{\prime})$. Suppose $u$ and $v$ are $\preceq_{N}$-comparable. Hence, $u$
and $v$ are also $\preceq_{N^{\prime}}$-comparable, and thus
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N^{\prime}}(u)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(v)=\operatorname{\mathtt{C}}_{N}(v)$
or
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}(v)_{N^{\prime}}\subseteq
C_{N^{\prime}}(u)=\operatorname{\mathtt{C}}_{N}(u)$. Conversely, if
$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)$ or
$\operatorname{\mathtt{C}}_{N}(v)\subseteq\operatorname{\mathtt{C}}_{N}(u)$,
then also
$\operatorname{\mathtt{C}}_{N^{\prime}}(u)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
or
$\operatorname{\mathtt{C}}_{N^{\prime}}(v)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(u)$.
Hence, $u$ and $v$ are $\preceq_{N^{\prime}}$-comparable and thus also
$\preceq_{N}$-comparable.

Now suppose $N$ satisfies (PCC). By similar argument as above, it holds, for
all $u,v\in V(N)=V(N^{\prime})\setminus\\{w^{\prime}\\}$ that $u$ and $v$ are
$\preceq_{N}$-comparable if and only if
$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)$ or
$\operatorname{\mathtt{C}}_{N}(v)\subseteq\operatorname{\mathtt{C}}_{N}(u)$.
To show that $N^{\prime}$ satisfies (PCC), it therefore only remains to
consider $w^{\prime}$ and some vertex $v\in V(N)$. It holds that $v$ and
$w^{\prime}$ are $\preceq_{N^{\prime}}$-comparable if and only if $v$ and $w$
are $\preceq_{N^{\prime}}$-comparable. To see this, suppose first $v$ and
$w^{\prime}$ are $\preceq_{N^{\prime}}$-comparable. If
$v\prec_{N^{\prime}}w^{\prime}$, then $v\preceq_{N^{\prime}}w$ since $w$ is
the unique child of $w^{\prime}$. If $w^{\prime}\prec_{N^{\prime}}v$, then
$w\prec_{N^{\prime}}w^{\prime}$ implies $w\prec_{N^{\prime}}v$. Now suppose
$v$ and $w$ are $\preceq_{N^{\prime}}$-comparable. If
$v\preceq_{N^{\prime}}w$, then $w\prec_{N^{\prime}}w^{\prime}$ implies
$v\prec_{N^{\prime}}w^{\prime}$. If $w\prec_{N^{\prime}}v$, then
$w^{\prime}\preceq_{N^{\prime}}v$ (and thus $w^{\prime}\prec_{N^{\prime}}v$)
since $w^{\prime}$ is the unique parent of $w$ in $N^{\prime}$. Taken together
and since $v,w\in V(N)$, the arguments so far imply that $v$ and $w^{\prime}$
are $\preceq_{N^{\prime}}$-comparable if and only if $v$ and $w$ are
$\preceq_{N^{\prime}}$-comparable if and only if
$\operatorname{\mathtt{C}}_{N^{\prime}}(v)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(w)=\operatorname{\mathtt{C}}_{N^{\prime}}(w^{\prime})$
or
$\operatorname{\mathtt{C}}_{N^{\prime}}(w^{\prime})=\operatorname{\mathtt{C}}_{N^{\prime}}(w)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
In summary, therefore, $N^{\prime}$ satisfies (PCC). ∎

Cor. 3.14 and Lemma 4.13 imply that semi-regularity is preserved by
$\operatorname{\textsc{expd}}$ applied on arbitrary vertices and
$\operatorname{\textsc{cntr}}(u,w)$ applied to arcs $(u,w)$ where
$\operatorname{outdeg}(u)=1$.

######  Corollary 4.14.

Let $N$ be a network, $w\in V(N)$, and $N^{\prime}$ the network obtained from
$N$ by applying $\operatorname{\textsc{expd}}(w)$. Then $N$ is semi-regular if
and only if $N^{\prime}$ is semi-regular.

######  Proposition 4.15.

Let $N$ be a network satisfying (PCC). The unique regular network
$\mathfrak{H}(\mathscr{C}_{N})$ is obtained from $N$ by repeatedly executing
one of the following operations until neither of them is possible:

(1)

remove a shortcut $(u,w)$, and

(2)

apply $\operatorname{\textsc{cntr}}(u,w)$ for an arc $(u,w)$ with
$\operatorname{outdeg}(u)=1$.

###### Proof.

Let $N^{\prime}$ be the network obtained by applying one of the following
operations until neither of them is possible. By construction, we have
$V(N^{\prime})\subseteq V(N)$. We can repeatedly apply Lemma 3.8 and 3.11 to
conclude that $N^{\prime}$ is a network with leaf set $X$ and that, for all
$v,v^{\prime}\in V(N^{\prime})$, it holds $v\preceq_{N}v^{\prime}$ if and only
if $v\preceq_{N^{\prime}}v^{\prime}$. Similarly, Lemma 3.8 and 3.11 imply that
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
holds for all $v\in V(N^{\prime})$ and, in particular,
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$.

By assumption, $N$ satisfies (PCC), i.e., for all $u,v\in V(N)$, it holds that
$u$ and $v$ are $\preceq_{N}$-comparable if and only if
$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)$ or
$\operatorname{\mathtt{C}}_{N}(v)\subseteq\operatorname{\mathtt{C}}_{N}(u)$.
To see that $N^{\prime}$ also satisfies (PCC), consider $u,v\in
V(N^{\prime})$. Suppose $u$ and $v$ are $\preceq_{N^{\prime}}$-comparable.
Hence, $u$ and $v$ are also $\preceq_{N}$-comparable, and thus
$\operatorname{\mathtt{C}}_{N^{\prime}}(u)=\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
or
$\operatorname{\mathtt{C}}_{N^{\prime}}(v)=\operatorname{\mathtt{C}}_{N}(v)\subseteq\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N^{\prime}}(u)$.
Conversely, if
$\operatorname{\mathtt{C}}_{N^{\prime}}(u)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(v)$
or
$\operatorname{\mathtt{C}}_{N^{\prime}}(v)\subseteq\operatorname{\mathtt{C}}_{N^{\prime}}(u)$,
then also
$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)$ or
$\operatorname{\mathtt{C}}_{N}(v)\subseteq\operatorname{\mathtt{C}}_{N}(u)$.
Hence, $u$ and $v$ are $\preceq_{N}$-comparable and thus also
$\preceq_{N^{\prime}}$-comparable. Therefore, $N^{\prime}$ satisfies (PCC).
Since moreover $N^{\prime}$ is shortcut-free by construction, $N^{\prime}$ is
semi-regular. This together with Thm. 4.8 and the fact that, by construction,
there is no vertex $v$ with $\operatorname{outdeg}_{N^{\prime}}(v)=1$ implies
that $N^{\prime}$ is regular. This, together with
$\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$, implies that $N^{\prime}$ is the
unique regular network $\mathfrak{H}(\mathscr{C})$. ∎

######  Proposition 4.16.

Let $N$ be a least-resolved network satisfying (PCC). Then $N$ is the unique
regular network for $\mathscr{C}_{N}$.

###### Proof.

By Cor. 3.12, $N$ is shortcut-free (and thus, semi-regular) and contains no
vertex with outdegree $1$. By Thm. 4.8, therefore, $N$ is regular. ∎

As a consequence of Cor. 3.45, Thm. 4.8, and Prop. 4.16, we obtain

######  Theorem 4.17.

A network $N$ is regular if and only if $N$ is least-resolved and satisfies
(PCC).

###  4.2 Separated Networks and Cluster Networks

Recall that a network $N$ is _separated_ if all hybrid vertices have outdegree
$1$. We have already seen above that the Hasse diagrams of the clustering
systems cannot produce separated networks with hybrid vertices because
$\operatorname{outdeg}(v)=1$ implies that
$\operatorname{\mathtt{C}}(v)=\operatorname{\mathtt{C}}(u)$ whenever $u$ is
the only child of $v$. By Thm. 4.8, furthermore, a regular network does not
have any vertex with outdegree $1$. Therefore, a regular network cannot be
separated whenever it contains at least one hybrid vertex and vice versa.

The _Cluster-popping_ algorithm [26] constructs a separated network for a
given clustering system $\mathscr{C}$ by first constructing the Hasse diagram,
and thus the unique regular network $\mathfrak{H}(\mathscr{C})$, and then
applying $\operatorname{\textsc{expd}}(w)$ to all hybrid vertices $w\in
V(\mathfrak{H}(\mathscr{C}))$. In particular, the resulting network is a so-
called _cluster network_ [26, 37]:

######  Definition 4.18.

A network $N$ is a _cluster network_ if (i) it satisfies (PCC), and, for all
$u,v\in V(N)$, it holds

  1. (ii)

$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$ if and
only if $u=v$ or $v$ is a hybrid vertex and parent of $u$ or vice versa,

  2. (iii)

if $u$ is a child of $v$, then there exists no node $w$ with
$\operatorname{\mathtt{C}}_{N}(u)\subsetneq\operatorname{\mathtt{C}}_{N}(w)\subsetneq\operatorname{\mathtt{C}}_{N}(v)$,
and

  3. (iv)

every hybrid vertex $v$ has exactly one child, which is a tree node.

We note that the definition of cluster networks usually is expressed using the
following condition instead of (PCC):

  * (i’)

$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)$ if
and only if $u\preceq_{N}v$ for all $u,v\in V(N)$ [26, 59].

However, this contradicts the existence of hybrid vertices $v$, which are
required to have exactly one child $u$ by (iv). To see this, observe that
$u\prec_{N}v$ and, by Obs. 3.36, we have
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$. The
latter means that
$\operatorname{\mathtt{C}}_{N}(v)\subseteq_{N}\operatorname{\mathtt{C}}_{N}(u)$
is satisfied and thus (i’) implies $v\preceq_{N}u$; a contradiction.

We can rephrase conditions (i)-(iv), and thus the definition of cluster
networks, as follows:

######  Theorem 4.19.

A network $N$ is a cluster network if and only if it is semi-regular,
separated, and phylogenetic.

###### Proof.

Suppose first that $N$ is a cluster network, i.e., it satisfies conditions
(i)-(iv) in Def. 4.18. By condition (i) and (ii), resp., $N$ satisfies (PCC)
and is separated. Hence, it remains to show that $N$ is shortcut-free and
phylogenetic. Suppose, for contradiction, that $(v,u)$ is a shortcut in $N$.
Then there is $w\in\operatorname{child}_{N}(v)\setminus\\{u\\}$ and
$w^{\prime}\in\operatorname{par}_{N}(u)\setminus\\{v\\}$ such that
$u\prec_{N}w^{\prime}\preceq_{N}w$. By Lemma 3.33,
$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(w^{\prime})\subseteq\operatorname{\mathtt{C}}_{N}(w)\subseteq\operatorname{\mathtt{C}}_{N}(v)$.
If $\operatorname{\mathtt{C}}_{N}(w)=\operatorname{\mathtt{C}}_{N}(v)$, then
conditions (ii) and (iv) imply that $v$ is a hybrid vertex with exactly one
child; a contradiction. Therefore,
$\operatorname{\mathtt{C}}_{N}(w)\subsetneq\operatorname{\mathtt{C}}_{N}(v)$
must hold. If
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(w^{\prime})$,
then conditions (ii) and (iv) imply that $w^{\prime}$ is a hybrid vertex and
its unique child $u$ is a tree node, contradicting that
$w^{\prime},v\in\operatorname{par}_{N}(u)$. Hence, we have
$\operatorname{\mathtt{C}}_{N}(u)\subsetneq\operatorname{\mathtt{C}}_{N}(w^{\prime})\subseteq\operatorname{\mathtt{C}}_{N}(w)\subsetneq\operatorname{\mathtt{C}}_{N}(v)$,
which contradicts (iii). Therefore, $N$ must be shortcut-free and thus semi-
regular. Suppose, for contradiction, that $N$ is not phylogenetic. Hence,
there is a vertex $v$ with exactly one child $u$ and
$\operatorname{indeg}_{N}(v)\leq 1$. By Obs. 3.36, we have
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$ and thus
$v$ must be a hybrid vertex by (ii); a contradiction.

Conversely, suppose $N$ is semi-regular, separated, and phylogenetic. Hence,
$N$ satisfies (PCC), i.e., condition (i). Condition (iii) must be satisfied
since an arc $(v,u)$ with
$\operatorname{\mathtt{C}}_{N}(u)\subsetneq\operatorname{\mathtt{C}}_{N}(w)\subsetneq\operatorname{\mathtt{C}}_{N}(v)$
for some $w\in V(N)$ would be a shortcut by Obs. 4.3. We continue with showing
(ii). Suppose
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$ and $u\neq
v$. By (PCC), it holds $u\prec_{N}v$ or $v\prec_{N}u$. Suppose w.l.o.g. that
$u\prec_{N}v$. Then Lemma 4.5 implies that $\operatorname{outdeg}_{N}(v)=1$
and $u$ is the unique child of $v$. Since $N$ is phylogenetic, $v$ must be a
hybrid vertex. Conversely, a hybrid vertex $v$ in a separated network has
exactly one child $u$ implying
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$ by Obs.
3.36. Since $N$ is separated, it remains to show that the unique child $u$ of
a hybrid vertex $v$ is a tree node. Suppose for contradiction that $u$ is a
hybrid node. Then $u$ again has a unique child $w$. Hence, we have
$w\prec_{N}u\prec_{N}v$ and, by Obs. 3.36, it holds
$\operatorname{\mathtt{C}}_{N}(w)=\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$.
By (ii), this implies that $(v,w)$ is an arc in $N$ and, in particular, a
shortcut; a contradiction. Therefore, condition (iv) is also satisfied. ∎

We shall see in Thm. 4.25 in the following section that cluster networks are
uniquely determined by their cluster sets. To obtain this result it will be
convenient to make use of the fact the semi-regular networks are encoded by
their multisets of clusters.

###  4.3 Cluster Multisets of Semi-Regular Networks

######  Lemma 4.20.

Let $N$ be a semi-regular phylogenetic network. Then, the multiplicity of each
cluster $C\in\mathscr{C}$ in the cluster multiset $\mathscr{M}_{N}$ is either
one or two. In the latter case, the two distinct vertices $u,v\in V(N)$ with
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)=C$ are
adjacent.

###### Proof.

Recall that a semi-regular network $N$ satisfies (PCC) and is shortcut-free.
Let $C\in\mathscr{C}$. Thus, there is at least one vertex $v\in V(N)$ with
$\operatorname{\mathtt{C}}_{N}(v)=C$. Now suppose there is $u\in
V(N)\setminus\\{v\\}$ with $\operatorname{\mathtt{C}}_{N}(u)=C$. By (PCC), it
holds $u\prec_{N}v$ or $v\prec_{N}u$. Suppose that $u\prec_{N}v$. Then Lemma
4.5 implies that $\operatorname{outdeg}_{N}(v)=1$ and $u$ is the unique child
of $v$. Suppose, for contradiction, there is a third vertex $w\in
V(N)\setminus\\{u,v\\}$. By (PCC), it holds $w\prec_{N}v$ or $v\prec_{N}w$. If
$w\prec_{N}v$, then Lemma 4.5 implies that $w$ is the unique child of $v$; a
contradiction. If $v\prec_{N}w$, then we have also $u\prec_{N}v\prec_{N}w$. By
Lemma 4.5, therefore, $v$ and $u$ are both the unique child of $w$, which is
not possible since $u\neq v$. One argues similarly if $v\prec_{N}u$. In
particular, $u$ and $v$ are adjacent in both cases. ∎

As we shall see in Theorem 4.23, the property of being phylogenetic, however,
is not necessary for semi-regular networks to be identified by their cluster
multisets. In order to prove this, the following map will be of useful.

######  Definition 4.21.

Let $N$ and $\tilde{N}$ be two networks satisfying (PCC) and
$\mathscr{M}_{N}=\mathscr{M}_{\tilde{N}}$. Then, the map $\varphi_{PCC}\colon
V(N)\to V(\tilde{N})$ is given by the following steps for all
$C\in\mathscr{C}_{N}=\mathscr{C}_{\tilde{N}}$:

  1. (i)

sort the $k\geq 1$ vertices in $N$ with cluster $C$ such that
$v_{1}\prec_{N}\dots\prec_{N}v_{k}$,

  2. (ii)

sort the $k$ vertices in $\tilde{N}$ with cluster $C$ such that
$\tilde{v}_{1}\prec_{\tilde{N}}\dots\prec_{\tilde{N}}\tilde{v}_{k}$, and

  3. (iii)

set $\varphi(v_{i})=\tilde{v}_{i}$ for all $1\leq i\leq k$.

In other words, we map the $\preceq_{N}$-larger vertices with cluster $C$ in
$N$ to $\preceq_{\tilde{N}}$-larger vertices with cluster $C$ in $\tilde{N}$,
which is possible since, by (PCC), these vertices are totally ordered w.r.t.
$\preceq_{N}$ and $\preceq_{\tilde{N}}$, respectively.

######  Lemma 4.22.

Let $N$ and $\tilde{N}$ be two networks satisfying (PCC) and
$\mathscr{M}_{N}=\mathscr{M}_{\tilde{N}}$. Then $\varphi_{PCC}$ is a bijection
between $V(N)$ and $V(\tilde{N})$ that is the identity on the common leaf set
$X$. Writing $\tilde{v}\coloneqq\varphi_{PCC}(v)$, it moreover holds

  1. 1.

$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{\tilde{N}}(\tilde{v})$
for all $v\in V(N)$,

  2. 2.

$v$ is a leaf if and only if $\tilde{v}$ is a leaf for all $v\in V(N)$, and

  3. 3.

$u\prec_{N}v$ if and only if $\tilde{u}\prec_{\tilde{N}}\tilde{v}$ for all
$u,v\in V(N)$.

###### Proof.

Since $\mathscr{M}_{N}=\mathscr{M}_{\tilde{N}}$, the multiplicity of every
cluster $C\in\mathscr{C}\coloneqq\mathscr{C}_{N}=\mathscr{C}_{\tilde{N}}$ is
equal in $\mathscr{M}_{N}$ and $\mathscr{M}_{\tilde{N}}$, i.e., there are
$k\geq 1$ vertices with cluster $C$ in $N$ and $k$ vertices with cluster $C$
in $\tilde{N}$. One easily verifies that, by construction, $\varphi_{PCC}$ is
a bijection between $V(N)$ and $V(\tilde{N})$ that is the identity on the
common leaf set $X$ and satisfies
$\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{\tilde{N}}(\tilde{v})$
for all $v\in V(N)$. To see that $u\prec_{N}v$ if and only if
$\tilde{u}\prec_{\tilde{N}}\tilde{v}$, suppose $u\prec_{N}v$. By Lemma 3.33,
this implies
$\operatorname{\mathtt{C}}_{N}(u)\subseteq\operatorname{\mathtt{C}}_{N}(v)$.
If
$\operatorname{\mathtt{C}}_{N}(u)\subsetneq\operatorname{\mathtt{C}}_{N}(v)$
(and thus
$\operatorname{\mathtt{C}}_{\tilde{N}}(\tilde{u})\subsetneq\operatorname{\mathtt{C}}_{\tilde{N}}(\tilde{v})$),
then Obs. 4.3 implies $\tilde{u}\prec_{\tilde{N}}\tilde{v}$. If, on the other
hand, $\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)$,
then $\tilde{u}\prec_{\tilde{N}}\tilde{v}$ holds by construction of $\varphi$.
Analogously, $\tilde{u}\prec_{\tilde{N}}\tilde{v}$ implies $u\prec_{N}v$. In
particular, this implies that, for every $v\in V(N)$, $v$ is a leaf if and
only if $\tilde{v}$ is a leaf. ∎

######  Theorem 4.23.

Let $N$ be a semi-regular network. Then $N$ is the unique semi-regular network
whose cluster multiset is $\mathscr{M}_{N}$.

###### Proof.

Suppose $N$ and $\tilde{N}$ are semi-regular networks with
$\mathscr{M}_{N}=\mathscr{M}_{\tilde{N}}$. By assumption, both $N$ and
$\tilde{N}$ are shortcut-free and satisfy (PCC). We continue with showing that
$\varphi_{PCC}\colon V(N)\to V(\tilde{N})$ is a graph isomorphism. By Lemma
4.22, $\varphi_{PCC}$ is a bijection that is the identity on the common leaf
set $X$. In the following, we write $\tilde{v}\coloneqq\varphi_{PCC}(v)$ for
all $v\in V(N)$. Suppose that $(v,u)\in E(N)$. Thus, we have $u\prec_{N}v$
which implies $\tilde{u}\prec_{\tilde{N}}\tilde{v}$ by Lemma 4.22(3). Assume,
for contradiction, that $(\tilde{v},\tilde{u})\notin E(\tilde{N})$. Then there
must be $\tilde{z}\in V(\tilde{N})$ such that
$\tilde{u}\prec_{\tilde{N}}\tilde{z}\prec_{\tilde{N}}\tilde{v}$. By Lemma
4.22(3), we have $u\prec_{N}z\prec_{N}v$. Hence, the arc $(v,u)$ must be a
shortcut in $N$; a contradiction. Therefore, $(\tilde{v},\tilde{u})\in
E(\tilde{N})$. By analogous arguments, $(\tilde{v},\tilde{u})\in E(\tilde{N})$
implies $(v,u)\in E(N)$. Hence, $\varphi_{PCC}$ is a graph isomorphism that is
the identity on $X$ and thus $N\simeq\tilde{N}$. Therefore, $N$ is the unique
semi-regular network whose cluster multiset is $\mathscr{M}_{N}$. ∎

We emphasize that none of the two conditions (PCC) and shortcut-free that
define semi-regular networks can be omitted in Theorem 4.23 as shown by the
examples in Fig. 8.

Figure 8: Two pairs of non-isomorphic (phylogenetic) networks $N$ and
$N^{\prime}$ for which $\mathscr{M}_{N}=\mathscr{M}_{N^{\prime}}$. (A) $N$ and
$N^{\prime}$ satisfy (PCC) but are not shortcut-free. (B) $N$ and $N^{\prime}$
are shortcut-free but do not satisfy (PCC).

It is an easy task to verify that semi-regular networks $N$ (as any other
network for which the property of being phylogenetic has been left out) are
not determined by their clustering systems $\mathscr{C}_{N}$. The network $N$
in Fig. 9(A), for example, is not phylogenetic (but semi-regular). Suppression
of any vertex with in- and outdegree $1$ yields a network $N^{\prime}$ with
$N\not\simeq N^{\prime}$ but $\mathscr{C}_{N}=\mathscr{C}_{N^{\prime}}$. We
will see in the following that there is a 1-to-1 correspondence between
clustering systems and cluster networks. To show this, we will need the
following technical result that relates the occurrence of vertices with equal
clusters in such networks to the structure of the Hasse diagram.

######  Lemma 4.24.

Let $N$ be a cluster network with clustering system $\mathscr{C}$. Then, for
every cluster $C\in\mathscr{C}$, there is either exactly one vertex $v\in
V(N)$ with $\operatorname{\mathtt{C}}_{N}(v)=C$ or there are exactly two
vertices $u,v\in V(N)$ with
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)=C$. The
latter case occurs if and only if $C$ has indegree at least $2$ in
$\mathfrak{H}(\mathscr{C})$. Moreover, in this case, $u$ and $v$ are adjacent
in $N$.

###### Proof.

By Theorem 4.19, $N$ is phylogenetic, separated, and semi-regular, i.e., it
satisfies (PCC) and is shortcut-free. By Lemma 4.20, it only remains to show
that there are two distinct vertices $u,v\in V(N)$ with
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)=C$ if and
only if $C$ has indegree at least $2$ in $\mathfrak{H}(\mathscr{C})$.

Suppose $C=\operatorname{\mathtt{C}}_{N}(v)=\operatorname{\mathtt{C}}_{N}(u)$
for two distinct vertices $v,u\in V(N)$ and assume w.l.o.g. that
$u\prec_{N}v$. By Lemma 4.5, $u$ must be the unique child of $v$. Since $N$ is
phylogenetic, this implies that $\operatorname{indeg}_{N}(v)\geq 2$. Thus let
$v_{1}$ and $v_{2}$ be two distinct parents of $v$. Since $N$ is shortcut-free
and by Obs. 2.6, $v_{1}$ and $v_{2}$ are $\prec_{N}$-incomparable. Using
(PCC), we conclude that $C_{1}\coloneqq\operatorname{\mathtt{C}}_{N}(v_{1})$
and $C_{2}\coloneqq\operatorname{\mathtt{C}}_{N}(v_{2})$ are distinct and none
of them is contained in the other. Moreover, we have $C\subseteq C_{1}\cap
C_{2}$ by Lemma 3.33, and thus, and $C\subsetneq C_{1},C_{2}$. Suppose there
is $C^{\prime}\in\mathscr{C}$ such that $C\subsetneq C^{\prime}\subsetneq
C_{1}$. Let $v^{\prime}\in V(N)$ be a vertex with
$\operatorname{\mathtt{C}}_{N}(v)=C^{\prime}$. By Obs. 4.3, we have
$u\prec_{N}v^{\prime}\prec_{N}v$. Therefore, $(v,u)\in V(N)$ must be a
shortcut; a contradiction. Hence, there is no $C^{\prime}\in\mathscr{C}$ with
$C\subsetneq C^{\prime}\subsetneq C_{1}$ and $C_{1}$ must be a parent of $C$
in $\mathfrak{H}(\mathscr{C})$. By similar arguments, $C_{2}$ is a parent of
$C$ in $\mathfrak{H}(\mathscr{C})$, which together with $C_{1}\neq C_{2}$
implies that $C$ has indegree at least $2$ in $\mathfrak{H}(\mathscr{C})$.

Conversely, suppose $C$ has at least two distinct parents $C_{1}$ and $C_{2}$
in $\mathfrak{H}(\mathscr{C})$. Hence, it holds $C\subsetneq C_{1}$ and
$C\subsetneq C_{2}$ and none of $C_{1}$ and $C_{2}$ is contained in the other.
Let $v,v_{1},v_{2}\in V(N)$ be vertices with
$C=\operatorname{\mathtt{C}}_{N}(v)$,
$C_{1}=\operatorname{\mathtt{C}}_{N}(v_{1})$, and
$C_{2}=\operatorname{\mathtt{C}}_{N}(v_{2})$. Clearly, $v$, $v_{1}$, and
$v_{2}$ are pairwise distinct. By Obs. 4.3, we have $v\prec_{N}v_{1}$ and
$v\prec_{N}v_{2}$, i.e., there are a $v_{1}v$-path $P_{1}$ and a $v_{2}v$-path
$P_{2}$ in $N$. Let $v^{\prime}$ be the $\preceq_{N}$-maximal vertex in
$P_{1}$ that is also a vertex in $P_{2}$. We distinguish the two cases
$v^{\prime}=v$ and $v^{\prime}\neq v$. If $v^{\prime}=v$, then $v$ has a
parent in each of $P_{1}$ and $P_{2}$ which are distinct by construction. Thus
$v$ is a hybrid vertex. Since moreover $N$ is separated, $v$ has a unique
child $u$. By Obs. 3.36, this implies
$\operatorname{\mathtt{C}}_{N}(u)=\operatorname{\mathtt{C}}_{N}(v)=C$. Now
suppose $v^{\prime}\neq v$. Lemma 3.33 and
$v\prec_{N}v^{\prime}\preceq_{N}v_{1},v_{2}$ imply $C\subseteq
C^{\prime}\coloneqq\operatorname{\mathtt{C}}_{N}(v^{\prime})$,
$C^{\prime}\subseteq C_{1}$ and $C^{\prime}\subseteq C_{2}$. Since none of
$C_{1}$ and $C_{2}$ is contained in the other, we must have $C\subseteq
C^{\prime}\subsetneq C_{1}$ and $C\subseteq C^{\prime}\subsetneq C_{2}$. Since
$C_{1}$ and $C_{2}$ are parents of $C$ in $\mathfrak{H}(\mathscr{C})$, the
latter is only possible if $C=C^{\prime}$. Hence, in both cases, there are two
distinct vertices in $N$ with cluster $C$. ∎

######  Theorem 4.25.

For every clustering system $\mathscr{C}$, there is a unique cluster network
$N$ with $\mathscr{C}=\mathscr{C}_{N}$. It is obtained from the unique regular
network $\mathfrak{H}(\mathscr{C})$ of $\mathscr{C}$ by applying
$\operatorname{\textsc{expd}}(v)$ to all hybrid vertices. In particular, $N$
is the unique semi-regular separated phylogenetic network with clustering
system $\mathscr{C}$.

###### Proof.

By Thm. 4.8, the unique regular network $\mathfrak{H}(\mathscr{C})$ is
shortcut-free, satisfies (PCC), and has no vertex with outdegree $1$. In
particular, $\mathfrak{H}(\mathscr{C})$ is phylogenetic. Now let $N$ be the
network obtained from $N$ by repeatedly applying
$\operatorname{\textsc{expd}}(w)$ to some hybrid vertex whose outdegree is not
$1$ until no such vertex exists. Clearly this is achieved by applying
$\operatorname{\textsc{expd}}(w)$ to all hybrid vertices $w\in V(N)$ since
they all satisfy $\operatorname{outdeg}_{\mathfrak{H}(\mathscr{C})}(w)\neq 1$
and, moreover, no expansion step introduces new such vertices but reduces
their number by $1$. We can repeatedly (i.e., in each expansion step) apply
Lemma 3.13 to conclude that the resulting digraph $N$ is a phylogenetic
network, Lemma 3.13 to conclude that $N$ satisfies
$\mathscr{C}_{N}=\mathscr{C}_{\mathfrak{H}(\mathscr{C})}=\mathscr{C}$, and
Cor. 4.14 to conclude that $N$ is semi-regular. In particular, by
construction, all hybrid vertices in $N$ have outdegree $1$, i.e., $N$ is
separated. By Theorem 4.19, $N$ is a cluster network.

It remains to show that $N$ is the unique cluster network with clustering
system $\mathscr{C}$. To this end, let $\tilde{N}$ be a cluster network with
$\mathscr{C}=\mathscr{C}_{\tilde{N}}$. By Theorem 4.19, both $N$ and
$\tilde{N}$ are semi-regular, shortcut-free, and phylogenetic. Moreover, by
Lemma 4.24, for every cluster $C\in\mathscr{C}$, $C$ has multiplicity $2$ in
$\mathscr{M}_{N}$ if and only if $C$ has indegree at least $2$ in
$\mathfrak{H}(\mathscr{C})$ if and only if $C$ has multiplicity $2$ in
$\mathscr{M}_{\tilde{N}}$; and multiplicity $1$ in both $\mathscr{M}_{N}$ and
$\mathscr{M}_{\tilde{N}}$ otherwise. Hence, we have
$\mathscr{M}_{N}=\mathscr{M}_{\tilde{N}}$. By Theorem 4.23, we conclude that
$N\simeq\tilde{N}$, and thus, $N$ is the unique cluster network. In