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

Question

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.

Any insights would be helpful.

Answer 1

The phrase "contains all even cycles" means that it contains every even cycle (obviously of length less than or equal to the circumference of the graph). On the other hand, "contains only even cycles" or "all cycles of the graph are even" would mean that it contains no odd cycles; that every cycle, if any, must be even.

In particular, look at the corollary to Theorem 1 in the paper you refer to: "Connected bipartite circulants contain all even and only even cycles" (emphasis mine). And in the next section, they discuss circulants containing cycles of all lengths.