Rules

Start with a complete graph -- that is, a set of points of all which are connected by lines. Take turns coloring one of the edges. The winner is the first person to color edges which form a triangle. For example, start with a complete graph on 5 points:

For example, start with a complete graph on 5 points:

If the first player colored edges blue and the second player colored edges red, then the first player has a triangle and wins.

You can play on graphs with any number of vertices -- to start with you probably want to stick with 4-8 vertices.

Questions

1. If you started with 3 vertices, there is no way that someone will win (at most a player colors two edges) so the game ends in a draw. Is there always the possibility that the game ends in a draw? Or can you start with some number of vertices and always have a winner?

   Hint

   Answer

2. Is there a strategy for winning? What is it? Does it help to be a first or second player?

   Hint

   Answer

3. Extension: What if you want to play with more players?

   Answer

4. Extension: What if you are trying to get a different graph? Say a complete graph on four vertices in your color, or a cycle of four edges?

   Hint

   Answer

5. Extension: What if both players are trying to avoid drawing a certain graph? This version of the game -- when both players are trying to avoid drawing a triangle -- is called Hexi or Sim.

   You can play it online at here.

   Hint

   Answer

Variation: Pekec's Ramsey Graph Game

Rules

The game is played in the same manner, except winning is defined differently. The first player wins in the same way -- making a triangle. The second player wins by keeping the first player from making a triangle; the second player wins if all edges are colored and there is no triangle in the first player's colors.

Therefore, for a game on 5 vertices, the second player would win the game below, even though there are no triangles in one color:

Questions

1. Can you come up with winning strategies for either player?

   Hint

   Answer