A007112 -id:A007112 - cp's OEIS frontend

A006290 Number of 3-connected graphs with n nodes.

1, 3, 17, 136, 2388, 80890, 5114079, 573273505, 113095167034, 39582550575765, 24908445793058442, 28560405143495819079, 60364410130177223014724, 237403933018799958309530349, 1750323137355778190158082029500, 24333358813699371350715221107464003, 640811613278752754485012443963579501421

Offset: 4

N. J. A. Sloane

Robinson and Walsh list first 25 terms.

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 4..25
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
R. W. Robinson, Tables
R. W. Robinson, Tables [Local copy, with permission]
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
T. R. S. Walsh, Counting unlabeled three-connected and homeomorphically irreducible two-connected graphs, J. Combin. Theory Ser. B 32 (1982), no. 1, 12-32.
Eric Weisstein's World of Mathematics, k-Connected Graph
David Kofoed Wind, Connected Graphs with Fewest Spanning Trees, Bachelor Thesis, Spring 2011.

Row sums of A339072.

Cf. A000088, A001349, A002218, A006289, A007112, A338511.

More terms from Ronald C. Read.

A123545 Triangle read by rows: T(n,k) = number of unlabeled connected graphs on n nodes with degree >= 3 at each node (n >= 1, 0 <= k <= n(n-1)/2).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 5, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 18, 30, 34, 29, 17, 9, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 35, 136, 309, 465, 505, 438, 310, 188, 103, 52, 23

Offset: 1

N. J. A. Sloane, Nov 13 2006

			Triangle begins:
n = 1
k = 0 : 0
************************ TOTAL (n = 1) = 0
n = 2
k = 0 : 0
k = 1 : 0
************************ TOTAL (n = 2) = 0
n = 3
k = 0 : 0
k = 1 : 0
k = 2 : 0
k = 3 : 0
************************ TOTAL (n = 3) = 0
n = 4
k = 0 : 0
k = 1 : 0
k = 2 : 0
k = 3 : 0
k = 4 : 0
k = 5 : 0
k = 6 : 1
************************ TOTAL (n = 4) = 1
n = 5
k = 0 : 0
k = 1 : 0
k = 2 : 0
k = 3 : 0
k = 4 : 0
k = 5 : 0
k = 6 : 0
k = 7 : 0
k = 8 : 1
k = 9 : 1
k = 10 : 1
************************ TOTAL (n = 5) = 3
From _Hugo Pfoertner_, Nov 22 2020: (Start)
Transposed table:
                            Nodes                             Sums
       4  5  6   7    8      9      10      11     12    13 |A338604
  Edges-----------------------------------------------------|-------
   6 | 1  .  .   .    .      .       .       .      .     . |      1
   7 | .  .  .   .    .      .       .       .      .     . |      0
   8 | .  1  .   .    .      .       .       .      .     . |      1
   9 | .  1  2   .    .      .       .       .      .     . |      3
  10 | .  1  4   .    .      .       .       .      .     . |      5
  11 | .  .  5   4    .      .       .       .      .     . |      9
  12 | .  .  4  18    5      .       .       .      .     . |     27
  13 | .  .  2  30   35      .       .       .      .     . |     67
  14 | .  .  1  34  136     27       .       .      .     . |    198
  15 | .  .  1  29  309    288      19       .      .     . |    646
  16 | .  .  .  17  465   1377     357       .      .     . |   2216
  17 | .  .  .   9  505   3978    3478     208      .     . |   8178
  18 | .  .  .   5  438   7956   18653    4958     85     . |  32085
  19 | .  .  .   2  310  11904   65011   50575   4291     . | 132093
  20 | .  .  .   1  188  14134  163812  302854  85421  1958 | 568368
(End)

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.

R. W. Robinson, Rows 1 through 14, flattened

Row sums give A007112. Cf. A123546, A338604.

A338593 Number of unlabeled connected nonplanar graphs with n edges with degree >= 3 at each node.

Original entry on oeis.org

1, 2, 3, 10, 30, 100, 371, 1419, 5764, 24482, 107583, 487647, 2271488, 10847623

Offset: 9

Hugo Pfoertner, Nov 21 2020

First differs from A338583 for n = 13. All unlabeled nonplanar graphs with n <= 12 edges and degree >= 3 at each node are 3-connected. For this reason the illustrations of the graphs are identical up to n = 12. The first differences for n = 13 and n = 14 are shown in the illustrations of A338584.

Hugo Pfoertner, Illustrations of terms a(9) - a(12), from A338583.
Hugo Pfoertner, Illustration of terms a(13) and a(14), showing graphs counted in this sequence, but not in A338583 (illustrations from A338584).
Hugo Pfoertner, Unlabeled nonplanar graphs with vertex degree >=3 for n<=19 edges, list in PARI-readable format.

Cf. A007112, A002840, A123545, A338511, A338583, A338584, A338594, A338604.

\\ It is assumed that the a338593.gp file (from the linked zip archive) has been read before, i.e., \r [path]a338593.gp
for(k=9,#EdgeDataNonplanarDegge3,print1(#EdgeDataNonplanarDegge3[k],", "));
\\ printing of the edge lists of the graphs for n <= 11
print(EdgeDataNonplanarDegge3[9..11])

a(n) = A338604(n) - A338594(n).

A338594 Number of unlabeled connected planar graphs with n edges with degree >= 3 at each node.

Original entry on oeis.org

1, 0, 1, 2, 3, 6, 17, 37, 98, 275, 797, 2414, 7613, 24510, 80721, 270018, 915034

Offset: 6

Hugo Pfoertner, Nov 21 2020

			a(6) = 1: the 3-connected edge graph of the tetrahedron;
a(7) = 0: no connected planar graph with degree >=3 at each node exists;
a(8) = 1: the 3-connected 5-wheel graph, edge graph of 4-sided pyramid;
a(9)-a(11): see linked illustrations.

Hugo Pfoertner, Illustrations of terms a(9) - a(11).

Cf. A007112, A002840, A123545, A338511, A338583, A338584, A338593, A338604.

a(n) = A338604(n) - A338593(n).

A338604 Number of unlabeled connected graphs with n edges with degree >= 3 at each node.

Original entry on oeis.org

1, 0, 1, 3, 5, 9, 27, 67, 198, 646, 2216, 8178, 32095, 132093, 568368, 2541506, 11762657, 56183633, 276288402, 1396172601, 7238931364

Offset: 6

Hugo Pfoertner, Nov 21 2020

			a(10)=5:
There are 5 graphs with 10 edges and degree >=3 at all nodes (see table in A123545):
The complete graph on 5 nodes, given by the edge list
[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]],
and 4 graphs on 6 nodes:
  [[1,3],[1,5],[1,6],[2,4],[2,5],[2,6],[3,5],[3,6],[4,5],[4,6]],
  [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6],[4,6]],
  [[1,3],[1,4],[1,6],[2,4],[2,5],[2,6],[3,5],[3,6],[4,6],[5,6]],
  [[1,3],[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,5],[3,6],[4,6]].
The first one has degree 3 or 4 at all nodes, but becomes disconnected by removing nodes 5 and 6 and their incident edges. It is therefore not 3-connected.
    .--5--.
   /  / \  \
  1--3   4--2
   \  \ /  /
    .--6--.
.
The complete graph on 5 nodes and the last 3 graphs with 6 nodes are all 3-connected. Thus A338511(10)=4, and by inclusion of the graph shown above a(10)=5.

Cf. A007112, A123545, A338511, A338593, A338594.

A338584 Number of unlabeled nonplanar connected graphs with n edges with minimum degree 3 at each node that are not 3-connected.

Original entry on oeis.org

1, 6, 28, 128, 558, 2421, 10675, 47810, 217572, 1006211

Offset: 13

Hugo Pfoertner, Nov 21 2020

Hugo Pfoertner, Illustration of terms a(13) and a(14).

Cf. A006290, A007112, A123545, A338583, A338593, A338594, A338604.

a(n) = A338593(n) - A338583(n).

A007111 Number of unlabeled graphs with n nodes and degree >= 3.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 19, 150, 2590, 84245, 5203135, 577076735, 113373008891, 39618075369549, 24916469695937480, 28563628406766988588, 60366734880395211775791, 237406976195471782149927759, 1750330442243458287054664072364

Offset: 0

N. J. A. Sloane

nonn

R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson, Table of n, a(n) for n = 0..28

Euler transform of A007112.

A123546 Triangle read by rows: T(n,k) = number of unlabeled graphs on n nodes with degree >= 3 at each node (n >= 1, 0 <= k <= n(n-1)/2).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 5, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 18, 30, 34, 29, 17, 9, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 35, 136, 309, 465, 505, 438, 310, 188, 103, 52, 23

Offset: 0

N. J. A. Sloane, Nov 14 2006

			Triangle begins:
n = 0
k = 0 : 0
************************* total (n = 0) = 0
n = 1
k = 0 : 0
************************* total (n = 1) = 0
n = 2
k = 0 : 0
k = 1 : 0
************************* total (n = 2) = 0
n = 3
k = 0 : 0
k = 1 : 0
k = 2 : 0
k = 3 : 0
************************* total (n = 3) = 0
n = 4
k = 0 : 0
k = 1 : 0
k = 2 : 0
k = 3 : 0
k = 4 : 0
k = 5 : 0
k = 6 : 1
************************* total (n = 4) = 1
n = 5
k = 0 : 0
k = 1 : 0
k = 2 : 0
k = 3 : 0
k = 4 : 0
k = 5 : 0
k = 6 : 0
k = 7 : 0
k = 8 : 1
k = 9 : 1
k = 10 : 1
************************* total (n = 5) = 3

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.

R. W. Robinson, Rows 0 through 14, flattened

Row sums give A007111. Cf. A007112, A123545.

A380127 Number of connected unlabeled graphs with n nodes and minimum vertex degree >= 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 29, 424, 15471, 1249972, 187095836, 48211095992, 21124789189703, 15899588477573380, 20900616544566305160, 48843531771541430977365, 206305644374013971584957120, 1597725697294349735784472597650, 22957145992821363656862872542094876, 617791721556546579087246090934406095676

Offset: 1

Eric W. Weisstein, Mar 11 2025

nonn

First differs from A324227(n) at n = 10.

Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Minimum Vertex Degree.

Cf. A007112 (connected graphs with degree >= 3).

Cf. A324227 (4-edge-connected graphs).

geng $n -d4 -c -u # see nauty documentation, Georg Grasegger, Mar 20 2025

a(11)-a(12) added by Georg Grasegger, Mar 20 2025

a(13) onwards from Andrew Howroyd, May 25 2025

cp's OEIS Frontend

A006290 Number of 3-connected graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A123545 Triangle read by rows: T(n,k) = number of unlabeled connected graphs on n nodes with degree >= 3 at each node (n >= 1, 0 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

A338593 Number of unlabeled connected nonplanar graphs with n edges with degree >= 3 at each node.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A338594 Number of unlabeled connected planar graphs with n edges with degree >= 3 at each node.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A338604 Number of unlabeled connected graphs with n edges with degree >= 3 at each node.

Views

Author

Keywords

Examples

Crossrefs

A338584 Number of unlabeled nonplanar connected graphs with n edges with minimum degree 3 at each node that are not 3-connected.

Views

Author

Keywords

Links

Crossrefs

Formula

A007111 Number of unlabeled graphs with n nodes and degree >= 3.

Views

Author

Keywords

References

Links

Crossrefs

A123546 Triangle read by rows: T(n,k) = number of unlabeled graphs on n nodes with degree >= 3 at each node (n >= 1, 0 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

A380127 Number of connected unlabeled graphs with n nodes and minimum vertex degree >= 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Extensions