{'fraction_non_alphanumeric': 0.04527137640095706, 'fraction_numerical': 0.008961927549007261, 'mean_word_length': 3.5977998649039855, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Trinets encode tree-child and level-2 phylogenetic networks

Phylogenetic networks generalize evolutionary trees, and are commonly used to represent evolutionary histories of species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. Recently, there has been great interest in trying to develop methods to construct rooted phylogenetic networks from triplets, that is rooted trees on three species. However, although triplets determine or encode rooted phylogenetic trees, they do not in general encode rooted phylogenetic networks, which is a potential issue for any such method. Motivated by this fact, Huber and Moulton recently introduced trinets as a natural extension of rooted triplets to networks. In particular, they showed that level-1 phylogenetic networks are encoded by their trinets, and also conjectured that all"recoverable"rooted phylogenetic networks are encoded by their trinets. Here we prove that recoverable binary level-2 networks and binary tree-child networks are also encoded by their trinets. To do this we prove two decomposition theorems based on trinets which hold for all recoverable binary rooted phylogenetic networks. Our results provide some additional evidence in support of the conjecture that trinets encode all recoverable rooted phylogenetic networks, and could also lead to new approaches to construct phylogenetic networks from trinets.


Introduction
Phylogenetic trees are routinely used in biology to represent the evolutionary relationships between a given set of species. More formally, for a set X of species, a rooted phylogenetic tree is a rooted (graph theoretical) tree that has no indegree-1 outdegree-1 vertices, and in which the leaves are bijectively labelled by the elements in X [27]; a (rooted) triplet is a phylogenetic tree with three leaves. Given a rooted phylogenetic tree T and three of its leaves, there is unique triplet spanned by those leaves that is contained in T . A fundamental result in phylogenetics states that T is in fact encoded by its triplets, that is, T is the unique phylogenetic tree containing the set of triplets that arises from taking all combinations of three leaves in T [9]. This result is important since it has led to various approaches to constructing phylogenetic trees from set of triplets cf. e.g. [14,15,18].
Recently, there has been some interest in using networks rather than trees to represent evolutionary relationships between species that have undergone reticulate evolution [17,25]. This is motivated by the fact that processes such as hybridization, recombination and lateral gene transfer can lead to evolutionary histories which are not best represented by a tree. Formally, a (rooted phylogenetic) network for a set X of species is a directed acyclic graph that has a single root, has no indegree-1 outdegree-1 vertices, and has its leaves bijectively labelled by X (see Section 2 for full definitions concerning networks). Such a network is called binary if all vertices have indegree and outdegree at most two and all vertices with indegree two have outdegree one. In addition, a binary network is called level -k [11,12,13,14,18,19] if each biconnected component has at most k indegree-2 vertices, and it is called tree-child [6, 8,21,29] if each non-leaf vertex has at least one child which has indegree 1. Note that a rooted phylogenetic tree is a network, but that networks are more general since they can represent evolutionary events where species combine rather than speciate.
As with phylogenetic trees, efficient algorithms have been developed which, given a set of triplets, aim to build a network that contains this set (see e.g. [2,14,15,22]). However, these algorithms share a common weakness in that, even if all of the triplets within a given network are taken as input, there is no guarantee that the original network will be reconstructed. This is because, in contrast to trees, the triplets in a network do not necessarily encode the network [13]. For example, Figure 1 presents three different networks that all contain the same set of triplets. Note that a similar observation has been made concerning the set of trees and set of clusters displayed by a network (see e.g. [17,20]).
Motivated by this problem, Huber and Moulton [16] recently proposed a possible alternative way to encode rooted phylogenetic networks by introducing a natural extension of rooted triplets to networks. More specifically, a trinet is a rooted phylogenetic network on three leaves. As with the triplets in a tree, a network contains or "exhibits" a trinet on every three leaves (see Section 2). For example, Figure 2 presents a phylogenetic network and four of the trinets that it exhibits. The main result in [16] implies that level-1 networks encoded by their trinets. Moreover, it is conjectured that any "recoverable" network (a network that satisfies some relatively mild condition which we recall below) is also encoded by its trinets. Here, we provide some evidence in support of this conjecture by showing that recoverable level-2 and tree-child networks are also encoded by their trinets.
We now give an overview of the rest of this paper, in which all networks are assumed to be binary. After presenting some preliminaries in Section 2, we begin by studying the relationship between the structure of a network and the trinets that it exhibits. In particular, in Section 3 we present two decomposition theorems for general networks. Essentially, these two theorems state that the cut-arcs of a network (that is, arcs whose removal disconnect the network) can be directly deduced from its set of trinets (Theorem 1), and that a network is encoded by its trinets if and only if each of its biconnected components is encoded by its trinets (Theorem 2). In tandem, these theorems essentially restrict the problem of deciding whether or not trinets  encode networks to the class of networks that do not have any cut-arcs apart from pendant arcs (so-called "simple" networks).
By restricting our attention to simple networks, in Section 4 we show that a recoverable level-2 network is always encoded by its trinets (Corollary 1). To do this, we use the concept of "generators" for level-k networks, using the generators for level-2 networks presented in [18]. In Section 5, we then use alternative techniques to prove that tree-child networks are also encoded by their trinets (Theorem 4). Note that this class of networks includes the class of regular networks [1]. Thus it is interesting to note that a regular network is encoded by the set of trees 1 that it contains [28], but that this is not the case for tree-child networks (e.g. all of the networks in Figure 1 contain the same set of trees). We conclude with a discussion of our results, two corollaries, and some possible future directions in Section 6.
Ultimately, it is hoped that the results presented in this paper will lead to new methods for constructing phylogenetic networks. In principle it should be straight-forward to infer lowlevel trinets for biological datasets consisting of molecular sequences using existing methods to construct phylogenetic networks. For example, given a multiple sequence alignment, the most parsimonious or most likely level-1 or level-2 trinet for every sub-alignment of three sequences could be computed using, e.g., methods described in [23,24], which becomes computationally tractible since there are a bounded number of such trinets (under certain natural restrictions, see Sections 2 and 6). The structural results in this paper, such as the decomposition theorems presented in Section 3, could then be used to help design algorithms to construct networks from the trinets inferred in this way. Note that this has the potential advantage that 'breakpoints' need not be computed for the multiple alignment, a first (and sometimes quite difficult) step that is commonly required for constructing phylogenetic networks from phylogenetic trees or clusters (cf. e.g. [26, Section 2]).

Preliminaries
Throughout the paper, X is a finite set. As mentioned in the introduction, a rooted phylogenetic network on X is a directed acyclic graph with a single indegree-0 vertex (the root) and a bijective labelling of its outdegree-0 vertices (leaves) by the elements of X. We identify each leaf with its label. A phylogenetic network is binary if all vertices have indegree and outdegree at most 2 and all vertices with indegree 2 have outdegree 1. We will often refer to a rooted phylogenetic network simply as a phylogenetic network or a network for short. See Figures 1,2  and 3 for examples. Let u and v be two vertices of a phylogenetic network N . If (u, v) is an arc of N , then we say that u is a parent of v and that v is a child of u. Furthermore, we write u ≤ N v and say that v is below u, if there is a directed path from u to v in N , or u = v. For two leaves x and y, we say that x is below y if the parent of x is below the parent of y. For an arc a = (u, v) and a vertex w, we say that w is below a if w is below v.
Let D be a directed graph with a single root ρ. The indegree of a vertex v of D is denoted δ − (v) and v is said to be a reticulation vertex or a reticulation if δ − (v) ≥ 2. The reticulation number of D is defined as Hence, the reticulation number of a binary network is simply the number of its reticulation vertices.
We say that a vertex v of D is a cut-vertex if its removal disconnects the underlying undirected graph of D. Similarly, an arc a of D is a cut-arc if its removal disconnects the underlying undirected graph of D. A directed graph is called biconnected if it has no cut-vertices. A biconnected component is a maximal biconnected subgraph (i.e. a biconnected subgraph that is not contained in any other biconnected subgraph). Note that, by this definition, each cut-arc is a biconnected component. We call these the trivial biconnected components. Thus, rephrasing the definitions given in the introduction, a phylogenetic network is level-k if each biconnected component has reticulation number at most k, and it is tree-child if every non-leaf vertex of the network has at least one child that is not a reticulation.
Given a nontrivial biconnected component B, we say that B is redundant if it has only one outgoing arc and we say that B is strongly redundant if it has only one outgoing arc (u, v) and all leaves of the network are below v. We say that a phylogenetic network N is recoverable if it has no strongly redundant biconnected components (see e.g. Figure 3). We remark that all level-1 networks are recoverable [16]. Moreover, neither level-1 nor tree-child networks can have any redundant biconnected components. On the other hand, there are level-2 networks that do have redundant (and strongly redundant) biconnected components (see Figure 3).
A trinet is a phylogenetic network with three leaves. Ignoring leaf-labels, there are 14 distinct level-1 trinets, 8 of which are binary [16]. Note that there is an infinite number of level-2 trinets, and even of recoverable level-2 trinets. On the other hand, it is not too difficult to see that the number of level-2 trinets without redundant biconnected components is finite (in fact, the number of level-k trinets without redundant biconnected components is bounded by a function of k). We shall return to this point in Section 6. a b c a b c Figure 3. The phylogenetic network on the left is not recoverable because it has a strongly redundant biconnected component. The phylogenetic network on the right is recoverable, because its only nontrivial biconnected component, although redundant, is not strongly redundant.
Given a network N on X and X ⊆ X, a lowest stable ancestor LSA(X ) is defined as a vertex w / ∈ X of N for which all paths from the root to any x ∈ X pass through w, and such that no vertex below w has this property. A lowest common ancestor of X in N is a vertex w such that w ≤ N x for all x ∈ X and no vertex below w has this property. Note that the lowest stable ancestor is unique but that this not necessarily the case for a lowest common ancestor [10]. If a lowest common ancestor of X is unique, then we denote it by LCA(X ). For two vertices u, v, we write LSA(u, v) as shorthand for LSA({u, v}) and LCA(u, v) as shorthand for LCA({u, v}). The following easily proven fact will be useful later on. Observation 1. If N is a phylogenetic network on X and X ⊆ X with X ≥ 2, then there exist x, y ∈ X such that LSA(x, y) = LSA(X ).
Given a phylogenetic network N on X and {x, y, z} ⊆ X, the trinet on {x, y, z} exhibited by N is defined as the trinet obtained from N by deleting all vertices that are not on any path from LSA({x, y, z}) to x, y or z and subsequently suppressing all indegree-1 outdegree-1 vertices and parallel arcs. See Figure 2 for some examples. We note that this definition is equivalent to the definition of "display" in [16] but we call it "exhibit" to clearly distinguish it from other usages of "display" (in particular, the definition of when a network displays a tree or triplet). We will often (implicitly) use the following observation.
Observation 2. Given a phylogenetic network N on X and {x, y, z} ⊆ X, the trinet on {x, y, z} exhibited by N can be obtained from N by removing all leaves except x, y and z and repeatedly applying the following operations until none is applicable: • deleting all unlabelled outdegree-0 vertices; • deleting all indegree-0 outdegree-1 vertices; • suppressing all indegree-1 outdegree-1 vertices; • suppressing all parallel arcs; and • suppressing all strongly redundant biconnected components.
The following observation, linking lowest common ancestors in networks and their exhibited trinets, will be used in the proof of Theorem 4.
Observation 3. Suppose that u is the unique lowest common ancestor of two leaves x and y in a network N and that P is a trinet exhibited by N that contains x and y. Then, P contains u (where we consider P as being obtained from N as described in Observation 2) and u is the unique lowest common ancestor of x and y in P .
We now make a definition that will be crucial for the decomposition theorems in Section 3 (note that a somewhat related definition appeared in [14]). In the next section, we will make use of the following easily proven fact that relates the CA-sets of a network to the CA-sets of its exhibited trinets.
Observation 4. Let N be a phylogenetic network on X and P the trinet on {x, Given two phylogenetic networks N and N on X, we write N = N if there is a graph isomorphism between N and N that preserves leaf labels, i.e. if there exists a bijective function f : V (N ) → V (N ) such that f (x) = x for each leaf x of N and such that for every u, v ∈ V (N ) holds that (u, v) is an arc of N if and only if (f (u), f (v)) is an arc of N .
We use T n(N ) to denote the set of all trinets exhibited by a phylogenetic network N . A phylogenetic network N is encoded by its set of trinets T n(N ) if there is no recoverable phylogenetic network N = N with T n(N ) = T n(N ).

Decomposition theorems for trinets
It is well known that any graph can be decomposed into its biconnected components. We begin by showing that trinets can be used to recover this decomposition of binary phylogenetic networks. Note that similar results have been proven for triplets in [19] and for quartets in unrooted phylogenetics networks [11]. Theorem 1. Let N be a recoverable binary phylogenetic network on X, and A ⊂ X. Then, A is a CA-set of N if and only if |A| = 1 or, for all z ∈ X \ A and x, y ∈ A with x = y, {x, y} is a CA-set of the trinet on {x, y, z} exhibited by N .
To prove the "only if" direction, assume that A is a CA-set of N . Let z ∈ X \ A and x, y ∈ A with x = y. There exists a unique trinet P on {x, y, z} in T n(N ). Since A is a CA-set of N , it follows from Observation 4 that {x, y} is a CA-set of P and we are done. It remains to prove the "if" direction. Assume that for all z ∈ X \ A and x, y ∈ A with x = y, {x, y} is a CA-set of the trinet on {x, y, z} exhibited by N . Assume that A is not a CA-set of N .
First assume that the arc entering LSA(A) is a cut-arc a. By Observation 1, there exist x, y ∈ A such that LSA(x, y) = LSA(A). Moreover, there exist z ∈ X \ A below a because A is not a CA-set. Consider the trinet P on {x, y, z} exhibited by N . By the definition of "exhibit", all paths from LSA({x, y, z}) and hence from LSA(x, y) to x, y and z are retained in P . It follows that, z is also below LSA(x, y) in P . This means that {x, y} is not a CA-set of P , which is a contradiction. Hence, there is no cut-arc entering LSA(A), which implies that LSA(A) is in a nontrivial biconnected component. Now, let B be the nontrivial biconnected component of N containing LSA(A). Let r B be the root of B. Choose x, y ∈ A that are below different cut-arcs leaving B such that LSA(x, y) = LSA(A). First, we observe that there is no leaf z ∈ X \ A below LSA(x, y), because otherwise we could argue as before that the trinet on {x, y, z} exhibited by N does not have {x, y} as a CA-set. Pick z ∈ X \ A arbitrarily below a cut-arc leaving B. Note that neither x nor y is below this cut-arc because otherwise z would be below LSA(x, y).
By assumption, the trinet P on {x, y, z} exhibited by N has {x, y} as a CA-set. This means that P has a cut-arc a such that x and y are below a but z is not. Consider the arc a = (u, v) of N corresponding to cut-arc a of P . Observe that v is the lowest stable ancestor of x and y in N , because all paths from LSA(x, y), to x and y are retained in P . Also observe that a is not a cut-arc in N because x, y and z are below three different cut-arcs leaving a biconnected component B. Thus, a is some arc of B and the operations from Observation 2 that turn N into P destroy the biconnectivity of B. Observe that the only one of these operations that does not preserve biconnectivity is the deletion of unlabelled outdegree-0 vertices in case they have indegree greater than 1. We claim that there then exists a reticulation r in N with directed paths from v to r and from some ancestor of u to r not passing through a (see Figure 4).
To prove this claim, first note that, since a is not a cut-arc of N , there is some undirected path U in N from v to u not passing through a . Consider the last vertex r of U that is below v. Clearly, r is a reticulation. Let p be the next vertex on path U . Then p is not below v. Clearly, p is below the root and, since p is not below v, the path from the root to p does not pass through a . It follows that r is a reticulation with directed paths from v to r and from some ancestor of u to r not passing through a . Now, consider any leaf y below r. First observe that y ∈ A because no leaves z ∈ X \ A are below LSA(x, y). However, then we obtain a contradiction because LSA(x, y ) is closer to the root than LSA(x, y) = v.
Note that we could have used [19,Lemma 3] in the proof of the last result. However, we presented the above proof since it is shorter, self-contained and provides some insight into how to make arguments using trinets. We also note that for an arbitrary binary recoverable network N there is not necessarily a bijection between the cut-arcs of N and the CA-sets of N because different cut-arcs might correspond to the same CA-set. However, it is easy to see that the following related observation does hold.
Observation 5. If N is a binary phylogenetic network without redundant biconnected components, then there is a bijection between the cut-arcs of N and the CA-sets of N .
We now turn to showing that, roughly speaking, a binary network is encoded by its trinets if and only if each of its biconnected components is encoded by its trinets. To this end, let N be a phylogenetic network and B a nontrivial biconnected component with b outgoing cut-arcs Proof. To prove the "only if" direction of the theorem, suppose that N is a recoverable binary phylogenetic network on X that is encoded by its trinets T n(N ). Consider any nontrivial biconnected component B of N with at least four outgoing cut-arcs. For contradiction, suppose that N B is not encoded by T n(N B ), i.e. there exists a recoverable network N B = N B such that T n(N B ) = T n(N B ). By Theorem 1, N B has the same CA-sets as N B . Moreover, since T n(N B ) = T n(N B ) and N B has no redundant biconnected components, it follows quite easily that N B has no redundant biconnected components. Combining these observations, we see that N B consists of one nontrivial biconnected component with leaves attached to it by cut-arcs. Let B be the nontrivial biconnected component of N B . Let N be the result of replacing B by B in N . We will show that T n(N ) = T n(N ), which will contradict the fact that N is encoded by T n(N ), since N is clearly recoverable.
To show that T n(N ) = T n(N ), let P ∈ T n(N ) and let x, y and z be the leaves of P . If x, y and z are all below different cut-arcs, or all below the same cut-arc leaving B, then clearly P ∈ T n(N ) since the only difference between N and N is that B is replaced by B , and T n(N B ) = T n(N B ). Now suppose that P contains leaves x, y that are below the same cut-arc leaving B and a leaf z below a different cut-arc leaving B. Then consider a fourth leaf q that is below a third cut-arc leaving B. Since T n(N B ) = T n(N B ), the trinets on {x, z, q} exhibited by N and N are the same. Hence, the binet (phylogenetic network on two leaves) on {x, z} exhibited (defined in the same way as for trinets) by N and by N is the same. Hence, the trinet on {x, y, z} exhibited by N and by N is the same, and so P ∈ T n(N ). The case that P contains one or more leaves that are not below B can be handled similarly.
It therefore easily follows that T n(N ) = T n(N ), as required.
To prove the "if" direction, let N be a recoverable phylogenetic network on X such that for each nontrivial biconnected component B with at least four outgoing cut-arcs the network N B is encoded by T n(N B ). Let N be a recoverable network on X with T n(N ) = T n(N ). We will show that N = N . First, we show that N Bρ = N B ρ . If b ≥ 4, this is true by assumption (because T n(N Bρ ) = T n(N B ρ ) and by assumption N Bρ is encoded by T n(N Bρ ). Moreover, b ≥ 2 since N is recoverable. For b = 3 the statement is trivial. Hence, the only case left is b = 2. Consider two leaves x, y of N that are below the same cut-arc leaving B ρ and a leaf z that is below the other cut-arc leaving B ρ . These leaves exist since |X| ≥ 3. Consider the trinet P in T n(N ) on {x, y, z}. Let B ρ (P ) be the biconnected component of P containing the root of P . Then, N Bρ(P ) = N Bρ . Moreover, since N also exhibits P , N Bρ(P ) = N B ρ . It follows that N Bρ = N B ρ . Now, let i ∈ {1, . . . , b}. We will show that N i = N i . Since |X i | < |X|, this follows by induction if (a) N i and N i are recoverable and (b) |X i | ≥ 3. To show the general case, consider the networks R i and R i obtained from N i and N i respectively by suppressing all strongly redundant biconnected components. Then, R i and R i are recoverable. Hence, if |X i | ≥ 3, R i = R i by induction. If |X i | = 1, then clearly R i = R i because both consist of a single leaf. The only case left is |X i | = 2. Consider any leaf z ∈ X \ X i and the trinet P on X i ∪ {z}. By Observation 4, X i is a CA-set of P . Let P * be the result of deleting all vertices that are not below LSA(X i ). Then, P * = R i . Moreover, since P is exhibited by N , we also have Figure 5. The four level-2 generators. Each side is labelled by a capital letter.
Hence, in all cases, R i = R i . So, to complete the proof that N i = N i , it remains to show that N i and N i have the same strongly redundant biconnected components, in the same order. To prove this, we distinguish the cases |X i | = 1 and |X i | ≥ 2.
First, suppose |X i | = 1, say X i = {x}. Let y, z ∈ X \ X i such that LSA(u i ) ≤ N z. Consider the trinet P on {x, y, z}. Let a be the cut-arc in P such that x is below a, y and z are not below a and there is no cut-arc a with this property with a below a . Consider the network P x obtained from P by deleting all vertices that are not below a. Then, P x = N i = N i . Now suppose that |X i | ≥ 2. Let z ∈ X \ X i such that LSA(u i ) ≤ N z and let x, y ∈ X i such that LSA(x, y) = LSA(X ) (such x, y exist by Observation 1). Consider the trinet P on {x, y, z}. Consider the cut-arc a of P such that x and y are below a, z is not below a and such that there is no cut-arc a with this property with a below a . Let D be the directed graph obtained from P by deleting all vertices that are not below a and deleting all vertices that are below LSA(x, y). Then, D is isomorphic to the strongly redundant biconnected components of N i and of N i . Now, since R i = R i and N i and N i have the same strongly redundant biconnected components, in the same order, as required.

Trinets encode level-2 networks
In this section we show that binary recoverable level-2 networks are encoded by their trinets.
To do this, we will consider each biconnected component of such a network separately, and will apply some structural results concerning these components that are presented in [18]. Throughout the section, we restrict to binary networks.
We begin by recalling some relevant definitions. A level-k phylogenetic network is called a simple level -k network if it contains one nontrivial biconnected component B containing exactly k reticulations and no cut-arcs other than the ones leaving B (see the left of Figure 6 for an example of a simple level-2 network). A (binary) level-k generator is a directed acyclic biconnected multigraph with exactly k reticulations with indegree 2 and outdegree at most 1, a single vertex with indegree 0 and outdegree 2, and apart from that only vertices with indegree 1 and outdegree 2. The arcs and outdegree-0 vertices of a generator are called its sides. For example, all level-2 generators are depicted in Figure 5.
Note that deleting all leaves of a simple level-k network N gives a level-k generator G N . We call G N the underlying generator of N . Conversely, N can be reconstructed from G N by "hanging leaves" from the sides of G N as follows (see van Iersel et al. [18]): • for each arc a of G N , replace a by a directed path with ≥ 0 internal vertices v 1 , . . . , v and, for each such internal vertex v i , add a leaf x i ∈ X and an arc (v i , x i ); and • for each indegree-2 outdegree-0 vertex v, add a leaf x ∈ X and an arc (v, x).
We say that a leaf x "is on side" s if it is hung on side s in this construction of N from G N . More precisely, for a leaf x ∈ X of a simple level-k network N with underlying generator G N and a side s of G N , we say that x is on side s if s is an indegree-2 outdegree-0 vertex of G N and (s, x) is an edge of N or if s is an edge (u, v) of G N and the parent of x in N lies on the directed path from u to v in N . Now, given a level-2 generator G, we call a set of sides of G a set of crucial sides if it contains all vertices with indegree 2 and outdegree 0 together with one arc of each pair of parallel arcs. Consider any simple level-2 network N on X with underlying generator G and a trinet P on X ⊆ X. We say that P is a crucial trinet of N if X contains at least one leaf on each side in some set of crucial sides of G. For example, Figure 6 depicts a simple level-2 network, one crucial trinet and two non-crucial trinets. The following observation can be verified by inspecting all level-2 generators in Figure 5.
Observation 6. If G is a level-2 generator, then it has a set of crucial sides of size at most 2.
Hence, every simple level-2 network N has at least one crucial trinet. Moreover, for every leaf x of N , there exists a crucial trinet of N containing x.
Before proving the main result of this section, we also state one other useful fact.
Observation 7. Let N be a simple level-k network, G its underlying generator and P ∈ T n(N ). Then, P is a crucial trinet of N if and only if P is a simple level-k network. Moreover, if P is a crucial trinet of N then G is its underlying generator.
Proof. Let N be any binary, simple level-2 network on X, with |X| ≥ 3. Assume that T n(N ) = T n(N ) for some recoverable network N . We will show that N = N .
We begin by showing that N is a binary, simple, level-2 network. First, it is a level-2 network because any level-k network with k > 2 has a level-k trinet with k > 2, but T n(N ) = T n(N ) contains only level-2 trinets. Second, N is simple network because its set of CA-sets equals the set of CA-sets of N by Theorem 1 and it has no redundant biconnected components because the trinets in T n(N ) = T n(N ) have no redundant biconnected components. Third, N is binary. Indeed, assume that N has a vertex with outdegree greater than 2 and let c 1 , c 2 , c 3 be three of its children. Then, consider three (not necessarily different) leaves x 1 , x 2 and x 3 below c 1 , c 2 and c 3 respectively. Then, any trinet containing x 1 , x 2 and x 3 exhibited by N is not binary, while all trinets in T n(N ) = T n(N ) are binary.  Figure 6. The underlying generator of simple level-2 network N is 2b (see Figure 5). Leaf x is on side G, y is on side H, z and z are on side E and q and q are on side A. Trinet P c , the trinet on {x, y, z}, is one of the four crucial trinets, which determine the side each leaf is on. Trinet P 1 on {x, z, z } and trinet P 2 on {y, q, q }, which are non-crucial trinets, determine the order of the leaves on each side. This is Case "G = 2b" in the proof of Lemma 3.
Now, let G be the underlying generator of N . First, we show that G is also the underlying generator of N . By Observation 6, N has at least one crucial trinet P c . By Observation 7, P c is a simple level-2 network and its underlying generator is G. Since T n(N ) = T n(N ), P c is also a trinet of N . Moreover, P c is a crucial trinet of N by Observation 7 because N is a simple level-2 network and P c is a simple level-2 network. Hence, G is the underlying generator of N , again by Observation 7.
The remainder of the proof is divided into four cases, based on the four level-2 generators 2a, 2b, 2c and 2d (see Figure 5 for these generators and the labels of their sides).
Case G = 2a. First, observe that there are no symmetries, i.e. no relabelling of the sides of 2a gives an isomorphic generator. Let x be the leaf on side F in N . Since x is then the leaf on side F in every crucial trinet of N , and since these crucial trinets are exhibited by N , and since there are no symmetries, it follows that x is also the leaf on side F in N . Now consider any side s = F of N and any leaf y on that side. Consider any crucial trinet P c of N containing y. Then y is on side s in P c and, since P c is exhibited by N and there are no symmetries, y is on side s in N . Hence, each leaf is on the same side in N as it is in N . It remains to show that the leaves on each side are in the same order in N and N . Consider a side s with at least two leaves and two leaves y, z on that side such that z is below y. It follows that z is below y in the crucial trinet on {x, y, z} and from that it follows that z is below y in N . We conclude that N = N since both networks have the same underlying generator, the same leaves on each side, and the same order of the leaves on each side.
Case G = 2b. Again, there are no symmetries. Let x be the leaf on side G, y the leaf on side H and z a leaf on some other side s (see Figure 6). Then, the trinet P c on {x, y, z} is crucial and, since there are no symmetries, it follows that leaves x, y, z are, respectively, on sides G, H, s in P c and hence in N . Consequently, all leaves are on the same side in N as in N . To see that they are in the same order, first consider two leaves z, z that are both on side C, D or E and consider the (non-crucial) trinet P 1 on {x, z, z }. Observe that P 1 is a simple level-1 network and that z and z are on the same side of P 1 . Moreover, if z is below z in N , then z is below z in P 1 , and hence z is below z in N . Now consider leaves q, q both on side A, B or F . Then the trinet P 2 on {y, q, q } is a simple level-1 network and, as before, if q is below q in N , then q is below q in P 2 and hence in N . It follows that N = N as required.
Case G = 2c. In this case there is some symmetry since sides A, C and E can be interchanged with B, D and F , respectively, to obtain an isomorphic generator. Similarly, sides C, H, D can be interchanged with E, G, F , respectively, again yielding an isomorphic generator. Let x be on side G, y on side H and z on some other side s in N . Then, the crucial trinet P c on {x, y, z} implies that x and y are on side G and H in N . Assume without loss of generality that x is on side G and y on side H in N . Then, again using trinet P c , it follows that z is on side Now, consider two leaves z, z that are both on side A, B, C or D. In view of the trinet on {y, z, z }, z and z are on the same side of N and in the same order. Similarly, for two leaves z, z that are both on side E or F . Also, the trinet on {x, z, z } implies that z and z are on the same side of N and in the same order. Thus, leaves that are on the same side in N are on the same side in N and in the same order. First assume that there is at least one leaf on side A in N and that the leaves that are on side A in N are on side A in N . Let a be one such leaf on side A. Then, any leaf c that is on side C in N is on side C in N by the trinet on {a, c, y} (because a and c are on the same side of this trinet, which is a simple level-1 network). Similarly, for leaf z on side s ∈ {B, D} in N holds that z is on side s in N by the trinet on {a, z, y} and for leaf z on side s ∈ {E, F } in N holds that z is on side s in N by the trinet on {a, z, x}. It follows that N = N because all leaves are on the same side, in the same order. Now assume that the leaves that are on side A in N are not on side A in N . Then these leaves are on side B in N . Then we can argue in exactly the same way that the leaves that are on sides B, C, D, E, F in N are on sides A, D, C, F, E in N . Hence, again N = N by relabelling the sides appropriately. Finally, if there is no leaf on side A, then there is a leaf on one of the sides B, C, D, E, F (since |X| ≥ 3) and we can apply similar arguments based on that leaf.
Case G = 2d. In this case, the only symmetry is that sides B and C can be interchanged with C and B, respectively. Let x be the leaf on side F , y a leaf on side B or C and z a leaf on some side s ∈ {A, B, C, D, E} in N . Note that there exists at least one such leaf z since |X| ≥ 3. Then, by the crucial trinet on {x, y, z}, x is on side F and y is on side B or C. Without loss of generality, y is on the same side in N as in N . So it follows that z is on side s in N . Hence, without loss of generality (i.e. by relabelling sides B and C if necessary), each leaf is on the same side in N as in N . Now consider two leaves z, z that are on the same side of N . Then the trinet on {x, z, z } implies that the order of z and z is the same in N as in N . We can conclude that N = N , since (after possibly relabelling sides B and C) both networks have the same leaves on the same sides in the same order.
Corollary 1. Every binary recoverable level-2 network N on X, with |X| ≥ 3, is encoded by its set of trinets T n(N ).
Proof. Follows from Theorem 2, Lemma 3 and the fact that level-1 networks are encoded by their trinets [16].

Trinets encode tree-child networks
In this section we show that tree-child networks are encoded by their trinets. We begin by presenting a definition and some observations. A directed path in a network is called a tree path if it does not contain any reticulations apart from possibly its first vertex. It is easily seen that from every vertex of a tree-child network there is a directed tree path that ends at some leaf.
Observation 8. Suppose that a network N has an arc (u, v) such that v is a reticulation and such that there is no directed path from u to the other parent of v. Suppose that there are tree paths from u to a leaf x and from v to a leaf y. Then, x and y are distinct and u is their unique lowest common ancestor in N .
Observation 9. Suppose that a network N contains a tree path from a reticulation r to a leaf x. Then, r is the only reticulation with a tree path to x. Moreover, suppose that p 1 and p 2 are the parents of r and that there is a directed path from p 1 to p 2 and a tree-path from p 1 to a leaf y. In addition, suppose that P is a trinet exhibited by N that contains x and y. Then, P contains r and a tree path from r to x.
Notice that, in Observation 9, the presence of leaf y in trinet P ensures that, in the process of obtaining P from N , the incoming arcs of r do not become parallel arcs, which would have to be suppressed. We are now ready to prove the main result of this section.
Theorem 4. Every binary tree-child network N on X, with |X| ≥ 3, is encoded by its set of trinets T n(N ).
Proof. The proof is by induction on the level k of the network. The induction basis for k = 1 has been shown in [16].
Let k ≥ 2 and assume that every binary, tree-child, level-(k − 1) network with at least three leaves is encoded by its trinets. Let N be a binary tree-child level-k network on X, with |X| ≥ 3, and let T = T n(N ). If |X| = 3, the theorem is obviously true, hence we can assume |X| ≥ 4. By Theorem 2, we may assume that N is a simple level-k network, i.e. it has a single nontrivial biconnected component B and no cut-arcs except for the ones leaving B.
Consequently, for each cut-arc (u, v) of N , the vertex v is a leaf. Now, let N be any recoverable network on X exhibiting T . We will show that N = N .
Suppose that x is a leaf of N at maximum distance from the root.
We first claim that the parent of x is a reticulation r such that there is no arc between the parents of r. To see this, first assume that r is not a reticulation. Then it has some other child s, which must be a leaf because otherwise there would be a tree-path from s to some leaf at greater distance from the root than x. However, in that case, the arc entering r would be a cut-arc, which is not possible because N is a simple level-k network. Hence, r is a reticulation. Now let p 1 and p 2 be the parents of r and assume that there is an arc (p 1 , p 2 ). Since p 2 is not a reticulation by the tree-child property, it has a second child s. Observe that, by the tree-child property, s cannot be a reticulation. Moreover, if s is not a leaf then it has two children, which must be leaves because x has maximum distance from the root. But, this is not possible because then the arc entering s would be a cut-arc. Hence, s is a leaf. However, then there are only two leaves below p 1 . Since |X| ≥ 4, there must be some arc entering p 1 and this is a cut-arc. This is again a contradiction to the fact that N is a simple level-k network. Thus, we conclude that the parent r of x is a reticulation and that there is no arc between the parents of r, as claimed.
Now, let T * be the result of removing all trinets containing x from T and let N * be the result of removing x from N and "cleaning up" the network by repeatedly deleting unlabelled outdegree-0 vertices and indegree-0 outdegree-1 vertices and suppressing indegree-1 outdegree-1 vertices, until a valid network is obtained. Note that it is not necessary to suppress parallel arcs and redundant biconnected components because these cannot arise by the described modifications since N is a tree-child network. Moreover, it can easily be seen that N * is again a tree-child network and has level k − 1. Since N has at least four leaves, N * has at least three leaves. Hence, by induction, N * is encoded by its trinets. It follows that removing x from N , and cleaning up in the same way as we did in N , also gives N * . Hence it only remains to show that the location of x in N and N is the same.
To this end, consider again the reticulation r in N of which x is the child and the parents p 1 and p 2 of r in N and in N . We need to show that the location of p 1 and p 2 is the same in N and N . We consider p 1 and note that the same arguments can be applied to p 2 . By the tree-child property, there is a tree path in N from p 1 to a leaf y. Thus, p 1 has outdegree 2 and hence it is not a reticulation. We distinguish three cases: (1) the parent g 1 of p 1 in N is a reticulation, (2) the parent g 1 of p 1 in N has outdegree 2, and (3) p 1 is the root ρ of N . See Figure 7 for some illustrations of these cases.
Case (1): The parent g 1 of p 1 in N is a reticulation. Let h be a parent of g 1 such that there exists no directed path from h to the other parent of g 1 . Then there is a tree path from h to some leaf q. Observe that q and y must be distinct and that h must be their unique lowest common ancestor in N by Observation 8. Moreover, the same holds in N * and consequently in N because removing leaf x and cleaning up as specified does not affect lowest common ancestors of other leaves. Consider the trinet P xyq ∈ T on {x, y, q}. In P xyq , h is also the unique lowest common ancestor of q and y by Observation 3. Moreover, in P xyq also, x is below the reticulation-child (which we can also call g 1 ) of h. This means that, because N exhibits P xyq , p 1 is below g 1 in N . We will show that p 1 is in fact the child of g 1 in N (just as it is in N ).
Let s be the child of p 1 other than r, in N . Note that s cannot be a reticulation by the tree-child property. If s is a leaf, then s = y is the child of g 1 in N * and, since we know that p 1 is below g 1 in N , p 1 can only be the child of g 1 in N . Now suppose that s is not a leaf in N . Then it has two children, and one of these children is y because otherwise y would be at greater distance from the root than x. Let n be the other child of x. (Note that n may or may not be a reticulation but that n cannot be equal to r because there is no arc between the parents of r (by the choice of x).) There is a tree path from n to some other leaf y . By Observation 8, s is the unique lowest common ancestor of y and y in N , in N and in N * .
In view of the trinet on {y, y , x}, it follows that LCA(x, y) ≤ N LCA(y, y ), i.e. p 1 ≤ N s. Since s is below p 1 and we already know that p 1 is below g 1 , we conclude that p 1 is the child of g 1 in N , as required.
Case (2): The parent g 1 of p 1 has outdegree 2. Then g 1 has some child a other than p 1 . Note that a cannot be equal to r because there is no arc between the parents of r. From a there is a tree path to some leaf q. As before, let s be the child of p 1 other than r, in N . There is again a tree path from s to some leaf y. If s is a leaf, then again s = y and, in view of the trinet on {x, y, q}, p 1 is the parent of y in N . Now we distinguish three subcases: (2.1) a = n and there is no directed path from s to a, (2.2) a = n and there is a directed path from s to a and (2.3) a = n (and consequently there is no directed path from s to a).
In Case (2.1), q and y are distinct and g 1 is their unique lowest common ancestor by Observation 8. We can now use similar arguments as in Case (1) to show that, in N , p 1 is the child of g 1 on the directed path to y.
In Case (2.2), a is the unique reticulation from which there is a tree path to q and g 1 is its parent from which there is a directed path to the other parent, in N, N * , N and in the trinet on {q, y, x}, by Observation 9. In view of this trinet, p 1 is below g 1 , on the directed path to y.
We can now use similar arguments as in Case (1) to show that, in N , p 1 is the child of g 1 on the directed path to y.
In Case (2.3), s is the unique lowest common ancestor of y and y in N, N * , N and in any trinet containing y, y by Observations 3 and 8. Also, g 1 is the parent of s in N * . In view of the trinet on {y, y , x}, p 1 has to be the parent of s = LCA(y, y ) in N . Thus, the location of p 1 is the same in N and N .
Case (3): p 1 is the root ρ of N . We define s, n, y, y as before. In this case, s is the root of N * . Hence, s cannot be a leaf. We can argue as in Case (1), concluding that p 1 is the root of N .
After applying exactly the same arguments to p 2 as we did to p 1 , it follows that, in all cases, the location of p 1 and p 2 is the same in N and N . Hence, the location of x is the same in N and N . It follows that N = N .

Discussion
We have proven that binary, recoverable level-2 and binary tree-child networks are encoded by their trinets, using two distinct methods of proof. We expect that our results could also hold for non-binary networks, and it would be of interest to verify this.
For settling the question if all recoverable phylogenetic networks are encoded by their trinets, the decomposition theorems in Section 3 will be useful since they essentially show that it is sufficient to answer this question for simple networks (i.e. networks having no cut-arcs apart from pendant arcs).
The proof for level-2 networks might be extended to show that higher level networks are encoded by their trinets (or be used to provide a counter-example). However, a new technique would have to be developed for k ≥ 4 since, for such k, there exist level-k networks that have no crucial trinets. Another difficulty is that the number of generators for level-k networks grows very rapidly (the number of level-k generators is at least 2 k−1 [11]) making a similar case analysis impossible in general. To prove that tree-child networks are encoded by trinets, we heavily depended on special properties of such networks, and we have not been able to find a way to extend our proof to even slightly more general networks (e.g. reticulation-visible networks [17]).
We note that a natural extension to the definition of "exhibit" is to define it as in Observation 2 but to suppress not only strongly redundant biconnected components, but all redundant biconnected components. If one then changes the definition of "recoverable" accordingly (i.e. to not having any redundant biconnected components), then it can be checked that all proofs in this paper still hold. This could be relevant when reconstructing phylogenetic networks via trinets, because the number of recoverable trinets then becomes bounded by a function of k.
It is also worth noting that Theorem 2, Theorem 3 and Theorem 4 can be combined to provide the following more general result.
Corollary 2. If X is a finite set with |X| ≥ 3 and N is the set of binary recoverable phylogenetic networks N on X for which each biconnected component of N either • has at most two reticulations; or • is tree-child; or • has at most three outgoing cut-arcs, then each N ∈ N is encoded by T n(N ).
In addition, we note that our results also yield some new metrics on level-2 and tree-child networks. These are of potential intesest since several metrics have been recently developed for special classes of networks (see e.g. [3,4,5,7,16]). More specifically, Corollary 2 immediately implies the following result (where ∆ denotes the symmetric difference of two sets). Finally, it could be of some interest to study some algorithmic issues related to the results that we have presented. For example, it would be interesting to know whether or not it is possible to reconstruct a recoverable (level-2 or tree-child) network from a set of trinets in polynomial time. Hopefully shedding light on this and related complexity problems could help provide new algorithms for constructing phylogenetic networks.