You need a larger boat to create more interesting problems. Try this larger boat version . You can also play it with my applet below.

Difficulty level 2:Again you have to cross the river 7 times to get everybody to the right. But this time you can get two students in the boat at the same time.

- Click at "A", "E", "I", "M", "Q" in the red box to the right.
- Click on "Start".

Now we choose several students by clicking on them in the setup phase. Some
hostilities will never play a role in our particular game, namely those
where one of its two participants is not chosen. On the other hand, if we
choose two enemies, we have the hostility. So by choosing our students,
the vertices of our graph, we automatically choose the edges of our graph.
The chosen students/vertices and the generated hostilities/edges form our
game graph. In graph-theoretical terminology, the game graph is an induced
subgraph of the red box graph. For our example above, the game graph looks as follows: |
The induced
subgraph, induced by a subset W of the vertces, contains all
edges that have both ends in W. |

The grid-like red-box graph above is a special bipartite
graph. The coloring of the red-box graph above would be the well-known
checkerboard pattern. |
The vertices of a bipartite
graph can be colored with two colors such that no vertices of the same color
are adjacent. |

What about really large boats? Are you interested to find out how to decide the question whether a first move is possible for large k?

**Question 2:** What about
the game graph shown on the right? How large a boat do we need?

It turns out that this question is in general a really difficult one, but for bipartite game graphs, like the one shown, it is related to several other parameters and can be computed rather quickly (at least in polynomial time). Take a digression into the important topic of matchings in bipartite graphs. |

**Research Question:**
Now we know when we may make a first move.
Is it also possible to describe those game graphs where the puzzle can be solved?

Erich Prisner, 2002-2004