## Saturday, March 7, 2009

### Connecting Graphs

This is a game for any number of players.

Start with an n-by-n grid lightly drawn on paper. Or perhaps a square array of dots (representing a grid's vertices) would be better.

Players take turns connecting any ADJACENT pair of dots/vertices with a straight line-segment, one segment each move. Only pairs of dots that have not been previously connected may be connected on any move. Although any particular dot/vertex can have multiple line-segments drawn to it.

Line-segments may be vertical or horizontal. In a variation of the game, diagonally adjacent vertices/dots may be connected as well, as long as no line-segments cross. (In the variation, each line-segment is drawn either N, NE, E, SE, S, SW, W, or NW.)

Borrowing a term from graph-theory, a "graph" of connected line-segments (each line-segment drawn during the game's play) is a "connected graph" if one can trace along the line-segments from any vertex of the graph to any other vertex (possibly, but not necessarily, connecting each vertex to any other in multiple ways).

Whenever 2 distinct connected graphs are combined into 1 connected graph by a line-segment, the player drawing that line-segment gets a point.

No points are obtained for starting a new connected graph, for extending a single connected graph (in a way that does not connect to another connected graph), or for connecting a connected graph back to itself.

The game is over as soon as there is exactly one connected graph, no more, of line-segments drawn on the grid. The initial single connected graph, formed when the first move of the game is made, does not end the game. (Otherwise, what a dumb game this would be!)

Highest score wins.

How does allowing diagonally drawn line-segments alter the game, I wonder?

This game sounds familiar too. Where have I stolen the idea from?

Thanks,
Leroy Quet