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

We Already Have Go 2

I've been using Go since Go 1.4. Since I started using Go then (2014-2015 ish), I’ve seen the language evolve significantly. The Go I write today is roughly the same Go as the Go I wrote back when I was still learning the language, but the toolchain has …

via Xe's Blog on

Google has been DDoSing SourceHut for over a year

Just now, I took a look at the HTTP logs on git.sr.ht. Of the past 100,000 HTTP requests received by git.sr.ht (representing about 2½ hours of logs), 4,774 have been requested by GoModuleProxy — 5% of all traffic. And their requests are not cheap: every one …

via Drew DeVault's blog on

Status update, May 2022

Hi all! This month’s status update will be shorter than usual, because I’ve taken some time off to visit Napoli. Discovering the city and the surrounding region was great! Of course the main reason to visit is to taste true Neapolitan pizza. I must admit, th…

via emersion on