Largest graphs of girth at least 6

Question

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Update Nov 2015: For $51\le n\le 63$, all extremal graphs are bipartite except for $n=63$, where there are 3 bipartite extremal graphs and 4 non-bipartite extremal graphs (187 edges).

Answer 1

I am collecting some varied thoughts on the problem, in the hopes that it will inspire someone to finish the problem.

I suggested earlier that the graphs in $G_{n+1}$ could be built incrementally from graphs in $G_n$ by adding one vertex and thee appropriate number of edges. Brendan McKay assured me that this would not be possible for $n=44$ as "that graph had too many edges", to reinterpret his assurance. Even so, it might be useful to consider the subgraph relation on the union of the $G$'s and see if most of them can be built up incrementally, and to characterize the ones that aren't and are primitive in some sense.

It is clear that removing one vertex and its adjacent edges from an example in $G_{n+1}$ does not reduce the minimum girth, and that adding a vertex and single edge also does not reduce the girth, so that the function $e(n)$ is increasing in $n$ for $n>4$ and further increases by no more than the minimum degree taken over all the vertices of all the members of $G_{n+1}$.

There likely is a nice argument bounding the maximum degree among all members of $G_n$, but I don't see it. I can build a graph on an even number of vertices by gluing a number of length 3 paths together at their endpoints, but this gives an average degree of slightly less than 3 and a max degree of slightly less than n/2, so this is useful more for providing a lower bound for $e(n)$ than anything else.

Another construction giving a bipartite involves associating each point in a set L with a small subset (of size 3, say) of another set R in a way that no two subsets of R so chosen intersect in more than one point. The result has girth 6 or more and if both L and R have 7 points, a maximal example resembles a BIBD (or for me, an adjacency matrix of 0's and 1's with order 7 and absolute determinant value of 24) which I believe corresponds to Brendan's example for $n=14$. Perhaps BIBD's contribute more examples? They might be a significant subclass of the primitive graphs in the subgraph relation I mention above.

Also, why so many graphs for $n=45$? It makes me think of the combinatorial explosion of equivalence classes of Hadamard matrices, although it might be better to think of equivalence classes (under row and column permutations and perhaps under switching as well) of 0-1 matrices having maximal determinant values. Are there combinatorial analogues in the literature which might suggest such a brief plethora of examples?

Gerhard "Binary Matrices On My Mind" Paseman, 2012.06.28

Answer 2

It seems I have an answer to my own question, though credit belongs to my computer. Namely, $e_6(47)=118$ and the unique graph in that class is not bipartite. I wish I could offer some insight, but at the moment it is a mystery.

Very sorry, that was incorrect. I must have been looking at the wrong file. Up to $n=48$ vertices inclusive there is always at least one bipartite graph with $e_6(n)$ edges. So the problem remains open.