# Long monotone trails in graphs

During a recent dinner discussion I was presented with a beautiful proof to the following problem: Given an arbitrary graph $G = (V, E)$, and an ordering $\Phi$ of $E$, what is the longest monotone trail in $G$ that is guaranteed to exist?

A trail in a graph is a sequence of edges such that

- adjacent edges share an incident vertex and
- no edge is traversed twice

Take a few moments to think about this problem before reading the solution, as it such a simple seeming problem is quite tricky: Clearly there are graphs where there exists no trail of length greater than zero, namely the empty graph. Thus the solution must somehow correlate with some graph property.

### The solution

It turns out that the longest monotone trail has length equal to the average degree $d$ of $G$. The proof is truly astouding:

Let $n = |V|$ and $m = |E|$ the number of edges of $G$. Put a person on each vertex of $G$, and for each edge $e$ in $E$, traversed in order of $\Phi$, exchange the two people standing at vertices incident to $e$. Each person will walk a monotone trail on $G$.

All people together traversed a distance of $2m$ units, and since there are $n$ people the average distance traveled is $2m / n$, which is exactly the average degree of $G$. By the pigeonhole principle at least one person must have traveled $2m / n$ units, which concludes our proof.

It is not difficult to see that this result is best possible. If $G$ is a matching on $2k$ vertices, then the average degree $d$ in $G$ is $1$, and the longest monotone trail also has length $1$.