I'm looking for simple 6regular bipartite graphs with no 8cycles, as small as possible. It doesn't matter if there are 4cycles or 6cycles, provided there are no 8cycles. 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.

$\begingroup$ Have you tried things like Cayley graphs or poset Hasse diagrams for wellstructured posets? $\endgroup$ – Patricia Hersh Jul 29 '12 at 14:40

$\begingroup$ 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 $\endgroup$ – Gerhard Paseman Jul 29 '12 at 16:03

1$\begingroup$ 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 $\endgroup$ – Gerry Myerson Jul 29 '12 at 23:07

1$\begingroup$ 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. $\endgroup$ – Douglas Zare Jul 30 '12 at 3:07

1$\begingroup$ 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." $\endgroup$ – joro Aug 2 '12 at 7:11
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 7812vertex 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.

$\begingroup$ 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 4cycles and 6cycles are allowed. $\endgroup$ – Brendan McKay Mar 16 '13 at 5:59

$\begingroup$ 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 ngons. 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. $\endgroup$ – Andrew Woldar Mar 16 '13 at 15:56