last byte
DOI: 10.1145/1378704.1378726
Peter Winkler
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 [e-mail].
We start with three delightful graph-theoretic puzzles. Here we go.

1.Si nce 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.Th e 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?)

Peter Winkler ( [e-mail]) 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.