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

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. 

