Let $A$ and $B$ be any two towns. We know that it must be possible to move from $A$ to some other town $X$ and from $B$ to some other town $Y$. From four towns $A, B, X, Y$ we can form three pairs which all have a direct connection between them. Of those at least one way goes from either $A$ or $X$ to either $B$ or $Y$. Therefore it is possible to travel from $A$ to $B$.
Look at some possible way of getting from $A$ to $B$; let $C$ be the first town after town $A$ on this way and $D$ be the last town before town $B$ (see fig. 36). Assume that $A, C, D, B$ are all distinct, because otherwise the problem statement follows trivially. Because of the same reason assume that there does not exist a direct connection between $A$ and $B, A$ and $D$ or $C$ and $B$. As according to the problem statement we can get three pairs from those four that all have direct connection between them, a direct connection must be between $C$ and $D$.

Figure 36

Figure 37

Figure 38

Figure 39

Let $E$ be some town that is not $A, B, C$ or $D$. If there is a direct connection between $E$ and $A$ and also between $E$ and $B$, then the problem statement holds. Therefore let us assume in the following that there is no direct connection between either $E$ and $A$ or $E$ and $B$. From $A, C, E$ and $B$ we can form three pairs that have a direct connection between them. As there is a maximum of one direct connection between $E, A$ and $B$ and there is no direct connection between $B$ and $C$, then there must be one between $E$ and $C$. By switching the roles of $A$ and $B$ and also $C$ and $D$ we get analogously that there is a direct connection between $E$ and $D$ (see fig. 37).
If the connections between $A$ and $C$, and $D$ and $B$, are of different kind, then on the path $A \to C \to D \to B$ there must be at least two consecutive steps with same mode of transportation. For this path the problem statement holds. But if connections between $A$ and $C$, and $D$ and $B$, are of the same kind, then there must exist two consecutive steps with the same mode of transportation on the path $A \to C \to E \to D \to B$. For this the problem statement also holds.

Let $A$ and $B$ be any two towns. Suppose that there is no direct connection between them, because otherwise the problem statement holds trivially.
Let $X$ be any town distinct from $A$ and $B$. If there is no direct connection between $A$ and $X$ and no direct connection between $B$ and $X$, then from a fourth town $Y$ there must be a direct connection to $A$, $B$ and $X$ (see fig. 38). In that case one can go from $A$ to $B$ via $Y$ and the problem statement holds. Because of that suppose in the following that from any town $X$ distinct from $A$ and $B$ there is a direct connection to either $A$ or $B$.

Let $X$ and $Y$ be any two distinct towns that are not $A$ or $B$. Suppose that there is no direct connection between $X$ and $Y$. As there is also no direct connection between $A$ and $B$, but from $A$, $B$, $X$ and $Y$ we can form three pairs that have a direct connection between them, it is possible to go from $A$ to $B$ via $X$ or $Y$, in which case the problem statement holds. Now the only case to look at is the one where between any two towns that are not $A$ and $B$ there is a direct connection.
As there are at least 5 towns in the country, there are at least 3 towns other than $A$ and $B$. Therefore either $A$ or $B$ must have a direct connection to at least two other towns. Without loss of generality assume that $A$ has a direct connection to $C$ and $D$. But $B$ also has a direct connection to some town $E$; if $E$ coincides with any of the previously mentioned ones then the problem statement holds, which leaves us to look at the case where $E$ is a new town. Previously mentioned facts give us that $C$, $D$ and $E$ all have direct connections between them.

If now either $A$ and $C$ or $A$ and $D$ have a direct connection between them of different kind than what is between $B$ and $E$, then either path $A \to C \to E \to B$ or $A \to D \to E \to B$ has two consecutive steps with same mode of transportation. For this path the problem statement holds. But if the connection between $A$ and $C$ or $A$ and $D$ is of the same kind as the connection between $B$ and $E$, then either on the path $A \to C \to D \to E \to B$ or $A \to D \to C \to E \to B$ there are two consecutive steps with same mode of transportation. For this also the problem statement holds.