1
$\begingroup$

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.

$\endgroup$
  • 4
    $\begingroup$ By cheating: Find the number of trees with up to 5 edges by drawing them all, and stick the numbers you find into OEIS. This finds 116 sequences, the first of which is described as being what you want. $\endgroup$ – hmakholm left over Monica Apr 5 '13 at 1:35
  • $\begingroup$ @Henning: That link returns $381$ sequences for me, of which the second is the right one. $\endgroup$ – Brian M. Scott Apr 5 '13 at 4:20
  • $\begingroup$ @BrianM.Scott: Hm, I must have copied the wrong link. The one that finds 116 sequences is a search for 1,1,1,2,3,6. $\endgroup$ – hmakholm left over Monica Apr 5 '13 at 11:10
1
$\begingroup$

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;
| cite | improve this answer | |
$\endgroup$

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.