MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
For those of us less adept but still wanting to play, can you comment briefly on how e_6(n) can be nicely estimated? Gerhard "Hopes For Easy And Good" Paseman, 2012.06.15 – Gerhard Paseman Jun 16 '12 at 6:19
This is a rough/nonprecise estimate of $e_6(n).$ The odd graph $O_n$ ($n >3$) has $O(n)$ vertices and $O(n^2)$ edges and girth precisely 6. – Jernej Jun 16 '12 at 9:28
@Brendan is there a graph in $G_6(n)$ for some $n$ with girth greater than 6? – Jernej Jun 16 '12 at 9:31
@Jernej: The only example up to 44 vertices is the 7-gon. I doubt there are any others, but I don't know a proof. – Brendan McKay Jun 16 '12 at 15:17
@Jernej: The odd graph $O_n$ that I know has exponentially many vertices. The one on 35 vertices has 70 edges, compared with $e_6(35)=77$. – Brendan McKay Jun 16 '12 at 15:22

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.

share|cite|improve this answer
Are you confident enough of your results to list some of them here? In particular I am thinking of a table listing e_6(n) and (the number of isomorphism types of) G_6(n)? The more courageous of us might attempt to verify/alternatively derive your computations. Gerhard "Still Checking My Courage Meter" Paseman, 2012.06.25 – Gerhard Paseman Jun 25 '12 at 7:32
@Gerhard: I added a table, but the program and the output need a lot of checking yet before I'd swear to it being correct. – Brendan McKay Jun 25 '12 at 14:40
Thank you for the table. Do the results follow your intuition? I'm surprised at the number of occurrences of "g=1]" in the table. Gerhard "Ask Me About System Design" Paseman, 2012.06.25 – Gerhard Paseman Jun 25 '12 at 17:24

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

share|cite|improve this answer

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.