Ben Fiedler

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$.

Articles from blogs I follow

What's cooking on Sourcehut? January 2021

Another year begins, and hopefully with better prospects for us all. SourceHut has emerged from 2020 relatively unscathed, thankfully, and I hope the same is true of most of our users. A body which, by the way, today numbers 19,647 strong, up 623 from Decemb…

via Blogs on Sourcehut on

New PGP Key Fingerprint

New PGP Key Fingerprint This morning I got an encrypted email, and in the process of trying to decrypt it I discovered that I had lost my PGP key. I have no idea how I lost it. As such, I have created a new PGP key and replaced the one on my website with it. …

via Christine Dodrill's Blog on

Status update, January 2021

Hello from the future! My previous status update was last year, but it feels like it was only a month ago. I hope you didn't miss my crappy jokes too much during the long wait. One of the advancements that I would like to mention this month is the genera…

via Drew DeVault's blog on