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.
  2. It is possible to start on any road and return to your starting point, paying only one 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.



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

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: