# Are there exactly 79 seven edges connected graphs?

I am trying to solve some basic graph theory problem and I want to know how many seven edges connected graphs are there. I think the exact number is 79 but I am not sure. For example for the case of six edges I have obtained 30 connected graphs. Thank you for your helps.

• This question was examined by using the Polya Enumeration Theorem at the following MSE link. The output from the Maple code that was posted there indeed yields $79.$ – Marko Riedel Sep 1 '17 at 21:45

This seems correct. The numbers are 4, 19, 33, and 23 graphs on 5, 6, 7, and 8 vertices respectively.

Not too hard to verify using SageMath via the following code:

graph_list=[]
# number of vertices is at least 5 and at most 8.
for n in range(5,9):
for g in graphs(n):
if g.is_connected() and g.num_edges()==7:
graph_list.append(g)
print len(graph_list)
# For some pictures! :-)
graphs_list.show_graphs(graph_list)


This is a brute force approach and takes a bit more than a minute to run at the sagecell server.

This agrees with the numbers tabulated here (which is linked to from here)

It lists the number of connected graphs ( and all graphs ) first by numbers of vertices and then by number of edges for a given number of vertices.

This is another useful link to resources.

• That table indicates there are $30$ connected graphs with $6$ edges, so the OP must have overlooked one. See also oeis.org/A002905 – Barry Cipra Sep 1 '17 at 15:34
• Yes it appears so. OEIS, a very useful link. – PM. Sep 1 '17 at 15:44
• Thank you so much – Djalal Ounadjela Sep 1 '17 at 16:05
• 30 sounds about right, via nauty's geng. Did OP miss $K_4$? :P – fidbc Sep 1 '17 at 17:42