Question regarding circulant graphs

Question

When I was studying about circulant graphs I came up with the following definition.

A circulant graph with $N$ vertices and jumps $\{j_1, j_2, …, j_m\}$ is an undirected graph in which each vertex $n, 0 \leq n \leq N-1$, is adjacent to all the vertices $n \pm j$, with $1 \leq i \leq m-1$. We denote this graph as $C_N(j_1,j_2,…,j_m)$.

Next it was mentioned that "it is clear that the circulant graph $C_N(j_1,j_2,…,j_m)$ is connected iff $gcd(j_1,j_2,…,j_m,N)=1$". But how can we prove this? How is it clear that the graph is connected iff $gcd(j_1,j_2,…,j_m,N)=1$?

Can someone please help me to understand how to see that the graph is connected iff $gcd(j_1,j_2,…,j_m,N)=1$.

Thanks a lot in advance.

Answer 1

In one direction, suppose that $\gcd(j_1, j_2, \dots, j_m,N) = d > 1$. Then if we label the vertices $0, 1, 2, \dots, N-1$ going around the circle, an edge of the $i^{\text{th}}$ type whose connects two vertices either of the form $\{k, k+j_i\}$ or $\{k, k+j_i - N\}$. In either case, $$k \equiv k + j_i \equiv k + j_i - N \pmod d$$ so the labels of the two vertices are congruent modulo $d$. By induction, any walk we take starting from a vertex $k$ will lead only to vertices with labels congruent to $k$ modulo $d$, so we will not be able to get to, for example, vertex $k+1$. Therefore $C_N(j_1, j_2,\dots,j_m)$ is not connected.

In the other direction, we can use Bézout's identity to say that if $\gcd(j_1, j_2,\dots,j_m,N) = 1$, then there exist integers $x_0, x_1, \dots, x_m$ such that $$ j_1 \cdot x_1 + j_2 \cdot x_2 + \dots + j_m \cdot x_m + N \cdot x_0 = 1. $$ Starting at a vertex $k$, take the following walk:

• If $x_1 > 0$, take $x_1$ steps that go $n \to n+j_1$ or (when $n+j_1\ge N$) go $n \to n+j_1-N$.
• If $x_1 < 0$, instead take $|x_1|$ steps going the other way: $n \to n - j_1$ or (when $n-j_1 < 0$ $n \to n + N -j_1$).
• Repeat the same thing for $x_2, \dots, x_m$.

Since $j_1 \cdot x_1 + \dots + j_m \cdot x_m \equiv 1 \pmod N$, we end up at a vertex with label $k'\equiv k+1 \pmod N$, but since the vertices are labeled $\{0,1,\dots,N-1\}$, the only such label is $k+1$ (or when $k=N-1$, the only such label is $0$).

This shows that for any vertex $k$, there is a walk connecting $k$ to $k+1\bmod N$. Repeating this procedure any number of times, we can get from $k$ to any other vertex, so the circulant graph is connected.