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.
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.