{'fraction_non_alphanumeric': 0.06217904466856364, 'fraction_numerical': 0.010742006633778391, 'mean_word_length': 3.402490549255059, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 72, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Comparison of Galled Trees

Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomial time algorithms for their reconstruction. In this paper we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence when they can be safely used to evaluate galled tree reconstruction methods.

more than one hybrid node. We have studied the relationships among these types of networks [35]: see Section 3 below. Now, various algorithms are known for reconstructing galled trees from either sequences [18][19][20][21], trees [33], distances [15], splits [23], or triplets [24], and metrics provide a safe way to assess phylogenetic reconstruction methods [28,32]. A few polynomial time computable metrics, like the path multiplicity or µ-distance [14] or Nakhleh's metric m for reduced networks [31], are known for tree child evolutionary networks [14], which include galled trees [35]. But most distance measures introduced so far were only known to be metrics on time consistent [4] tree-child phylogenetic networks, including the Robinson-Foulds distance [3,13,10], the tripartitions distance [13,29], the nodal and splitted nodal distances [9,11], and the triplets distance [11]. Since galled trees need not be time consistent, it was not known whether these distance measures define metrics for galled trees. On the other hand, Nakhleh gave in his PhD Thesis [30] two metrics for time consistent galled trees (based on splits and subtrees), but they are not metrics for arbitrary galled trees [14]. Recent simulation studies using the coalescent model with recombination show that only a small fraction of the simulated galled trees are time consistent [1].
In this paper, we study which of the aforementioned metrics for tree-child time consistent phylogenetic networks are also metrics for galled trees, under the various notions of the latter. We show that the Robinson-Foulds distance is only a metric in the binary case (in which the original galled trees, the level-1 networks and the 1-nested networks are the same objects); the tripartitions distance is a metric for 1-nested networks without any restriction on the degrees of their nodes (besides the general restriction that hybrid nodes have in-degree 2); and the splitted nodal distance is a metric in the semibinary (hybrid nodes of in-degree 2 and out-degree 1) case, in which the 1-nested and level-1 conditions define the same objects, but they are strictly weaker than the node-disjoint reticulation cycles condition). On the other hand, neither the nodal distance nor the triplets distance are metrics even for the most restrictive case of binary galled trees.

Preliminaries
Given a set S, a S-rDAG is a rooted directed acyclic graph with its leaves bijectively labeled in S.
A tree node of a S-rDAG N = (V, E) is a node of in-degree at most 1, and a hybrid node is a node of in-degree at least 2. A tree arc (respectively, a hybridization arc) is an arc with head a tree node (respectively, a hybrid node). A node v ∈ V is a child of u ∈ V if (u, v) ∈ E; we also say in this case that u is a parent of v. Two nodes are sibling when they have a common parent.
We denote by u v any path in N with origin u and end v. Whenever there exists a path u v, we shall say that v is a descendant of u and also that u is an ancestor of v. The length of a path is its number of arcs, and the distance from a node u to a descendant v of it is the length of a shortest path u v.
A node v is a strict descendant of a node u in N when every path from the root of N to v contains the node u; thus, v is a non-strict descendant of u when it is a descendant of u, but there exist paths from the root to v that do not contain u.
The following straightforward result, which is Lemma 1 in [10], will be used often, usually without any further notice. Lemma 1. Every strict ancestor of a node v is connected by a path with every ancestor of v.

⊓ ⊔
A tree path is a path consisting only of tree arcs, and a node v is a tree descendant of a node u when there is a tree path u v. The following result summarizes Lemma 3 and Corollary 4 in [13], and it will also be used many times in this paper without any further notice.  A subgraph of an undirected graph is biconnected when it is connected and it remains connected if we remove any node and all edges incident to it. A subgraph of a S-rDAG N is said to be biconnected when it is so in the undirected graph associated to N .

1-nested networks
In the rest of this paper, by a hybridization network on a set S we understand a S-rDAG without out-degree 1 tree nodes and with all its hybrid nodes of indegree 2. We shall also use the term hybridization network with n leaves to refer to a hybridization network on a set S with n elements. A phylogenetic tree is a hybridization network without hybrid nodes.
We shall say that a hybridization network is semibinary when its hybrid nodes have out-degree 1, and that it is binary when it is semibinary and its internal tree nodes have out-degree 2.
A hybridization network is: a galled tree, when every pair of reticulation cycles have disjoint sets of nodes [19]. -1-nested, when every pair of reticulation cycles have disjoint sets of arcs: by [35,Prop. 12], this is equivalent to the fact that every pair of reticulation cycles for different hybrid nodes have disjoint sets of intermediate nodes, and hence it corresponds to the notion of nested (hybridization) network with nesting depth 1 [25,27]. -level-1, when no biconnected component contains more than 1 hybrid node [16,26].
To simplify the language, from now on we shall write simply 1-nested network to mean a 1-nested hybridization network. The following two results summarize the main results on 1-nested networks proved in [35]. Proof. Let N be a 1-nested network. Let the galled-length of a path in N be the number of reticulation cycles which the arcs of the path belong to, and the galled-depth of a node in N the largest galled-length of a path from the root to it. Notice that the galled-depth of a hybrid node is equal to the galled-depth of the intermediate nodes of its reticulation cycle (because every arc in N belongs at most to one reticulation cycle). Assume that N does not contain any internal tree node with all its children tree leaves. Let h be a hybrid node of largest galled-depth in N , and let v denote either h or any intermediate node in the reticulation cycle K for h. It turns out that v has no hybrid descendant other than h, because any path from v to any other hybrid node h ′ = h would contain arcs belonging to at least one more reticulation cycle, making the galled-depth of h ′ larger than that of v.
Let v ′ be any descendant of v not belonging to K. Then, v ′ is a tree node and all its descendants are tree nodes, and therefore, since we assume that N does not contain any internal tree node with all its children tree leaves, we conclude that v ′ is a tree leaf.

Reductions for 1-nested networks
We introduce in this section a set of reductions for 1-nested networks. Each of these reductions, when applied to a 1-nested network with n leaves and m nodes, produces a 1-nested network with at most n leaves and less than m nodes, and given any 1-nested network with more than one leaf, it is always possible to apply to it some of these reductions. We shall also show that suitable subsets of these reductions have similar properties for binary and for semibinary 1-nested networks. Similar sets of reductions for other types of evolutionary networks have already been published [7,11].
The R reductions. Let N be a 1-nested network with n leaves, and let u be an internal node whose children are exactly the tree leaves i and j. The R i;j reduction of N is the network R i;j (N ) obtained by removing the leaves i and j, together with their incoming arcs, and labeling with i their former common parent u, which has become now a leaf; cf. Fig. 1. 3 It is clear that R i;j (N ) is a 1-nested network on S \ {j}, and it has 2 nodes less than N .
The T reductions. Let N be a 1-nested network with n leaves, and let u be an internal node with two tree leaf children i, j and at least some other child. The T i;j reduction of N is the network T i;j (N ) obtained by removing the leaf j together with its incoming arc; cf. Fig. 2. It is clear that T i;j (N ) is a 1-nested network on S \ {j} with 1 node less than N .   The G reductions. Let N be a 1-nested network with n leaves. Assume that N contains a reticulation cycle K consisting of two merge paths (u, v 1 , . . . , v k , h) and , with k k ′ (k ′ can be 0, in which case the corresponding merge path is simply the arc (u, h), but then k > 0), such that the hybrid node h has only one child, and it is the tree leaf i; -each intermediate node of K has only one child outside K, and it is a tree leaf: the child outside K of each v j is the leaf i j and the child outside Notice that u may have children outside K.
. . , v ′ k , h and the leaves i 1 , . . . , i k , i ′ 1 , . . . , i ′ k ′ , i, together with all their incoming arcs, and then adding to the node u two new tree leaf children, labeled i and i 1 ; cf. Fig. 3. Since we remove a complete reticulation cycle and all descendants of its intermediate nodes, and we replace it by two tree leaves, it is clear that . . , i ′ k ′ } (and in particular, if k = 1 and k ′ = 0, it has the same leaves as N ) with 2(k + k ′ ) nodes less than N . The G reductions. The G i;i 1 ,...,i k ;i ′ 1 ,...,i ′ k ′ reduction is the same as G i;i 1 ,...,i k ;i ′ 1 ,...,i ′ k ′ , except for the fact that in order to apply the G i;i 1 ,...,i k ;i ′ 1 ,...,i ′ k ′ reduction, the hybrid node h must be the leaf labeled i, instead of the leaf's parent: see Fig. 4. Then, Remark 1. In the G and G reductions, we leave two tree leaves attached to the former split node of the removed reticulation cycle in order to ensure that their application never generates an out-degree 1 tree node, while avoiding to increase unnecessarily the number of reductions.
Now we have the following basic applicability results.

Proposition 2.
Let N be a 1-nested network with more than one leaf. Then, at least one R, T , G, or G reduction can be applied to N , and the result is a 1-nested network.
Proof. If N contains some internal node v with at least two children that are tree leaves, say i and j, then we can apply to N the R i;j reduction, if the out-degree of v is 2, or the T i;j reduction, if its out-degree is greater than 2. Assume now that N does not contain any internal node with more than one tree leaf child: in particular, it does not contain any internal tree node with all its children tree leaves. Then, by Proposition 1, it contains a hybrid node h with all its children tree leaves (and therefore, by the current assumption on N , h either is a leaf itself or has out-degree 1), and such that all the intermediate nodes in its reticulation cycle K have all their children outside K tree leaves (and therefore each one of them has exactly one child outside K, by Lemma 3 and the current assumption on N ): let i 1 , . . . , i k and i ′ 1 , . . . , i ′ k ′ , with k k ′ , be the tree leaf children of the intermediate nodes of the two respective merge paths of K, listed in descending order of their parents along the path. Then, if h has out-degree 1 and its child is the tree leaf i, we can apply to N the The fact that the result of the application of a R, T , G, or G reduction to N is again a 1-nested network has been discussed in the definition of the reductions. Corollary 2. Let N be a semibinary 1-nested network with more than one leaf. Then, at least one R, T , or G reduction can be applied to N , and the result is a semibinary 1-nested network.
Proof. Since N does not contain hybrid leaves, we cannot apply to it any G reduction, and therefore, by Proposition 2, we can apply to it at least one R, T , or G reduction. Now, if we can apply a R i;j or T i;j reduction to N , the common parent of the tree leaves i and j is a tree node, and if we can apply a G i;i 1 ,...,i k ;i ′ 1 ,...,i ′ k ′ reduction, the split node of the reticulation cycle for the hybrid parent of i is a tree node (in both cases because hybrid nodes in N have out-degree 1), and therefore neither application produces a hybrid node of out-degree different from 1.

Corollary 3.
Let N be a binary 1-nested network with more than one leaf. Then, at least one R or G reduction can be applied to N , and the result is a binary 1-nested network.
Proof. Since N does not contain nodes with out-degree greater than 2, we cannot apply to it any T reduction, and thus, by Corollary 2, we can apply to it some R or G reduction. Now, if we apply a R reduction to N , we replace an internal tree node with two tree leaf children by a tree leaf, and the result is again binary. And if we apply to N a G reduction, the split node of the reticulation cycle we remove is, as in the semibinary case, a tree node, and in this case moreover without any child outside the reticulation cycle (because its out-degree must be 2), and after the application of the reduction it is still a tree node of out-degree 2.
We shall call the inverses of the R, T , G, and G reductions, respectively, the R −1 , T −1 , G −1 , and G −1 expansions, and we shall denote them by More specifically, for every 1-nested network N : if N contains a leaf labeled with i but no leaf labeled with j, then the R −1 i;j expansion can be applied to N , and R −1 i;j (N ) is obtained by unlabeling the leaf i and adding to it two tree leaf children labeled i and j; if N contains a tree leaf labeled with i that has some sibling, but no leaf labeled with j, then the T −1 i;j expansion can be applied to N , and T −1 i;j (N ) is obtained by adding to the parent of the leaf i a new tree leaf child labeled with j; -if N contains an internal node u with two tree leaf children i 1 , i, but no leaf labeled with i 2 , . . . , i k , i ′ 1 , . . . , i ′ k ′ (with k k ′ ), then the G −1 expansion can be applied to N , and G −1 (N ) is obtained by removing the leaves i, i 1 and their incoming arcs, and then starting in u two new internally disjoint paths with k and k ′ , respectively, intermediate nodes and ending in the same hybrid node h, and then adding to each intermediate node of these paths one new tree leaf and labeling these leaves (in descending order along the paths) with i 1 , . . . , i k and i ′ 1 , . . . , i ′ k ′ , respectively, and finally adding to h a new tree leaf child labeled with i; -the application condition for the G that the new hybrid node is itself a leaf labeled with i.
¿From these descriptions we easily see that the result of a R −1 , T −1 , G −1 or G −1 expansion applied to a 1-nested network is always a 1-nested network.
The following result is easily deduced from the explicit descriptions of the reductions and expansions. Moreover, if we apply a R, T , G, or G reduction to a 1-nested network N , then we can apply to the resulting network the corresponding inverse R −1 , T −1 , G −1 , or G −1 expansion and the result is a 1-nested network isomorphic to N . ⊓ ⊔

Proving metrics through reductions
Let C be throughout this section a class endowed with a notion of isomorphism ∼ =.
A metric on C is a mapping d : C × C → R satisfying the following axioms: for every A, B, C ∈ C, A metric space is a pair (X, d) where X is a set and d is a metric on X, taking as the notion of isomorphism in X the equality (that is, replacing ∼ = by = in the separation axiom).
All distances for hybridization networks considered in this paper are induced through representations, in the following sense. A representation of C in a metric space (X, d) is a mapping Given such a representation, the distance induced by d through F is the mapping The metric axioms for d imply that this mapping is non-negative, symmetric, it sends pairs of isomorphic members of C to 0, and it satisfies the triangle inequality. So, to be a metric on C, d F only needs to satisfy that d F (A, B) = 0 implies A ∼ = B. Now, it is straightforward to prove the following result (cf. [12,Prop. 1]).

Lemma 5. The mapping d F is a metric on C if, and only if, it is injective up to isomorphism, in the sense that, for every
Reductions as those introduced in the last section can be used to prove the injectivity up to isomorphism of a representation F and hence, as a consequence, that the corresponding d F is a metric; it was done for specific classes C of evolutionary networks and specific metrics in [7,11]. Since we shall use several times this kind of proofs in this paper, we make explicit here their general outline and the lemma they rely on.
Let C S ′ ,m denote a class of 1-nested hybridization networks of some specific type on a given set S ′ and with at most m nodes, and let C S ′ = m |S ′ | C S ′ ,m . Assume we have a set of reductions R 1 , . . . , R s that can be applied to members of C S ′ , with inverse expansions R −1 1 , . . . , R −1 s . Consider the following conditions on these reductions and expansions: (R1) For every N ∈ C S ′ ,m with |S ′ | 2, there exists some reduction R i that can be applied to N . (R2) For every N ∈ C S ′ ,m and for every reduction can be applied to N , then it can also be applied to N ′ and the resulting networks are isomorphic.
The definitions and results given in Section 4 imply that: -The set of all R and G reductions satisfy conditions (R1) to (R4) for the classes C S ′ of all binary 1-nested hybridization networks on a set S ′ .
-The set of all R, T , and G reductions satisfy conditions (R1) to (R4) for the classes C S ′ of all semibinary 1-nested hybridization networks on a set S ′ . -The set of all R, T , G, and G reductions satisfy conditions (R1) to (R4) for the classes C S ′ of all 1-nested hybridization networks on a set S ′ . Now, we have the following result.
Lemma 6. Let S be a given set of labels. For every S ′ ⊆ S, let C S ′ ,m and R 1 , . . . , R s be as above, and assume that these reductions satisfy conditions (R1) to (R4). For Then, F S is injective up to isomorphism if the following two conditions are satisfied for every S ′ ⊆ S, for every m |S ′ |, for every reduction R i , and for every N, In particular, if these two conditions are satisfied, then d Proof. We shall prove by induction on |S ′ | + m the following statement: The starting case, when |S ′ | + m = 2, is obvious because then S ′ must be a singleton, and there is, up to isomorphism, only one 1-nested hybridization network on a given singleton {i}: a single node labeled with i.
Let now N, N ′ ∈ C S ′ ,m be such that F S ′ (N ) = F S ′ (N ′ ) and |S ′ | + m 3. If |S ′ | = 1, we reason as in the starting case to deduce that N ∼ = N ′ , so we assume that |S ′ | 2. By (R1), some reduction R i can be applied to N , and since F S ′ (N ) = F S ′ (N ′ ), by (A) it can also be applied to N ′ . Then, by (R2), . Therefore the induction hypothesis applies, implying ). This implies that N ∼ = N ′ , as we wanted to prove. Thus, in particular, we have that for every m |S|, if N, then there exists some m such that N, N ′ ∈ C S,m : take as m the largest number of nodes in N or in N ′ . Therefore, F S is injective up to isomorphism, as we claimed.
Remark 2. If one wants to use a result like the last lemma to prove the injectivity up to isomorphism of a certain representation of S-rDAGs more general than 1nested networks, then it may be necessary to explicitly add to (A) and (R) a third condition that covers the starting case: We shall also use a couple of times the following straightforward fact.
When the hypothesis of this lemma is satisfied, we say that F refines F ′ , and also that d F refines d ′ F ′ . Notice that if d ′ F ′ is a metric and d F refines it, then it is also a metric. 6 Robinson-Foulds distance where each member appears with multiplicity the number of nodes having it as cluster. In particular, the cardinal of C(N ) (as a multiset, that is, every element counted with its multiplicity) is equal to the number of nodes in N . The Robinson-Foulds distance between a pair of S-rDAGs N, N ′ is where the symmetric difference and its cardinal refer to multisets. It is the natural generalization to S-rDAGs of the well known Robinson-Foulds distance for phylogenetic trees [34].

Remark 3.
If v is an ancestor of u in N , then C(u) ⊆ C(v), but the converse implication is false, even in binary galled trees. See, for instance, Fig. 7 below: in both networks, the root and its tree child have the same cluster, but the root is not a descendant of its child.
It is known that the Robinson-Foulds distance is a metric on the class of all regular evolutionary networks on a given set S (the networks N such that the mapping v → C(v) induces an isomorphism of directed graphs between N and the Hasse diagram of (C(N ), ⊇)) [3] and on the class of all tree-child phylogenetic networks on a given set S that do not contain any hybrid node with two parents connected by a path [13]. Unfortunately, 1-nested networks, or even binary galled trees, need not be regular (by Remark 3) and they can contain reticulation cycles where one merge path is a single arc. So, we cannot use those results to prove that the Robinson-Foulds distance is a metric, even on the class of all binary galled trees.
As a matter of fact, the cluster representation is not injective up to isomorphism, and hence the Robinson-Foulds distance is not a metric, for 1-nested networks, or even galled trees, unless we restrict the possible in-and out-degrees of their nodes: they cannot contain either internal tree nodes of out-degree other than 2 (see Fig. 5), or hybrid nodes of out-degree 0 (see Fig. 6) or greater than 1 (see Fig. 7). Therefore, the Robinson-Foulds distance can only be a metric for binary 1-nested networks, that is, for binary galled trees. Now, we have the following result.   Theorem 2. Let N, N ′ be two binary 1-nested networks on a given set S such that C(N ) = C(N ′ ).
(A) If a specific R or G reduction can be applied to N , then it can also be applied to N ′ . (R) If a specific R or G reduction is applied to N and N ′ , the resulting networks have the same cluster representations. ⊓ ⊔ In order not to lose the thread of the paper, we postpone the proof of this theorem until §A2 in the Appendix at the end of the paper. Combining Lemma 6 with this theorem, we obtain the following result.

Tripartitions distance
Notice that the tripartition associated to a node v refines its cluster C(v), by splitting it into A(v) and B(v). The tripartitions representation of N is the multiset of tripartitions of the nodes of N . The tripartitions distance between a pair of S-rDAGs N, where the symmetric difference and its cardinal refer to multisets. It turns out that the tripartitions distance is a metric on the class of all 1nested networks on a given set. It is a consequence of the following proposition, whose proof we postpone until §A3 in the Appendix. (A) If a specific R, T , G, or G reduction can be applied to N , then it can also be applied to N ′ . (R) If a specific R, T , G, or G reduction is applied to N and N ′ , the resulting networks have the same tripartitions representations. ⊓ ⊔ So, using Lemma 6, we deduce the following result.
Corollary 5. The tripartitions distance is a metric on the class of all 1-nested networks on a given set S. ⊓ ⊔ Remark 4. Another refinement (in the sense of Lemma 7) of the Robinson-Foulds distance, the so-called µ-distance, was introduced by Cardona et al [14] and proved to be a metric on the class of all tree-child S-rDAGs for any given S: then, in particular, it is a metric on the class of all 1-nested networks on a set S. Soon later, L. Nakhleh [31] proposed a distance m that turned out to refine the µ-distance [12] and therefore that is also a metric on the class of all 1-nested networks on a set S. The interested reader can look up the aforementioned references for the specific definitions of these metrics.

Nodal and splitted nodal distances
Let N = (V, E) be a S-rDAG; to simplify the language, throughout this section we assume that S = {1, . . . , n} with n = |S|. Recall from [10] that the least common semistrict ancestor, LCSA for short, of a pair of nodes u, v ∈ V is the node that is a common ancestor of u and v and strict ancestor of at least one of them, and that is a descendant of all other nodes in N satisfying these properties. Such a LCSA of a pair of nodes u, v always exists and it is unique [10,§IV], and we shall denote it by [u, v].
The LCSA of a pair of nodes in a phylogenetic tree is their lowest common ancestor. It turns out that such a characterization extends to 1-nested networks. Recall that a lowest common ancestor, LCA for short, of a pair of nodes u, v in a rDAG is any common ancestor of u and v that is not a proper ancestor of any other common ancestor of them [5]. Proof. Let x be any LCA of u and v, and let us prove that x must be a strict ancestor of u or v. Indeed, by Lemma 9 in §A1 in the Appendix, if x is not a strict ancestor of u, then it is intermediate in the reticulation cycle for a hybrid node h u that is a strict ancestor of u. In a similar way, if x is not a strict ancestor of v, then it is intermediate in the reticulation cycle for a hybrid node h v that is a strict ancestor of v. Now, if x were not a strict ancestor either of u or of v, then it either would happen that it is intermediate in reticulation cycles for two different hybrid nodes, which is impossible in a 1-nested network, or that it is a proper ancestor of a common ancestor of u and v, namely h u = h v , against the assumption that x is a LCA of u and v.
So, x is a common ancestor of u and v and a strict ancestor of at least one of them, and thus it is an ancestor of [u, v]. Since x cannot have proper descendants that are common ancestors of u and v, we conclude that For every pair of leaves i, j ∈ S, let ℓ N (i, j) and ℓ N (j, i) be the distances from [i, j] to i and to j, respectively, and let ν N (i, j) = ℓ N (i, j) + ℓ N (j, i).
The LCSA-path lengths matrix of N is the symmetric matrix and the splitted LCSA-path lengths matrix of N is the (not necessarily symmetric) matrix The nodal distance between a pair of S-rDAGs N, N ′ is half the Manhattan, or L 1 , distance between ν(N ) and ν(N ′ ): The splitted nodal distance between N and N ′ is the Manhattan distance between ℓ(N ) and ℓ(N ′ ): Of course, instead of using the Manhattan distance on the set of n × n matrices, one can use any other distance for real-valued matrices to compare LCSA-path lengths, or splitted LCSA-path lengths, matrices, like for instance the euclidean distance. The results in this section do not depend on the actual metric for realvalued matrices used. The nodal distance d ν is the natural generalization to S-rDAGs of the classical nodal metric for binary phylogenetic trees [17,38], while the splitted nodal distance d ℓ generalizes to S-rDAGs the recently introduced homonymous metric for arbitrary phylogenetic trees [8].
It is known [9,11] that d ν is a metric on the class of all binary tree-child time consistent phylogenetic networks on a given set S, and that d ℓ is a metric on the class of all tree-child time consistent phylogenetic networks on a given set S, but no binary galled tree containing a reticulation cycle with one merge path consisting of a single arc is time consistent, and therefore we cannot use these results to prove that d ν or d ℓ are metrics even for binary galled trees.
It turns out that ν is not injective up to isomorphism, and hence d ν is not a metric, even for binary galled trees, as Fig. 8 shows. As far as ℓ goes, it is not injective up to isomorphism for 1-nested networks, or even galled trees, that are not semibinary: if we allow hybrid nodes of out-degree 0 (see Fig. 9) or greater than 1 (see Fig. 10), there exist pairs of non-isomorphic galled trees with the same splitted LCSA-path length matrices. Therefore, d ℓ can be a metric at most on the class of all semibinary 1-nested networks. Now, we have the following result.   (A) If a specific R, T , or G reduction can be applied to N , then it can also be applied to N ′ . (R) If a specific R, T , G reduction is applied to N and N ′ , the resulting networks have the same splitted LCSA-path lengths matrices. ⊓ ⊔ As we did previously, we postpone the proof of this theorem until §A4 in the Appendix at the end of the paper. Combining Lemma 6 with this theorem, we obtain the following result. Corollary 6. The splitted nodal distance is a metric on the class of all semibinary 1-nested networks on a given set S.

Conclusion
Several slightly different definitions of galled tree, capturing the notion of a hybridization network with isolated reticulation cycles, have been proposed so far in the literature. The most general such definition is as a network with arc-disjoint reticulation cycles [16,26], called in this paper 1-nested, and the most restrictive is Gusfield et al's original definition of a galled tree as a network with node-disjoint reticulation cycles [19]: in between lie the level-1 networks of Janson, Sung et al [25,27]. In the semibinary (hybrid nodes of in-degree 2 and out-degree 1) case, level-1 and 1-nested networks are the same, and in the binary (semibinary plus tree nodes of out-degree 2) case, galled trees, level-1 networks and 1-nested networks are the same objects.
In this paper we have established for which classes of 1-nested networks on a fixed set of labels, several distance measures introduced so far in the literature satisfy the axioms of metrics: actually, only the separation axiom (distance 0 means isomorphism) is relevant here, because all other axioms of metrics are always satisfied by these distances. In summary, we have proved that: (a) The Robinson-Foulds distance [3,10] is a metric only for binary galled trees. (b) The tripartitions distance [29], the µ-distance [14] and Nakhleh's metric m for reduced networks [31] are metrics for arbitrary 1-nested networks. (c) The natural translation of the nodal distance for phylogenetic trees to evolutionary networks [9] is not a metric even for binary galled trees. (d) The splitted nodal distance [9,11] is a metric for semibinary 1-nested networks, but not for arbitrary galled trees.
We would like to mention that the 1-nested networks turn out to form the first welldefined class of evolutionary networks where the tripartitions distance is shown to be a metric but the Robinson-Foulds distance is not a metric.
There are other distances that have not been discussed in this paper because they obviously fail to be metrics even for binary galled trees. This is the case of the triplets distance [11], which cannot be a metric for binary galled trees because there are many more binary galled trees with 3 leaves than possible triplets in the sense defined in the aforementioned paper. And, as it was already observed in [14,§II.D], it is also the case of any distance defined by comparing the multisets of induced subtrees, or the multisets of splits of induced subtrees: for instance, the pairs of galled trees depicted in Figs. 9 or 10 have the same multisets of induced subtrees.
The splitted nodal distance and the triplets distance were introduced in [11] as suitable generalizations of the corresponding distances for phylogenetic networks with the aim of obtaining metrics on the class of tree-child time consistent phylogenetic networks, and hence they were not designed to cope with reticulation cycles where one merge path is a single arc. This is the main reason of their failure as metrics for arbitrary 1-nested networks. But it seems not difficult to modify them to obtain metrics for 1-nested networks, by taking into account the restricted, and specific, topological structure of these networks: something similar was already done with the splitted nodal distance to make it work on tree-child time consistent evolutionary networks with hybrid nodes of (almost) arbitrary type [9].
Galled trees, 1-nested networks, and level-1 networks are defined as having hybrid nodes of in-degree 2, in the first case by semantical reasons and in the other two cases for practical reasons (to guarantee that certain reconstruction algorithms run in polynomial time), and we have kept this restriction in this paper. But, although Gusfield et al's node-disjoint reticulation cycles condition implies that hybrid nodes must have in-degree 2, this restriction is not necessary in level-1 and 1-nested networks, and polynomial time algorithms for the reconstruction of level-1 or 1-nested networks with hybrid nodes of arbitrary in-degree may be discovered in the future, in which case it would be interesting to know whether the distance measures discussed in this paper define metrics in this more general case and they can be used thus to assess these new algorithms.

Proof. (a)
If v is a node with only one child and this child is the tree leaf i, then C(v) = {i} ∈ C I (N ). Conversely, let v be an internal node such that C(v) = {i}. Since every internal node in N has a tree descendant leaf, i must be a tree descendant leaf of v (and in particular a tree leaf). Let w be the parent of i, and let us prove that it has out-degree 1. Indeed, if u is a child of w other than i, it has a tree descendant leaf j, and j = i, because, otherwise, the only parent w of i would be a descendant of its child u. But then j ∈ C(v), against the assumption that C(v) = {i}. So, the tree path v i cannot have any intermediate node, because otherwise w would be intermediate in this path and hence it would be a tree node, but internal tree nodes in N have out-degree greater than 1. Therefore, v is the parent of i. But then, as we have just seen, it must have out-degree 1.
(b) Assume that the every member of C I (N ) containing i or j contains both of them, but that i and j are not sibling. Let v 1 be a parent of i: then i ∈ C(v 1 ) implies j ∈ C(v 1 ) and, since v 1 is not a parent of j, v 1 is a proper ancestor of some parent w 1 of j. Then, j ∈ C(w 1 ) implies i ∈ C(w 1 ) and thus, since w 1 is not a parent of i, w 1 is a proper ancestor of some parent v 2 = v 1 (because v 1 is a proper ancestor of w 1 ) of i. Iterating this process, we obtain that v 2 is a proper ancestor of another parent w 2 = w 1 of j, and then that w 2 is a proper ancestor of another parent v 3 = v 1 , v 2 of i, which is impossible because every node in N has at most 2 parents.
(c) Let u be the parent of the tree node v. Assume that C(u) = C(v) and let i be a tree descendant leaf of v, and hence also of u. For every other internal node w, if C(v) C(w), then i ∈ C(w), and therefore either the path u i is contained in the path w i or conversely. But C(v) C(w) implies that w cannot be a descendant of v, and we conclude that u i is contained in the path w i, and hence u is a descendant of w, which implies that C(u) ⊆ C(w).
Assume now that u has out-degree greater than 1 and that C(u) = C(v). Let v ′ be another child of u and let j be a tree descendant leaf of v ′ . Then, j ∈ C(v), and therefore either the path v j contains the path v ′ j or the path v ′ j contains the path v j. But the last situation is impossible, because if v belongs to the path v ′ j, its only parent u should also belong to it, and u cannot be a descendant of its child v ′ . So, we conclude that v ′ is a descendant of v, and therefore that v ′ is a hybrid node and its reticulation cycle consists of the arc (u, v ′ ) and a path (u, v, . . . , v ′ ).
(d) Assume that v is a non-strict descendant of u. Let u v be any path from u to v, and r v a path from the root r of N to v not containing u. Let w be the first node in u v contained also in r v. Since, by assumption, w = u and, clearly, w = r, w will have different parents in both paths, which implies that it is hybrid. Let now r u be any path from the root to u and let x be the last node in this path belonging to the subpath r w of r v: again, u = x. Then, the subpath x w of r v and the concatenation of the subpath x u of r u and the subpath u w of u v are internally disjoint, and hence they form a reticulation cycle for w with split node x and having u as intermediate node.
It remains to prove that w is a strict ancestor of v. But if it were not, then, as we have just seen, w would be intermediate in a reticulation cycle for an ancestor of v, which is impossible by Lemma 3.   if they belong to the same merge path, we take them so that y is a proper descendant of x. We shall prove that C(x) = C(y).
Since both nodes are of tree type, x has a child v outside K. Let l be a tree descendant leaf of v, and assume that l ∈ C(y). Then, either the path v l contains the path y l or vice versa. But the tree path u y contained in the merge path is the unique path from u to y, and it does not contain v, and therefore y cannot be a descendant of v. Thus, v is a descendant of y, and since x is not a descendant of y by (a), we conclude that v is a hybrid node such that its parent other than x is a descendant of y. But then, y is intermediate in the reticulation cycle of v, which is impossible because it is already intermediate in the reticulation cycle of h. So, we reach a contradiction that implies that l / ∈ C(y), and hence that C(x) = C(y). On the other hand, the fact that i is a non-strict descendant of x is obvious: the composition of any path r u with the merge path u h not containing x, and ending, if necessary, with the arc (h, i), yields a path r i not containing x. (e) Any path r i contains h and therefore it contains one of its parents. But the merge path from u to any parent of h is a tree path, and hence it must be contained in the subpath r h of r i. This implies that u belongs to the path r i.
(f ) Let v be a node outside K such that i ∈ C(v). Then, by (e) and Lemma 1, u and v are connected by a path. Now, since v = h, v will be an ancestor of one of the parents of h, say x. But then, if v were a descendant of u, it would belong to the only path u x, which is contained in K, against the assumption that v does not belong to K. Thus, u is a descendant of v.
(g) Let x be an intermediate node of K and assume that there exists some w = x such that C(w) = C(x). We know by (b) that w is neither h (because C(h) = C(x)) nor any intermediate node of K and therefore, by (f), C(u) ⊆ C(w) = C(x). Thus, C(x) contains all clusters of nodes in K, which implies that the merge path not containing x cannot contain any intermediate node (by (d)) and that x is the child of u in the only merge path of K of length greater than 1 (otherwise, the cluster of its parent in the merge path would strictly contain C(x), by (b), and would be included in C(u)).
(h) Let v and v ′ be the parents of h. Since every proper ancestor w of h is an ancestor of v or v ′ , and hence C(w) contains C(v) or C(v ′ ), we deduce that C(v) and C(v ′ ) are the only possible minimal members of C I (N ) strictly containing C(h).
Now, if C(v) and C(v ′ ) are two different such minimal members of C I (N ), then they do not contain each other and therefore v and v ′ are not connected by a path. This implies that neither v nor v ′ is the split node u of K, and therefore that they are intermediate in K. Conversely, if only one of these two clusters, say C(v), is minimal strictly containing C(h), then it is contained in the other. By (d), this implies that v ′ cannot be intermediate in K, and therefore v ′ = u.

A2 Proof of Theorem 2
To ease the task of the reader, we split the proof of Theorem 2 into several lemmas. Throughout this subsection, N stands for a binary 1-nested network (or, equivalently, a binary galled tree) on a fixed set S. Conversely, assume that (1)-(4) are satisfied. Then, the parent h of i has outdegree 1 and therefore it is hybrid, and, by Lemma 10.(h), its parents are connected by a path, because there is only one minimal element of C I (N ) strictly containing {i}, namely {i k , i}. Therefore, the reticulation cycle K for h consists of an arc (u, h) and a tree path (u, v 1 , . . . , v l , h) with l 1. In this situation, Lemma 10 implies that: The only possibility of making these two lists of properties compatible is that k = l and C(v j ) = {i j , . . . , i k , i} for every i = 1, . . . , k.
It remains to prove that the only child of every v j outside K is the corresponding leaf i j . Let w j be the only parent of i j ; we want to prove that w j = v j . Since i j ∈ C(v j ), there exists a path v j w j and hence C(w j ) ⊆ C(v j ). On the other hand, i j ∈ C(w j ) implies, by (4), that i ∈ C(w j ) and therefore, by Lemma 10.(f), either w j belongs to K or it is an ancestor of u. The second case cannot hold, because w j is a proper descendant of u. Therefore, w j is a node of K that is a descendant of v j and an ancestor of i j : it must be v j . (1) {i} ∈ C I (N ).
Proof. The proof that if N contains a reticulation cycle K consisting of the merge paths (u, v 1 , . . . , v k , h) and (u, v ′ 1 , . . . , v ′ k ′ , h), with k k ′ > 0, such that the only child of the hybrid node h is the leaf i, the child outside K of each tree node v j is the tree leaf i j , and the child of each tree node v ′ j outside K is the tree leaf i ′ j , then it satisfies conditions (1) to (5), is similar to the proof of the corresponding implication in the previous lemma, and we do not repeat it here.
As far as the converse implication goes, assume that conditions (1)-(5) in the statement are satisfied. Then, the parent h of i has out-degree 1 and therefore it is hybrid, and, by Lemma 10.(h), its two parents are not connected by a path, because there are two minimal elements of C I (N ) strictly containing {i}, namely {i k , i} and {i ′ k ′ , i}. Therefore, the reticulation cycle K for h consists of two merge paths (u, v 1 , . . . , v l , h) and (u, v ′ 1 , . . . , v ′ l ′ , h) with l, l ′ 1. In this situation, Lemma 10 implies that: -C(v l ) and C(v ′ l ′ ) are the minimal elements of C I (N ) strictly containing {i}; -C(v l ) · · · C(v 1 ), and then, by Lemma 9.(c), each C(v j ), j = 1, . . . , l − 1, is the minimal element of C I (N ) containing C(v j+1 ); -C(v ′ l ′ ) · · · C(v ′ 1 ), and then, by Lemma 9.(c), each C(v ′ j ), j = 1, . . . , l ′ − 1, is the minimal element of C I (N ) containing C(v ′ j+1 ); -C(v 1 ), . . . , C(v l ), C(v ′ 1 ), . . . , C(v ′ l ′ ) appear with multiplicity 1 in C I (N ); -the minimal element of C I (N ) strictly containing C(v 1 ) is the same as the minimal element of C I (N ) strictly containing C(v ′ 1 ), and it is C(u).
On the other hand, (1)- (5) imply that: -The minimal elements of C I (N ) strictly containing {i} are {i k , i} and {i ′ k ′ , i}; -{i k , i} . . . {i 1 , . . . , i k , i}, and each {i j , . . . , i k , i}, j = 1, . . . , k − 1, is the minimal element of C I (N ) strictly containing {i j+1 , . . . , i k , i}; i} appear with multiplicity 1 in C I (N ); -the minimal element of C I (N ) strictly containing {i 1 , . . . , i k , i} is the same as the minimal element containing {i ′ 1 , . . . , i ′ k ′ , i}, and it is {i 1 , . . . , i k , i ′ 1 , . . . , i ′ k ′ , i}. The only possibility of making these two lists of properties compatible is that (up to the interchange of k and k ′ ) k = l, k ′ = l ′ , C(v j ) = {i j , . . . , i k , i} for every j = 1, . . . , k, and C(v ′ j ) = {i ′ j , . . . , i ′ k , i} for every j = 1, . . . , k ′ . It remains to prove that the only child of every v j (respectively v ′ j ) not belonging to the reticulation cycle for h is the corresponding leaf i j (respectively i ′ j ). This fact can be proved using the same argument as in the last paragraph of the proof of the previous lemma.
Lemmas 11 to 13 prove that the fact that a given R or G reduction can be applied to N only depends on C(N ), from where point (A) in Theorem 2 follows. As far as point (R) goes, it is a consequence of the following straightforward lemma that shows that the application of a specific R or T reduction to N affects C(N ) in a way that does not depend on N itself, but only on its cluster representation; we leave its easy proof to the reader. As in the previous subsection, we split the proof of Theorem 3 into several lemmas to increase its readability. In the rest of this subsection, N stands for an arbitrary 1-nested network on some given set S. Since the set S is fixed, for every node v of N , if A(v) = {i 1 , . . . , i k } and B(v) = {j 1 , . . . , j l }, we shall use the following notation to denote the tripartition θ(v): To simplify the notations, we shall denote by θ I (N ) the multiset of tripartitions of its internal nodes, which is obtained by removing from θ(N ) one copy of every tripartition {i | ∅} with i ∈ S. Proof. If i, j are two sibling tree leaves and v is their common parent, then they are strict descendants of v and C(v) is contained in the cluster of any ancestor of i or j. Let now w be any node such that i, j ∈ C(w). Then, w is ancestor of v.
If v is a strict descendant of w, then i, j are also strict descendants of w, and if v is a non-strict descendant of w, then i, j are also non-strict descendants of w. Therefore, either i, j ∈ A(w) or i, j ∈ B(w). This finishes the proof of the 'only if' implication.
As far as the converse implication goes, the existence of the internal node v with i, j ∈ A(v) and such that C(v) is contained in the cluster of every ancestor of i or j implies that there does not exist any internal node whose cluster contains one of the labels i, j but not the other, and therefore, by Lemma 9.(b), that i and j are siblings. Let v 0 be a common parent of them: then, on the one hand, i, j ∈ C(v 0 ) implies that C(v) ⊆ C(v 0 ), and, on the other hand, since i, j ∈ A(v), v 0 must be a descendant of v, and therefore C(v 0 ) ⊆ C(v). We conclude that C(v 0 ) = C(v).
Let us prove now that i, j ∈ A(v 0 ). Indeed, if one of them were a non-strict descendant of v 0 , then by (b) both would be non-strict descendants of it. By Lemma 9.(d), and taking into account that v 0 is a parent of i and j, this would imply that i and j are hybrid leaves and v 0 intermediate in their reticulation cycles, which would contradict the 1-nested condition.
This implies that there would exist paths from the root of N to i and j that do not contain v 0 . This could only happen if both i and j were hybrid leaves and v 0 intermediate in their reticulation cycles (if it were the split node of one of them, the corresponding hybrid leaf would be a strict descendant of it by Lemma 10.(e)), Let us prove now that i and j are tree leaves. Indeed, if, say, i is a hybrid leaf and v ′ 0 its other parent, then, since i ∈ A(v 0 ), v ′ 0 is a descendant of v 0 and then intermediate in the reticulation cycle for i (which would have v 0 as split node). Now, since i ∈ C(v ′ 0 ), it must happen that j ∈ C(v ′ 0 ) and, since v ′ 0 cannot be an ancestor of v 0 , we conclude that j is also hybrid and that v ′ 0 is an ancestor of its other parent. But then, v ′ 0 is also intermediate in the reticulation cycle for j (which consists of the arc (v 0 , j) and the merge path v 0 v ′ 0 j), which is impossible. This shows that i and, by symmetry, j are tree leaves.
This finishes the proof that i and j are tree sibling leaves if, and only if, (a) and (b) are satisfied; moreover, from this proof we deduce that we can take as v in (a) the common parent of i and j. Now, as far as the last assertion in the statement, if i and j are the only children of their common parent v, it is clear that C(v) = {i, j}. Conversely, if v has a child u different from i and j, then u cannot be an ancestor of i and j, and therefore any descendant leaf of it is an element of C(v) different from i and j, which shows that {i, j} C(v).
As a direct consequence of this lemma we obtain the following two results. (1) There exists an internal node v such that i, j ∈ A(v), {i, j} C(v), and C(v) is contained in the cluster of any other internal ancestor of i or j. (2) For every node w of N such that i, j ∈ C(w), it happens either that i, j ∈ A(w) or i, j ∈ B(w).

⊓ ⊔
Let us consider now the G and G reductions. In contrast to the corresponding lemmas in §A2, here we do not need to distinguish between k ′ = 0 and k ′ > 0.
Proof. If N contains a reticulation cycle K consisting of the merge paths (u, v 1 , . . . , v k , h) and (u, v ′ 1 , . . . , v ′ k ′ , h) such that the only child of the hybrid node h is the tree leaf i and each tree node v j (respectively v ′ j ) has only one child outside K and it is the tree leaf i j (respectively i ′ j ), then . . , k ′ and hence θ I (N ) contains all tripartitions listed in points (1)- (3). Let now v be any internal node different from v 1 , . . . , v k , v ′ 1 , . . . , v ′ k ′ that is an ancestor of some leaf i 1 , . . . , i k , i ′ 1 , . . . , i ′ k ′ , say that i j ∈ C(v). Then it will be an ancestor of its parent v j and in particular i ∈ C(v j ) ⊆ C(v). Then, by Lemma 10.(f), u is a descendant of v. Now, if u is a strict descendant of v, then the leaves i 1 , . . . , i k , i ′ 1 , . . . , i ′ k ′ , i are also strict descendants of v, while if u is a non-strict descendant of v, then they are also non-strict descendants of v. This proves (4) and that all tripartitions listed in (2) and (3) appear only once in θ(N ) (Lemma 10.(g) did not guarantee it for θ(v 1 ) when k ′ = 0). This finishes the proof of the 'only if' implication.
Conversely, assume that (1)-(4) are satisfied. Using only the information of the clusters and arguing as in the proof of the 'if' implication in Lemmas 12 and 13, we already deduce that the parent h of i is hybrid, it has out-degree 1 and i is a tree child of it (using Lemma 9.(a)), that the reticulation cycle K for h consists of two tree merge paths (u, v 1 , . . . , v l , h) and (u, v ′ 1 , . . . , v ′ l ′ , h), with l k and l ′ k ′ , and that θ(v l−j ) = {i k−j , . . . , i k | i}, for every j = 0, . . . , k − 1, and θ(v ′ l ′ −j ) = {i ′ k ′ −j , . . . , i ′ k ′ | i} for every j = 0, . . . , k ′ − 1. Now, if l > k, C(v l−k ) would strictly contain C(v l−(k−1) ) and i 1 would be a strict descendant of v l−k (because it is a strict descendant of its tree child v l−(k−1) ) but i would be a nonstrict descendant of it, which would contradict (4). This implies then that k = l and C(v j ) = {i j , . . . , i k , i} for every i = 1, . . . , k, and then, by symmetry, k ′ = l ′ and C(v ′ j ) = {i ′ j , . . . , i ′ k ′ , i} for every i = 1, . . . , k ′ . It remains to prove that the only child of every v j (respectively, v ′ j ) not belonging to the reticulation cycle for h is the corresponding tree leaf i j (respectively, i ′ j ). Let us prove first that each i j is a tree leaf. Indeed, if i j were hybrid, then, since i j ∈ A(v j ), v j would be an ancestor of the split node w j of the reticulation cycle for i j . Since i j only belongs to the clusters of the nodes in K that are ancestors of v j , we conclude that w j does not belong to K and then, since i j ∈ A(w j ), by (4) we have that i ∈ A(w j ) and hence, by Lemma 10.(f), that w j is a strict ancestor of u, which is impossible.
Let now u j be a child of v j different from i j and from v j 's child in K. This node must be internal, because the other descendant leaves i j+1 , . . . , i k , i of v j are tree leaves and descendants of proper descendants of v j in K, and therefore v j is not their parent. Then, since C(u j ) ⊆ C(v j ) = {i j , . . . , i k , i}, by (4) we conclude that i ∈ C(u j ) and hence, since u j does not belong to K, by Lemma 10.(f) we conclude that u j is an ancestor of u, which is impossible. This shows that v j does not have any child outside K different from i j , and moreover, since i j is a descendant of v j , that it is its child. Lemma 19. The G i;i 1 ,...,i k ;i ′ 1 ,...,i ′ k ′ reduction (with k k ′ 0) can be applied to N if, and only if, the following conditions are satisfied: (2) For every j = 1, . . . , k, {i j , . . . , i k | i} ∈ θ(N ) with multiplicity 1.
Proof. If N contains a reticulation cycle K consisting of the merge paths (u, v 1 , . . . , v k , h) and (u, v ′ 1 , . . . , v ′ k ′ , h) such that the hybrid node h is the leaf i and each tree node v j (respectively, v ′ j ) has only one child outside K and it is the tree leaf i j (respectively i ′ j ), then, by Lemma 9.(a), {i} / ∈ C I (N ), and . . , k ′ and hence N satisfies (1)-(3). The rest of the 'only if' implication can be proved as in Lemma 18. Conversely, assume that (1)-(4) are satisfied. To begin with, let us prove that i is a hybrid leaf. Indeed, if it were a tree leaf, then its parent v would be a strict ancestor of i, and therefore θ(v) would be none of the tripartitions listed in (2) or (3). On the other hand, v would be a descendant of the node w having tripartition {i k | i}, which would imply, since {i} = C(v) by (1), that i k ∈ C(v). Then, by (4) and since i ∈ A(v), i k would also be a strict descendant of v . This would imply that w is a strict ancestor of v: any path r v not containing w followed by a path v i k (that does not contain w because w is an ancestor of v) would form a path r i k not containing w, against the assumption that i k ∈ A(w). But then the tree child i of v would be also a strict descendant of w, which would contradict the assumption that i ∈ B(w).
Let us also denote by h this hybrid leaf labeled with i, so that C(h) = {i}. Since we can still apply Lemma 10, the same argument as in the proof of the 'if' implication in Lemma 18 implies that the reticulation cycle K for h consists of two merge paths (u, v 1 , . . . , v k , h) and (u, v ′ 1 , . . . , v ′ k ′ , h) such that C(v j ) = {i j , . . . , i k , i}, for every j = 1, . . . , k, and C(v ′ j ) = {i ′ j , . . . , i ′ k ′ , i} for every j = 1, . . . , k ′ . The proof that the only child of every v j (respectively, v ′ j ) not belonging to K is the corresponding tree leaf i j (respectively, i ′ j ) is also similar to the one given for the corresponding fact in Lemma 18, and we do not repeat it here.
Lemmas 16 to 19 prove condition (A) in Lemma 6 for the R, T , G, and G reductions and the tripartitions representation. As far as point (R) goes, it is a consequence of the following lemma. We also split the proof of Theorem 4 into several lemmas, in parallel to the preceding subsections. In the rest of this subsection, N stands for a semibinary 1-nested network on S = {1, . . . , n}. Notice that all leaves in N are of tree type. For every pair of nodes u, v in N , we shall denote by CA(u, v) the set of common ancestors of u and v. By Lemma 8,[u,v] is the element of CA(u, v) that is a descendant of all other nodes in this set.
The following result summarizes what Lem. 5 and Cor. 4 in [11] say about N . Although these results were stated therein for tree-child time consistent evolutionary networks with out-degree 1 hybrid nodes, it is straightforward to check that the time consistency is not used anywhere in their proofs, and therefore their thesis also holds for tree-child (and, in particular, for 1-nested) semibinary hybridization networks. In the following statement, and henceforth, by saying that a leaf j is a quasi-sibling of a leaf i, we mean that the parent of j is a hybrid node that is a sibling of i: cf. Fig. 11. (c) The leaf j is a quasi-sibling of the leaf i if, and only if, ℓ N (i, j) = 1, ℓ N (j, i) = 2, and ℓ N (j, k) > 1 for every k ∈ S \ {i, j}.

⊓ ⊔
As a consequence of this lemma, we have the following results.
Lemma 22. The R i;j reduction can be applied to N if, and only if, ℓ N (i, j) = ℓ N (j, i) = 1 and ℓ N (i, k) > 1 for every k ∈ S \ {i, j}.
Proof. The R i;j reduction can be applied to N if, and only if, i, j are sibling leaves and their parent has out-degree 2. By the previous lemma we already know that ℓ N (i, j) = ℓ N (j, i) = 1 if, and only if, i, j are sibling leaves. Thus, it only remains to prove that the parent of i and j has out-degree 2 if, and only if, ℓ N (i, k) > 1 for every k ∈ S \ {i, j}. Now, if there is a leaf k = j such that ℓ N (i, k) = 1, then the parent of i and j is also an ancestor of k, which means that it has out-degree at least 3. Conversely, if the parent of i and j has out-degree at least 3 and v is a child of it other than i, j, then ℓ N (i, k) = 1 for every descendant leaf k of v.
A similar argument, using that the T i;j reduction can be applied to N if, and only if, i and j are tree sibling leaves and their parent has some other child, proves the following result. Lemma 23. The T i;j reduction can be applied to N if, and only if, ℓ N (i, j) = ℓ N (j, i) = 1 and there exists some k ∈ S \ {i, j} such that ℓ N (i, k) = 1.

⊓ ⊔
We have now the following lemmas for the G reductions.
Lemma 24. The G i;i 1 ,...,i k ;∅ reduction can be applied to N if, and only if, the following conditions are satisfied: (1) ℓ N (i, l) > 1 for every l ∈ S \ {i}.
(4) For every j = 1, . . . , k and for every l = i j , ..., i k , i, ℓ N (i j , l) > 1. Proof. Assume that N contains a reticulation cycle K consisting of the merge paths (u, v 1 , . . . , v k , h) and (u, h) such that the only child of the hybrid node h is the leaf i and each tree node v j has only one child outside K, and it is the tree leaf i j . Then, (1) and (2) are satisfied because i is a quasi-sibling of i k , (3) is satisfied because the parent v j+1 of each i j+1 is a sibling of i j , (4) is satisfied because the only descendant leaves of the parent v j of i j are i j , i j+1 , . . . , i k , i, and (5) is satisfied because [i j , i] = v j and the only path v j i has length k −j +2. As far as condition (6) goes, let l be any label different from i, i 1 , . . . , i k . Then, l is not a descendant of v 1 and therefore every common ancestor of i or i 1 and l must be an ancestor of Proof. (a) R i;j (N ) is obtained by removing the leaf j and replacing the leaf i by its parent. This implies that, for every pair of remaining leaves, their LCA is the same node in N and in R i;j (N ), and that any path ending in i is shortened in one arc, while all paths ending in any other remaining leaf are left untouched. The formulas for ℓ R i;j (N ) given in the statement follow immediately from these observations.
(b) T i;j (N ) is obtained by removing the leaf j without modifying anything else. This implies that, for every pair of remaining leaves, their LCA is the same node in N and in T i;j (N ) and no path ending in a remaining leaf is modified, and therefore that ℓ T i;j (N ) = ℓ N on S \ {j}.
(c) Let us denote by N ′ the network G i;i 1 ,...,i k ,i ′ 1 ,...,i ′ k ′ (N ), and let u be the split node of the removed reticulation cycle. We remove all (and only) descendants of u, and we add to u two new tree leaf children i and i 1 . This implies that the LCA in N ′ of i and i 1 is u (and therefore ℓ N ′ (i, i 1 ) = ℓ N ′ (i 1 , i) = 1) and that the LCA of any other pair of remaining leaves is the same node in N ′ as in N . On the other hand, any path ending in i 1 is shortened in one arc, the distance from any internal node to i in N ′ is the same as its distance to i 1 , and all paths ending in remaining leaves other than i or i 1 are not touched. From these observations, the formulas for ℓ N ′ given in the statement easily follow.