2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Marko Riedel Sep 1 '17 at 21:45
3
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.