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.



Cycles of length 1(mod 3) in regular graphs
According to [this paper](http://dx.doi.org/10.1016/S0166-218X%2801%2900190-1), 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](http://en.wikipedia.org/wiki/Biconnected_component) 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.


