# Separating Path Systems for the Complete Graph

Belinda Wickes ∗

(September 2022)

###### Abstract

For any graph $G$, a separating path system of $G$ is a family of paths in $G$
with the property that for any edges $e,e^{\prime}\in E(G)$ there is at least
one path in the family that contains one of $e$ and $e^{\prime}$ but not the
other. We investigate the size of the smallest separating path system for
$K_{n}$, denoted $f(K_{n})$.

It is known that $n-1\leq f(K_{n})\leq 2n+4$, our main result is a
construction that reduces the upper bound to
$f(K_{n})\leq\left(\frac{21}{16}+o(1)\right)n$ for sufficiently large $n$, and
to $f(K_{n})\leq n$ whenever $n=p,p+1$ for prime $p$.

A key idea in our construction is to reduce the problem to finding a single
path with some particular properties we call a Generator Path. These are
defined in such a way that the $n$ cyclic rotations of a generator path
provide a separating path system for $K_{n}$. Hence existence of a generator
path for some $K_{n}$ gives $f(K_{n})\leq n$. We construct such paths for all
$K_{n}$ with $n\leq 20$, and show that generator paths exist whenever $n$ is
prime.

00footnotetext: ∗ School of Mathematical Science, Queen Mary University of
London, London, E1 4NS, UK.
Contact<EMAIL_ADDRESS>
##  1 Introduction

The study of separation problems was initiated by Rényi in the 1960s [7]. The
problem is to find a minimal family $\mathcal{F}$ of subsets of ground set
$[n]=\\{1,2,\dotsc,n\\}$, so that for every ordered pair of distinct
$x,y\in[n]$ there is some $F\in\mathcal{F}$ with either $x\in F$ and $y\notin
F$, or $y\in F$ and $x\notin F$.

It is trivial that in this case $|\mathcal{F}|=\lceil\log_{2}(n)\rceil$.
However, by enforcing some structure on our ground set or various restrictions
to the members of $\mathcal{F}$, the question opens up to be an interesting
problem. One particularly interesting way of doing this is to have the ground
set be vertices or edges of a graph, and the separators inherit certain
properties from the graph (see [3],[2],[5]). In this paper we focus on what
separation means in the context of a ground set of graph edges, and when our
separators are restricted to being paths. Problems with such a focus were
introduced by Balogh, Csaba, Martin, and Pluhár [1] as well as Falgas-Ravry,
Kittipassorn, Korándi, Letzter, and Narayanan [4]. We begin by outlining
exactly what we mean to separate a graph by paths.

######  Definition 1.1.

Let $G$ be a graph and $e,e^{\prime}\in E(G)$, and let $P\subseteq E(G)$. We
say that $P$ separates $e$ and $e^{\prime}$ if we have $e\in P$ and
$e^{\prime}\notin P$, or $e^{\prime}\in P$ and $e\notin P$. Let $\mathcal{S}$
be a family of subsets of $E(G)$ such that for any distinct edges
$e,e^{\prime}\in E(G)$ there is some $P\in\mathcal{S}$ which separates $e$ and
$e^{\prime}$, then we say that $\mathcal{S}$ is a separating system for $G$.
If we also have the condition that every element of $\mathcal{S}$ is a path in
$G$, then we call $\mathcal{S}$ a separating path system of $G$.

We will use the notation $f(G)$ to mean the size of the smallest path
separating system for a graph $G$ as per [4]. Straight away we notice that
$E(G)$ is itself a separating path system where all the paths consist of a
single edge. So in particular we get $f(G)\leq|E(G)|$. We also get the bound
$f(G)\geq\log_{2}(|E(G)|)$ from the initial separating property without
considering paths.

In [4] the authors find bounds on $f(G)$ for a selection of graphs $G$
including trees and certain random graphs. They also ask about the case where
$G$ is the complete graph on $n$ vertices, that is to determine the exact
value of $f(K_{n})$. The current best known bounds are

$n-1\leq f(K_{n})\leq 2n+4.$

The upper bound here is a non-constructive result from [1] and the lower bound
a simple counting argument found in [4]. The aim of this paper is to
investigate the properties of separating path systems of $K_{n}$, and provide
a construction which improves the upper bound.

######  Theorem 1.2.

For $n\geq 44$, there exists a separating path system for $K_{n}$ with size at
most

$\frac{21n+16\log_{2}n+232}{16}.$

A key tool for our methods is the notion of Generator Paths, a special path in
$K_{n}$ with nice properties that allow us to create a separating path system
by taking only rotated copies of the generator. We show that existence of such
a path gives rise to a separating path system of size $n$. We define these
special paths and show that they exist for small values of $n$ as well as all
prime values of $n$. This gives the following results.

######  Proposition 1.3.

For all $n\leq 20$ we have that $f(K_{n})\leq n$.

######  Theorem 1.4.

Let $p$ be an odd prime, then we have $f(K_{p})\leq p$ and $f(K_{p+1})\leq
p+1$.

Our general upper bound (Theorem 1.2) comes from constructing an approximate
version of this special Generator Path, and correcting any problems with a
small number of additional paths. The bulk of the work is in finding this
approximation path, which is the content of Section 3.3.

The version of the problem we are considering is sometimes called ‘weak
separation’, the case where we have all pairs $x,y$ separated by two
separators in an identical way is referred to as ‘strong separation’.
Equivalently, unordered distinct $x,y\in[n]$ are strongly separated by
$\mathcal{F}$ if there exists $F,F^{\prime}\in\mathcal{F}$ with $x\in F$,
$y\notin F$ and $y\in F^{\prime}$, $x\notin F^{\prime}$. For this paper we
will stick to the weak version of the problem, but elements of our approach
may be adapted to suit this alternate definition. We will discuss this briefly
at the end of Section 3.1.

##  2 Lower Bound

There are several key observations from the definition that highlight the
structure of small separating path systems. Let $\mathcal{S}$ be a separating
path system for a graph $G$. Firstly, there can be no more than one edge that
is not found in any $P\in\mathcal{S}$. This means our family of paths must
cover all but one of the edges of $G$.

Secondly, at most one edge in $G$ can appear in every path of $\mathcal{S}$.
If not, say $x,y\in P$ for all $P\in\mathcal{S}$, then there is clearly no $P$
that separates $x$ and $y$, therefore $\mathcal{S}$ cannot be a separating
path system for $G$.

Finally, looking at some path $P$ in $\mathcal{S}$, if any two edges appear
exclusively in $P$ then they cannot be separated by $\mathcal{S}$. Hence, for
any path in $\mathcal{S}$ there is at most one unique edge, that is, at most
one edge that does not appear in any other path.

With these observations in mind, we repeat the lower bound argument from [4]
to demonstrate the properties small separating path systems should have.

######  Lemma 2.1.

(Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan [4]) For the
complete graph on $n$ vertices, the minimum size of a path separating system
is at least $n-1$. That is, $f(K_{n})\geq n-1$.

###### Proof.

Let $n\in\mathbb{N}$ and suppose for a contradiction that $\mathcal{S}$ is a
separating path system for $K_{n}$ such that $|\mathcal{S}|\leq n-2$.

Each $P\in\mathcal{S}$ has at most 1 unique edge, therefore at most $n-2$
edges of $K_{n}$ appear exactly once in $\mathcal{S}$. Recall that there is at
most 1 edge that appears exactly 0 times in $\mathcal{S}$. We use this to
count the number of edges that appear at least twice in $\mathcal{S}$, the
number of such edges is at least

$\binom{n}{2}-(n-2)-1=\frac{1}{2}(n-2)(n-1).$

On the other hand, as the maximum length of any $P\in\mathcal{S}$ is $n-1$, we
have that the total number of edges used (with multiplicity) is at most
$(n-1)(n-2)$. The number of edges in $K_{n}$ appearing in $\mathcal{S}$ is at
least $\binom{n}{2}-1$. We can count the edges that appear twice using these
values, this is at most

$(n-2)(n-1)-\left(\binom{n}{2}-1\right)=\frac{1}{2}(n-2)(n-3).$

This is a contradiction since $\mathcal{S}$ cannot satisfy both conditions,
hence $f(K_{n})\geq n-1$. ∎

This proof demonstrates the importance of long paths in separating systems. To
get an upper bound matching this lower bound of $n-1$, we must construct
families with full length paths. In fact any separating path system for
$K_{n}$ with size $n-1$ must have the following properties:

  * •

Each path has length $n-1$,

  * •

There is one edge in $K_{n}$ that is not in any path in the system,

  * •

Every path in the system has one unique edge,

  * •

All other edges appear in exactly two paths.

With this in mind it is easy to construct separating path systems of size
$n-1$ by hand for small values of $n$, showing this lower bound is tight for
small $n$.

It should also be noted that the only property of paths used in this proof is
the fact that a path contains at most $n-1$ edges. Since this is true of many
graphs it can be used in other separation contexts. For example, any tree
which is a subgraph of $K_{n}$ has at most $n-1$ edges, so this lower bound
holds for trees in general. In fact, by taking a family of $n-1$ stars, each
centred around a different vertex of $K_{n}$, we create a separating tree
system for $K_{n}$ of size exactly $n-1$. So the lower bound of $n-1$ is tight
for separating tree systems.

##  3 Upper Bounds

While there has been no direct work on an upper bound for our problem, Balogh,
Csaba, Martin, and Pluhár gave the following result for the strong version of
the problem.

######  Theorem 3.1.

(Balogh, Csaba, Martin, and Pluhár [1]) For $n\geq 10$ there exists a strong
separating path system for $K_{n}$ with size at most $2n+4$.

This gives an upper bound of $f(K_{n})\leq 2n+4$, the proof in this case was
probabilistic.

###  3.1 Generator Paths

Thinking of the vertices of $K_{n}$ as vertices of a regular polygon, we may
take any path $P$ and create a new path $P^{\prime}$ by rotating each edge of
$P$ one vertex clockwise. In this way we can find $n$ paths that are
isomorphic copies of each other. If our initial path $P$ has some carefully
chosen properties forcing each rotation to share exactly one edge with $P$,
then we may have a family of separating paths generated by a single path. This
reduces the problem to looking for one path rather than a whole system of
paths. We need to be careful when choosing our path so that the rotations
overlap each other in the right way.

To set it up, label the vertices $1,\dotsc,n$ and arrange them clockwise on a
regular polygon. It is helpful to think of our edges by the distance they
travel rather than endpoints here. We call an edge at vertex $v$ an $x$-type
edge if its other endpoint is $v+x$ for $1\leq
x\leq\lfloor\frac{n}{2}\rfloor$, where all calculations are done modulo $n$.
Note that there are precisely $n$ edges in $K_{n}$ that have type $x$ for
$1\leq x<\frac{n}{2}$, and in the case where $n$ is even there are precisely
$\frac{n}{2}$ edges that have type $\frac{n}{2}$.

$1$$2$$3$$4$$5$$P$$P^{\prime}$ Figure 1: Rotations in $K_{5}$

In Figure 1 we have an example of a path $P=(4,1,2,5)$ in $K_{5}$. This path
contains two $2$-type edges, at vertices $4$ and $5$, and one $1$-type edge at
vertex $1$. Consider the path $P^{\prime}=(5,2,3,1)$, it also contains two
$2$-type edges, this time at vertices $5$ and $1$, and one $1$-type edge at
vertex $2$. This new path is simply $P$ rotated once clockwise. Note that the
edge types appear in the same order and at the same distance from each other,
this is because edge type is unchanged by rotation. If we take the family
consisting of all 5 rotations of $P$, we get a separating path system for
$K_{5}$.

Naturally we wish to pin down the properties a path must have in order to
generate a separating path system. But first we clarify some terminology and
notation. For any $x$-type edge $e=(v,v+x)$ we call $v$ the starting vertex of
$e$. Note that every edge has a unique starting vertex unless it is of type
$\frac{n}{2}$, in which case either endpoint can be considered as the starting
vertex. We define the clockwise distance (on $K_{n}$) between vertices $v$ and
$u$ to be the value $\min(|v-u|,n-|v-u|)$ and write $cd(v,u)$ for this.
Similarly, we say the clockwise distance (on $K_{n}$) between two edges $e$
and $e^{\prime}$ to mean the clockwise distance between the starting vertices
of $e$ and $e^{\prime}$ and we write $cd(e,e^{\prime})$ for this value. In
particular, if $e=(v,v+x)$ has type $x$ and $e^{\prime}=(u,u+y)$ has type $y$,
then $cd(e,e^{\prime})=cd(v,u)=\min(|v-u|,n-|v-u|)$.

######  Definition 3.2.

A path $P$ on the complete graph $K_{n}$ is called a generator path for $n$ if
it satisfies the following conditions. For odd $n$:

(GP1)

$P$ contains at least one edge of each of the $\frac{n-1}{2}$ types.

(GP2)

There is at most one edge type that appears exactly once, and there are no
edge types that appear more than twice in $P$.

(GP3)

Let $e$ and $e^{\prime}$ be $x$-type edges in $P$, and let
$cd(e,e^{\prime})=d$. If there two other edges $h,h^{\prime}\in P$, such that
both have type $y\neq x$, then $cd(h,h^{\prime})\neq d$.

For even $n$:

(GP1)

$P$ contains at least one edge of each of the $\frac{n}{2}$ types.

(GP2)

There is at most one edge type from $[\frac{n}{2}-1]$ that appears exactly
once, and there are no edge types that appear more than twice in $P$.

(GP3)

Let $e$ and $e^{\prime}$ be $x$-type edges in $P$, and let
$cd(e,e^{\prime})=d$. If there two other edges $h,h^{\prime}\in P$, such that
both have type $y\neq x$, then $cd(h,h^{\prime})\neq d$. Additionally, no pair
of edges in $P$ with the same type are at distance $\frac{n}{2}$.

The next result shows that if we can find a generator path for $n$, then it
will give us a separating path system of size $n$.

######  Lemma 3.3.

If $P$ is a generator path for $n$, then the family of all $n$ rotations of
$P$ is a separating path system for $K_{n}$. Hence, if such a path $P$ exists
then $f(K_{n})\leq n$.

###### Proof.

Let $P$ be a generator path for $n$, and $\mathcal{S}$ be the family generated
by taking all the rotations of $P$. In particular, let $P=P_{0}$ and
$P_{i}=\\{(u+i,v+i):(u,v)\in P\\}$ be the path generated by rotating $P$
clockwise by $i$. Since $P$ is a path in $K_{n}$ we have that every
$P_{i}\in\mathcal{S}$ is a path in $K_{n}$. It is left only to show that every
pair of edges in $K_{n}$ is separated by some path in $\mathcal{S}$.

Consider edges $e=(v,v+x)$ and $e^{\prime}=(v^{\prime},v^{\prime}+y)$ in
$K_{n}$, where $e$ is an $x$-type edge and $e^{\prime}$ is a $y$-type edge.

By (GP1), $P$ contains at least one edge of type $x$, therefore there is some
$i\in[0,n-1]$ such that $e\in P_{i}$. If $e^{\prime}\notin P_{i}$ then the
edges are separated by $P_{i}$, so assume otherwise.

Suppose first that $y=x$. Let $cd(e,e^{\prime})=d$, without loss of generality
we can assume that $v^{\prime}=v+d$. Consider the path $P_{i+d}$, where
calculations are modulo $n$, we must have $e^{\prime}\in P_{i+d}$. Note that
$v^{\prime}+d=v+2d\neq v$. Indeed, this is only true when $2d=n$, since $P$ is
a generator path we have $d\neq\frac{n}{2}$ by (GP3). Therefore, $e\notin
P_{i+d}$ since $P_{i}$ does not contain any additional $x$-type edges (by
(GP2)). Hence, $e$ and $e^{\prime}$ are separated by $P_{i+d}$.

Now suppose that $y\neq x$. We first consider the case where $n$ is even and
$x=\frac{n}{2}$. If $x=\frac{n}{2}$, then we have that $e\in
P_{i+\frac{n}{2}}$. Since $e^{\prime}\in P_{i}$ in order for $e^{\prime}$ to
be in $P_{i+\frac{n}{2}}$ we must have that $P_{i}$ contains another $y$-type
edge $h^{\prime}=(u^{\prime},u^{\prime}+y)$, such that
$u^{\prime}+\frac{n}{2}=v^{\prime}$ or $u^{\prime}-\frac{n}{2}=v^{\prime}$. In
other words we must have $cd(e^{\prime},h^{\prime})=\frac{n}{2}$, this cannot
happen by (GP3). Similarly, if $y=\frac{n}{2}$ then $e$ and $e^{\prime}$ are
separated by $\mathcal{S}$.

Finally we suppose that $y\neq x$ and $x,y\neq\frac{n}{2}$. Then by (GP1), $P$
contains two edges of one of the types $x$ or $y$. Without loss of generality
assume that $P$ contains two $x$-type edges. Let $h=(u,u+x)\in P_{i}$ be the
other $x$-type edge, and let $cd(e,h)=d$. We have that $e\in P_{j}$ for one of
$j=i+d$ or $j=i-d$. The only way for $e^{\prime}\in P_{j}$ is if there is
another $y$-type edge $h^{\prime}=(u^{\prime},u^{\prime}+y)\in P_{i}$ such
that $cd(e^{\prime},h^{\prime})=d$. This clearly cannot happen by (GP3). So we
have that $e$ and $e^{\prime}$ are separated by $P_{j}$. ∎

This makes finding separating path systems for small values of $n$ fairly
straightforward. In fact we can find generator paths for all $n\leq 20$ by
hand. The generator paths for $n=2,3,4$ are trivial, the generator paths
$P(n)$ for other values of $n\leq 20$ are given below:
$P(5)=(1,3,2,5)$,
$P(6)=(1,5,4,3,6)$,
$P(7)=(1,2,3,5,7,4)$,
$P(8)=(1,3,5,2,6,7,8)$,
$P(9)=(1,5,9,3,4,6,8,2)$,
$P(10)=(1,4,7,6,5,9,3,8,10)$,
$P(11)=(1,3,5,10,4,11,7,8,9,6)$,
$P(12)=(1,2,11,9,10,3,7,4,8,6,12,5)$,
$P(13)=(1,3,4,13,11,6,10,7,12,5,8,9)$,
$P(14)=(1,3,6,9,10,11,2,7,13,5,12,8,4)$,
$P(15)=(1,14,15,5,10,3,12,6,9,13,2,4,11,8,7)$,
$P(16)=(1,11,13,15,14,3,8,12,16,9,2,10,7,4,5)$,
$P(17)=(1,3,5,16,10,11,12,9,6,15,7,14,4,17,13,8)$,
$P(18)=(1,15,10,5,13,3,12,9,6,7,8,2,14,16,18,11,4)$,
$P(19)=(1,3,5,18,12,11,10,13,16,7,17,6,14,9,4,19,15,8)$,
$P(20)=(1,5,10,15,18,8,17,6,20,14,7,19,2,4,16,9,13,12,11)$.

######  Proposition 1.3.

For all $n\leq 20$ we have that $f(K_{n})\leq n$.

As well as these small examples, we can also find generator paths for prime
values of $n$. The construction uses the properties of primitive roots, an
integer $g$ is a primitive root modulo $n$ if for every integer $h$ which is
co-prime to $n$ there is some integer $i$ such that $h\equiv g^{i}\mod n$.

######  Lemma 3.4.

There exists a generator path for $n$ whenever $n$ is an odd prime.

###### Proof.

Let $p$ be an odd prime, then it is known that there exists a primitive root
$g$ modulo $p$. We can therefore write every integer in $[p-1]$ in the form
$g^{i}$ for $i\in[p-1]$.

Consider the path on $K_{p}$ given by
$P=(p,g,g+g^{2},g+g^{2}+g^{3},\dotsc,\sum_{i=1}^{p-2}g^{i})$, which is the
path starting at vertex $p$ and taking a $g$ length edge, followed by a
$g^{2}$ length edge, followed by a $g^{3}$ length edge, and so on until there
are $p-2$ edges in the path. Here we use ‘length’ to avoid confusion, an
$x$-type edge may have length $x$ or $n-x$. We claim that this path is a
generator path for $n=p$.

We must check that $P$ is indeed a path in $K_{p}$, and that it satisfies
(GP1), (GP2), and (GP3).

First we show that $P$ is indeed a path. To see this note that $P$ is a path
as long as none of the vertices
$p,g,g+g^{2},g+g^{2}+g^{3},\dotsc,\sum_{i=1}^{j}g^{i},\dotsc,\sum_{i=1}^{p-2}g^{i}$
are congruent modulo $p$.

Suppose that

$\sum_{i=1}^{m}g^{i}\equiv\sum_{i=1}^{j}g^{i}\mod p$

for some $m,j\in[p-2]$. Then we must have that

$\frac{g^{m+1}-g}{g-1}\equiv\frac{g^{j+1}-g}{g-1}\mod p$

and hence

$g^{m-j}\equiv 1\mod p.$

Since $g$ is a primitive root we know that $g^{p-1}\equiv 1\mod p$ and
$g^{i}\not\equiv 1\mod p$ whenever $i<p-1$. Therefore we must have

$m\equiv j\mod p-1.$

Clearly this means $m=j$ since $m,j\in[p-2]$. Now we must also check that the
vertex $p$ is distinct from the others. For a contradiction suppose that

$\sum_{i=1}^{m}g^{i}\equiv p\mod p$

for some $m\in[p-2]$. This gives

$g^{m}\equiv 1\mod p$

so we must have $m\equiv 0\mod p-1$, a contradiction of $m\in[p-2]$.

We conclude that $P$ is indeed a path in $K_{p}$. It remains to show that $P$
satisfies the three conditions.

Let $k=\frac{p-1}{2}$ and note that since $g$ is a primitive root and $p$ is
prime, we have that $g^{k}\equiv-1\mod p$ and $g^{i}\not\equiv-1\mod p$
whenever $i<k$. This means that $g^{i}+g^{k+i}\equiv 0\mod p$. In other words
an edge in $P$ with length $g^{i}$ and an edge with length $g^{k+i}$ have the
same edge type.

Observe that the first $k$ edges of $P$ each have unique edge type, and the
$k+i$ edge of $P$ has the same type as edge $i$. Thus $P$ contains two edges
of every type except type $1$, since the $k$th edge in $P$ is the unique
$1$-type edge. Hence, $P$ satisfies (GP1) and (GP2).

For any pair of same type edges in $P$ one edge will be length $g^{j}$ and the
other will be length $g^{k+j}$ for $j\in[k]$. Since $g^{i}\not\equiv
g^{k+i}\mod p$ this means we have one of two cases, either

  1. 1.

the starting vertex of the $g^{j}$ edge will be $\sum_{i=1}^{j-1}g^{i}$ and
the starting vertex of the $g^{k+j}$ edge will be $\sum_{i=1}^{k+j}g^{i}$, or

  2. 2.

the starting vertex of the $g^{j}$ edge will be $\sum_{i=1}^{j}g^{i}$ and the
starting vertex of the $g^{k+j}$ edge will be $\sum_{i=1}^{k+j-1}g^{i}$.

Note that the clockwise distance between the edges for the first case is given
by

$\sum_{i=1}^{k+j}g^{i}-\sum_{i=1}^{j-1}g^{i}\equiv\frac{g^{k+j+1}-g^{j}}{g-1}\mod
p\quad\text{ or }\quad-\frac{g^{k+j+1}-g^{j}}{g-1}\mod p$

whichever is in $[k]$, and in the second case it is given by

$\sum_{i=1}^{k+j-1}g^{i}-\sum_{i=1}^{j}g^{i}\equiv\frac{g^{k+j}-g^{j+1}}{g-1}\mod
p\quad\text{ or }\quad-\frac{g^{k+j}-g^{j+1}}{g-1}\mod p.$

Since we know the additive inverse of $g^{j}$ is $-g^{j}\equiv g^{k+j}\mod p$
we can see that the distances in the two cases are equivalent. So we assume we
are in case 1.

We must now show that the clockwise distance between pairs of same type edges
are not repeated, (GP3).

Consider edges in $P$ given by $g^{j}$,$g^{k+j}$,$g^{m}$, and $g^{k+m}$.
Suppose that

$\frac{g^{k+j+1}-g^{j}}{g-1}\equiv\frac{g^{k+m+1}-g^{m}}{g-1}\mod p.$

Then we have that

$g^{k+j+1}(1-g^{m-j})\equiv g^{j}(1-g^{m-j})\mod p$

and hence

$g^{k+1}\equiv 1\mod p.$

This is a contradiction as we know that $g^{p-1}\equiv 1\mod p$ and
$g^{i}\not\equiv 1\mod p$ whenever $i<p-1$. The proof when we take one or both
of the clockwise distances to be $-\frac{g^{k+i+1}-g^{j}i}{g-1}\mod p$ is
equivalent.

Therefore $P$ is indeed a generator path for $n=p$. ∎

This gives us an upper bound for $f(K_{n})$ when $n$ is a prime number.

######  Corollary 3.5.

We have $f(K_{p})\leq p$ whenever $p$ is prime.

We can also use the structure of the generator path in Lemma 3.4 along with
the properties of primes to give an upper bound for $n=p+1$.

######  Theorem 3.6.

Let $p$ be an odd prime, then we have $f(K_{p+1})\leq p+1$.

###### Proof.

Let $K^{\prime}$ be the complete graph on $p$ vertices given by removing the
vertex $p+1$ from $K_{p+1}$. Let $P$ be the generator path for $p$ given in
the proof of Lemma 3.4, and let $\mathcal{P}=\\{P_{i}:0\leq i\leq p-1\\}$ be
the family of rotations of $P$, where $P_{i}$ is $P$ rotated clockwise by $i$.
Recall that the edge $h=(\sum_{i=1}^{k-1}g^{i},\sum_{i=1}^{k}g^{i})$ where
$k=\frac{p-1}{2}$ is the unique $1$-type edge in $P$.

Let $T=\\{(1,2),(2,3),\dotsc,(p-1,p),(p,1)\\}$ be the set of all $1$-type
edges in $K^{\prime}$, and note that $T\setminus\\{h\\}$ is a path in
$K^{\prime}$ and also in $K_{p+1}$.

Let $P^{\prime}_{i}=P_{i}\cup\\{(i,p+1)\\}$ for every $1\leq i\leq p-1$. Since
each $P_{i}$ has the vertex $i$ and as endpoint, each $P^{\prime}_{i}$ is a
path in $K_{p+1}$ and contains $P_{i}$ as a sub-path.

Define
$\mathcal{S}=\\{P_{0},P^{\prime}_{1},P^{\prime}_{2},\dotsc,P^{\prime}_{p-1},T\setminus\\{h\\}\\}$.
We claim that $\mathcal{S}$ is a separating path system for $K_{p+1}$.

Clearly all elements of $\mathcal{S}$ are paths in $K_{p+1}$, so it remains to
check that any two edges are separated by some path in $\mathcal{S}$. Let
$e,e^{\prime}\in E(K_{p+1})$, suppose first that $e,e^{\prime}\in
E(K^{\prime})$. Then $e$ and $e^{\prime}$ are separated by
$\\{P_{0},P^{\prime}_{1},P^{\prime}_{2},\dotsc,P^{\prime}_{p-1}\\}$ since we
know the are separated by $\mathcal{P}$.

Suppose instead that $e^{\prime}\in E(K^{\prime})$ and $e\notin
E(K^{\prime})$. Then $e$ must be of the form $(v,p+1)$ for some $v\in[p]$. Let
$x\in[\frac{p-1}{2}]$ be the edge type of $e^{\prime}$ in $K^{\prime}$, and
note that if $x\neq 1$ there exists $0\leq i,j\leq p-1$ such that
$e^{\prime}\in P_{i},P_{j}$. Therefore we have $e^{\prime}\in
P^{\prime}_{i},P^{\prime}_{j}$. Clearly $e=(v,p+1)$ cannot be in both of these
paths, therefore the edges $e$ and $e^{\prime}$ must be separated by
$\mathcal{S}$. Now, if $x=1$ note that either $e^{\prime}\in P_{0}$ or
$e^{\prime}\in T\setminus\\{h\\}$, and since $e$ cannot be in either of these
paths, the edges are again separated by $\mathcal{S}$.

Finally, suppose $e,e^{\prime}\notin E(K^{\prime})$. Then we can write them in
the form $e=(v,p+1)$ and $e^{\prime}=(u,p+1)$ where $u,v\in[p]$. Since $u\neq
v$ we must have that at least one of $u$ and $v$ lies in $[p-1]$, without loss
of generality assume $v\in[p-1]$. Then we have that $e\in P^{\prime}_{v}$, and
clearly $u\notin P^{\prime}_{v}$. Hence the edges are separated by
$\mathcal{S}$.

∎

Together, Corollary 3.5 and Theorem 3.6 give Theorem 1.4. Based on the small
cases along with Lemma 3.4, we suspect that a generator path exists for every
$n$, and in particular that the lower bound in Theorem 2.1 is close to the
true value of $f(K_{n})$ for all $n$. It would be useful to know for certain
whether or not generator paths exist in general.

######  Question 3.7.

For which values of $n\in\mathbb{N}$ do generator paths exist?

Our motivation for this question comes from separating path systems, but the
question of existence of paths containing specific arrangements of edge types
seems tricky and interesting in its own right. For instance, McKay and Peters
investigate which multisets of edge types are realisable as a path in [6].

Furthermore, if $P$ is a generator path such that each edge type appears
exactly twice (except $\frac{n}{2}$ in the even case), then the separating
path system produced by rotations of $P$ is in fact strongly separating. This
follows from an easy variant of the proof of Lemma 3.3. This would also give
an upper bound of $n$ for the strong problem. In fact, $P(12)$ and $P(15)$
above are both generators of strongly separating path systems.

######  Question 3.8.

For which values of $n\in\mathbb{N}$ do generator paths with two edges of each
type from $[\frac{n-1}{2}]$ exist?

It is also worth noting that the definition given in 3.2 is a little more
strict than needed for generating a separating path system. For $n$ odd, let
$P$ be a path in $K_{n}$ that contains $3$ edges of type $x$ such that
$P\setminus\\{e\\}$ (which is not necessarily a path) satisfies (GP1), (GP2),
and (GP3), where $e$ is one of the $x$-types in $P$. Then the rotations of $P$
give a separating path system for $K_{n}$ as long as $cd(e,e^{\prime})$ and
$cd(e,e^{\prime\prime})$ are not both equal to $\frac{n}{3}$, where
$e^{\prime}$ and $e^{\prime\prime}$ are the other $x$-type edges in $P$. There
is also an equivalent condition for even values of $n$, with more care taken
when $x=\frac{n}{2}$. Since the conditions for these paths are slightly more
relaxed they are possibly easier to find, but we do not make use of them in
this paper so we keep to the simpler definition here.

###  3.2 Main Construction

Since the conditions for a generator path are all based on edge types, any
path $P$ which is not a generator path fails the conditions for at least one
type. In other words, we can separate the edge types of $P$ into two
classifications, those that follow (GP1), (GP2), and (GP3), $F$, and those
that do not, $D$. Formally we have the following definition.

######  Definition 3.9.

A set of edges $A$ is an $F$-separator for $K_{n}$ if we can partition the
edge types of $K_{n}$ into sets $F$ and $D$ such that the following holds.

  1. 1.

$A$ contains at least one $y$-type edge for every $y\in F\cup D$.

  2. 2.

$A$ contains exactly two $x$-type edges for every $x\in F$.

  3. 3.

$A_{F}$ satisfies (GP3), where $A_{F}=\\{e\in A:\text{the edge type of
}e\text{ is in }F\\}$.

If $A$ is a path in $K_{n}$, we call it an $F$-separator path. Whenever we
have an $F$-separator we will use $D:=[\frac{n}{2}]\setminus F$ to mean the
other half of the partition.

Note that a generator path is an $F$-separator path, where
$F=[\frac{n-1}{2}]\setminus\\{x\\}$ with $x$ the edge type that appears
exactly once (of which there is at most one).

It is plain to see by the argument in the proof of Lemma 3.3, the family of
paths constructed by taking all the rotations of an $F$-separator path $P$
will separate all edges with type in $F$ from each other. This means if we can
find some $P$ which is an $F$-separator path for some large set $F$, then we
can find a family of $n$ paths that separates most of the edges in $K_{n}$. We
are then able to use a number of ‘fixing’ paths that will separate edges with
type in $D$. The family containing the two types of path gives a separating
path system of $K_{n}$.

Our aim for the rest of this section is as follows. We first define these
fixing paths, giving a separating path system based on any path (Theorem
3.11). We then construct an $F$-separator path $P$ with large $F$ (and hence
small $D$) to use as the base (Theorem 3.12). Our construction only works when
$n\equiv 3\mod 6$ or $n\equiv 5\mod 6$. The final step is to use the
construction of $P$ and the family based on it to give separating path systems
for other values of $n$ (Theorem 1.2).

Note that the rotation construction method naturally forces edges of the same
type to be separated from each other. Indeed, looking at the proof of Lemma
3.3 we see that for the case $x=y$ the only condition needed was that
$cd(e,e^{\prime})\neq\frac{n}{2}$. This is always the case when $n$ is odd
since $\frac{n}{2}$ is not an integer. So as long as there is no edge type
appearing more than twice in $P$, and $n$ is odd, we have that all edges of
the same type are separated from each other. In general, if $P$ contains
exactly $m$ edges of the same type $e_{1},\dotsc,e_{m}$, then they are
separated from each other by the rotations of $P$ unless
$cd(e_{i},e_{i+1})=\frac{n}{m}$ for all $i\in[m-1]$. We say that any $P$ with
such edges of type $x$ has equally spaced $x$-type edges. This leads us to
Theorem 3.11, but before we state this we need the following result.

######  Lemma 3.10.

For all $n$ and each edge type $x$ there exist two paths in $K_{n}$, $Q_{x}$
and $Q_{x}^{\prime}$, such that $Q_{x}\cup Q_{x}^{\prime}$ covers all $x$-type
edges in $K_{n}$ and all edges in $Q_{x}\cup Q_{x}^{\prime}$ have type from
$\\{1,x\\}$.

###### Proof.

Let $f$ be the highest common factor of $n$ and $x$, and let $a\in\mathbb{N}$
be such that $af=n$.

Consider the subgraph of $K_{n}$ containing only $x$-type edges, we have
exactly $f$ isomorphic cycles of length $a$. Let $C_{1},C_{2},\dotsc,C_{f}$ be
the cycles labelled so that a vertex $i$ will be contained in cycle $C_{i\mod
f}$. We now describe a path in $K_{n}$ using sections of each $C_{i}$ and some
linking $1$-type edges.

The path $Q_{x}$ starts at vertex $1$, and follows $C_{1}$ for $a-1$ edges,
before moving to $C_{2}$ with a $1$-type edge. It then follows $C_{2}$ for
$a-1$ edges. This continues until $a-1$ edges from each of the cycles
$C_{1},C_{2},\dotsc,C_{f}$ have been followed. Formally, set $v_{1}=1$ and
recursively define $v_{i}^{\prime}=v_{i}-x\mod n$ and
$v_{i+1}=v_{i}^{\prime}+1$ for $i\in[f]$. Note that for each $i\in[f]$ the
edge $(v_{i},v_{i}^{\prime})\in C_{i}$ and therefore has type $x$. Also note
that the edges $(v_{i}^{\prime},v_{i+1})$ are $1$-type edges for all
$i\in[f]$. We define the path $Q_{x}$ as follows,

$Q_{x}:=\left(\bigcup_{i=1}^{f}C_{i}\setminus\\{(v_{i},v_{i}^{\prime})\\}\right)\cup\left\\{(v_{i}^{\prime},v_{i+1}):i\in[f-1]\right\\}.$

Note this is indeed a path since the cycles $C_{1},C_{2},\dotsc,C_{f}$ are
pairwise vertex disjoint, and each edge $(v_{i}^{\prime},v_{i+1})$ links
$C_{i}$ to $C_{i+1}$.

Then we define $Q_{x}^{\prime}$ to be

$Q_{x}^{\prime}:=\\{(v_{i},v_{i}^{\prime}):i\in[f]\\}\cup\\{(v_{i}^{\prime},v_{i+1}):i\in[f-1]\\}.$

Thus all the $x$-type edges are covered in two paths using only $x$-type and
$1$-type edges. ∎

Now we can give our result.

######  Theorem 3.11.

Let $n\in\mathbb{N}$ be odd, and $P$ an $F$-separator path for $K_{n}$ with no
equally spaced $x$-type edges. Then $\mathcal{P}\cup\mathcal{D}$ is a
separating path system for $K_{n}$ where
$\mathcal{D}=\\{Q_{x},Q_{x}^{\prime}:x\in D\cup\\{1\\}\\}$ (with $Q_{x}$ and
$Q_{x}^{\prime}$ as in Lemma 3.10 and $D=[\frac{n}{2}]\setminus F$), and
$\mathcal{P}$ is the family of $n$ rotations of $P$. In particular
$f(K_{n})\leq n+2|D\cup\\{1\\}|$.

###### Proof.

Consider a pair of edges $e,e^{\prime}\in E(K_{n})$. Suppose first that $e$
and $e^{\prime}$ have the same type, $x$. Then $\mathcal{P}$ separates $e$ and
$e^{\prime}$. Indeed, if $e,e^{\prime}\in P_{i}$ (the rotation of $P$ by $i$
vertices clockwise), and $cd(e,e^{\prime})=d$ then one of
$P_{i+d},P_{i+2d},P_{i+3d},\dotsc$ contains $e$ but not $e^{\prime}$.
Otherwise we would have a collection of $\frac{n}{d}$ edges
$e_{1},\dotsc,e_{\frac{n}{d}}$ (which includes $e$ and $e^{\prime}$), all with
type $x$ and such that $cd(e_{i},e_{i+1})=d$. This cannot be, since we have no
equally spaced $x$-type edges in $P$.

Suppose instead that $e$ has type $x$ and $e^{\prime}$ has type $y$. If
$x,y\in F$ then $e$ and $e^{\prime}$ are separated by $\mathcal{P}$ since $P$
is an $F$-separator path. The paths $Q_{1},Q_{1}^{\prime}\in\mathcal{D}$
contain only $1$-type edges and together cover all $1$-types in $K_{n}$.
Therefore if $x=1$ then one of these two paths separates $e$ and $e^{\prime}$.
So assume $x,y\neq 1$, and that $x\notin F$. Then $Q_{x}$ and $Q_{x}^{\prime}$
contain only $x$-type and $1$-type edges and together cover all $x$-types in
$K_{n}$. One of these paths separates $e$ and $e^{\prime}$. ∎

To prove Theorem 1.2 it is left to find some path $P$ with small $D$ and no
equally spaced edges of the same type.

######  Theorem 3.12.

When $n\equiv 3\mod 6$ or $n\equiv 5\mod 6$, there is an $F$-separator path
$P$ for $K_{n}$, with no equally spaced $x$-type edges and with
$|D\cup\\{1\\}|\leq\frac{1}{32}(5n+16\log_{2}n+167)$. Where
$D=[\frac{n}{2}]\setminus F$.

The construction of this path is rather involved and makes up the bulk of the
argument, the proof can be found in Section 3.3. We first show how to use this
result to get separating path systems for all sufficiently large values of
$n$. The methods for extending paths that are used here are similar to those
used in the proof of Theorem 3.6.

######  Theorem 1.2.

For $n\geq 44$, there exists a separating path system for $K_{n}$ with size at
most

$\frac{21n+16\log_{2}n+232}{16}.$

###### Proof.

Case 1: $n$ is odd and $\frac{n-1}{2}$ is not a multiple of 3.
Let $P$ be the path from Theorem 3.12, and $D$ its associated set of badly
behaved edge types. Then by 3.11 there is a separating path system for $K_{n}$
with size at most

$n+2\cdot\frac{5n+16\log_{2}n+167}{32}.$

Case 2: $n-1$ is odd and $\frac{n-2}{2}$ is not a multiple of 3.
Consider the complete graph on $n-1$ vertices formed by removing vertex $v$
from $K_{n}$. Then $K_{n-1}$ fits the conditions for Case 1, let $P$ and $D$
be as in Case 1. Use 3.11 to give a separating path system for $K_{n-1}$ of
the form $\mathcal{P}\cup\mathcal{D}$, where $\mathcal{P}$ is the rotations of
$P$ and $\mathcal{D}=\\{Q_{x},Q_{x}^{\prime}:x\in D\cup\\{1\\}\\}$. Then
$|\mathcal{P}\cup\mathcal{D}|\leq n-1+2|D\cup\\{1\\}|$ where

$|D\cup\\{1\\}|\leq\frac{5(n-1)+16\log_{2}(n-1)+167}{32}.$

Let $P_{i}$ denote the rotation of $P$ by $i$ vertices clockwise on $K_{n-1}$,
and similarly $w_{i}$ for the vertex of $K_{n-1}$ which is $i$ clockwise
vertices on from $w$. Let $u$ be an endpoint of the path $P=P_{0}$. Then the
family $\mathcal{P^{\prime}}\cup\mathcal{D}$ is a separating path system for
$K_{n}$ where
$\mathcal{P^{\prime}}=\\{P_{i}\cup\\{(u_{i},v)\\}:i\in[0,n-2]\\}$.

Indeed, any pair of edges from $E(K_{n-1})$ are separated since they are
separated by $\mathcal{P}\cup\mathcal{D}$. So let $e=(w,v)$ for some $w\in
V(K_{n-1})$, and consider any edge $e^{\prime}\in E(K_{n-1})$. The edge $e$
only appears in one path from $\mathcal{P^{\prime}}\cup\mathcal{D}$, namely
the path $P_{i}\cup\\{(u_{i},v)\\}$ where $u_{i}=w$. Therefore if $e^{\prime}$
appears in any other path, then we are done. Clearly this is the case if
$e^{\prime}$ has type $x\in D$. Suppose that $e^{\prime}$ has type $x\in F$,
then by definition $P$ must have two $x$-type edges, therefore $e^{\prime}$
appears in two rotations of $P$.

Finally if $e^{\prime}$ is also an edge at $v$, then clearly it is not
contained in the path $P_{i}\cup\\{(u_{i},v)\\}$, and the two edges must be
separated.

Note that $|\mathcal{P^{\prime}}|=|\mathcal{P}|=n-1$, and
$|\mathcal{D}|=2|D\cup\\{1\\}|$.

Case 3: $n$ is odd and $\frac{n-1}{2}$ is a multiple of 3.
Consider the complete graph on $n-2$ vertices given by removing vertices $v$
and $v^{\prime}$ from $K_{n}$. Clearly $K_{n-2}$ satisfies the conditions for
Case 1, so let $\mathcal{P}\cup\mathcal{D}$ be the corresponding separating
path system for $K_{n-2}$ given by Theorem 3.11. We will take each path from
$\mathcal{P}$ and adapt it to a path on $K_{n}$, we will also add some edge
types to the set $D$ and create additional paths for our family this way.

Let $u$ be any endpoint of $P$. Select some edge $g\in P$ such that if $x_{g}$
is the edge type of $g$, then $P$ contains at least one other edge with type
$x_{g}$. Set $g=(p,q)$ for $p,q\in V(K_{n-2})$, and let $g_{i}=(p_{i},q_{i})$
be the rotation of $g$ in $K_{n-2}$ by $i$ vertices. We fix the new paths
$P^{\prime}_{i}=(P_{i}\setminus\\{g_{i}\\})\cup\\{(p_{i},v),(v,q_{i}),(u_{i},v^{\prime})\\}$,
and let $\mathcal{P^{\prime}}=\\{P^{\prime}_{i}:i\in[0,n-3]\\}$.

If there are edges $h,h^{\prime}\in P$ with the same edge type $x_{h}\in F$,
such that $cd(h,h^{\prime})=x_{g}$ on $K_{n-2}$, then define
$D^{\prime}=D\cup\\{x_{g},x_{h}\\}$. Note that there can be at most one such
pair since $x_{h}\in F$. Otherwise define $D^{\prime}=D\cup\\{x_{g}\\}$. Let
$\mathcal{D^{\prime}}=\\{Q_{x},Q_{x}^{\prime}:x\in D^{\prime}\cup\\{1\\}\\}$
be the family of fixing paths on each type in $D^{\prime}$ (such paths
described in 3.10). Then $\mathcal{P^{\prime}}\cup\mathcal{D^{\prime}}$ is a
separating path system for $K_{n}$.

Let $e,e^{\prime}$ be any two edges in $K_{n}$. If $e,e^{\prime}\in
E(K_{n-2})\setminus\\{g_{i}:i\in[n-2]\\}$ then the edges are separated by
$\mathcal{P}\cup\mathcal{D}$ and hence by
$\mathcal{P^{\prime}}\cup\mathcal{D^{\prime}}$. Suppose $e^{\prime}=g_{i}$ for
some $i\in[n-2]$, and let $x_{e}$ be the edge type of $e$. Since $x_{g}\in
D^{\prime}$ we have that the path
$Q\in\\{Q_{x_{g}},Q_{x_{g}}^{\prime}\\}\subseteq\mathcal{D^{\prime}}$ contains
the edge $g_{i}$. The path $Q$ separates $g_{i}$ from $e$ unless $x_{e}=x_{g}$
or $x_{e}=1$. If $x_{e}=1$ then one of
$Q_{1},Q_{1}^{\prime}\in\mathcal{D^{\prime}}$ separates the pair. If
$x_{e}=x_{g}$ then, since there is still an $x_{g}$-type edge in $P^{\prime}$
and there are no equally spaced edge types, $\mathcal{P^{\prime}}$ separates
the pair.

Suppose then that $e=(v,w)$ for some $w\in V(K_{n-2})$, and $e^{\prime}\in
E(K_{n-2})$, then the edges are separated if $e^{\prime}$ is in some
$\mathcal{D^{\prime}}$ path, otherwise there is some other edge in $P_{i}$
with the same type as $e^{\prime}$. The distance between these edges cannot be
the same as the distance between the two edges at $v$ since $x_{h}\in
D^{\prime}$, therefore the edges must be separated by the rotations (as in
3.3). If $e=(v,w)$ and $e^{\prime}=(v,w^{\prime})$, then let $i$ be such that
$w_{i}=w^{\prime}$. We have that if $e,e^{\prime}\in P^{\prime}_{j}$ then
$e^{\prime}\in P_{j+i}$, the only other edge at $v$ in $P_{j+i}$ is
$(v,w^{\prime}_{i})$. Therefore the edges are separated. Finally, if
$e=(v^{\prime},w)$ then note that it is the unique edge a path in
$\mathcal{P^{\prime}}$, since every other edge type either appears twice in
$P^{\prime}$ or in $D^{\prime}$, there are no other unique edges. Therefore
the edges are separated.

Note that $|\mathcal{P^{\prime}}|=|\mathcal{P}|=n-2$, and
$|\mathcal{D^{\prime}}|=2|D^{\prime}\cup\\{1\\}|=2(|D\cup\\{1\\}|+2)$.

Case 4: $n-1$ is odd and $\frac{n-2}{2}$ is a multiple of 3.
This case is very similar to Case 3. We consider the family
$\mathcal{P}\cup\mathcal{D}$ from 3.11 on the $K_{n-3}$ obtained by removing
the vertices $v,v^{\prime}$ and $\bar{v}$ from $K_{n}$. Then we adapt the
paths $P$ and add to the set $D$ to obtain a new family.

Let $u$ be any endpoint of $P$, and let
$g=(p,q),g^{\prime}=(p^{\prime},q^{\prime})\in P$ be edges with type $x_{g}$
and $x_{g}^{\prime}$ respectively such that $x_{g}\neq x_{g}^{\prime}$ and
$P\setminus\\{g,g^{\prime}\\}$ still contains an edge of type $x_{g}$ and and
edge of type $x_{g}^{\prime}$. Set the new paths to be
$P^{\prime}_{i}=(P_{i}\setminus\\{g_{i},g_{i}^{\prime}\\})\cup\\{(p_{i},v),(v,q_{i}),(p^{\prime}_{i},v^{\prime}),(v^{\prime},q^{\prime}_{i}),(w,\bar{v})\\}$
and $\mathcal{P^{\prime}}=\\{P^{\prime}_{i}:i\in[0,n-4]\\}$.

If there are edges $h,h^{\prime}\in P$ both with edge type $x_{h}\in F$ such
that the clockwise distance between them on $K_{n-3}$ is equal to $x_{g}$,
then set $D^{\prime}=D\cup\\{x_{g},x_{g}^{\prime},x_{h}\\}$. If there is also
a pair of edges with type $x_{h}^{\prime}\in F$ with clockwise distance equal
to $x_{g}^{\prime}$ then set
$D^{\prime}=D\cup\\{x_{g},x_{g}^{\prime},x_{h},x_{h}^{\prime}\\}$. Note that
there can be at most one of each since $x_{h},x_{h}^{\prime}\in F$. Otherwise,
set $D^{\prime}=D\cup\\{x_{g},x_{g}^{\prime}\\}$. Then by the same reasoning
as for Case 3, the family $\mathcal{P^{\prime}}\cup\mathcal{D^{\prime}}$ is a
separating path system for $K_{n}$.

Note that $|\mathcal{P^{\prime}}|=|\mathcal{P}|=n-3$, and
$|\mathcal{D^{\prime}}|=2|D^{\prime}\cup\\{1\\}|=2(|D\cup\\{1\\}|+4)$. ∎

###  3.3 Proof of Theorem 3.12

The aim now is to construct an $F$-separator path with many edge types in $F$.
We will start by defining three sets of edges ($M_{0}$, $R$, and $B$) which
together form a linear forest. This linear forest will almost follow (GP1),
(GP2), and (GP3). We will then add certain joining edges to connect our forest
into a single path. The types associated to the special edges in the linear
forest will end up in $F$ and the types associated to the joining edges will
end up in $D$.

Step 1: Defining the linear forest

Let $n\in\mathbb{N}$ be such that $n\equiv 3\mod 6$ or $n\equiv 5\mod 6$. For
the remainder of this section we label the vertices of $K_{n}$ slightly
differently for ease of notation. First label any vertex $0$, from here label
vertices clockwise following the order
$1,2,\dotsc,\frac{n-1}{2},-\frac{n-1}{2},-(\frac{n-1}{2}-1),\dotsc,-2,-1$. Now
we define three sets of edges from $K_{n}$ which we will combine to make an
approximation of a generator path.

First we define a set containing one edge of each type,

$M_{0}=\left\\{(-i,i):i\in\left[\frac{n-1}{2}\right]\right\\}.$

Note that $M_{0}$ is a maximal matching in $K_{n}$ and that the vertex $0$ is
the only vertex which is not an endpoint of an edge in $M_{0}$. We also use
$M_{k}$ to denote the rotation of $M_{0}$ in which vertex $k$ has no incident
edges.

Next we define an edge set containing only the largest edge types. Let
$R=R_{1}\cup R_{2}$ where

$R_{1}=\left\\{\left(1,-\frac{n-3}{2}\right),\left(-1,-\frac{n-1}{2}\right)\right\\},$

and

$R_{2}=\left\\{\left(-3-2k,\frac{n-1}{2}-k\right):0\leq k\leq r-1\right\\},$

where $r=\frac{n-7}{4}$ for when $\frac{n-1}{2}$ is odd, and $r=\frac{n-9}{4}$
otherwise.

Note that $R_{1}$ consists of a $\frac{n-1}{2}$-type edge and a
$\frac{n-3}{2}$-type edge. Further, note that $(-3,\frac{n-1}{2})$ has type
$\frac{n-5}{2}$, and that if an edge $(-3-2k,\frac{n-1}{2}-k)$ is $x$-type,
then $(-3-2(k+1),\frac{n-1}{2}-(k+1))$ is an $(x-1)$-type edge. Thus, $R$
contains the largest $r+2$ edge types.

Define $r(i)=\frac{n+2+i}{2}$ for every $i=-3-2k$ where $0\leq k\leq r-1$, and
$r(i)=-\frac{n-2-i}{2}$ for $i=-1,1$. Then we can write each edge in $R$ as
$(i,r(i))$. Similarly let $r^{-1}(i)=2i-n-2$ for $i=\frac{n-1}{2}-k$ where
$0\leq k\leq r-1$, and $r^{-1}(i)=2i+n-2$ for
$i=-\frac{n-3}{2},-\frac{n-1}{2}$. Then we can also write $R$ edges in the
form $(r^{-1}(i),i)$.

The contents of the final edge set depend on the edges in $R$ as well as the
properties of $\frac{n-1}{2}$. We define this set so that it continues with
the large edge types roughly where $R$ left off, containing approximately
types $\frac{n}{4}$ down to $\frac{n}{8}$. Choose $i_{b}$ even and as large as
possible such that $(-i_{b},i_{b}+3)$ is an edge with odd type at most
$\frac{n-1}{4}$. Set $b=(-i_{b},i_{b}+3)$ and denote $x_{b}=2i_{b}+3$ as the
edge type of $b$. Note that $b\in M_{-\frac{n-3}{2}}$ and

$x_{b}\in\left\\{\left\lfloor\frac{n-1}{4}\right\rfloor,\left\lfloor\frac{n-1}{4}\right\rfloor-1,\left\lfloor\frac{n-1}{4}\right\rfloor-2,\left\lfloor\frac{n-1}{4}\right\rfloor-3\right\\}.$

Then we can define the final edge set as

$B=\left\\{\left(-\frac{x_{b}-3}{2}+2k,\frac{x_{b}+3}{2}+k\right):0\leq k\leq
t-1\right\\},$

where $t=\frac{x_{b}+1}{2}$.

Let $b(i)=\frac{3x_{b}+3+2i}{4}$ for each $i=-\frac{x_{b}-3}{2}+2k$ where
$0\leq k\leq t-1$. Also, let $b^{-1}(i)=-\frac{3x_{b}+3-4i}{2}$ for every
$i=\frac{x_{b}+3}{2}+k$ where $0\leq k\leq t-1$. Then we can write $B$ edges
in the form $(i,b(i))$ and $(b^{-1}(i),i)$.

See Figure 2 for an example of the edge sets $M_{0}$, $R$, and $B$.

Let $L=M_{0}\cup R\cup B$ denote this collection of edges. Our task now is to
extend $L$ to a path. In order to do this we must have that $L$ is acyclic,
and that the maximum degree of any vertex is $2$.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$-1$$-2$$-3$$-4$$-5$$-6$$-7$$-8$$-9$$-10$$-11$$-12$$-13$$-14$$-15$$-16$$-17$$R$$B$
Figure 2: The linear forest $L$ for $n=35$

######  Claim 3.13.

$L$ is a linear forest.

###### Proof.

First we consider the degree condition. Observe that $M_{0}$ is a maximal
matching and therefore no $M_{0}$ edges share vertices. It is clear from the
constructions of $R$ that no two $R$ edges share a vertex, similarly no two
$B$ edges share a vertex. This means all edges of high degree must be an
endpoint of an edge in each of $M_{0},R$, and $B$. As usual we write
$[a,b]=\\{c\in\mathbb{N}:a\leq c\leq b\\}$ where $a$ and $b$ are non-negative
integers with $a\leq b$. We also write $[-a,b]=\\{c\in\mathbb{Z}:-a\leq c\leq
b\\}$ where $a$ and $b$ are non-negative integers, and
$[-a,-b]=\\{c\in\mathbb{Z}:-a\leq c\leq-b\\}$ where $a$ and $b$ are non-
negative integers and $a\geq b$.

Let $I_{1}=[-2,1]=\\{-2,-1,0,1\\}$ and $I_{2}=[-\frac{n-5}{2},-3]$, then each
$R$ edge has one vertex in the set $I=I_{1}\cup I_{2}$, moreover this vertex
is odd. Let $I_{1}^{\prime}=[-\frac{n-1}{2},-\frac{n-3}{2}]$ and
$I_{2}^{\prime}=[\frac{n+9}{4},\frac{n-1}{2}]$, then each $R$ edge has one
vertex in the set $I^{\prime}=I_{1}^{\prime}\cup I_{2}^{\prime}$. Similarly,
let $J=[-\frac{x_{b}-3}{2},\frac{x_{b}+1}{2}]$ and
$J^{\prime}=[\frac{x_{b}+3}{2},x_{b}+1]$, each $B$ edge has exactly one vertex
in $J$, which is even, and one vertex in $J^{\prime}$.

Using the fact that all $R$ endpoints in $I$ are odd and every $B$ endpoint in
$J$ is even together with the fact that $I\cap J^{\prime}=\emptyset$, we have
that no vertex in $I$ is the endpoint of both a $B$ and an $R$ edge. Then the
only candidates for a vertex of high degree must be found in $I^{\prime}$.
Note first that $I_{1}^{\prime}\cap(J\cup J^{\prime})=\emptyset$, so any high
degree vertex must come from $I^{\prime}_{2}$. The largest vertex which is
also an endpoint in $B$ is $x_{b}+1$. Recall that $x_{b}\leq\frac{n-1}{4}$,
therefore $x_{b}+1\leq\frac{n+3}{4}<\frac{n-1}{2}-k$ for all $0\leq k\leq
r-1$. Therefore there are no vertices of degree greater than $2$ in $L$.

It is left to show that $L$ is acyclic. Suppose for a contradiction that $C$
is a cycle in $M_{0}\cup R$, clearly $C$ must alternate between $M_{0}$ edges
and $R$ edges. Let $e=(-i,i)$ be the edge in $C\cap M_{0}$ such that
$i\in[\frac{n-1}{2}]$ is maximal. Let $r^{+},r^{-}\in C\cap R$ be edges with
an endpoint at $i$ and $-i$ respectively. Observe that if $i=\frac{n-1}{2}$
then $r^{+}=(-3,\frac{n-1}{2})\in R_{2}$ and so $(-3,3)\in C$. Since $3\notin
I\cup I^{\prime}$ there is only one edge in $M_{0}\cup R$ at $3$, meaning $C$
cannot be a cycle. Further note that the edge $(-\frac{n-3}{2},\frac{n-3}{2})$
is in the same path as $(-\frac{n-1}{2},\frac{n-1}{2})$ by edges in $R_{1}$,
therefore $i<\frac{n-3}{2}$. This means that $r^{+},r^{-}\in R_{2}$, so let
$r^{+}=(r^{-1}(i),i)$ and $r^{-}=(-i,r(-i))$. Suppose that
$|r^{-1}(i)|<r(-i)$, then after $r^{+}$ the cycle $C$ must follow an $M_{0}$
edge to $\ell=|r^{-1}(i)|$ where there must be another $R$ edge
$(r^{-1}(\ell),\ell)$ for $C$ to continue. Since $\ell<r(-i)$, the
construction of $R_{2}$ means we have $r^{-1}(\ell)<-i$. Since all $R$
vertices in $I_{2}$ are negative this means $|r^{-1}(\ell)|>i$. The next edge
in $C$ after $(r^{-1}(\ell),\ell)$ must be in $M_{0}$, so we have that
$(r^{-1}(\ell),|r^{-1}(\ell)|)\in C$ where $|r^{-1}(\ell)|>i$ contradicting
the maximality of $i$. The case where $|r^{-1}(i)|>r(-i)$ is analogous.

So every cycle must contain a $B$ edge. Again, for a contradiction, let $C$ be
a cycle in $L$, then $C$ must alternate between $M_{0}$ edges and $R\cup B$
edges. Let $(i,b(i))\in B\cap C$ and note that by definition of $B$ we have
$|i|<b(i)$. The edge $(-b(i),b(i))$ must appear in $C$. Since $b(i)\in
J^{\prime}$ we have that $-b(i)\notin J\cup J^{\prime}$, this means there is
no $B$ edge at $-b(i)$. So there must be an $R$ edge at $-b(i)$ to continue
the cycle, in particular we must have $-b(i)\in I$. In order to have $C$ be a
cycle, we must be able to continue in this direction along $C$ and end up back
at the vertex $i$.

Let $\ell=r(-b(i))$, then the edge $(-b(i),\ell)$ must be in $C$. Note that
$\ell\in I^{\prime}$ and therefore $\ell>|i|$ since $i\in J$. $C$ must
continue after $(-b(i),\ell)\in R$ with the edge $(-\ell,\ell)\in M_{0}$.
Since $-\ell\neq i$ we have not connected $C$. The next edge must be from
$R\cup B$, and since $\ell\notin J\cup J^{\prime}$ this must be another $R$
edge. In particular $(-\ell,r(-\ell))$. Note that as $r(-\ell)\in I^{\prime}$
we must have that $r(-\ell)>|i|$. Again, the next edge in $C$ must be
$(-r(-\ell),r(-\ell))\in M_{0}$. Since $r(-\ell)>|i|$ we have $-r(-\ell)\neq
i$ and we have not completed $C$.

We can continue with this same argument, but at each stage we go through a
vertex in $I^{\prime}$ then to a vertex in $-I^{\prime}$ via $M_{0}$, then
back to $I^{\prime}$ with an $R$ edge. This means we can never get back to the
vertex $i$ since $|i|$ is smaller than all vertices in $I^{\prime}$. ∎

######  Claim 3.14.

$L$ satisfies (GP1) and (GP3). Moreover, the sub-forest of $L$ which contains
all edges of type matching those in $R\cup B$ satisfies (GP2).

###### Proof.

For (GP1), note that $n$ is odd and $M_{0}$ contains exactly one edge of every
type. Clearly then, $L$ contains at least one edge of each type.

Recall that each edge in $R$ has a different type from
$[\lceil\frac{n-1}{4}\rceil,\frac{n-1}{2}]$, and that each $B$ edge has a
different type from $[\frac{x_{b}+3}{2},x_{b}]$ where
$x_{b}\leq\lfloor\frac{n-1}{4}\rfloor$. This means that there is no edge type
that appears more than twice in $L$. Moreover, for any edges $e,e^{\prime}\in
L$ that have the same type, we have $e\in M_{0}$ and $e^{\prime}\in R\cup B$.
This means the restriction of $L$ to edges with type found in $R\cup B$
contains exactly two edges of each type, hence satisfies (GP2).

Since $M_{0}$ contains exactly one of each edge type, the family of rotations
of $M_{0}$ must cover the edges of $K_{n}$. In other words, any edge in $R\cup
B$ is found in $M_{i}$ for some $i\in[-\frac{n-1}{2},\frac{n-1}{2}]$. Let
$e\in M_{0}$ and $e^{\prime}\in R\cup B$ both be $x$-type edges. Then
$e^{\prime}\in M_{i}$ for some $i$, and since $M_{i}$ is a rotation of $M_{0}$
by $|i|$ we must have that $cd(e,e^{\prime})=|i|$. This means that (GP3) is
equivalent to the conditions

$M_{0}\cap(R\cup B)=\emptyset\qquad\text{and}\qquad|(M_{i}\cup
M_{-i})\cap(L)|\leq 1$

for every $i\in[\frac{n-1}{2}]$.

We associate to the edges of $K_{n}$ a number from $[0,\frac{n-1}{2}]$ called
the crossing number. Each $M_{i}$ (except $M_{0}$) contains a single edge
$e_{i}$ at the vertex $0$, define the crossing number of all edges in $M_{i}$
to be the type of the edge $e_{i}$. We define the crossing number of edges in
$M_{0}$ to be $0$. Note that by this definition the crossing number of edges
in $M_{i}$ is the same as the crossing number of $M_{-i}$ edges, we also have
that any pair $M_{i},M_{j}$ with $|i|\neq|j|$ contain edges with different
crossing numbers. Therefore, to show the conditions above hold, it is
sufficient to show that no two edges from $R\cup B$ have the same crossing
number, and that no edge in $R\cup B$ has crossing number $0$.

Consider the edge $e=(1,-\frac{n-3}{2})\in R_{1}$, let $M_{\ell}$ be the
matching containing $e$. Then $M_{\ell}$ must also contain the edge
$(0,-\frac{n-5}{2})$ and hence $e$ has crossing number $\frac{n-5}{2}$.
Similarly we see that $(-1,-\frac{n-1}{2})$ has crossing number
$\frac{n-1}{2}$. Now, for edges in $R_{2}$ we first note that
$(-3,\frac{n-1}{2})$ has crossing number $m=\frac{n-7}{2}$. Then observe that
$(-3-2,\frac{n-1}{2}-1)$ has crossing number $m-3$, and similarly
$(-3-2k,\frac{n-1}{2}-k)$ has crossing number $|m-3k|$. Note that
$|m-3k|\neq|m-3k^{\prime}|$ for any $k\neq k^{\prime}$, so no edges in $R_{2}$
have the same crossing number. Further note that $m$ is not a multiple of $3$
since $\frac{n-1}{2}$ is not a multiple of $3$, this means no $R_{2}$ edge has
crossing number $0$.

Since $r\leq\frac{n-7}{4}$ we have that $|m-3k|<\frac{n-5}{2}$ for all $0\leq
k\leq r-1$, meaning that there are no edges in $R_{2}$ with the same crossing
number as an edge in $R_{1}$. In particular this means that no two edges in
$R$ have the same crossing number, and no edge in $R$ has a crossing number
which is $0$ or a multiple of $3$.

We now consider edges in $B$. Recall that the edge
$b=(-\frac{x_{b}-3}{2},\frac{x_{b}+3}{2})\in M_{-\frac{n-3}{2}}$ and therefore
has crossing number $3$. Note also that
$(-\frac{x_{b}-3}{2}+2,\frac{x_{b}+3}{2}+1)$ has crossing number $6$ and in
general the edge $(-\frac{x_{b}-3}{2}+2k,\frac{x_{b}+3}{2}+k)$ has crossing
number $3(k+1)$ for $0\leq k\leq t-1$. Recall also that $t\leq\frac{n+3}{8}$,
therefore $3(k+1)\leq\frac{n-1}{2}$ for all $n\geq 13$. In particular we have
that no edges in $B$ have crossing number $0$, and clearly no two edges from
$B$ have the same crossing number. We saw earlier that no edges in $R$ have a
crossing number which is a multiple of $3$, since edges in $B$ only have
crossing numbers which are multiples of $3$ we see that there are no two edges
in $R\cup B$ with the same crossing number. ∎

The above tells us that the only edge types that fail the conditions of
Definition 3.2 are those that appear only once (and hence fail (GP2)). These
are exactly the types that do not appear in $R\cup B$. In other words, let

$F_{L}=\\{x:\text{there is an }e\in R\cup B\text{ with edge type }x\\}$

be the set of edge types from edges in $R\cup B$, then $L$ is an
$F_{L}$-separator. Note that $F_{L}$ is close to the set
$[\frac{n}{8},\frac{n-1}{2}]$, possibly with a small number of elements
missing.

We now must connect our $L$ into a single path without using too many edges
with type in $F_{L}$.

Step 2: Finding connecting edges to join the linear forest into a path

We can do this by adding edges between endpoints of paths in $L$, but it is in
our interests to keep these joining edges as short as possible to avoid using
edges from $F_{L}$. In this step we will find a set of edges $C$ such that
$L\cup C$ is a path and where the edge types in $C$ do not overlap too much
with those in $F_{L}$. To do this, we need to know where the endpoints of
paths in $L$ appear, and a little more about the behaviour of each path in
$L$. We partition the non-zero vertices of $K_{n}$ into sets depending on
their label. First set $T^{+}=[x_{b}+1]$ , $M^{+}=[x_{b}+2,\frac{n-1}{2}-r]$
and $U^{+}=[\frac{n-1}{2}-r+1,\frac{n-1}{2}]$, then $T^{-},M^{-}$ and $U^{-}$
contain the respective negative vertices (see Figure 3).

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$-1$$-2$$-3$$-4$$-5$$-6$$-7$$-8$$-9$$-10$$-11$$-12$$-13$$-14$$-15$$-16$$-17$$T^{-}$$T^{+}$$M^{-}$$M^{+}$$U^{-}$$U^{+}$
Figure 3: The segments of $L$ for $n=35$

First consider vertices in $U^{+}$, note that each vertex in $U^{+}$ is an
$I^{\prime}$ vertex of an $R_{2}$ edge. Since these vertices also all have an
incident $M_{0}$ edge we conclude that there are no endpoints in $U^{+}$.

Next $M^{+}$, since all vertices in $M^{+}$ are larger than $x_{b}+1$ and
smaller than $\frac{n-1}{2}-r+1$ there can be no incident $B$ or $R$ edges
here. Hence every vertex in $M^{+}$ is an endpoint of a path in $L$. Note that
$|M^{+}|=\frac{n-1}{2}-r-x_{b}-1$, then due to the values of $x_{b}$ and $r$,
we must have that $1\leq|M^{+}|\leq 4$.

For $T^{+}$ note that every vertex in $J^{\prime}\subseteq T^{+}$ is an
endpoint of a $B$ edge, therefore the only vertices in $T^{+}$ with degree $1$
must be in $[\frac{x_{b}+1}{2}]$. In particular, by the construction of $B$,
these endpoints must all be odd vertices since $-\frac{x_{b}-3}{2}+2k\in J$ is
even for $0\leq k\leq t-1$. Further note that there is an $R_{1}$ edge at
vertex $1$, but this is the only $R$ edge with an endpoint in $T^{+}$.
Together this means all odd vertices in $[3,\frac{x_{b}-1}{2}]$ are endpoints
in $L$, this is $\frac{x_{b}-3}{4}$ vertices since
$(i_{b}+3)-1=\frac{x_{b}+1}{2}$ is even.

For the negative side, we know that all odd vertices have an incident $R$
edge, so the only endpoints on this side must be even. For $U^{-}$ note that
$-\frac{n-3}{2}$ and $-\frac{n-1}{2}$ are both vertices with edges from
$R_{1}$, so the endpoints in $U^{-}$ are all even vertices in
$[-\frac{n-5}{2},-\frac{n-1}{2}+r-1]$. For $M^{-}$ this means that all even
vertices are endpoints. In particular each endpoint is from a path consisting
of one edge and terminating in $M^{+}$, there are
$\lfloor\frac{|M^{+}|}{2}\rfloor$ such vertices (this is at most $2$). Finally
for $T^{-}$ we have that even vertices in $J$ are endpoints of $B$ edges,
therefore the only vertices with degree $1$ are in
$[-x_{b}-1,-\frac{x_{b}-3}{2}-2]$. This is $\frac{x_{b}+5}{4}$ vertices.

This information is summarised in the table below.

Set | Range in which endpoints lie | Endpoint type | Number of endpoints
---|---|---|---
$\\{0\\}$ | - | all | $1$
$U^{+}$ | - | none | $0$
$M^{+}$ | $[x_{b}+2,\frac{n-1}{2}-r]$ | all |  $1$ to $4$
$T^{+}$ | $[3,\frac{x_{b}-1}{2}]$ | odd | $\frac{x_{b}-3}{4}$
$U^{-}$ | $[-\frac{n-5}{2},-\frac{n-1}{2}+r-1]$ | even |  $\lceil\frac{n-17}{8}\rceil$ to $\lfloor\frac{n-15}{8}\rfloor$
$M^{-}$ | $[-\frac{n-1}{2}-r,-x_{b}-3]$ | even |  $0$ to $2$
$T^{-}$ | $[-x_{b}-1,-\frac{x_{b}-3}{2}-2]$ | even | $\frac{x_{b}+5}{4}$
Table 1: Endpoints in each segment of $L$

In total we have $\frac{n-2x_{b}+1}{2}$ vertices in $L$ with degree $1$ when
$\frac{n-1}{2}$ is even, and $\frac{n-2x_{b}-1}{2}$ otherwise. This means $L$
consists of

$\frac{n-2x_{b}+(-1)^{\frac{n-1}{2}}}{4}$

paths. We now look at the behaviour of each path.

######  Claim 3.15.

Any path in $L$ with an endpoint in $T^{-}$ must have its other endpoint in
$T^{-}\cup\\{0\\}$.

###### Proof.

Recall that all endpoints in $T^{-}$ are in the set
$[-x_{b}-1,-\frac{x_{b}-3}{2}-2]$, and that only even vertices are endpoints.
Set $a_{1}=-x_{b}-1$ and $a_{2}=-\frac{x_{b}-3}{2}-2$, so our interval of
endpoints can be written as $[a_{1},a_{2}]$. We will work in stages, checking
the largest endpoint in our interval at each step. We will show that the path
from this largest vertex terminates at the smallest endpoint in our interval
(or at $0$). We then remove these endpoints from our interval and start again,
checking the largest endpoint, continuing until we have found the all the
paths with endpoints in $T^{-}$. We will start with step $0$.

Step $0$, our interval is $[a_{1},a_{2}]$ and we check the path at the largest
vertex, $a_{2}=-\frac{x_{b}-3}{2}-2$. We know there is an $M_{0}$ edge at
$a_{2}$, so our path must go through the vertex
$-a_{2}=\frac{x_{b}-3}{2}+2=-\frac{x_{b}-3}{2}+2(t-1)$. From the construction
of $B$, we see that there is a $B$ edge at this vertex which our path must
follow next. This takes the path to the vertex $b(-a_{2})=x_{b}+1$, where we
must again follow an $M_{0}$ edge to $-(x_{b}+1)=a_{1}$. We know that $a_{1}$
is even and is the smallest vertex in our interval $[a_{1},a_{2}]$, so the
path terminates here.

Every remaining endpoint is an even vertex in
$[-x_{b}+1,-\frac{x_{b}-3}{2}-4]$. Indeed, our original interval was
$[-x_{b}-1,-\frac{x_{b}-3}{2}-2]$ and we found $-(x_{b}+1)$ and
$-\frac{x_{b}+1}{2}$ to be endpoints of the first path. Since $-(x_{b}+1)+1$
and $-\frac{x_{b}+1}{2}-1$ are odd, they cannot be endpoints of a path in $L$.
Hence our new interval is $[a_{1}+2,a_{2}-2]$. This completes step $0$.

Step $k$, our interval is $[a_{1}+2k,a_{2}-2k]$, note that
$k\leq\frac{x_{b}+1}{8}$. We check the largest vertex in our interval,
$-v=a_{2}-2k$. We know $-v$ has an edge to $v$ via $M_{0}$, and since
$v>\frac{x_{b}+3}{2}$ we have that $v\in J^{\prime}$ has an incident $B$ edge.
In particular this $B$ edge is
$(-\frac{x_{b}-3}{2}+2(2k-1),\frac{x_{b}+3}{2}+2k-1)$ where
$v=\frac{x_{b}+3}{2}+2k-1$.

We know that $b^{-1}(v)$ is even, if $b^{-1}(v)=0$ then the path must end here
since there is only one edge at vertex $0$. Also note that when $b^{-1}(v)=0$
we have $k=\frac{x_{b}+1}{8}$ and hence our interval consists of a single
vertex, therefore we must be on the final step. Assume then that
$b^{-1}(v)\neq 0$. In this case we have that $b^{-1}(v)<0$ since we are
assuming $k<\frac{x_{b}+1}{8}$.

From $b^{-1}(v)$ we move along the path to $|b^{-1}(v)|$, since this is an
even vertex and as $|b^{-1}(v)|<|-\frac{x_{b}-3}{2}|$, there must be another
$B$ edge here. Since $b^{-1}(v)$ is even, there are exactly $|b^{-1}(v)|-1$
even vertices between $b^{-1}(v)$ to $|b^{-1}(v)|$ (not inclusive). This means
there are $|b^{-1}(v)|-1$ $B$ edges between those at $b^{-1}(v)$ and
$|b^{-1}(v)|$. In other words, the $B$ edge at $|b^{-1}(v)|$ must be
$(-\frac{x_{b}-3}{2}+2(\ell-1),\frac{x_{b}+3}{2}+\ell-1)$ where
$\frac{x_{b}+3}{2}+\ell-1=v+|b^{-1}(v)|$. Now, recall that
$|b^{-1}(v)|=\frac{x_{b}-3}{2}-2(2k-1)$, and that $v=\frac{x_{b}-3}{2}+2+2k$.
Using these we get $\frac{x_{b}+3}{2}+\ell-1=x_{b}+1-2k$. We then follow the
$M_{0}$ edge at $x_{b}+1-2k$ to get to $-(x_{b}+1-2k)=a_{1}+2k$.

Clearly then $a_{1}+2k$ is even and inside the interval $[a_{1}+2k,a_{2}-2k]$.
So it must be an endpoint in $L$, and therefore our path ends in $T^{-}$ as
claimed. We remove vertices from our interval to give the new interval of
$[a_{1}+2k+2,a_{2}-2k-2]$.

We can repeat the above process until we have seen that all paths with
endpoints in $T^{-}$ have their other endpoint at $0$ or in $T^{-}$. ∎

Note that due to the structure shown in the above, it is easy to join these
paths into a single path using short edges.

######  Claim 3.16.

We can use only $2$-type edges to connect the paths with endpoints in $T^{-}$
into a single path.

###### Proof.

Use the connecting edges

$C_{B}=\Bigg{\\{}\left(-\frac{x_{b}-3}{2}-2,-\frac{x_{b}-3}{2}-4\right),(-x_{b}+1,-x_{b}+3),\dotsc,\\\
\left(-\frac{x_{b}-3}{2}-2-4k,-\frac{x_{b}-3}{2}-4-4k\right),(-x_{b}-1+2+4k,-x_{b}-1+4+4k),\dotsc\Bigg{\\}}.$

Note that this connected path has one end vertex at $(-x_{b}-1)$, which is the
vertex with the smallest label in $T^{-}$, and the other end is either $0$ or
the vertex $-\frac{3x_{b}+7}{4}\in T^{-}$. ∎

By doing this, we have replaced $\lceil\frac{x_{b}+5}{8}\rceil$ paths with a
single path.

Now we consider vertices in $T^{+}$. Firstly, for $n\geq 44$ we have that
vertices $3$ and $5$ are endpoints of the same path, this path uses the all
$R_{1}$ edges along with the first two edges of $R_{2}$. When $n<44$ there is
a $B$ edge at vertex $5$ meaning it cannot be an endpoint. This leaves us to
check odd vertices in $[7,\frac{x_{b}-1}{2}]$.

######  Claim 3.17.

Every odd vertex in $[7,\frac{x_{b}-1}{2}]$ is the beginning of a path in $L$
that terminates in $U^{-}$.

###### Proof.

Every vertex $v\in[7,\frac{x_{b}-1}{2}]$ has an incident $M_{0}$ edge to
$-v\in T^{-}$, since $v$ is odd $-v$ has an incident $R_{2}$ edge. By the
definition of the $R_{2}$ edges and of $U^{+}$, this edge must be $(-v,r(-v))$
where $r(-v)\in U^{+}$. Again from $r(-v)$ the path must follow the $M_{0}$
edge to $-r(-v)\in U^{-}$. Now we have two cases, either $r(-v)$ is even and
hence there is no $R$ edge at $-r(-v)$ (also clearly no $B$ in $U^{-}$), or
$r(-v)$ is odd and there is another $R$ edge that leads to a vertex in
$U^{+}$.

For the case where $r(-v)$ is even, since there are no other edges at $-r(-v)$
the path must terminate here. This follows the claim as $-r(-v)\in U^{-}$. So
we assume $r(-v)$ is odd and that $(\ell,r(\ell))$ is the $R$ edge with
$-r(-v)=\ell$. By definition of $U^{+}$ we have that $r(\ell)\in U^{+}$, so
the path must continue via $M_{0}$ to $-r(\ell)\in U^{-}$. Once again, if
$r(\ell)$ is even the path terminates here and proves the claim. So we must
assume $r(\ell)$ is odd, in which case we follow the path to another vertex in
$U^{+}$ via $R$ as before, returning to $U^{-}$ via $M_{0}$. Here we are faced
again with termination of the path at an even vertex, or continuing to $U^{+}$
and subsequently back to $U^{-}$ at odd vertex. Since the graph is finite this
process must end, clearly the only location the process finishes is at an even
vertex in $U^{-}$. ∎

Once again we can use this structure to join together the above paths into
fewer longer paths. Indeed, using the edges $(5,7),(9,11),(13,15),\dotsc$ for
all odd vertices in $[7,\frac{x_{b}-1}{2}]$ immediately halves the number of
paths. But we can do better than this.

######  Claim 3.18.

We can use only $2$-type edges to connect the paths with endpoints in $T^{+}$
into at most $\frac{1}{2}(\lceil\log_{2}(\frac{x_{b}-11}{4})\rceil+1)$ paths.

###### Proof.

Recall that we are considering $n\geq 44$.

Consider the path $P_{1}$ from vertex $7$, and $P_{2}$ from vertex $9$. After
three edges ($M_{0}$, $R$, and $M_{0}$), $P_{1}$ must go through vertex
$-\frac{n-5}{2}$, and $P_{2}$ through $-\frac{n-7}{2}$. Clearly, one of
$-\frac{n-5}{2}$ and $-\frac{n-7}{2}$ is even and therefore is the endpoint of
the path. Let $v=7$ if $\frac{n-5}{2}$ is even, and $v=9$ otherwise, and let
$-u$ be the other endpoint of the path at $v$. Then we must have that the path
from $v+4$ terminates at $-u+2$, and in general the path at
$v+4k\in[7,\frac{x_{b}-1}{2}]$ terminates at $-u+2k$ for $k\in\mathbb{N}$.

Similarly, consider the paths from vertices $v+2$ and $v+6$, $P_{3}$ and
$P_{4}$. After $3$ edges, both paths are at an odd vertex in $U^{-}$, in
particular, $P_{3}$ is on $-u+1$ and $P_{4}$ is on $-u+3$. This means they are
on odd vertices in $U^{-}$ and hence the next edge in both paths is an $R$
edge to $U^{+}$. Let $w=r(-u+1)$, then we must have that $(-u+3,w+1)$ is the
$R$ edge at $-u+3$. The paths $P_{3}$ and $P_{4}$ must then follow $M_{0}$
edges to $-w$ and $-w-1$ respectively. Once again, one of $-w$ and $-w-1$ is
even and hence the path terminates here, the other must continue along another
$R$ edge. Let $w^{\prime}$ be the even vertex out of $w$ and $w+1$, and let
$v^{\prime}$ be the vertex in $T^{+}$ on the path to $w^{\prime}$ (either
$v+2$ or $v+6$). Then we have that the path from $v^{\prime}+8$ must terminate
at $-w^{\prime}-2$, and similarly the path from vertex
$v^{\prime}+8k\in[7,\frac{x_{b}-1}{2}]$ terminates at vertex $-w^{\prime}-2k$.

In the first stage we found that paths from every other vertex in
$[7,\frac{x_{b}-1}{2}]$ terminate at consecutive endpoints in $U^{-}$. Let
$T_{1}\subseteq[7,\frac{x_{b}-1}{2}]$ be those vertices. Then we looked at
$[7,\frac{x_{b}-1}{2}]\setminus T_{1}$ and found that half of these vertices
lead a path that terminates after $5$ edges and have consecutive endpoints in
$U^{-}$. Let $T_{2}\subseteq[7,\frac{x_{b}-1}{2}]\setminus T_{1}$ be those
vertices found to be in paths of length $5$. Then we can continue and consider
odd vertices in $[7,\frac{x_{b}-1}{2}]\setminus(T_{1}\cup T_{2})$. By using
the same argument as above we find again that half of these vertices are
endpoints to paths that have $7$ edges and with the $U^{-}$ endpoints all
consecutive.

By the end of this process we have at most
$\lceil\log_{2}(\frac{x_{b}-11}{4})\rceil+1$ sets $T_{i}$. For each set
$T_{i}$, let $U_{i}$ be the set of vertices in $U^{-}$ which are endpoints of
paths starting in $T_{i}$.

We are now ready to define our connecting edges. First we use the edges

$C_{0}=\\{(9,11),(13,15),\dotsc\\}$

for all odd vertices in $[9,\frac{x_{b}-1}{2}]$. Since every path starting in
$T^{+}$ terminates in $U^{-}$ adding these edges does not create any cycles.
In particular, these edges connect a vertex in $T_{1}$ with a vertex in
$T_{i}$ where $i\neq 1$. This means that the new path has one endpoint in
$U_{1}$ and the other in $U_{i}$. After adding these edges, the vertex $7$
remains an endpoint in $T^{+}$, but the only other possible endpoint is the
vertex $\frac{x_{b}+3}{2}-2=\frac{x_{b}-1}{2}$.

Let $T_{i}=\\{v^{i}_{1},v^{i}_{2},\dotsc,v^{i}_{\ell_{i}}\\}$ where
$v^{i}_{j}<v^{i}_{k}$ whenever $j<k$. Similarly, we let
$U_{i}=\\{u^{i}_{1},u^{i}_{2},\dotsc,u^{i}_{\ell_{i}}\\}$ where the path from
$v^{i}_{j}$ ends at $u^{i}_{j}$. The next connecting edges we add will be

$C_{1}=\\{(u^{1}_{1},u^{1}_{2}),(u^{1}_{3},u^{1}_{4}),\dotsc\\}.$

Again, this cannot create a cycle since no path begins and ends in $U_{1}$.
Observe that the edge $(u^{1}_{2i-1},u^{1}_{2i})$ joins a path through vertex
$v^{1}_{2i-1}$ with a path through $v^{1}_{2i}$. If $v^{1}_{2i-1}=k$ then
$v^{1}_{2i}=k+4$, meaning that $k$ is joined to $k^{\prime}\in\\{k-2,k+2\\}$
by an edge in $C_{0}$ (or $k=7$ has degree $1$) and $k+4$ is joined to
$k^{\prime}+4$ by a $C_{0}$ edge (unless $k+4=\frac{x_{b}-1}{2}$ has degree
$1$). Since $k^{\prime}$ and $k^{\prime}+4$ differ by $4$ and neither are in
$T_{1}$ we must have that either $k^{\prime}\in T_{2}$ or $k^{\prime}+4\in
T_{2}$ but cannot have both. This means that the new path containing the edge
$(u^{1}_{2i-1},u^{1}_{2i})$ cannot have both endpoints in $U_{2}$.

Again, we now do an analogous process for connectors in $T_{2}$. That is, we
use connectors
$C_{2}=\\{(u^{2}_{1},u^{2}_{2}),(u^{2}_{3},u^{2}_{4}),\dotsc\\}$, noting that
we have not created a cycle since no path has two endpoints in $U_{2}$. Using
an analogous argument to the above we also have that no new path has two
endpoints in $U_{3}$. We continue this way until we have defined connector
sets $C_{0},C_{1},\dotsc,C_{\ell}$ where
$\ell\leq\lceil\log_{2}(\frac{x_{b}-11}{4})\rceil+1$.

Finally we add the special connecting edge $(5,7)$.

It is left to count the number of paths we now have, as well as the number of
paths we replaced. Recall that there were $\frac{x_{b}-11}{4}$ endpoints in
$[7,\frac{x_{b}-1}{2}]$ and hence $\frac{x_{b}-11}{4}$ paths from $T^{+}$ to
$U^{-}$, along with the path from $3$ to $5$. We count the new number of paths
by again counting the number of endpoints. Note that the vertex $3$ is an
endpoint and $\frac{x_{b}-1}{2}$ may also be an endpoint (if it is $1\mod 4$).
There are now no other endpoints in $T^{+}$. Since we connected vertices in
$U_{i}$ by pairing them, there can be at most $1$ endpoint in each $U_{i}$,
and hence at most $\lceil\log_{2}(\frac{x_{b}-11}{4})\rceil+1$ endpoints in
$\cup_{1\leq i\leq\ell}U_{i}$. Therefore, in total we have replaced
$\frac{x_{b}-7}{4}$ paths with at most

$\frac{\lceil\log_{2}(\frac{x_{b}-11}{4})\rceil+1}{2}$

new paths. It is left only to note that we have only used $2$-type edges in
this construction as we have connected consecutive odd vertices in $T^{+}$ and
consecutive even vertices in each $U_{i}$. ∎

At this point, the total number of paths in $L\cup C_{B}\cup
C_{0}\cup\dots\cup C_{\ell}\cup\\{(5,7)\\}$ is given by

$\frac{n-2x_{b}+(-1)^{\frac{n-1}{2}}}{4}-\left\lceil\frac{x_{b}+5}{8}\right\rceil+1-\frac{x_{b}-7}{4}+\frac{\left\lceil\log_{2}(\frac{x_{b}-11}{4})\right\rceil+1}{2}.$

This is at most

$\frac{n+16\log_{2}n+163}{32}.$

Let $L^{\prime}=L\cup C_{B}\cup C_{0}\cup\dots\cup C_{\ell}\cup\\{(5,7)\\}$ be
the linear forest at this point. Finally we will connect $L^{\prime}$ using
any suitable edges, call the set of these additional edges $C_{A}$. Let $P$ be
the path $P=L\cup C$, where $C=C_{B}\cup C_{0}\cup\dots\cup
C_{\ell}\cup\\{(5,7)\\}\cup C_{A}$.

Note that $|C_{A}|\leq\frac{1}{32}(n+16\log_{2}n+131)$ by the number of paths
remaining in $L^{\prime}$. Furthermore, we are able to choose the edges of $C$
in such a way that for any $x$, if there are more than two $x$-type edges in
$P$ then they are not spaced out evenly on $K_{n}$. This ensures that all
edges of the same type are separated from each other by the rotations of $P$.
All the edge types in $C_{A}$ will end up in $D$, so apart from ensuring the
edges are not equally spaced there are no other conditions for these edges to
follow.

######  Claim 3.19.

We can join the paths in the linear forest $L^{\prime}$ into a single path $P$
such that there are no evenly spaced $x$-type edges in $P$.

###### Proof.

Consider the linear forest $L^{\prime}$ and its endpoints (see summary in
Table 2).

Set | Endpoints in set | Other endpoint of path | Reference
---|---|---|---
$\\{0\\}$ | all |  $-x_{b}-1$ or $U^{-}$ | Claim 3.16
$U^{+}$ | none | - | See Table 1
$M^{+}$ | all |  $U^{-}$ and possibly $M^{-}$ | See $M^{-}$
$T^{+}$ |  $3$ and possibly $\frac{x_{b}-1}{2}$ |  $U^{-}$ or the pair $\\{3,\frac{x_{b}-1}{2}\\}$ | Claim 3.18
$U^{-}$ | some evens |  $U^{-}$, $M^{+}$, and possibly $T^{+}$ and $0$ | See $M^{+},T^{+},\\{0\\}$
$M^{-}$ | all evens | $M^{+}$ | Length $1$ paths
$T^{-}$ |  $-x_{b}-1$ and possibly $-\frac{3x_{b}+7}{4}$ |  $0$ or the pair $\\{-x_{b}-1,-\frac{3x_{b}+7}{4}\\}$ | Claim 3.16

Table 2: Path connections between each segment of $L^{\prime}$

Starting with $C_{A}$ empty, we add edges as follows. First add the edge
$(0,3)$, note that this is a $3$-type edge. Since $R$ and $B$ only contain
edges of large type, there is only one $3$-type edge in $L^{\prime}$. In
particular, since $n$ is odd, $L^{\prime}\cup\\{(0,3)\\}$ does not have evenly
spaced $3$-type edges.

Next, suppose the vertex $v=-\frac{3x_{b}+7}{4}$ is indeed and endpoint. This
means that the distance from $v$ to some endpoint in $U^{-}$ is at most
$\frac{3n-29}{16}<\frac{n-1}{4}$. Indeed, in $L$ there was an endpoint at
every even vertex of $[-\frac{n-5}{2},-\frac{n-1}{2}+r-1]$ until we added
$C_{0}\cup\dots\cup C_{\ell}\cup\\{(5,7)\\}$. This left at least
$\frac{n+3}{16}$ vertices in $U^{-}$. Further note that any edge from $v$ to
an endpoint in $U^{-}$ must have even edge type since both endpoints are on
even vertices. Let $e_{v}$ be any such edge, note that
$L^{\prime}\cup\\{(0,3),e_{v}\\}$ is still a linear forest.

We now move on to the vertices in $M^{+}$. If $|M^{+}|=1$ leave this vertex as
an endpoint. If $|M^{+}|=2$ then use a $1$-type edge $e_{+}$ to join them,
noting that this creates a path with one vertex in $M^{-}$ and the other in
$U^{-}$. This cannot create a cycle since we have not added any edges to
vertices in $M^{-}$. If $|M^{+}|=3$, join with $e_{+}$ as in the previous
case, and leave one as an endpoint. Finally, if $|M^{+}|=4$ join with two
$1$-type edges $e_{+}$ and $e_{+}^{\prime}$, again this does not create a
cycle. Denote by $E_{M}$ the set of edges added within $M^{+}$, so $E_{M}$
depends on $|M^{+}|$ and is equal to one of $\emptyset$, $\\{e_{+}\\}$ or
$\\{e_{+},e_{+}^{\prime}\\}$. Note that $L^{\prime}\cup E_{M}$ does not
contain evenly spaced $1$-type edges. Indeed, when
$E_{M}=\emptyset,\\{e_{+}\\}$ then $L^{\prime}\cup E_{M}$ contains at most $2$
type $1$ edges, and therefore they cannot be evenly spaced. When
$E_{M}=\\{e_{+},e_{+}^{\prime}\\}$ there are exactly $3$ $1$-type edges in
$L^{\prime}\cup E_{M}$ and two of them, $e_{+}$ and $e_{+}^{\prime}$, have
clockwise distance $2$ between them. Therefore there are no evenly spaced
$1$-type edges.

At this point $C_{A}=\\{(0,3),e_{v}\\}\cup E_{M}$.

Now, $L^{\prime}\cup C_{A}$ is a linear forest and has at most two endpoints
outside of $U^{-}\cup M^{-}\cup\\{-x_{b}-1\\}$, the vertices
$\frac{x_{b}-1}{2}$, and some vertex $u\in M^{+}$. Since $u$ and
$\frac{x_{b}-1}{2}$ are not endpoints of the same path (see construction in
3.18), we simply need to join all endpoints within $U^{-}\cup
M^{-}\cup\\{-x_{b}-1\\}$ to create our path $P$. Note that since all endpoints
in this region are even vertices, this will only require edges of even edge
type. Moreover it only requires edges of type $\frac{n-1}{4}$ or shorter.
Indeed, the longest possible edge in this interval is
$(-x_{b}-1,-\frac{n-5}{2})$, which has type at most $\frac{n+1}{4}$, but since
there are at least $\frac{n+3}{16}-1$ endpoints remaining in $U^{-}$ (as we
saw earlier in this proof) we do not need to use this longest edge. All other
edges in the interval have type at most $\frac{n-1}{4}$ as required.

We add as many of these short even edges to $C_{A}$ as required, until
$L^{\prime}\cup C_{A}$ is a path. Then we set $P=L^{\prime}\cup C_{A}$.

It is left to check that $P$ has no evenly spaced edge types. Note that $L$
clearly does not since $L$ contains at most $2$ edges of each type. So we only
need to check the edge types appearing in $C$. Note that among all the edges
in $C$, the only edges that are not even are the edges in $E_{M}$ and the edge
$(0,3)$. The remaining edges in $C$ are all even and have edge type at most
$\frac{n-1}{4}$. We have seen that the $3$-type edge and the $1$-type edges do
not create a problem, it is left to check the even edges of $C$.

Consider edges of even type in the linear forest $L$, with starting vertex in
$[\frac{x_{b}+3}{2},\frac{n-1}{2}]\cup[-\frac{n-1}{2},-\frac{n-3}{2}]$. Such
edges must all be from $R$. Indeed, even-type $M_{0}$ edges all start on a
negative vertex, and in particular the $M_{0}$ edges at $-\frac{n-1}{2}$ and
$-\frac{n-3}{2}$ both have odd type. Also all $B$ edges have their starting
vertex in the interval $J$, which does not intersect
$[\frac{x_{b}+3}{2},\frac{n-1}{2}]\cup[-\frac{n-1}{2},-\frac{n-3}{2}]$. We
also know that all edges in $R$ have a type from
$[\lceil\frac{n-1}{4}\rceil,\frac{n-1}{2}]$.

The only edges added to this interval to create $P$ are the edges in $E_{M}$.
We know that $E_{M}$ only contains edges with odd type. In other words, in $P$
no edges of even type from $[2,\frac{n-1}{4}]$ has a starting vertex in the
interval
$[\frac{x_{b}+3}{2},\frac{n-1}{2}]\cup[-\frac{n-1}{2},-\frac{n-3}{2}]$. This
means that if $e_{1},\dotsc,e_{m}$ are all the $x$-types in $P$ with even
$x\in[2,\frac{n-1}{4}]$, and $cd(e_{i},e_{i+1})=\frac{n}{m}$ then
$\frac{n}{m}\leq\frac{3n+17}{8}$. This forces $m<3$, since $n$ is odd we
cannot have any evenly spaced $x$-type edges when $m=2$.

Therefore there are no evenly spaced $x$-type edges in $P$. ∎

We use $P$ as the base path for Theorem 3.11 to give a separating path system
for $K_{n}$. The size of this family is dependent on the size of
$D=[\frac{n}{2}]\setminus F$.

######  Claim 3.20.

Let $P$ be the path defined in this section. Then $P$ is an $F$-separator
path, where $D$ satisfies the following.

$|D\cup\\{1\\}|\leq\frac{5n+16\log_{2}n+167}{32}$

###### Proof.

From 3.14 we know that in $L$ all edge types in $R\cup B$ appear exactly
twice, and the remainder appear exactly once. This means there are at most

$\frac{n-1}{2}-\frac{n-9}{4}-2-\frac{x_{b}+1}{2}\leq\frac{n+9}{8}$

edge types in $L$ that appear exactly once. We put all of these edge types
into $D$. Note that, by the construction of $R$ and $B$, these are the
shortest $\approx\frac{n}{8}$ edge types. In particular $1,2\in D$.

Moreover, we know by 3.14 that $L$ is an $F_{L}$-separator where
$F_{L}=\\{x:\text{there is an }e\in R\cup B\text{ with edge type }x\\}$. To
turn $L$ into $P$ we added various connecting edges $C$. The only way an edge
type can be in $F_{L}$ but not in $F$ is if some edge in $C$ has edge type
from $F_{L}$. Therefore, for the path $P$, the types associated with these $C$
edges must also appear in $D$, and the remaining types in $F$.

All edges in $C_{B}\cup C_{0}\cup\dots\cup C_{\ell}\cup\\{(5,7)\\}$ have type
$2$, which are already accounted for. We used a final
$\frac{1}{32}(n+16\log_{2}n+131)$ edges in $C_{A}$. This means $D$ contains at
most

$\frac{n+9}{8}+\frac{n+16\log_{2}n+131}{32}=\frac{5n+16\log_{2}n+167}{32}$

edge types. ∎

We note that the methods in this section do not adapt too well to the strong
version of the problem. Indeed, the way to adapt the path system given in
Theorem 1.2 using methods from this paper would be to use more fixing paths
(as in Lemma 3.10). However, this gives an upper bound of approximately $2n$,
which is not an improvement from the previously known result Theorem 3.1.

## References

  * [1] J. Balogh, B. Csaba, R. Martin, and A. Pluhár. On the path separation number of graphs. Discrete Applied Mathematics, 213 (2016): 26-33.
  * [2] B. Bollobás, A. Scott. Separating systems and oriented graphs of diameter two. Journal of Combinatorial Theory, Series B 97.2 (2007): 193-203.
  * [3] M. Cai. On separating systems of graphs. Discrete Mathematics 49 (1984): 15-20.
  * [4] V. Falgas-Ravry, T. Kittipassorn, D. Korándi, S. Letzter, and B. Narayanan. Separating path systems. Journal of Combinatorics, 5.3 (2014): 335-354.
  * [5] F. Foucaud, M. Kovše. Identifying path covers in graphs. Journal of Discrete Algorithms 23 (2013): 21-34.
  * [6] B. D. McKay, and T. Peters. Paths through equally spaced points on a circle. Preprint 2022. arXiv:2205.06004 [math.CO]
  * [7] A. Rényi. On random generating elements of a finite Boolean algebra. Acta Sci. Math. Szeged 22 (1961): 75-81.