H2. A ladybird walks from $A$ to $B$ along the edges of the network shown. She never walks along the same edge twice. However, she may pass through the same point more than once, though she stops the first time she reaches $B$.
How many different routes can she take?
Solution
Label the centre point $X$, as shown in the diagram alongside.
Clearly any route that the ladybird takes from $A$ to $B$ passes through $X$, and she stops the first time she reaches $B$.

Therefore the number of different routes that the ladybird can take is equal to (the number of routes from $A$ to $X$ ) $\times$ (the number from $X$ to $B$ ).

The number of routes from $A$ to $X$ is equal to (the number of 'direct' routes from $A$ to $X$ ) + (the number from $A$ to $X$ that visit $X$ twice), which is $3+3 \times 2$.
However, the number of routes from $X$ to $B$ is just 3 , since the ladybird stops the first time she reaches $B$, so that it is not possible for her to visit $X$ again. Thus the total number of different routes that the ladybird can take is $9 \times 3$, which equals 27 .