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

Record your Linux Desktop with ffmpeg and slop to any format

This two-line shell script allows you to record a region of your linux desktop to a video file, or a `.gif`, using `slop` and `ffmpeg`. I use it often when a screenshot is not enough, or when you need to explain a sequence of events to someone.

via Raymii.org on

What's cooking on SourceHut? March 2021

Hi! Another month of development has passed, and I’m here to fill you in on what’s new. Another 686 signups this month has brought us to 21,041 users. As always, I’ll be counting on you to make the new users feel at home, please be patient with them and help…

via Blogs on Sourcehut on

Status update, March 2021

After the brief illusion of spring, this morning meets us with a cold apartment indoors and fierce winds outdoors. Today concludes a productive month, mainly for the secret project and for sourcehut, but also marked by progress in some smaller projects as we…

via Drew DeVault's blog on