Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
You can use geng
which is packaged with nauty.
geng 7 6:6 -c -u
Trees with 6 edges have 7 vertices, and any connected 7-vertex graph with 6 edges must be a tree. So we call geng to generate the 7-vertex connected (-c
) graphs with 6 edges. The -u
means to count them.
>A geng -cd1D6 n=7 e=6
>Z 11 graphs generated in 0.00 sec
If you want the graphs themselves, we can redirect the output to a file
geng 7 6:6 -c > temp.txt
then use showg
to print the adjacency lists:
showg temp.txt
Here's the output:
Graph 1, order 7.
0 : 6;
1 : 6;
2 : 6;
3 : 6;
4 : 6;
5 : 6;
6 : 0 1 2 3 4 5;
Graph 2, order 7.
0 : 5 6;
1 : 6;
2 : 6;
3 : 6;
4 : 6;
5 : 0;
6 : 0 1 2 3 4;
Graph 3, order 7.
0 : 5 6;
1 : 5;
2 : 6;
3 : 6;
4 : 6;
5 : 0 1;
6 : 0 2 3 4;
Graph 4, order 7.
0 : 5;
1 : 5;
2 : 6;
3 : 6;
4 : 6;
5 : 0 1 6;
6 : 2 3 4 5;
Graph 5, order 7.
0 : 5 6;
1 : 5;
2 : 5;
3 : 6;
4 : 6;
5 : 0 1 2;
6 : 0 3 4;
Graph 6, order 7.
0 : 4 6;
1 : 5 6;
2 : 6;
3 : 6;
4 : 0;
5 : 1;
6 : 0 1 2 3;
Graph 7, order 7.
0 : 4 5;
1 : 5 6;
2 : 6;
3 : 6;
4 : 0;
5 : 0 1;
6 : 1 2 3;
Graph 8, order 7.
0 : 4 6;
1 : 5 6;
2 : 5;
3 : 6;
4 : 0;
5 : 1 2;
6 : 0 1 3;
Graph 9, order 7.
0 : 4 6;
1 : 5;
2 : 5;
3 : 6;
4 : 0;
5 : 1 2 6;
6 : 0 3 5;
Graph 10, order 7.
0 : 3 6;
1 : 4 6;
2 : 5 6;
3 : 0;
4 : 1;
5 : 2;
6 : 0 1 2;
Graph 11, order 7.
0 : 3 5;
1 : 4 6;
2 : 5 6;
3 : 0;
4 : 1;
5 : 0 2;
6 : 1 2;
1,1,1,2,3,6
. $\endgroup$ – hmakholm left over Monica Apr 5 '13 at 11:10