Imagine that the graph is the map of a neighborhood. The edges are streets and at every vertex is a house. The mail carrier doesn't want to walk down any more streets than necessary to pick up and deliver mail to all of the houses. What is the best route to take? Where should they put a drop box where the truck will leave all the mail that needs to be delivered in the neighborhood?
This problem seems very much like The Painter of Lines in the Street. Try both games on the same graph and see what you think.
The person who paints the lines in the streets works hard and doesn't want to have to spend time and energy lugging painting equipment when it is not necessary. What is the best route to take as you paint the streets so that all the streets get painted, and the only time that you are on a street is when you are painting it? Can you end up where you started?
This problem seems very much like The Mail Carrier's Tour. Try both problems on the same graph and see what you think.
In Tourist Town there is something interesting to see in every house, and the people who live there want the tourists to visit them all. The City Council has decided to buy enough paint to repaint all of the houses. If tourists leave a house that they have just visited and look down a street and see a house that is the same color, they might think that it is just like the house that they just left and not visit it. So the City Council wants to repaint the houses so that no house is the same color as the next house down the street in any direction. How many different colors of paint will the City Council need to buy?
This problem is related to the one of coloring the sidewalks of Tourist Town, but they are not quite the same, as you will see if you do them on the same graphs. These in turn are related to map coloring.
Since all the grownups got to paint their houses, the City Council decided that the children should be able to paint the sidewalks in bright and interesting colors. They don't want the tourists to ever get bored by walking down two streets in a row whose sidewalks are the same color. How many different colors of sidewalk paint must the City Council buy? Experiment by drawing graphs and coloring their "sidewalks". ( Here's an example. )
This problem is related to the one of coloring the houses of Tourist Town, but they are not quite the same, as you will see if you do them on the same graphs. These in turn are related to map coloring. See also, Quibble, Crouch, Cornerstone, Quoink
Huge game boards can be drawn with chalk on a parking lot or painted with lawn paint (the same non-toxic paint used to mark lines in playing fields) on the grass. Both have their drawbacks: the lines scuff off, skinned knees on concrete, the paint is expensive. Recently we have tried using brightly colored plastic tape available inexpensively from buiding supply stores. It can be fastened to tufts of grass with masking tape, or fastened to the ground with heavy wire bent into the shape of a "U". (Be very careful to pick up all the wire when you are finished.)
To play, one player stands in each region of the map and can assume one of several different body positions. When no player has the same body position as any of her neighbors, the game is finished.