Wolf-Goat-Cabbage 6:   B o a t   s i z e   τ ( G ) + 1

Thus a boat size of τ(G) is necessary to be able to make a first move, but it does not guarantee that we can eventually transfer all vertices. But if the boat has one more space than this, we can always transfer all n children, even in 2n-2τ(G)-1 moves.

The strategy is quite simple. We put a vertex-edge covering of sice τ(G) in the boat. These vertices stay in the boat permanently, until the very end. There is one more place available in the boat which can be used to transfer the remaining n-τ(G) vertices one by one from left to right. We need n-τ(G) trips from left to right, and n-τ(G)-1 trips back to left. Therefore the transfer can be done in 2n-2τ(G)-1 steps.

Therefore there are two sorts of graphs:

• Those where crossing the river is possible with a boat of size τ(G), but not with a smaller boat. These graphs are called small boat graphs in [CHW2008].
• Those graphs where crossing the river is possible with a boat of size τ(G)+1, but not with a smaller boat. These graphs are called large boat graphs in [CHW2008].