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.

  • $\begingroup$ 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? $\endgroup$ – jackson jose Mar 31 at 7:11
  • $\begingroup$ 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. $\endgroup$ – Rosie F Mar 31 at 8:12
  • $\begingroup$ @RosieF the question is answered, that "contains all even cycles" has been explained below. $\endgroup$ – jackson jose Mar 31 at 17:36

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.

  • 1
    $\begingroup$ Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man. $\endgroup$ – jackson jose Mar 31 at 17:24
  • $\begingroup$ Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd? $\endgroup$ – jackson jose Mar 31 at 17:49
  • $\begingroup$ @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, +)$.] $\endgroup$ – M. Vinay Apr 1 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.