# Cycles of length 1(mod 3) in regular graphs

Does every 4-regular graph contain a cycle of length (number of edges in the cycle) $1 (\mod3)$? Are there only finitely many exceptions?

I suspect such cycles exist for most 3-regular graphs but 4-regularity is enough for what I'm investigating.

-
I guess you want the graph to be simple. Take two vertices connected by 4 edges. –  Tony Huynh Jul 22 '10 at 12:58
Yes thanks for the correction, simple and connected. –  Gjergji Zaimi Jul 22 '10 at 13:30
Do you mean simple cycle? –  Grigory Yaroslavtsev Jul 22 '10 at 13:39
Yes, the cycles are simple, too. –  Gjergji Zaimi Jul 22 '10 at 13:46

According to this paper, N. Dean et al. have shown that if a simple graph G

• is 2-connected,
• has minimum degree at least 3, and
• is not isomorphic to the Petersen graph,

then G contains a cycle of length 1 mod 3.

Now consider any 4-regular graph H. If I'm not mistaken, it's fairly easy to show that H contains a subgraph G such that two nodes of G have degree 3, all other nodes of G have degree 4, and G is 2-connected. Clearly G can't be the Petersen graph, and thus the above theorem implies that G (and therefore also H) contains a cycle of length 1 mod 3.

Edit: Here is how would construct G given H. Recall that H has a 2-factorisation, i.e., it consists of cycles such that each node of H is "covered" by exactly 2 cycles. If there are no articulation points in H, the claim is clear. Otherwise consider the block tree of H and pick a biconnected component K that contains only one articulation point; let x be the articulation point. Consider the subgraph K' = Kx; this graph consists of one path P and a set of cycles, and each node of K' is covered by either P and one cycle or exactly 2 cycles. It may be the case that K' contains articulation points. However, each articulation point is an endpoint of a bridge, and each bridge is an edge of P. Remove all bridges and let G be one of the connected components in the resulting bridgeless graph.

-
Finding your subgraph G is easy, as you say: if H is not biconnected, find a block with only one articulation point adjacent to it, and let G be the remaining vertices in that block. If H is biconnected, you can just use H in place of G, since you don't actually require the existence of the two degree-three vertices, but if you really want them you can remove the last ear in an ear decomposition. –  David Eppstein Jul 27 '10 at 3:14
@David: I think you need to be a bit more careful in the construction of G; removing the articulation point may create new articulation points. I added a sketch of the construction of G above; essentially just do what you said, remove all bridges, and pick one of the components. –  Jukka Suomela Jul 27 '10 at 14:44

This paper shows that such graphs may lack a cycle of a particular length:

Some 4-valent, 3-connected, planar, almost pancyclic graphs

S. A. Choudum

Discrete Mathematics, Volume 18, Issue 2, 1977, Pages 125-129

Abstract:

For each positive integer k (≠ 5,6), a 4-valent, 3-connected, planar graph, having cycles of all (possible) lengths except k is constructed.

-
This sounds interesting, however as I understand it these graphs do not provide a counterexample, that is they have some cycle of length 3m+1 for some m. –  Gjergji Zaimi Jul 22 '10 at 13:45
Gjergij: Yes, that is correct. While not noted above there is quite a large literature about the existence (or lack of existence) of cycles in graphs, in particular mod m. Perhaps things are easier in the case that interests you for planar graphs. –  Joseph Malkevitch Jul 22 '10 at 21:37