Page 30 - Tequio 11

28 On some polytopes in phylogenetics/Hoessly/27-40

Many fascinating objects originated from methods and structures used to understand the evolutionary
history of species (Dress, Huber, Koolen, Moulton, & Spillner, 2011; Semple & Steel, 2003). We will first
introduce objects from discrete mathematics and then focus on three polytopes which can be related to objects
of interest in phylogenetics. Our treatment does not aim to be comprehensive in its scope, as these are fairly
developed fields. In our exposition and treatment we mostly focus on phylogenetic trees, tree-like metric
spaces and corresponding polytopes.

2. Introduction to some discrete objects

We introduce notions related to the combinatorics of phylogenetics, i.e. graphs in x 2.1, polytopes in x 2.2, finite
metric spaces and splits in x 2.3 and phylogenetic trees in x 2.4.

2.1 Graphs and trees
In phylogenetics, graphs and trees are used to represent evolutionary relationships between species. We will
2
focus on undirected graphs, since this is our main setting of interest.
A finite undirected graph = (, ) consists of vertices = () and edges ⊆ , written as = (). A
*
path is a sequence , , - , ⋯ , / of edges which join a sequence of distinct vertices. Graphs in which two arbitrary
vertices are connected by exactly one path are called trees, as an example consider Figure 1. A graph is
connected if there is a path between any two vertices. The degree () of a vertex ∈ is the number of
edges incident to .

Figure 1.
Only the right graph is a tree.

Lemma 2.1 ((Bollobas, 1998, equation (1), p.4 and x 1.2)) Let = (, ) be a connected graph. Then

∑ () = 2||, and furthermore || = || − 1 if and only if is a tree.
5∈6

Next we introduce a particular notion of a tree used in phylogenetics. Let be a set. An -tree is a labelling of
some of the vertices of a tree , where every leaf of is labelled. We denote an -tree by (, ), where : →
() is the labelling map. When all internal vertices are of degree 3, we call it binary -tree.

2 I.e. graphs where the edges are not directed.
2 I.e. graphs where the edges are not directed.

Tequio, enero-abril 2021, vol. 4, no. 11