Lesson 16: Deadlock

Note: This lesson is the "Toss 'n' Sort" activity which is freely available from the "More Games on Graphs" page of the MegaMath web site.

Toss 'n' Sort


This game illustrates routing and deadlock in networks. Each student is like a "packet" of information or a message which has a destination. In order to get to that destination, the traveler can only travel along a route when it is clear. Since the object is for all the travelers to get home, everyone has to work together to find a way for this to happen.


  • Graph on the playing area. (Here are diagrams of some interesting sample graphs.)
  • One ball that is easy to throw and catch
  • Optional: Extra balls make the game easier

Number of players

When there is one less player than the number of vertices in the graph, the game is the most challenging. Decreasing the number of players or increasing the number of balls makes it easier. (Why?)


  • Players will stand in vertices of the graph and throw and catch balls, so the graph should not be so large that the players cannot throw all the way across.
  • Label each vertex of the graph uniquely--with letter, numbers, names of places, symbols, etc.
  • Prepare a set of cards that match the labels for the vertices. Make the cards so that players can wear them--pinned to their clothing, or on strings around their necks, for example.

How to play

  • Players take their places at the vertices of the graph. At least one vertex will be left empty.
  • Distribute the cards randomly among the players.
  • Give the ball to one of the players
  • The object of the game is for all of the players to get to the vertex whose label matches the card that they have.
  • Players can run down the edge to the next vertex only if:
    • the vertex is empty
    • they are holding the ball
  • A player who has the ball can throw it to any other player.


  • Depending on the size of the graph, the game can be quite difficult when only one vertex is left empty and just one player at a time can move. Decreasing the number of players to leave two or more vertices empty will make the game easier. Increasing the number of balls permits more than one player to move at a time. In some cases this makes the game easier, and in others it increases the level of confusion.
  • Have a player stand in every vertex. Use one or more pairs of matching balls (i.e., two red, two blue, etc.). Any two players who are holding identical balls can exchange places.
  • Play the game or any of its variations without talking, signaling, or using any other means to tell other players what to do. In addition to being strangely quiet, it requires that all participants have some kind of strategy for working the game out. Sometimes it helps to have a planning session before beginning the period of silence.
  • Use a stopwatch to time how long it takes to play a round, then try to beat previous records for shortest time.
  • Count how many times the ball is tossed from start to finish, and try to beat previous records for fewest tosses.
  • Invent a rhythm of foot-stamping and hand-clapping that is 4 to 8 beats long. When the rhythm is being tapped out, the player holding the ball throws it to someone else. When the rhythm is complete, the player who is holding the ball must run to a neighboring vertex.
  • Invent a rap or rhyme which all players chant to accompany the rhythm (above). This has the same effect as a rule which prohibits telling other players what to do, but is considerably more fun.
  • Label the vertices of the graph so that the labels can only be seen when the player at the vertex. Have players conceal the cards which tell the label of their "home" vertex from other players. Whenever a player arrives in the vertex that matches the card that she is carrying, she crouches down to signal to the other players that she is in her home vertex. A player who is crouched in her home vertex can still catch the ball and travel to neighboring vertices at any time.


  • Problem solving / reasoning / communication / connections
  • Strategy development
  • Cooperative problem solving