BMO 2019 Shortlist

$N$ odd. In fact, the number of trajectories has the same parity as $N$. The setting is a (multi)graph where every vertex has degree three. Each vertex has an orientation, an ordering of its incident edges. We call Vlad's possible paths trajectories, and a complete trajectory if he traverses every edge in both directions. We may assume the multigraph is connected, as otherwise a complete trajectory is certainly not possible.

N odd (construction): There is an example when $N=1$, as shown in Figure 10. Figure 10: C4: $N=1$ There are two 3-regular graphs on two vertices, the handcuffs and theta. The handcuffs fail since each self-loop has its own trajectory, but the theta does work for two of the four possible orientations. We now construct examples for $N\ge 3$ odd by induction. Suppose we have a valid 3-regular graph on $2(N-2)$ vertices, such that Vlad's trajectory is complete. This has at least two (undirected) edges, so pick two of them, $e$ and $e^{\prime }$. (It does not matter if they share incident vertices.) Split both $e$ and $e^{\prime }$ into three, by adding two new vertices to each, and connect as in Figure 11. New vertices have degree three; other degrees are unchanged, so the graph is still 3-regular. For each edge $e$ and $e^{\prime }$, pick a direction. (Both up in the figure.) These directed edges are part of the complete trajectory given by the induction hypothesis. Choose the orientations of the new vertices to preserve these two sections of the trajectory. The remaining two directed edges in the original graph will end up as partial trajectories in the new graph (see Figure 11). However, because all the new partial trajectories start and finish at the same places and in the same directions in the original graph, and no other directed edges are changed, the trajectory remains complete. The result for $N$ odd follows by induction.

N even: Split each edge $e$ in the graph into two directed edges $\overrightarrow{e}$ and $\overrightarrow{e^{\prime }}$. Let $D$ be the set of the $6N$ directed edges. Let $\alpha$ be the permutation of $D$ which exchanges $\overrightarrow{e}$ and $\overrightarrow{e^{\prime }}$.

Now, for each roundabout $v$, let ${\vec{e}}_1,{\vec{e}}_2,{\vec{e}}_3$ be the three directed edges into $v$. The roundabout has a cyclic orientation, either $({\vec{e}}_1,{\vec{e}}_2,{\vec{e}}_3)$ or $({\vec{e}}_1,{\vec{e}}_3,{\vec{e}}_2)$. Let $\theta ({\vec{e}}_1)$ describe the directed edge after ${\vec{e}}_1$ in this orientation. By considering all roundabouts, $\theta$ is also a permutation of $D$. Note that $\theta ({\vec{e}}_1)$ is directed towards $v$, so the directed edge after ${\vec{e}}_1$ in a trajectory is $\alpha (\theta ({\vec{e}}_1))$. So Vlad makes a complete trajectory precisely if $\alpha \theta$ is a cyclic permutation of $D$. Note that the cycle type of $\theta$ is $(3,3,\dots ,3)$, and the cycle type of $\alpha$ is $(2,2,\dots ,2)$. So $\theta$ is always an even permutation, while $\alpha$ is an even permutation precisely when $N$ is even. However, a cyclic permutation of $D$ is always odd, since $|D|=6N$ is even. So there is certainly no complete trajectory when $N$ is even. $\square$

Alternative I: We claim that in a graph with $E$ edges, and $V$ vertices, the number of trajectories, $T$, has the same parity as $V+E$. We allow degenerate cases of this statement, for example graphs that are disconnected, or trajectories that consist of only a single vertex, so that the graph that consists of $V$ vertices and no edges has precisely $V$ trajectories, and thus satisfies the given claim. This shows that $N$ cannot be even. We prove the claim by induction on $E$. Suppose we are given a graph with $E\ge 1$ edges and $T$ trajectories. Then consider any edge $e$, and its two directions $\vec{e},\leftarrow e$. Let $A$ be the sequence of directed edges starting from the one after $\vec{e}$ in its trajectory, ending at the edge before $\leftarrow e$ or $\vec{e}$, whichever appears first. Similarly define $B$ starting after $\leftarrow e$. $A$ and $B$ are disjoint, and may be empty. Figure 12: C4: (a) Initial trajectories. (b) After removing $e$. We consider removing $e$, but otherwise keep the orientations at its incident vertices the same. Then if $\vec{e},\leftarrow e$ are in different trajectories, these are the concatenations $(\vec{e},A)$ and $(\leftarrow e,B)$. After removing $e$, for each direction $\vec{e},\leftarrow e$, instead of proceeding onto this directed edge, the relevant trajectory moves to the other trajectory. In other words, the resulting trajectory is the concatenation $(A,B)$. So $T$ decreases by one.

Similarly, if both directions of $e$ are part of the same trajectory, this is the concatenation $(\vec{e},A,\overleftarrow{e},B)$. Then when we remove $e$, this splits into the two trajectories $(A)$ and $(B)$, by an essentially identical argument. So $T$ increases by one. Thus in both cases, removing one edge changes the parity of $T$, and so the claim follows by induction on $E$.

In the original setting we have $V=2N$, $E=3N$, so $T$ must have the same parity as $5N$. Thus $T=1$ is impossible when $N$ is even. $\square$

Alternative II: An alternative is to induct on $N$, using the following stronger claim. Claim: You can't have exactly one trajectory for $N$ even; nor exactly two trajectories for a connected graph with $N$ odd. Proof of claim: We have to check that the claim is true for $N=1,2$. Checking $N=2$ requires a couple of case. Alternatively, one can argue that a single cyclic edge with no vertices (!) counts as the case $N=0$. Now use strong induction by contradiction. If $N$ is even, but has exactly one trajectory, then there are no self-loops, so pick any edge $e$, connecting vertices $v\ne w$. Remove $e$, then remove $v$, and connect $v$'s other two incident edges (which are distinct from each other and $e$) to form a single edge. Do the same for $w$. Figure 13: C4: Trajectories in the old and new graphs

The effect on the trajectories is shown in Figure 13. Note that the new graph is still 3-regular. We then argue as in Proof I that this operation splits the trajectory into two. So if the new graph is connected, this contradicts the hypothesis for $N-1$. Alternately, the new graph might consist of two components. Since it is 3-regular, each component has an even number of vertices. The total number of vertices is $2(N-1)$, which is 2 modulo 4, and so one of the components has a number of vertices which is a multiple of four, and a complete trajectory of this component, which also contradicts the induction hypothesis. Now suppose $N$ is odd, but the original oriented graph has exactly two trajectories. If there is a self-loop at some vertex $v$, then one of the trajectories involves only this self-loop. So remove this vertex, and consider the other vertex $w$ connected to $v$. Remove $w$ and join up its other two incident edges. The resulting graph corresponds to $N$ even, and has a complete trajectory, which is a contradiction.

Otherwise, there are no self-loops, but the graph is connected hence there must be one edge $e$ connecting vertices $v\ne w$ which has one trajectory in one direction, and the other trajectory in the other direction. Collapse this edge as in Figure 13, and again by the same argument as in Proof I, this merges the two trajectories, giving a complete trajectory for $N$ even, and a contradiction. $\square$