{'fraction_non_alphanumeric': 0.04381357622498504, 'fraction_numerical': 0.008077920351040489, 'mean_word_length': 3.8974358974358974, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
HOW TREE-BASED IS MY NETWORK? PROXIMITY MEASURES FOR UNROOTED PHYLOGENETIC NETWORKS

Evolutionary events like hybridization and horizontal gene transfer cannot be represented by a tree but require a phylogenetic network instead. Nonetheless, it has been argued that evolution is fundamentally tree-like, in the sense that it can be modeled by a tree with additional arcs. Phylogenetic networks with this property are called tree-based, and this concept has recently attracted significant attention in evolutionary research. But classifying networks into treebased and non-tree-based ones is usually not sufficient for biological purposes, because sometimes tree-basedness is missed merely due to incomplete sampling. Therefore, measures are needed to quantify how close a non-tree-based network is to being tree-based. Such measures naturally also lead to characterizations of tree-based networks, and some measures for this purpose have recently been introduced both for binary and non-binary rooted phylogenetic networks. In the present manuscript, we generalize all these measures to unrooted networks, for which tree-basedness is mathematically more involved, and also present some new measures. This leads to new characterizations of unrooted tree-based networks. We analyze the relationships of the new proximity measures to one another to demonstrate their common properties as well as their respective differences.


Introduction
Phylogenetic networks are a generalization of phylogenetic trees that allow for representation of reticulation events such as hybridization or horizontal gene transfer, and can also be used to represent uncertainty. While hybridization, for instance, means that the evolutionary history of species cannot be adequately modeled by a tree, it has nevertheless been argued that evolution may be fundamentally "treelike", in the sense that evolution basically follows a tree-like structure with occasional additional arcs here and there [11,6]. This debate inspired the definition of a "tree-based network", which is a network that can be obtained from a tree by the addition of new arcs between arcs of the tree, initially defined in the rooted setting [6]. This family of networks has received quite a bit of theoretical development over the last few years, including extensions to the non-binary case [10,14], and the unrooted setting [3,7,2]. Numerous characterizations of rooted tree-based networks have been published, many using interesting combinatorial constructions such as graph matchings [6,10,14,5,1].
Not all networks are tree-based of course, and it was observed [6, Corollary 1] that any network can be made tree-based by adding additional leaves, which means that a network connecting a set of taxa may fail to be tree-based simply because of incomplete sampling. Nevertheless, measuring the extent to which a network is tree-based is an important question, and brings all phylogenetic networks into the conversation about tree-basedness. In the rooted setting, i.e. for a rooted phylogenetic network N r with leaf set X, several definitions of distance from being tree-based were introduced in [5], recently extended to the non-binary setting in [12]: (1) Any rooted spanning tree of N r has the leaves of N r and possibly others: let (N r ) denote the minimal number of others. (2) If N r is not tree-based it can be made tree-based by adding extra leaves. Let t(N r ) denote the smallest number of leaves needed. (3) The vertex set V (N r ) of N r can be partitioned by a set of disjoint paths, of which there will be at least |X| plus possibly some extras. Let p(N r ) denote the number of extras. All three are zero if and only if N is tree-based, and have been shown to be generically equal to each other in the rooted setting. This provides several equivalent lenses through which to see non-tree-basedness in rooted networks [5,12].
In this paper, we define eight measures of distance from tree-basedness for unrooted phylogenetic networks, both in the binary and non-binary settings. Some of these are straightforward adaptations from the rooted case, but others require subtle modifications. Five of these are entirely new measures, in the sense that they are not unrooted versions of known rooted measures. One of them can be shown to be equal to the generalizations, whereas the others can be shown to be distinct.
Possibly the most interesting of the new measures, namely δ NNI , is based on socalled nearest neighbor interchange (NNI) moves. δ NNI measures the NNI distance of a non-tree-based network to the nearest tree-based one.
As we explain in Section 7, this new measure cannot only measure the distance from a non-tree-based network to a tree-based one (as the other measures do, too), but additionally, it can measure the proximity of a tree-based network to a nontree-based one. In some sense, this leads to an interesting measure of robustness of tree-basedness for a given network.
Throughout the manuscript, we elaborate all these new measures and their relationships to one another and also investigate in Section 6 which of the new ones can lift to the rooted setting. Section 5 presents a summary of all measures introduced in this manuscript and some of their relationships. We discuss our results and point out some possible directions for future research in Section 7.

Definitions and background
An unrooted phylogenetic network on a set X (typically a set of species or taxa) is a connected graph without degree 2 vertices, whose degree 1 vertices (leaves) are bijectively labelled by the elements of X. In the following, whenever there is no ambiguity, we use the term network to refer to an unrooted phylogenetic network. We do not restrict the degree of the non-leaf vertices, so we deal with the general "non-binary" case (internal vertices of binary networks have degree exactly 3). 1 The special case of an acyclic phylogenetic network is called a phylogenetic tree.
Throughout this manuscript, we will assume that |X| ≥ 2, and that N is proper. A proper network is one for which all components obtained by removing a cut edge or cut vertex contain at least one element of X (following the definition of [2], more general than the one given in [5]). Note that a network that is not proper cannot be tree-based (cf. for instance [2]). We will denote the set of proper unrooted phylogenetic networks on X by PN (X).
In the following, we denote by V d (N ) the set of degree d vertices in N , so that V 1 (N ) = X is the set of leaves. If k is minimal such that the deletion of k edges of N would turn N into a tree (i.e. a connected acyclic graph), we say that N has tier k. Note that the tier does not depend on N being a phylogenetic network -in fact, the tier of a connected graph can be defined analogously, and for technical reasons, we need this later on in this manuscript.
A related concept that we need to introduce is the level of a phylogenetic network. In this regard, recall that a blob of a network (or, more generally, of a graph) is a maximal connected subgraph that has no cut edge (if such a blob consists of only one vertex, it is called trivial). Note that while in a binary phylogenetic network, i.e. a network in which all internal vertices have degree 3, blobs cannot contain any cut vertices (as all cut vertices in a binary network are incident to a cut edge), a blob in a non-binary phylogenetic network is explictily allowed to contain cut vertices (see [2] for more details). A phylogenetic network (or a graph) is called simple if it contains at most one non-trivial blob. Now, a phylogenetic network (or graph) N is said to have level k, if the maximal tier of the blobs of N is k (consequently, for any network N , level(N ) ≤ tier(N )). While the tier and the level of N are related concepts, they may be arbitrarily different. For instance, the network in Figure 2 has level 5 but the tier is 5m, for m copies of the original blob.
A support tree T of a network N is a spanning tree of N satisfying V 1 (T ) = V 1 (N ) = X, that is, whose leaf set coincides with the leaf set X of N . If N contains such a support tree T , it is called tree-based. This is a direct generalization of the definition for binary phylogenetic networks in [3], and coincides with the notion of "loosely" tree-based introduced in [7]. Note that T is not necessarily a phylogenetic tree as it may contain degree-2 vertices. We denote the set of tree-based networks on X by TBN (X).
As a side note, observe that if N is a (proper) network with a spanning tree T with exactly two leaves, then it is tree-based. This is because if one leaf of T is not from X, then N has only one leaf, in which case it consists of only one vertex (proper networks with one leaf are trivial [2, Remark 1]). Therefore both leaves are from X, and so N has a support tree and is tree-based. Furthermore, all proper binary networks of level less than or equal to 4 are also tree-based [3], and the same is true for all proper non-binary networks of level less than or equal to 3 [2].
Generalizing support trees, we introduce the notion of a support network N of N to be a connected subgraph of N containing all of the vertices of N and a subset E ⊆ E(N ) such that the leaf set of N coincides with the leaf set X of N . Note that a support network N need not necessarily be a phylogenetic network, as it may contain vertices of degree 2.
We call a phylogenetic network N tier-k based, if it contains a support network N of tier k. Note that if N is tier-0 based, then N is a support tree of N , and N is tree-based. Moreover, note that if N is a tier-k network which is tier-k based, then k ≤ k , as N can act as its own support network.
Similarly, we call a phylogenetic network N level-k based, if it contains a support network N of level k. Note that if N is level-0 based, then N is a support tree of N , and N is tree-based. As for the tier, note that if N is a level-k network which is level-k based, then k ≤ k , as N can act as its own support network. An example of both tier-k and level-k-basedness is shown in Figure 4.
In the course of this paper we will need the idea of adding edges and leaves to a network. This requires "subdivision" of edges.
An edge {u, v} of a phylogenetic network may be subdivided by first creating a new vertex w, then deleting {u, v} and adding in {u, w} and {w, v}. That is, subdividing {u, v} amounts to creating a new network N from N whose vertex set is V (N ) = V (N ) ∪ {w} and whose edge set is To add an internal edge to a phylogenetic network, first subdivide two edges {u 1 , v 1 } and {u 2 , v 2 }, creating new vertices w 1 and w 2 respectively, and then add a new edge {w 1 , w 2 }. To add a leaf to an edge {u, v}, we subdivide it creating a new vertex w, then add an additional new vertex x (the leaf) and the edge {w, x}.
Moreover, we will refer to the leaf cut graph LCUT (N ) of a proper network N ∈ PN (X), with |V (N )| ≥ 3, which is the graph G obtained from N by deleting all leaves and their incident edges [1]. Note that this may result in some vertices of degree 2 and -e.g. if N is a tree -even new leaves not labelled by X, which we do not remove. We will also consider the simplified LCUT graph LCUT simp (N ), which results from repeating the leaf deletion (even of leaves not from X) and -if applicable -suppressing degree-2 vertices until no such operation is possible anymore.
The final concept we need to introduce for this manuscript, is the nearest neighbor interchange (NNI), which is a replacement of a path in the network with an alternative path, and was defined as follows for unrooted phylogenetic networks in [8].
Definition 2.1 (Nearest Neighbor Interchange (NNI)). Let N be a phylogenetic network in which a, b, c, d is a path for which neither {a, c} nor {b, d} is an edge. The NNI operation on this path replaces it with the path a, c, b, d: the edges {a, b} and {c, d} are deleted, and edges {a, c} and {b, d} are added. The NNI distance d NNI (N 1 , N 2 ) between two unrooted phylogenetic networks N 1 and N 2 is defined to be the minimum number of NNI moves between them.
We are now in the position to turn to proximity measures.

Unrooted proximity measures
We wish to analyze the proximity of phylogenetic networks to being tree-based, and in this regard, we define the following measures. Measures (1)-(3) are analogous to the ones presented in [5] for rooted networks; we will discuss this relationship more in Section 6. However, (4) gives rise to a new measure based on the tier of a network, which we later show to be identical to the ones given by (1)-(3) (cf. Theorem 3.2), so the tier provides a new perspective on the other measures. In Section 4 we will consider four additional new measures which can be shown to be different from the ones presented in this section. (1) Let (N ) := min{|V 1 (T ) \ X| | T a spanning tree for N }.
(2) Let t(N ) := min{| X| | X is a set of leaves that can be added to N in order to make N tree-based}; (3) Let p(N ) := k −|X|+1, where k is minimal such that there exists a sequence of paths (π 1 , . . . , π k ) in N partitioning V (N ) and satisfying the property that for all i = 2, . . . , k, an endpoint of π i is adjacent to one or more of the paths π 1 , . . . , π i−1 . (4) Let τ (N ) := min{k | N is tier k-based}.
We are now in the position to prove the main theorem of this section. Proof. We will show that (N ) We begin with (N ) ≤ p(N ). Let (π 1 , . . . , π k ) be a sequence inducing p(N ), i.e. partitioning V (N ) such that an endpoint of π i is adjacent to one or more of the paths π 1 , . . . , π i−1 for all i = 2, . . . , k. We construct a spanning tree T of N as follows: start with π 1 , and attach the path π i for all i = 2, . . . , k according to the order induced by the sequence. To be precise, given π 1 , we know that one endpoint of π 2 is adjacent to π 1 , so we only need to add one edge from N in order to connect both paths, and this connection will result in a tree with at most 3 leaves (as one endpoint of π 2 is not a leaf of the resulting tree, but both leaves of π 1 might be). We subsequently repeat this for following π i , in each step adding at most one leaf to the spanning tree. This results in a spanning tree T of N with at most k + 1 = p(N ) + |X| leaves (at most 2 from π 1 and at most 1 for all other i ∈ {2, . . . , k}). So clearly, a spanning tree of N with the minimum number of leaves will have at most p(N ) + |X| leaves. By definition of (N ), this implies (N ) + |X| ≤ p(N ) + |X| and thus (N ) ≤ p(N ).
Next we show that p(N ) ≤ t(N ). Suppose that t(N ) leaves are added to N to make a tree-based network N , and that this is minimal. Then there is a spanning tree T of N whose leaves are the |X| + t(N ) leaves of N . We will use T to construct a set of paths that partition the vertices of N , as follows.
Choose a path π 1 between two leaves in T that are also leaves of N (recall that by assumption, |X| ≥ 2). Delete all edges {u i , v i } of T that are not in the path but for which one endpoint (say u i ) is on the path. What remains apart from the path itself are a set of trees T i with one vertex v i that is one edge in N distant from the path, and whose leaves are all leaves of N . For each such tree T i , choose a path in T i from v i to a leaf, number the paths arbitrarily from π 2 onwards, and as before, delete all edges in T i that have one vertex in the path and the other not. This again creates a set of sub-trees of T i for each i. This process may be repeated until what remains is an ordered set of paths partitioning V (N ), each of which contains exactly one leaf of N except for the first path π 1 , which contains two leaves. That is, the number of such paths is one less than the number of leaves in N , namely |X| + t(N ) − 1. These paths also satisfy the criterion of the definition of p(N ), namely that aside from the first, they have one endpoint a leaf on N , and the other is adjacent to one of the earlier paths in the sequence.
From each of these paths whose corresponding leaf endpoint is not from N , delete the edge ending in the leaf. Now we have |X| + t(N ) − 1 paths that partition V (N ), each of which (apart from the first) has one endpoint adjacent to a preceding path, as required by the definition of p(N ). Some of these paths may of course be empty, and it may be that there is a more optimal choice of paths that does the job. But in any case the minimal number of paths k satisfies k ≤ |X| + t(N ) − 1, and so p(N ) = k − |X| + 1 ≤ t(N ) as required. Now we claim t(N ) ≤ τ (N ). First, observe that if τ (N ) = 0 then N is tree-based and so t(N ) = 0, and the inequality holds. So suppose now that we have a support network N for N of minimal tier τ (N ) > 0. We are going to add leaves to N that in each case reduce the tier by at least 1. Consider a cycle in N . All cycles in N must have vertices of degree 2, since otherwise the cycle would not be needed to cover all vertices, violating minimality of the tier of N . Choose a degree 2 vertex v in the cycle adjacent to a vertex w of higher degree in N (which must exist as otherwise the cycle would not be connected to the rest of N , contradicting the connectedness of support networks), add a new vertex v to the edge {v, w}, add a leaf to v , and delete the edge {v , w}, from both N and N .
This creates a new network N and support network N , but now tier( N ) < tier( N ) because one cycle has been eliminated. Thus at most tier( N ) additional leaves need to be added to N to make a network that has a support network of tier 0, and is therefore tree-based. It follows that t(N ) ≤ τ (N ).
Finally, we show that τ (N ) ≤ (N ). Let T be a spanning tree of N that has (N ) extra leaves, i.e. leaves which are internal vertices of N (additional to leaf set X). Each such extra leaf of T has degree 1 in T but degree at least 3 in N . In particular, each such vertex has an incident edge which is not contained in T . For each extra leaf, we add one such edge of N to T , i.e. for each leaf of T , we increase the tier by 1. The result is a support network N of N of tier (N ). Therefore, by the minimality of τ (N ), τ (N ) ≤ (N ).
This completes the proof.
There is a key difference between the rooted and unrooted measures in the path-based measure p(N ), which does not directly generalize from rooted to unrooted. A direct generalization might be a measure such as "the number of edge disjoint paths that partition the network, minus |X|", but this does not hold for unrooted networks, as can be seen in the level 5 example in Figure 1(i), which is not tree-based but whose vertex set can be partitioned by |X| = 2 edge-disjoint paths. The point is that paths in rooted phylogenetic networks are directed, and the information carried in that directedness needs to be captured in the unrooted characterization by the implied ordering on the paths in Definition 3.1(3).
It can be easily shown that, while the rooted counterparts of , t, and p introduced in [5] can all be calculated in polynomial time, this is not possible for the above unrooted proximity measures, because otherwise, it could easily be decided if they equal 0 (which would contradict the known NP-completeness of the unrooted treebasedness decision problem [3], cf. Section 7). However, if it is already known that the LCUT graph or the LCUT simp graph of an unrooted phylogenetic network N have a Hamiltonian path, all four measures in Definition 3.1 are bounded, which we prove in the following proposition. Proof. There is a spanning tree for the network that consists of the Hamiltonian path plus the additional edges to the leaves from N \ LCUT (N ) or plus the additional (i) (ii) Figure 1. (i) Level 5 non-tree-based network whose vertices are covered by two edge-disjoint paths, shown in bold (this example of a non-tree-based network was independently presented in [2] and the erratum [4] to [3]). (ii) The same network with an additional diagonal edge making it tree-based (support tree highlighted in bold). This example is referred to in Theorem 4.6.
pending subtrees induced by N \ LCUT simp (N ), respectively, and this spanning tree has leaves that are all elements of X but possibly in addition one or both of the endpoints of the Hamiltonian path. This completes the proof.
Note that Proposition 3.4 nicely extends a result from [1], which states that if LCU T (N ) is Hamilton-connected (i.e. if for all pairs {a, b} from the vertex set of LCU T (N ) there is a Hamiltonian path from a to b), then N is tree-based, i.e. (N ) = 0. We next turn our attention to four new proximity measures.

Four new proximity measures
In this section we introduce four new proximity measures to being tree-based. The first is similar to the tier-based concept introduced in the previous section but uses the level of the network instead of the tier, the second uses the number of edges one needs to add to a network to make it tree-based, the third uses the number of nearest neighbor interchange (NNI) moves, and the fourth counts the excess edges present in a spanning tree. For all four of these measures, we will show that they are really new in the sense that they are not identical to the ones presented in the previous section.

4.1.
A proximity measure based on the level of the network. Let N ∈ PN (X), and define Note that λ(N ) is 0 precisely if N is tree-based, because trees are the only level-0 networks, so if λ(N ) = 0, we know that N has a support tree.
The following main theorem of this subsection shows that the four measures described in Section 3 provide an upper bound for λ(N ).
Proof. As noted already in Section 2, the level of a network is bounded above by its tier.
So now let N be a phylogenetic network with support networks N and N , where N = arg min{k | N is level-k-based} and N = arg min{k | N is tier-k-based}. This implies that N gives us λ(N ) and N gives us τ (N ). Let level(N ) and level(N ) denote the levels of N and N and tier(N ) and tier(N ) denote the tiers of N and N , respectively.
Then, by the minimality of N , we know that λ(N ) = level(N ) ≤ level(N ), because both networks are support networks of N . On the other hand, as stated above, we know that level(N ) ≤ tier(N ) = τ (N ). So in total, this shows that λ(N ) ≤ τ (N ) and thus completes the proof.
Observe that the inequality stated in Theorem 4.1 can indeed be strict for some networks. In fact, τ and λ can be made arbitrarily different, as in Observation 4.2.   Figure 2. This network basically consists of m non-trivial blobs, each of which is a copy of the simple network presented in Figure 1(i). As the network from Figure 1(i) is not tree-based, both the level and the tier of all support networks of each blob in N must be at least 1. In fact, it can easily be seen that both the level and the tier of the support network of each individual blob in N is precisely 1; cf. the highlighted support network in Figure 2 (note that the equality of the level and the tier in this case are due to Proposition 4.3 below, as the network in Figure 1(i) is simple). However, this implies that N , the network from Figure 2, is level-1-based, while it is also clear that the tier of the support network of N equals the number of such blobs of N , which is m. So we have λ(N ) = 1 and τ (N ) = m, which means that the difference τ (N ) − λ(N ) = m − 1 can be made arbitrarily large by adding more and more identical blobs. So in fact, for general networks N , λ(N ) and τ (N ) need not be identical, which shows that λ(N ) is indeed a proximity measure different from the ones introduced in the previous section.
The fact that λ and τ are closely related but generally not equal immediately gives rise to the question of whether there are types of networks for which we can guarantee equality. We end this section with the following proposition, which shows that indeed equality holds for simple networks. Proof. Note that in simple networks N , by definition the level of N equals the tier of N .
So now let N be a simple network with support networks N and N , where N = arg min{k | N is level-k-based} and N = arg min{k | N is tier-k-based}. This implies that N gives us λ(N ) and N gives us τ (N ). Let level(N ) and level(N ) denote the levels of N and N and tier(N ) and tier(N ) denote the tiers of N and N , respectively. Note that as N was simple, so are N and N , whichby the above observation -implies level(N ) = tier(N ) and level(N ) = tier(N ). Moreover, by the minimality of N , we can conclude τ (N ) = tier(N ) ≤ tier(N ) = level(N ) = λ(N ). So τ (N ) ≤ λ(N ). Moreover, by Theorem 4.1 we already know that λ(N ) ≤ τ (N ). This completes the proof.
We next turn our attention to another new proximity measure, which can be shown to be bounded by the ones introduced in Section 3.

4.2.
Proximity measure based on adding edges to the network. Before we can introduce the next measure, recall the method for adding internal edges to a phylogenetic network described in Section 2 by choosing two edges, subdividing them with a new vertex each and connecting these two new vertices with an extra edge. This procedure does not create any additional leaves and thus also no edges adjacent to leaves, but only internal edges. This immediately leads to the following Lemma. Proof. Recall that in this manuscript, we only consider proper networks, and that this implies that N either consists of only one vertex (in which case it is trivially tree-based, so there is nothing to show), or has at least two leaves, cf. Section 2. So let us assume N is proper and has at least two leaves, but is not tree-based. Then it has a spanning tree with at least one leaf not from X. For each such leaf, we claim that one can add an internal edge to the network that allows the creation of a spanning tree with one fewer leaf that is not in X.
The method is as follows. Take a spanning tree T for the network and choose a non-X leaf v from T . The degree of v is at least 3 in N , so there are at least two edges connected to v in N that are not in T . Choose one of them and subdivide it, adding a vertex v . Now, there is at least one vertex in T of degree at least 3, say w, because T has at least 3 leaves (because N has at least 2 and T by assumption has at least one more). Choose an edge incident to w that is on a path that does not lead to v in T (this is always possible because of the at least three edges incident to w, only one can be on the unique path from v to w in T ), and subdivide it, creating a new vertex w . Now add the edge e = {v , w } to the network. Then T can be modified to build a new spanning tree T by deleting the edge {w, w } and adding the edges {v, v } and {v , w }. We repeat this procedure until the resulting network N is tree-based.
We can use Lemma 4.4 to define another proximity measure as follows.  For the first inequality, let N be a tree-based network derived from N by inserting e(N ) extra edges, and let T be a support tree of N .
Observe that T must contain all of the e(N ) newly inserted edges, because otherwise if one was not needed, it could be removed from N without affecting the spanning tree T , violating minimality of e(N ). Consequently, if we delete these e(N ) edges, T turns into a forest F of e(N ) + 1 components, such that each vertex of N is contained in one of the components of F .
Note that each of the deleted e(N ) edges has at most 4 "connection points" in T , where a connection point is a node adjacent in N to an endpoint of one of the e(N ) edges. That is, the connection points are endpoints of edges in N that were subdivided to build N . If both vertices of an edge of N that has been subdivided to insert one of the e(N ) new edges are connection points in T , we call both of them path points. All connection points that are not path points are called terminals.
This implies that we have a forest F covering all nodes of N and in total, we have at most 2e(N ) terminals that are leaves in F . This is because when e is removed from N , at most two of the terminals become leaves in F (see the cases in Figure 3). This  Figure 3. Cases for the spanning tree T in N using an additional edge e, used in the proof of Theorem 4.6. Spanning trees are shown in grey, and path points are indicated by white circles. Case (i) has four terminals and no path points, case (ii) has two terminals and two path points, and case (iii) has no terminals and four path points.
Note that all trees in F can also be connected via edges in N (as N is connected). So if we now delete the e(N ) extra edges from T and use other edges of N to connect the trees of F in N , all leaves of the resulting tree T are either also leaves in T or terminals. As N is tree-based, all leaves of T are contained in X. Therefore, the number of leaves in T that are not in X is at most the number of terminals, which is at most 2e(N ). Therefore, (N ) ≤ 2e(N ) and thus 1 2 (N ) ≤ e(N ). This completes the proof.
Note that the bounds given by Theorem 4.6 are tight: examples of reaching the bounds are Figure 4 for the lower bound, and Figure 1(i) for the upper bound. In the latter case, as the network is not tree-based, it can easily be seen that e(N ) = 1 by considering Figure 1(ii). Here, this is also equal to (N ), which can be seen by connecting one internal endpoint of the paths in Figure 1(i) with the adjacent attachment point of a leaf -this will turn the two depicted paths into a support tree of N with one extra leaf, which is minimal for a non-tree-based network. Therefore, for the network in Figure 1

4.3.
Two more proximity measures linked to the NNI and additional edges. We are now in the position to introduce the final two proximity measures and to relate them both to one another as well as the previously introduced measures. One of these new measures, δ NNI , which is based on NNI moves, is possibly the most interesting one, as already explained in Section 1. Recall the definition of NNI moves from Section 2. For N ∈ PN (X) we define δ NNI (N ) = min{d NNI (N, N ) | N ∈ TBN (X)}.
Note that because NNI moves do not change the tier (as NNI moves by definition do not change the number of edges of the network), this minimum will be attained for a network N with tier(N ) = tier(N ). A final new proximity measure uses additional edges in spanning trees of the network.
In any spanning tree T of N , there is a unique path between any two leaves. If we consider the union of such paths between leaves from X, we have a subtree T X of T that contains the elements of X as leaves, and no other leaves (note that T X is the minimum spanning tree of X in T ). The remaining edges of T , namely E(T )\E(T X ), form another set of subtrees of T that we will call "pendant trees", each of which has leaves from N plus one leaf that is a vertex from T X (the attachment point to T X ).
Define a distance to tree-based as follows: This measure has a connection to the NNI distance, and is also greater than or equal to the four proximity measures introduced in Section 3, as the following result shows.

Proof.
(1) We show that there is an NNI move that reduces m by exactly 1. The idea is then to repeat this move until we reach a tree-based network.
Suppose that e is an edge in E(T ) \ E(T X ) which has one vertex v i on a path between leaves of N and one vertex w 1 that is not. Let {v i−1 , v i } be an edge in E(T X ) (since v i is on a path between leaves in X there must be a vertex adjacent to it also on such a path -it is possible v i−1 is itself a leaf in X), and let {w 1 , w 2 } be any other edge in N with w 2 = v i (such a vertex must exist because w 1 is not a leaf in X).
Then the NNI move v i−1 , v i , w 1 , w 2 → v i−1 , w 1 , v i , w 2 has the effect of inserting the edge e = {w 1 , v i } into a path between leaves, replacing the edge {v i−1 , v i } with the pair of edges {v i−1 , w 1 }, {w 1 , v i } (see Figure 5). Since the edge e has shifted from E(T ) \ E(T X ) to E(T X ), m has decreased by 1 as required. This shows that we need at most as many NNI moves to reach a tree-based network as there are extra edges in T .
(2) For a spanning tree T of N that minimizes the size of the set of edges E(T ) \ E(T X ) (which has size m(N )), it will contain as a subset all edges to leaves that are not from X. Thus in particular for that spanning tree the number of such leaves is at most m(N ). Consequently, whatever spanning tree of N that minimizes (N ) must have at most m(N ) non-X leaves.  Figure 5. An NNI move on the path v i−1 , v i , w 1 , w 2 showing how an edge e = {v i , w 1 } that is in a spanning tree of N but not on a path between two leaves x 1 , x 2 ∈ X can be incorporated into the path.
Note that in general m(N ) = δ NNI (N ), as the example in Figure 6(i) shows. The network shown in Figure 4 has m(N ) = 8, but δ NNI is at most 3. Likewise, in general m(N ) = (N ), with the same example having (N ) = 2.
We are now in the position to summarize all proximity measures introduced in this manuscript as well as their relationships, before we make some comments about rooted networks.

A summary of proximity measures introduced in this paper
There have been eight tree-based proximity measures for unrooted phylogenetic networks introduced in this paper, and we summarize them in Table 1. We have shown the following relationships among these measures: (N ) the minimal number of additional leaves in a spanning tree of N t(N ) the minimal number of leaves to add to make N tree-based p(N ) the minimal number of disjoint paths k including a leaf that partition V (N ), and for which all but the first have one end adjacent to another path; minus (n − 1) τ (N ) the minimal tier of a support network of N λ (N ) the minimal level of a support network of N e(N ) the minimal number of edges to add to make N tree-based δ NNI (N ) the minimal number of NNI moves from N to a tree-based network m(N ) the minimal number of edges in a spanning tree of N beyond a spanning X-tree Table 1. Informal descriptors of proximity measures to tree-based.
We represent these relationships in Figure 7, before we turn our attention to rooted networks.

Connections with rooted phylogenetic networks
In this section we discuss some issues surrounding lifting our measures to the rooted situation. We begin by relating tree-basedness in the two contexts.  Figure 6. This sequence of two NNI moves shows that the distance δ NNI (N ) from the network N at the top to a tree-based network such as the one at the bottom is at most 2 (in fact, it is precisely 2, because an exhaustive computer search has shown that it is strictly greater than 1). The paths on which the NNI moves act are shown in bold in the top two figures, and a support tree for the resulting tree-based network at the bottom is also shown in bold. Only vertices relevant to the NNI moves are labelled. Note that m(N ) = 8, as can be seen by the spanning tree shown in Figure 4(i), showing that in general δ NNI (N ) = m(N ).
6.1. Rooted and unrooted tree-based networks. First we need to introduce definitions of rooted phylogenetic networks and rooted tree-based phylogenetic networks.
In contrast to unrooted phylogenetic networks, rooted phylogenetic networks have both a special vertex called the root, and an orientation on each edge (hence we call them arcs). That is, a rooted phylogenetic network is an acyclic digraph with: a root of in-degree 0 and out-degree at least 1; leaves of in-degree 1 and out-degree 0; and internal vertices of in-degree 1 and out-degree at least 2 ('tree vertices') or out-degree 1 and in-degree at least 2 ('reticulation vertices').
There are several definitions of rooted tree-based networks in the literature. Initially they were defined for binary networks on X by saying (roughly) that a network Measures that are neither above nor below each other are either not linearly comparable, or their relationship is unknown. For instance, for particular networks δ NNI (N ) might be greater than (N ) (e.g. Figure 6), while the relationship between δ NNI (N ) and (N ), or λ(N ) and e(N ), is not known.
N r is tree-based if it can be constructed from a tree by additional arcs that avoid cycles, and this was shown to be equivalent to the statement that N r has a spanning tree whose leaves are those of X [6]: this formulation was used as the definition of tree-based in [5]. The first of these definitions was generalized to the non-binary case in several ways in [10], the main one of which is as follows: Definition 6.1 (Definition 4, [10]). A rooted nonbinary phylogenetic network N r is called tree-based with base-tree T , when it can be obtained from T via the following steps: (1) Add some vertices to arcs of T called attachment points, with in-degree and out-degree 1. (2) Add arcs, called linking arcs, between pairs of attachment points and from tree vertices to attachment points, so that N r remains acyclic and so that attachment points have in-degree or out-degree 1. (3) Suppress any attachment points that are not incident to a linking arc.
For our purposes it makes sense to make explicit "spanning tree" formulation of tree-based networks equivalent to the one for unrooted networks, with the following lemma: Lemma 6.2. A rooted phylogenetic network N r on X is tree-based if and only if it has a (rooted) spanning tree whose leaf-set is X.
Proof. The reverse direction is immediate: if N r is tree-based according to Definition 6.1, then the tree T on which it is constructed is a spanning tree with leaf-set X as required. Now suppose that N r is a rooted phylogenetic network that has a spanning tree T whose leaves are X. We need to show that it is tree-based, which is to say we need to show that it can be constructed from a base-tree via the procedure in Definition 6.1.
The spanning tree T has two kinds of vertices (apart from the root and the leaves): tree vertices (in-degree 1 and out-degree > 1); and vertices of degree 2. The arcs that are in N r but not T are therefore between these types of vertices. Now the crucial thing to note is that any tree vertex of T is also a tree vertex in N , as its out-degree is larger than 1 in T , and thus also in N , so its in-degree can only be 1. Therefore, an additional arc can never be between a pair of tree-vertices, because there is only one arc into each tree vertex in N r , and so that arc must already be in T (since T is a spanning tree). For the same reason, such additional arcs cannot be from a degree 2 vertex to a tree vertex. Therefore the arcs that are in N r but not T are only between degree 2 vertices of T , or from tree vertices in T to degree 2 vertices of T . Thus N r is tree-based with base-tree T and attachment points given by the degree 2 vertices in T , as required.
Effectively, this generalizes the characterization in the binary setting [6,Prop 1]. We now characterize the concrete connections between rooted and unrooted treebased networks.
For some of these connections, we need to generalize the notion of phylogenetic networks to degenerate networks.
A degenerate network is an acyclic digraph with: a root of in-degree 0 and outdegree at least 1; leaves of in-degree 1 and out-degree 0; and internal vertices of in-degree at least 1 and out-degree at least 2. Note that all rooted phylogenetic networks are contained in the class of degenerate networks, as they fulfill all requirements; but degenerate networks additionally contain networks that have vertices of both in-degree more than 1 and out-degree more than 1 (we call such vertices degenerate vertices). We call a degenerate network D strictly degenerate if it contains such a vertex. (For a related concept, see the notion of compressed network, that removes arcs from reticulate vertices to tree-vertices and replaces each such pair of vertices with a single degenerate vertex [13,Section 10.3.4]).
Let D be a strictly degenerate network with degenerate vertex setV . We call a rooted phylogenetic network N r a phylogenetic refinement of D if N r can be obtained from D by substituting all verticesv ∈V by two new verticesv 1 andv 2 and a directed edge e = (v 1 ,v 2 ) such that all incoming edges ofv in D are incoming edges ofv 1 in N r and all outgoing edges ofv in D are outgoing edges ofv 2 in N r . An example of a phylogenetic refinement of a strictly degenerate network is shown in Figure 8. The important thing here is to note that every degenerate network has a phylogenetic refinement.
However, also note that in the binary case, the set of degenerate networks is identical to the set of rooted phylogenetic networks, as in the binary case, for each vertex the sum of its incoming and outgoing edges must be 3; so it is impossible for a vertex to have both indegree and outdegree larger than 1.
Finally, just as with phylogenetic networks, we call a degenerate network D treebased if it has a spanning tree whose leaf set X coincides with that of D. We say that a rooted phylogenetic network (degenerate or not) is phylogenetically tree-based if it is tree-based with a support tree whose root has out-degree ≥ 2. Theorem 6.3. If N is an unrooted phylogenetic network on X, then it is tree-based (in the unrooted sense) if and only if it can be rooted on the midpoint of an edge, and with orientations specified on the edges, to give a degenerate network D that is phylogenetically tree-based.
Moreover, if N r is a phylogenetic refinement of a degenerate (phylogenetically) tree-based network D, N r is also (phylogenetically) tree-based. Proof. We start by proving both directions of the 'if and only if' statement. Figure 8. Unrooted tree-based network N and its conversion to a rooted phylogenetically tree-based network D, which in this case is strictly degenerate as it contains the degenerate vertexv. However, D can be converted into its refinement N r by replacing vertexv by a new edge e = (v 1 ,v 2 ). Note that N r is a rooted phylogenetic network (as we assume that all edges of D and N r are directed away from the root). Support trees for each network are highlighted.

Nv ρ Dv
( ⇐= ) Suppose that N can be made into a degenerate phylogenetically tree-based network by assigning a root to an edge and specifying orientations on all edges, as in the theorem statement. Then any support tree of N r whose root has out-degree ≥ 2 will become a spanning tree for the unrooted network N when the orientations on edges are ignored (suppressing the root vertex if it has degree 2), showing that N is tree-based.
( =⇒ ) If N is tree-based (in the unrooted sense) then we can delete a set F of edges of N to obtain a spanning tree T of N with leaf set X. Now select any edge e of T , root T at the midpoint of e, and direct all edges of T away from this root. Now let t : V → {1, 2, 3, . . . , |V |} be any one-to-one map satisfying the property that if (w, w ) is an arc of the directed version of T then t(w) < t(w ) (such a map always exists, since by the order extension principle, any poset -such as the one induced by T -has a linear extension, which can e.g. be found by the following greedy approach: Take a path from the root to any leaf and label the internal vertices on this path increasingly, starting with assigning the root label 1. Then, as long as there are unlabelled internal vertices, take another leaf and its unique path to the root, and start labelling increasingly at the uppermost unlabelled internal vertex again, etc.). Now, for each edge {u, v} ∈ F that was deleted, orient the edge (u, v) (i.e. u directed to v) if t(u) < t(v) and (v, u) if t(v) < t(u). Now all arcs of N are directed in a way that leads to no directed cycles, so we have turned N into a valid degenerate network D (note that D may contain vertices of both in-degree > 1 and out-degree > 1, as in Figure 8, so we cannot guarantee that this D is a rooted phylogenetic network), and N is also (phylogenetically) tree-based in the rooted sense (as implied by the rooted version of T ). This completes the first part of the proof.
Next, we show that if N r is a phylogenetic refinement of a degenerate (phylogenetically) tree-based network D, N r is also (phylogenetically) tree-based. This can easily be seen, because every support tree T of D is a spanning tree and thus covers all vertices -in particular also all degenerate vertices. Now, while replacing a degenerate vertexv in D by e = (v 1 ,v 2 ) as described above in order to turn D into N r , we also perform the same replacement in T in order to turn T into a support tree T of N r . In particular, we make sure the edge e is contained in T . This procedure leads to a spanning tree T of N r with the same leaf set as T , and as both T and N r have the same leaf set as D, this shows that T is a support tree for N r . This scenario is depicted by Figure 8. This completes the proof.
This result immediately leads to the following corollary.
Corollary 6.4. If N is a binary unrooted phylogenetic network on X, then it is tree-based (in the unrooted sense) if and only if it can be rooted on the midpoint of an edge, and with orientations specified on the edges, to give a binary rooted phylogenetic network network N r that is phylogenetically tree-based.
Proof. This is a direct consequence of Theorem 6.3, exploiting the fact that in the binary case, there exist no strictly degenerate networks, so the conversion of an unrooted network N into a degenerate network D as described in the proof of Theorem 6.3 will immediately lead to a rooted binary phylogenetic network.
Note that these results explain the contrast in the decision problem between rooted and unrooted networks: for a rooted network, determining whether it is tree-based can be done polynomially [6]; for an unrooted network, it is NP-complete [3]. The problem for the unrooted case is that the conversion to a rooted network requires testing orientations on a large number of edges -an exponential problem.
Moreover, also note that Theorem 6.3 heavily depends on the spanning tree in N r having a root of outdegree larger than 1; and note that there are rooted phylogenetic networks which are tree-based, but only have support trees in which the root has outdegree precisely 1 (for example the right hand network in Figure 9). This shows that being tree-based is not sufficient for a rooted network to give rise to an unrooted tree-based network -it indeed needs to be phylogenetically tree-based.
One might ask whether the binary result, Corollary 6.4, extends to non-binary phylogenetic networks without the requirement to include degeneracy. Using the definition of tree-based in this paper (Hendriksen's "loosely" tree-based [7]), the answer is unfortunately no. This can be seen from considering the tree-based network on six leaves obtained from a triangle with two leaves attached to each corner (network N in Figure 8) 2 . There are two alternative definitions of tree-based provided in [7], one of which does provide a result analogous to Corollary 6.4, as follows.
Hendriksen's definition of "tree-based" is that N is tree-based if it has a spanning tree T that has all edges of N between vertices of degree > 3, and for which all degree 2 vertices in T were degree 3 in N . In this case it is conceivable that a good choice of edge to place a root on might make a network rooted tree-based, but a poor choice might not. So proving a result like Corollary 6.4 may require a way to make wise choices about edges on which to root the network.
The Hendriksen definition of "strictly" tree-based, on the other hand, is that N is tree-based if it has a spanning tree that has all edges of N incident to vertices of degree > 3 [7]. In this case, we have the following analogue to Corollary 6.4, that uses Jetten and van Iersel's definition of a strictly tree-based rooted network: N r is strictly tree-based if it can be obtained from a base tree by adding attachment points to arcs, and connecting additional arcs only between attachment points in such a way as to keep N r acyclic [10, Definition 5]. As before, a phylogenetically strictly tree-based network is a strictly tree-based network that has a spanning tree whose root has degree greater than 1.
Theorem 6.5. If N is an unrooted phylogenetic network on X, then it is strictly tree-based (in the unrooted sense) if and only if it can be rooted on the midpoint of an edge, and with orientations specified on the edges, to give a rooted phylogenetic network N r that is phylogenetically strictly tree-based.
Proof. The proof follows very similar lines to that of Theorem 6.3.
If N is an unrooted, strictly tree-based network, then by definition it has a spanning tree T that contains all edges incident to vertices of degree greater than 3. Thus all edges in N but not in T are between vertices of degree 3 in N , and so they connect vertices of degree 2 in T . Choosing an edge in T , placing a root at its midpoint, and orienting the tree and the edges not in T according to the process described in the proof of Theorem 6.4 produces a rooted phylogenetic network that is phylogenetically strictly tree-based as required. Note that reinserting the edges from N but not T will create degree 3 vertices that cannot be degenerate, and so the network will be a valid non-degenerate network.
Conversely, if N r is a phylogenetically strictly tree-based network then it has a support tree that includes all arcs incident to vertices of degree greater than 3, and with linking arcs between vertices of degree 3. Ignoring orientation on arcs, and suppressing the root if it is degree 2, we obtain an unrooted phylogenetic network with a spanning tree that contains all edges incident to any vertex of degree greater than 3, and so is a strictly tree-based unrooted phylogenetic network.
6.2. Tree-based proximity, rooted and unrooted. Proximity measures for rooted phylogenetic networks have already been well-studied [5,12], but an interesting question is whether the new measures for unrooted phylogenetic networks introduced in the present paper have analogs in the rooted setting.
At least in one case, the indications are that the lifting is not obvious, best seen through an example such as the one given in Figure 9. This network is not treebased, and has (N ) = 1 -there is a spanning tree that has one additional leaf not from X.
However, an exhaustive search using the computer algebra system Mathematica 10 [9] showed that there is no choice of two edges in N that can be connected by a single edge to make the network tree-based, showing that e(N ) > 1 = (N ) (recall that in the unrooted setting we have shown that (N ) ≤ e(N ), Theorem 4.6). In this search, we checked all 132 combinations of ordered edge pairs such that one was the outgoing edge for the new extra edge and the other one the incoming edge. Note that if the resulting network was tree-based, the support tree would be a Hamiltonian path from the root to the only leaf (as there is just this one leaf). In 128 of the 132 cases, the resulting directed graph had no Hamiltonian path and could therefore not be tree-based. In the remaining four cases, there was a Hamiltonian path from the root to the only leaf, but the graph also contained a cycle -i.e. it was not a valid rooted phylogenetic network.
While adding a single edge in this case is not sufficient to make N tree-based, N can be made tree-based with the addition of two extra directed edges, meaning that e(N ) = 2. One such choice of two additional edges is shown in Figure 9. This means that for rooted phylogenetic networks, Theorem 4.6 does not hold, as here we have e(N ) > (N ).
In general, it seems more difficult to prove that it is always possible to find edges to add to make a network tree-based, largely because placing orientation on the edges means that additional edges can cause cycles. However, we have failed to find a network for which it has not been possible, and so we make the following conjecture.
Conjecture 6.6. Let N be a rooted phylogenetic network on leaf set X. Then there exists a set of directed edges that can be added to N to turn it into a treebased rooted phylogenetic network on leaf set X. Furthermore, we conjecture that (N ) ≤ e(N ) ≤ 2 (N ).

Figure 9.
On the left is a rooted, non-tree-based phylogenetic network with one leaf, and on the right, the same network with two additional edges (shown as dashed arrows) making it tree-based (with tree base shown in grey). Note that there are other solutions. For instance, instead of the lower added edge in the figure, one could add an edge from below 6 to above 5 (subdividing the edge (3,5) twice), also making it tree-based without introducing a cycle.
Another interesting aspect about the difference between rooted and unrooted networks is that the proximity measures based on bipartite matchings introduced for rooted networks in [5] do not carry over to the unrooted case. This is due to the fact that finding a maximum matching and determining its size can be done in polynomial time. However, we know that determining tree-basedness of an unrooted network is NP-complete [3], so the size of a maximum matching cannot be decisive here (unless P=NP).

Discussion
In the present manuscript, we have generalized -from the rooted to the unrooted setting -three proximity measures that measure the distance from any phylogenetic network to a tree-based phylogenetic network. We have shown that -just like in the rooted case -these measures turn out to be identical. Moreover, we introduced five new measures, one of which was also identical to the first three, whereas four can be shown to be different in general. Introducing and analyzing such proximity measures for unrooted networks, however, is not only of mathematical interest. It is also relevant for biological studies, where phylogenetic networks are often unrooted, e.g. because the root position is unknown, or because the network represents conflicts in the data rather than the actual evolutionary history of the underlying species.
Tree-basedness in rooted phylogenetic networks is known to be fundamentally different from the unrooted setting, as it can be decided in polynomial time [6], whereas it is NP-complete in the unrooted case [3]. In this regard, Theorem 6.4 from the present manuscript will be of wide interest, as it shows that tree-basedness of rooted and unrooted phylogenetic networks is related in an explicit sense: unrooted networks are tree-based if and only if there exists a root position such that the resulting rooted network is tree-based.
However, note that the difference in the computational complexity of the treebasedness decision problem between the rooted an the unrooted setting immediately implies that the calculation of all proximity measures introduced in the present manuscript for unrooted networks is necessarily NP-complete (otherwise, one could easily determine if these measures are 0, which for all of them is the case if and only if the underlying network is tree-based). So despite the relationships between the measures in the rooted case that have been introduced in [5] (and which can be calculated in polynomial time) and their generalized unrooted counterparts introduced in the present manuscript, their calculation in the unrooted case is actually hard, except for some classes of networks for which tree-basedness can be guaranteed and for which the proximity measures are therefore necessarily 0 [1]. Therefore, it would be an interesting question for future research to find good approximations to these measures.
Furthermore, the NNI-based proximity measure δ NNI gives rise to several interesting additional questions: First, simply regarding the metric, what is the maximum value of δ NNI for given n and k, where n is the number of leaves and k is the tier? For instance, clearly it is 0 for k ≤ 4 if N is binary, and for k ≤ 3 in general (since all such networks are tree-based, cf. [3] for the binary case and [2] for the non-binary case) and it is 1 for k = 5 in the binary case (there are only two non-tree-based networks of level 5, cf. [2], and both can be made tree-based with a single NNI by changing them to some other network; this works as all others are guaranteed to be tree-based). In all other cases, bounds on δ NNI still need to be determined.
Second, one might ask an inverse question. Given the large number of possible NNI moves, could it be that it is always possible for networks in certain tiers, to make a tree-based network not tree-based by a single NNI move? It turns out that in general the answer is "no", as Example 7.1 illustrates.
In that light, we could ask just how tree-based is a given tree-based networkwhat is the number of moves required to make a tree-based network not tree-based?
The latter two observations suggest a unique measure associated to tree-basedness with NNI moves that may take values of any integer -positive or negative. If we define tree-based networks on the boundary of tree-basedness (one NNI move from being a non-tree-based proper phylogenetic network) as having "tree-based rank" 0, we can say a tree-based network that is at least i NNI moves from the boundary has tree-based rank i, and a non-tree-based proper phylogenetic network that is i NNI moves from being tree-based (δ NNI (N ) = i) has tree-based rank −i. That is, we write ||N || TB for the tree-based rank of N , defined by ||N || TB = −δ NNI (N ) if N ∈ PN (X) \ TBN (X) |NNI moves to non-tree-based| − 1 if N ∈ TBN (X).
Thus, network N in Figure 10 has ||N || TB > 0. It would be interesting to understand what features of a tree-based network give it rank > 0.
Example 7.1. The network N in Figure 10 has ||N || TB = 4, confirmed with an exhaustive Mathematica search over its 1-, 2-, and 3-neighborhoods. That is, there is a sequence of four NNI moves from N that reach the network shown in Figure 1(i), one of the only two non-tree-based binary level 5 proper phylogenetic networks, and all proper phylogenetic networks of less than four NNI moves from N are treebased. Note that one can easily see that N has tree-based rank > 0 by the following argument.
Noting that a network obtained by an NNI move on a binary network remains binary, and all proper, binary, phylogenetic networks of level less than 5 are treebased [3], for N to be changed to a proper non-tree-based phylogenetic network in a single NNI move, it must become level 5, which requires merging its blobs. This forces the single move to be centered on the edge {u, v}. The two distinct NNI moves possible centred on this edge produce the networks N and N shown: N is generated by the move u 1 , u, v, v 1 , while N is generated by the move u 1 , u, v, v 2 (the other two possible moves are symmetric). Both of these are tree-based.
While this network has tree-based rank 4, it is nevertheless possible to "destroy" its tree-based-ness in just two moves, but only by leaving the space of proper phylogenetic networks. That is, one can perform two NNI moves on N to produce a network that is not tree-based, but it is also not a proper phylogenetic network. The notion of rank uses a distance within the space of proper phylogenetic networks.
Other open questions arising from the present manuscript are some relationships between the eight measures we introduced in this manuscript -while we have elaborated on some of them and seen, for instance, that some of them are equal and some act as bounds for others, we have not investigated all possible relationships between the different measures. Moreover, in Section 6 we have discussed some of the issues involved in lifting the new measures to the rooted case.
We are confident that these questions will inspire more research, as phylogenetic networks in general and tree-based ones in particular have gained more and more importance over recent years. Figure 10. The tier 5 tree-based network N is four NNI moves away from one of the only two non-tree-based binary networks in tier 5 (see [1] for these: one is shown in Figure 1). Its two level 5 neighbors, one NNI move away, are N and N shown. See Example 7.1.