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.
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 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' = 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 4-valent, 3-connected, planar, almost pancyclic graphs
S. A. Choudum
Discrete Mathematics, Volume 18, Issue 2, 1977, Pages 125-129
For each positive integer k (≠ 5,6), a 4-valent, 3-connected, planar graph, having cycles of all (possible) lengths except k is constructed.