# Prove that the connected circulant regular graphs of degree at least three contain all even cycles.

This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13.

Now clearly when looking at this graph which is an example of circulant graph has a cycle of 13 length, which is odd, so we can disprove the above given statement.

There was also a proof I came across, which I could not gather much from, This is the link of the proof. In this they prove that it is true, for odd number of vertices in lemma 2. I am very confused now, am I missing something, is there any other interpretation for this question, my interpretation is that if there is a cycle in the circulant graph, it must be of even length.

• So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way? – jackson jose Mar 31 at 7:11
• Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles. – Rosie F Mar 31 at 8:12
• @RosieF the question is answered, that "contains all even cycles" has been explained below. – jackson jose Mar 31 at 17:36

• @jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, \ldots, 1 + (n - 1)a_2)$ (all $\mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $\gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(\mathbb Z/n\mathbb Z, +)$.] – M. Vinay Apr 1 at 1:21