# How to count the closed left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$.

Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed path on $\Gamma$ such that, at each vertex, the path turns left in the orientation $\mathcal O$.

I want to calculate the number of left-hand turn paths of $\Gamma$ without drawing them. I found the following:
When you look at a vertex with the given (planar) edge-coloring i.e. orientation, there are two situations that can happen:

$\hskip1.7in$

Lets start with the left figure: When you come from the color-1 edge and you want to go left you end at the color-2 edge. Coming from 2 you end at 3, and from 3 to 1.

Fine in the right figure the orientation is inverted, so left is right here. So if we come from the color-1 edge we end at (surprise,surprise) the color-2 edge.
And so forth…

So after 1 follows 2 after that 3 and then 1 again, no matter if we reach a left- or right-oriented vertex.

Now, the adajency matrix of the graph $A_\Gamma$ splits up into three different color submatrices, with $A_\Gamma=A_1+A_2+A_3$. $A_k$ are permutation matrices with $A_k^2=1$.

So the number of left-hand turn path can be calculated when you look at the number of unique solutions of
$$(A_3A_2A_1) v_kv_{k+1} =v_kv_{k+1},$$
where $v_k$ can be any vertex as starting point and $v_kv_{k+1}$ indicates the starting edge.
Vertices are allowed multiple times. Edges may be traversed in the opposite directions as well…

Is this correct and if so are there other ways to do it?

#### Solutions Collecting From Web of "How to count the closed left-hand turn paths of planar bicubic graphs?"

Solving your equation $(A_1A_2A_3)^t v_kv_{k+1} =v_kv_{k+1}$ will count each cycle multiple times, even if you only consider the minimal positive $t$ that works, since each cycle will be counted once for every $3\rightarrow 1$ transition it contains (and it must contain an even number of them, since the graph is bipartite).

Since the $A_k$ are permutation matrices, the matrix $M=A_1A_2A_3$ is itself a permutation matrix, and what you want is exactly the number of cycles in this permutation $\pi_M$.
Since the graph is bipartite, every cycle of $\pi_M$ will be of even length, corresponding to a unique “left hand turn” cycle in $\Gamma$ that is three times longer.
Clearly each cycle in $\pi_M$ corresponds to a unique “left hand turn” cycle in the graph, and vice versa.

You might be worried that $\pi_M$ could have cycles where we return to a vertex but we are traveling in the opposite direction and so it is not really a cycle. But this cannot happen, since every vertex in a cycle of $\pi_M$ is always being traversed in the $3\rightarrow 1$ direction.
If we return to a vertex, we are passing through it in exactly the same way.