Human Graph Theory

A problem-solving, name-learning activity

1998 Summer Institute || Participant Projects || List of Participants || Sum98 Staff || Agenda

The Math Forum's 1998 Summer Institute began at noon on the lawn outside the Swarthmore College guest house, Ashton House, with a graph theory game based on Toss and Sort (see also Graphs and Graph Theory) designed to help the group learn each other's names and get acquainted. (Thanks to Mel Sprouse, who provided the photographs!)

Each participant wrote his or her name on a piece of paper. Ken, Steve, and Dave then linked these pieces of paper, as well as two blank "nodes," with masking tape to form a graph with several cycles and dead ends. The following diagram is a reconstruction (we hope accurate) of this graph:

Folks then randomly re-settled on a node that did not necessarily bear their own name. Our shared objective: move people along the paths of the graph, advancing one person at a time and only to connected unoccupied nodes, so that we achieved a state where each person stood at the node bearing her or his name.

Ken helps start the game.

Left to right: Steve, Margaret, Becky, Richard, Dave, Ken, and Jon

We had one additional restriction on our movements: only one player could move at a time. To achieve this restriction, we used a tennis ball; whoever held it could advance to an unoccupied node. When a player finished moving, he or she tossed the ball to another player.

Ken and Bobbie discuss strategy, as John looks on.

After upwards of half an hour, scores of moves, and many more hypotheses and suggestions, we achieved our objective* and retired indoors to a hard-earned lunch.

[*In fact, we showed that the Ken-Steve part of our graph was doomed to forever contain the wrong players, so we rearranged our nodes to make victory possible.]