### 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

## No Responses Yet to “Better Know A Theorem: Las Vegas”