Finding an Eulerian path on complete graphs

Question

I want to prove the following algorithm to find an Eulerian path in a complete graph:

In the complete graph $K_{n}$ where $n = 2k + 1, k \in \mathbb{Z}^+$, let us label the vertices $1, 2, ..., n$. Then we can construct an Eulerian path by starting at the first vertex, and traversing along each next edge we have not previously visited, clockwise (assuming the vertices on a circle where clockwise means increasing $i$). That is, for a vertex $i$, take an unvisited edge to a vertex $j > i$, for the smallest possible $j$. If there exists no such $j$, we take the first unvisited edge to a vertex $j$ for $j \geq 1$, again for the smallest possible $j$. If there exists no unvisited edges at some vertex, it terminates.

For example, a path on $K_5$ generated by this algorithm would be:

$$ 1 \to 2 \to 3 \to 4 \to 5 \to 1 \to 3 \to 5 \to 2 \to 4 \to 1 $$

I strongly suspect that this algorithm is correct, but I don't know how to prove it.

Also, relatedly, I would like to prove that on complete graphs with even vertices, $K_{n}$ where $n = 2k, k \in \mathbb{Z}$, the same algorithm produces a path which is the longest path that does not use the same edge more than once.

Intuitively, it seems to work, but I am clueless on how to begin proving this.

Answer 1

Let $g_d = (n, d) = \gcd\{\,n, d\,\}$ be the greatest common divisor of $n$ and $d$. Let $0, 1, \ldots, n - 1$ modulo $n$ be the vertices of the graph (i. e., vertex $n$ is the same as vertex $0$, and $5n + 3$ is the same as $3$ and so on). Then all edges of the graph can be separated into the following sets of cycles: $$\begin{eqnarray*} \begin{gathered} C_d = \{\,(0, d, 2d, \ldots, \frac{n}{g_d}d),\\ (1, d + 1, 2d + 1, \ldots, \frac{n}{g_d}d + 1),\\ \vdots\\ (g_d - 1; d + g_d - 1, \ldots, \frac{n}{g_d}d + g_d - 1)\,\} \end{gathered} \end{eqnarray*}$$ for all $d = 1, 2, \ldots, \left\lfloor \frac {n - 1}2 \right\rfloor$ and the matching $M = (\{\,0, \frac n2\,\}, \{\,1, \frac n2 + 1\,\}, \ldots, \{\,\frac n2 - 1, n - 1\,\})$ if $n$ is even.

The described method starting from the vertex $0$ passes all cycles containing the vertex $0$ one by one for all $d = 1, 2, \ldots, \left\lfloor \frac {n - 1}2 \right\rfloor$. But if it meets a vertex which belongs to some non-passed cycle $X$ from a set $C_{d'}$ for $d' < d$ it firstly passes that cycle $X$ and continues passing the current cycle containing the vertex $0$.

Now note that every cycle in $C_d$ has at least one common vertex with every cycle in $C_{d + 1}$ for every $d = 1, 2, \ldots, \left\lfloor\frac {n - 1}2\right\rfloor - 1$, because greatest common divisor of $d$ and $d + 1$ is $1$. Also for the same reason for even $n$ every edge of matching $M$ has a common vertex with all (at most $2$) cycles in $C_{n / 2 - 1}$.

If means that the described method before finishing the first cycle from $C_{d + 1}$ passes all cycles from $C_d$. Let $m = \left\lfloor\frac{n - 1}2\right\rfloor$. For $n = 2k + 1$ the proof is finished because $(2k + 1, k) = 1$ and therefore $C_m$ has the only cycle.

For even $n = 2k$ we note that $|C_m| = (2k, k - 1) = (2, k - 1) \le 2$ cycles. If $|C_m| = 1$ then after passing the only cycle of $C_m$ methods passes the first edge of matching. Otherwise after passing the first cycle of $C_m$ it passes the edge and passes the other cycle of $C_m$. Note that that the longest trail has exactly $\frac{n(n - 2)}2 + 1$ edges.