[seqfan] confusion over k-connected graphs

[Brendan McKay]

I had cause to think about the number of 4-connected graphs and found 
trouble on OEIS.

Specifically, there are two sequences:

A052445        Number of simple 4-connected unlabeled n-node graphs.
a(1)=0, a(2)=0, a(3)=0, a(4)=1, a(5)=0, a(6)=3, a(7)=21

A086216        Number of 4-connected graphs on n nodes.
a(5)=1, a(6)=4, a(7)=25, a(8)=384, a(9)=14480, a(10)=1211735

Except for the "unlabeled", which actually applies to both, the 
descriptions are the same.  Both refer to Weisstein at 
http://mathworld.wolfram.com/k-ConnectedGraph.html .  But they disagree.

Examination of the numbers suggests that A052445 is intended to be 
"Number of simple unlabeled n-node graphs with connectivity exactly 4", 
while A086216 is correctly described (4-connected means connectivity 
greater than or equal to 4).

However, A052445 has an error in that it should have a(4)=0, a(5)=1.  I 
am not aware of any current graph theorist working on connectivity 
issues who considers the complete graph on n nodes as having 
connectivity other than n-1 (except perhaps for K_1, which doesn't 
matter).  The trauma (starting with thousands of wrong theorems) of 
having a graph with connectivity greater than its minimum degree 
effectively excludes the value n.  A086216 does this correctly.

Looking at the Weisstein page, we read (preposterously) "Note that there 
is a unique n-connected n-node graph, namely, the complete graph K_n."  
However, the table of values given does not agree with that, nor does it 
agree with the correct definition.  To make it match Weisstein's 
definition, insert a "0" after each leading "1" in the table.  To make 
it match the correct definition, add an extra leading  "0" to each row.

I doubt that connectivity 4 is the only connectivity with this problem.  
I hope someone with more time than me can sort this out. To assist, here 
are counts by connectivity.

n=2
>C        1 graphs with connectivity 0
>C        1 graphs with connectivity 1

n=3
>C        2 graphs with connectivity 0
>C        1 graphs with connectivity 1
>C        1 graphs with connectivity 2

n=4
>C        5 graphs with connectivity 0
>C        3 graphs with connectivity 1
>C        2 graphs with connectivity 2
>C        1 graphs with connectivity 3

n=5
>C       13 graphs with connectivity 0
>C       11 graphs with connectivity 1
>C        7 graphs with connectivity 2
>C        2 graphs with connectivity 3
>C        1 graphs with connectivity 4

n=6
>C       44 graphs with connectivity 0
>C       56 graphs with connectivity 1
>C       39 graphs with connectivity 2
>C       13 graphs with connectivity 3
>C        3 graphs with connectivity 4
>C        1 graphs with connectivity 5

n=7
>C      191 graphs with connectivity 0
>C      385 graphs with connectivity 1
>C      332 graphs with connectivity 2
>C      111 graphs with connectivity 3
>C       21 graphs with connectivity 4
>C        3 graphs with connectivity 5
>C        1 graphs with connectivity 6

n=8
>C     1229 graphs with connectivity 0
>C     3994 graphs with connectivity 1
>C     4735 graphs with connectivity 2
>C     2004 graphs with connectivity 3
>C      345 graphs with connectivity 4
>C       34 graphs with connectivity 5
>C        4 graphs with connectivity 6
>C        1 graphs with connectivity 7

n=9
>C    13588 graphs with connectivity 0
>C    67014 graphs with connectivity 1
>C   113176 graphs with connectivity 2
>C    66410 graphs with connectivity 3
>C    13429 graphs with connectivity 4
>C      992 graphs with connectivity 5
>C       54 graphs with connectivity 6
>C        4 graphs with connectivity 7
>C        1 graphs with connectivity 8

n=10
>C   288597 graphs with connectivity 0
>C  1973029 graphs with connectivity 1
>C  4629463 graphs with connectivity 2
>C  3902344 graphs with connectivity 3
>C  1109105 graphs with connectivity 4
>C    99419 graphs with connectivity 5
>C     3124 graphs with connectivity 6
>C       81 graphs with connectivity 7
>C        5 graphs with connectivity 8
>C        1 graphs with connectivity 9

n=11
>C  12297299 graphs with connectivity 0
>C 105731474 graphs with connectivity 1
>C 327695586 graphs with connectivity 2
>C 388624106 graphs with connectivity 3
>C 162318088 graphs with connectivity 4
>C  21500415 graphs with connectivity 5
>C    820956 graphs with connectivity 6
>C      9813 graphs with connectivity 7
>C       121 graphs with connectivity 8
>C         5 graphs with connectivity 9
>C         1 graphs with connectivity 10

Cheers, Brendan.