Does every 4regular 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 3regular graphs but 4regularity is enough for what I'm investigating.
Does every 4regular 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 3regular graphs but 4regularity is enough for what I'm investigating. 


According to this paper, N. Dean et al. have shown that if a simple graph G
then G contains a cycle of length 1 mod 3. Now consider any 4regular 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 2connected. 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 2factorisation, 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' = K − x; 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. 


This paper shows that such graphs may lack a cycle of a particular length: Some 4valent, 3connected, planar, almost pancyclic graphs S. A. Choudum Discrete Mathematics, Volume 18, Issue 2, 1977, Pages 125129 Abstract: For each positive integer k (≠ 5,6), a 4valent, 3connected, planar graph, having cycles of all (possible) lengths except k is constructed. 

