The Colored Bridges Problem: In Memory of Frank Harary (1921-2005)

摘要

A town has a network of walkways running through it, each colored gray. A red bridge is constructed between every two walkway intersections that are two blocks apart, and a blue bridge is constructed between every two intersections that are three blocks apart. The colored bridges problem asks whether it is possible to take a round-trip about the town passing through each of its intersections exactly once such that during this trip the walkway or bridge used to enter every intersection is of a different color than that used to exit it. With the aid of graph theory, we show that such a round-trip is always possible when the walkways of the town form a grid. Conditions are determined under which no blue bridges are needed.