Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.