Last byte

Puzzled: Delightful Graph Theory

Welcome to the new puzzle column. Each column will present three puzzles. The first two will have known (and usually elegant) solutions that will appear in the next issue of Communications. The third will be an open problem; good luck with that one.

Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

We start with three delightful graph-theoretic puzzles. Here we go.
  1. Article
  2. Author
  3. Footnotes
  1. Since this is an election year, it seems appropriate to visit that impressionable town in which, every evening, each citizen calls all his (or her) friends (always an odd number) and re-chooses his party affiliation—Republican or Democrat—the next day, in accordance with the majority of his friends at the time of the call. Can you show that, after a while, party affiliations will be the same on every alternate day?
  2. The island of Foosgangland boasts a complex web of footpaths. Each section of path, from one intersection to the next, is identified by a different number. If you happen to take a walk in Foosgangland, the "length" of your walk is the number of path sections you traverse, and your walk is "increasing" if the path numbers you encounter are always go up. Prove that there is someplace on the island where you can take an increasing walk whose length is at least the average number of paths meeting at the intersections in Foosgangland.
  3. In a graph-coloring game, a finite graph G and a palette of k: colors are fixed. Alice and Bob alternately choose an uncolored vertex of G and color it with a color not previously used on any neighboring vertex. Alice, who goes first, wins if all the vertices get colored; but if anyone gets stuck before that happens, Bob wins. (The game is described in an article—Bartnicki, T., Grytczuk, J., Kierstead, H.A., and Zhu, X. The map-coloring game. American Mathematical Monthly 114, 9 (Nov. 2007), 793–803—that pointed out that the following question remains embarrassingly open: Are there a G and a k such that Alice wins on G with k colors, but Bob wins with k+1?)

Back to Top

Back to Top

    DOI: http://doi.acm.org/10.1145/1378704.1378726

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More