[Math] How to tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all

discrete mathematicsgraph theorygraph-isomorphismtrees

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

Best Answer

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;
Related Question