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

I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist since the girth can be arbitrarily high, but what smaller examples are there? There are certainly none on less than 46 vertices.

share|improve this question
Have you tried things like Cayley graphs or poset Hasse diagrams for well-structured posets? –  Patricia Hersh Jul 29 '12 at 14:40
More specifically, can you take a dimension 7 hypercube graph and remove some edges from it? Gerhard "Ask Me About System Design" Paseman, 2012.07.29 –  Gerhard Paseman Jul 29 '12 at 16:03
I'm sure Brendan knows about these resources, but there's a table of cages (regular graphs with high girth and few vertices) at mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html, and a paper on small regular bipartite graphs of girth 8 (with a bibliography listing many papers on related topics) at ma3.upc.edu/users/balbuena/PAPERS/consgirth8.pdf –  Gerry Myerson Jul 29 '12 at 23:07
Some quotients of tilings of the hyperbolic plane would work, but I don't know how large they would have to be. Cycles are either contractible or not. If the tiling is of decagons or hexagons, or alternating squares and decagons, then there are no contractible octogons. –  Douglas Zare Jul 30 '12 at 3:07
The program "girth" from the Stanford GraphBase found a large Ramanujan graph with p,q=5,37: "So the diameter is 10, and the girth is 10. The graph has 50616 vertices, each of degree 6, and it is bipartite." –  joro Aug 2 '12 at 7:11

1 Answer 1

Hi Brendan. I just happened upon this while searching for some related material, and I'm not sure if you're still interested in finding such a graph. I'm relatively certain I can construct one on 7812 vertices, following a few old ideas used by Lazebnik, Ustimenko and me in a series of papers on extremal graphs (in the sense of Turan). In fact the 7812-vertex graph I mention has girth 10, and its construction, as well as a proof that the girth is 10, should be easy to follow, and/or present. Let me know if you're still interested. I'll be looking back here every so often. Or just drop me an email. Regards.

share|improve this answer
Hi Andrew, There is a generalized hexagon on 7812 vertices mentioned in one of my comments above. But I'm still hopeful that a very much smaller graph (maybe even less than 100 vertices) is possible if 4-cycles and 6-cycles are allowed. –  Brendan McKay Mar 16 '13 at 5:59
Brendan, you're correct. This is the same graph, only my model is constructed in a way that can be readily explained to, for example, a grad student who is not well versed in rank 2 groups of Lie type or generalized n-gons. I'm going to think more on this problem. I find it very intriguibg. One can reduce 7812 for sure, for example by constructing the polarity graph of the generalized hexagon, which introduces smaller cycles, but this merely cuts the verex set in half ... not the kind of numbers you're looking for. Cheers. –  Andrew Woldar Mar 16 '13 at 15:56

Your Answer


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.