A002905 -id:A002905 - cp's OEIS frontend

A066951 Number of nonisomorphic connected graphs that can be drawn in the plane using n unit-length edges.

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008

Offset: 1

Les Reid, May 25 2002

K_4 can't be so drawn even though it is planar. These graphs are a subset of those counted in A046091.

			Up to five edges, every planar graph can be drawn with edges of length 1, so up to this point the sequence agrees with A046091 (connected planar graphs with n edges) [except for the fact that that sequence begins with no edges]. For six edges, the only graphs that cannot be drawn with edges of length 1 are K_4 and K_{3,2}. According to A046091, there are 30 connected planar graphs with 6 edges, so the sixth term is 28.

M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 80.
R. C. Read, From Forests to Matches, Journal of Recreational Mathematics, Vol. 1:3 (Jul 1968), 60-172.

Jean-Paul Delahaye, Les graphes-allumettes, (in French), Pour la Science no. 445, November 2014.
Raffaele Salvia, A catalogue of matchstick graphs, arXiv:1303.5965 [math.CO], 2013-2015.
Alexis Vaisse, Matchstick graphs
Stefan Vogel and Mike Winkler, Matchstick Graphs Calculator (MGC), a web application for the construction and calculation of unit distance graphs and matchstick graphs.
Eric Weisstein's World of Mathematics, Matchstick Graph

Cf. A003055, A002905, A046091.

a(7) = 70. - Jonathan Vos Post, Jan 05 2007
Corrected, extended and reference added. a(7)=74 and a(8)=207 from Read's paper. - William Rex Marshall, Nov 16 2010
a(9) from Salvia's paper added by Brendan McKay, Apr 13 2013
a(9) corrected (from version 2 [May 22 2013] of Salvia's paper) by Gaetano Ricci, May 24 2013
a(10) from Vaisse's webpage added by Raffaele Salvia, Jan 31 2015

A076263 Triangle read by rows: T(n,k) = number of nonisomorphic connected graphs with n vertices and k edges (n >= 1, n-1 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 5, 4, 2, 1, 1, 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1, 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114, 56, 24, 11, 5, 2, 1, 1, 47, 240, 797, 2075, 4495

Offset: 1

Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

The index of the T(n,k) in the sequence is ((n-2)^3 - n + 6*k + 8)/6.

T(n,k)=1 for k = n*(n-1)/2-1 and k = n*(n-1)/2 (therefore {1,1} separates sublists for given numbers of vertices (n > 2)).

			There are 2 connected graphs with 4 vertices and 3 edges up to isomorphy (first graph: ((1,2),(2,3),(3,4)); second graph: ((1,2),(1,3),(1,4))). Index within the sequence is ((4-2)^3 - 4 + 6*3 + 8)/6 = 5.
Triangle begins:
   1;
   1;
   1,  1;
   2,  2,  1,   1;
   3,  5,  5,   4,   2,   1,   1;
   6, 13, 19,  22,  20,  14,   9,  5,  2,  1,  1;
  11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1;

T. D. Noe, Rows 1 to 16 of triangle, flattened (from Gordon Royle's website)
Keith M. Briggs, Combinatorial Graph Theory.
Sriram V. Pemmaraju, The Combinatorica Project
Marko R. Riedel, Number of distinct connected digraphs, Math StackExchange.
Marko Riedel, Maple code for sequences A008406 and A076263 including cycle indices.
Eric Weisstein's World of Mathematics, Connected Graph.

Row lengths (excluding first row): A000124. Number of connected graphs for given number of vertices: A001349. Number of connected graphs for given number of edges: A002905.
Number of entries in the n-th row is A152947. Row sums give A001349.
Starting each row from k=0 gives A054924, which is the main entry for this triangle.

NumberOfConnectedGraphs[vertices_, edges_] := Plus @@ ConnectedQ /@ ListGraphs[vertices, edges] /. {True->1, False ->0}
(* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Table[Plus @@ ConnectedQ /@ ListGraphs[Vert, i] /. {True -> 1, False -> 0}, {Vert, 8}, {i, Vert - 1, Vert*(Vert - 1)/2}]

Corrected by Keith Briggs and Robert G. Wilson v, May 01 2005
Rows 5, 6 & 7 from Robert G. Wilson v, Jun 21 2005
More terms from Keith Briggs, Jun 28 2005
Name corrected by Andrey Zabolotskiy, Nov 20 2017

A322140 Number of labeled 2-connected multigraphs with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 1, 1, 2, 7, 37, 262, 2312, 24338, 296928, 4112957, 63692909, 1089526922, 20389411551, 414146189901, 9070116944468, 212983762029683, 5336570227705763, 142083405456873290, 4004953714929148655, 119128974685786590410, 3728639072095285867881

Offset: 0

Gus Wiseman, Nov 27 2018

nonn

We consider a single edge to be 2-connected, so a(1) = 1.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Gus Wiseman, The a(5) = 37 labeled 2-connected multigraphs with 5 edges.

Cf. A002218, A002905, A013922, A275307, A291841, A304118, A304887, A322110, A322117, A322118, A322137, A322138.

seq(n)={Vec(1 + vecsum(Vec(serlaplace(log(x/serreverse(x*deriv(log(sum(k=0, n, 1/(1 - y + O(y*y^n))^binomial(k, 2) * x^k / k!) + O(x*x^n)))))))))} \\ Andrew Howroyd, Nov 29 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 29 2018

A383975 Irregular triangle: T(n,k) gives the number of connected subsets of k edges of the n-simplex up to isometries of the n-simplex, with 0 <= k <= A000217(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 3, 5, 6, 6, 4, 2, 1, 1, 1, 1, 1, 3, 5, 12, 19, 23, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 1, 3, 5, 12, 30, 56, 91, 128, 147, 147, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 1, 3, 5, 12, 30, 79, 180, 364, 633, 961, 1300, 1551, 1644, 1556, 1311, 980, 663, 402, 221, 115, 56, 24, 11, 5, 2, 1, 1

Offset: 0

Peter Kagey, May 16 2025

Connected subsets of edges are also called "polysticks", "polyedges", and "polyforms".
These are "free" polyforms, in that two polyforms are equivalent if one can be mapped to the other via the n! symmetries of the n-simplex.
Equivalently, T(n,k) is the number of connected unlabeled graphs with k edges and between 1 and n+1 vertices. - Pontus von Brömssen, May 27 2025

			Triangle begins:
 0 | 1;
 1 | 1, 1;
 2 | 1, 1, 1, 1;
 3 | 1, 1, 1, 3, 2, 1, 1;
 4 | 1, 1, 1, 3, 5, 6, 6, 4, 2, 1, 1;
 5 | 1, 1, 1, 3, 5, 12, 19, 23, 24, 21, 15, 9, 5, 2, 1, 1;
 6 | 1, 1, 1, 3, 5, 12, 30, 56, 91, 128, 147, 147, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1;

Peter Kagey, Illustration of row 3.

Cf. A333333 (cube, row 3), A383490 (dodecahedron), A383973 (octahedron, row 3), A383974 (icosahedron).

Cf. A000217, A002905, A292300.

T(n,n) = A002905(n).

The sum of row n is A292300(n+1)+1 for n >= 1. - Pontus von Brömssen, May 26 2025

Missing term a(62)=1 inserted and a(73)-a(91) added by Pontus von Brömssen, May 26 2025

A046745 Number of connected graphs with <= n edges.

Original entry on oeis.org

1, 2, 5, 10, 22, 52, 131, 358, 1068, 3390, 11461, 40964, 153786, 603927, 2471798, 10509270, 46296937, 210848414, 990794383, 4795761825, 23875074600, 122086530809, 640484152252, 3443478138871, 18954259427121, 106719731914780, 614115134054991, 3609008134177109

Offset: 1

N. J. A. Sloane

Andrew Howroyd, Table of n, a(n) for n = 1..60
G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.

Partial sums of A002905.

A000664 = Cases[Import["https://oeis.org/A000664/b000664.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
A002905 = EulerInvTransform[Rest@A000664];
Accumulate[A002905] (* Jean-François Alcover, Jul 16 2022 *)

More terms from Vladeta Jovovic, Apr 10 2001
More terms from Vladeta Jovovic, Jul 05 2003
Terms a(25) and beyond added by Andrew Howroyd, May 06 2021

A166974 Number of single-component graphs where the product of the valences of the nodes is n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 8, 1, 6, 1, 6, 2, 2, 1, 16, 2, 2, 4, 6, 1, 8, 1, 16, 2, 2, 2, 25, 1, 2, 2, 16, 1, 8, 1, 6, 6, 2, 1, 46, 2, 6, 2, 6, 1, 18, 2, 16, 2, 2, 1, 36, 1, 2, 6, 40, 2, 8, 1, 6, 2, 8, 1, 84, 1, 2, 6, 6, 2, 8, 1, 49, 12, 2, 1, 36, 2, 2, 2, 16, 1, 38, 2, 6, 2, 2, 2, 137

Offset: 0

Franklin T. Adams-Watters, Oct 26 2009

A single-component graph is any nonempty connected graph. If the empty graph was allowed, a(1) would be 2 instead of 1.
The sequence can be computed for n > 1 by looking at the graph that results when all valence 1 nodes are removed. This will be a connected graph, and labeling each node with its original valence, the product of the labels will be the original product. Each node must be labeled with at least its valence, and at least 2. Each such labeling, up to graph equivalence, uniquely defines the original graph, so we need only count the labelings for connected graphs with up to BigOmega(n) nodes.
Note, in particular, that a(n) = 1 for any prime, and 2 for any semiprime.
This product for the complete graph on n points is (n-1)^n. For the complete bipartite graph with n and m points in the parts the product is n^m*m^n. For the cyclic graph with n nodes it is 2^n.

Andrew Weimholt, Table of n, a(n) for n = 0..255

Cf. A000079, A001222 (BigOmega), A001349, A002905, A007778, A062275.

Corrected and extended by Andrew Weimholt, Oct 26 2009

A176425 Number of connected planar graphs with at most n edges.

Original entry on oeis.org

1, 2, 3, 6, 11, 23, 53, 132, 359, 1068, 3386, 11435, 40807, 152807, 597662, 2430734, 10237458, 44489603, 198831994, 911063459

Offset: 0

Jonathan Vos Post, Apr 17 2010

Partial sums of number of connected planar graphs with n edges (A046091).

Table of n, a(n) for n = 0..19

Cf. A002905, A066951, A046091.

a(n) = Sum_{i=0..n} A046091(i).

New name from Bartlomiej Pawlik, May 31 2022

A382348 Number of connected bipartite graphs with n edges.

Original entry on oeis.org

1, 1, 2, 4, 7, 17, 36, 94, 237, 658, 1845, 5527, 16809, 53357, 173298, 580331, 1988935, 6991328, 25124511, 92325353, 346401296, 1326493369

Offset: 1

Sergey Pupyrev, May 29 2025

			a(3) = 2 since there are two connected bipartite graphs with three edges: a path and a star "Y".

Brendan McKay and Adolfo Piperno, nauty and Traces.

Cf. A002905, A005142.

for (( i=$(bc <<< "sqrt(4*${n})"); i<=$((n+1)); i++ )) do ~/nauty2_8_9/geng -c -b ${i}:${i} ${n} -u; done

a(19)-a(22) from Sean A. Irvine, Jun 09 2025

cp's OEIS Frontend

A066951 Number of nonisomorphic connected graphs that can be drawn in the plane using n unit-length edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A076263 Triangle read by rows: T(n,k) = number of nonisomorphic connected graphs with n vertices and k edges (n >= 1, n-1 <= k <= n(n-1)/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A322140 Number of labeled 2-connected multigraphs with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A383975 Irregular triangle: T(n,k) gives the number of connected subsets of k edges of the n-simplex up to isometries of the n-simplex, with 0 <= k <= A000217(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A046745 Number of connected graphs with <= n edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A166974 Number of single-component graphs where the product of the valences of the nodes is n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A176425 Number of connected planar graphs with at most n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A382348 Number of connected bipartite graphs with n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

nauty

Extensions