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

Structured Logging with slog

The Go 1.21 standard library includes a new structured logging package, log/slog.

via The Go Blog on

Status update, August 2023

Hi! Let me start this status update with an announcement: from 2023-08-28 to 2023-10-01 (!), I will be on leave, so I will have reduced availability. Don’t be surprised if I miss some e-mails, and feel free to ping me again (more generally, please do ping me …

via emersion on

I had a great time at DEF CON 31

I've always admired DEF CON from a distance. I've watched DEF CON talks for years, but I've never been able to go. This year I was able to go, and I had a great time. This post is gonna be about my experiences there and what I learned. In short: I…

via Xe's Blog on