A Little-Known Graph Inequality

Here is a very simple, yet little-known result that proved useful to me recently. I'm surprised it is not better known, since it seems to be a natural question.

Suppose you have a directed graph G = (V,E) with n vertices that is strongly connected (so there is a directed path from every vertex to every other vertex). Consider the length of the shortest closed walk W that visits every vertex. In the worst case, how long can W be?

Here, as usual, by a "closed walk" we mean that we start at some vertex and return to it, and we are allowed to repeat vertices and edges. We measure the length of W by the number of edges, and write it as |W|. Such a walk is sometimes called a "Hamiltonian walk" in the literature.

The answer is floor((n+1)²/4). This simple result was apparently first proved by Yahya Ould Hamidoune, in Proposition 2.1 of his paper published in Discrete Mathematics 26 (1979), 227-234. Hamidoune just recently passed away; he was apparently one of Mauritania's most famous mathematicians, and proved many deeper results than the little proposition above. But his graph inequality might prove useful to others, so I reproduce his proof here.

To see the upper bound, let L be a longest simple path in G. (A simple path does not repeat edges or vertices.) Let V-L = { v_i : 1 ≤ i ≤ k }. Let v₀ be the last vertex in L and v_k+1 be the first vertex in L. Let L_i be a simple path from v_i to v_i+1. Then a Hamiltonian walk W is obtained by following the edges in L₀, L₁, ..., L_k, and then those in L. So the number of edges in W is at most (k+2)|L| = |L|(n+1-|L|). But it is easy to see that r(n+1-r) is maximized when r = ceil(n/2). You can now check that in this case, r(n+1-r) = floor((n+1)²/4), as claimed.

To see that this is best possible, consider a graph where there is a directed chain of floor(n/2) vertices, where the last vertex has a directed edge to ceil(n/2) other vertices, and each of those vertices have a single directed edge back to the start of the chain. The shortest walk covering all the vertices traverses the chain, then an edge to one of the other vertices, then a single edge back, and repeats this ceil(n/2) times. The total length is then (floor(n/2)+1)ceil(n/2) = floor((n+1)²/4). So the bound is tight.