Better Know A Theorem: Las Vegas
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.
- It is impossible to drive indefinitely without paying a toll.
- It is possible to start on any road and return to your starting point, paying only one toll.
- 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.
Filed under: b.k.a.t., graphs | Leave a Comment