Sign In

Communications of the ACM

Last byte

Puzzled: Delightful Graph Theory

  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


Peter Winkler ( is Professor of Mathematics and of Computer Science and Albert Bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, NH. He has written two puzzle books: Mathematical Puzzles: A Connoisseur's Collection and Mathematical Mind-benders, both published by A K Peters, Ltd., Wellesley, MA.

Back to Top



©2008 ACM  0001-0782/08/0800  $5.00

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents: