### Better Know A Theorem: Las Vegas

09Jan08

This one comes from Donald Knuth, who is rather well-known for writing a number of good books and inventing TeX (which is what mathy people use to make pretty formulas). Without further ado, here is the Las Vegas Theorem:

Suppose we have a finite network of one-way roads containing a distinguished city, Las Vegas, with the following property: there is a route (sequence of roads) from each city to each other city. It is possible to erect toll booths on these roads in such a way that the following 3 conditions are satisfied.

1. It is impossible to drive indefinitely without paying a toll.
3. There is a toll-free route from every city to Las Vegas.

The one-way road network is a directed graph; the requirement that you can get from any city to any other is strong connectivity. Knuth proved the Las Vegas theorem in a cute 1974 paper called “Wheels within Wheels;” his proof used a hierarchical decomposition of strongly connected directed graphs, which is the namesake of the paper. Maybe the theorem has another, possibly easier, proof? A related theorem that he mentions is the following:

Every minimally strongly connected directed graph has two nodes with in- and out-degree 1.

E.g., a bidirected path meets this bound with equality.