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' = 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.

1

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.