Extending A066951 to a(7) = 70

[Jonathan Post]

This is about as far as reasonable "by hand." Would love to see someone code
this tricky combination of combinatorial graph theoiry with Euclidean 2-D
geometry.

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

Previously (2002) known: a(1..6) = 1,1,3,5,12,28.

I'd provided a crude upper bound in a late 2006 comment.

Now, definitively, a(7) = 70.

This is confirmed by same answer on two different approaches.  (1)
negatively, by tightening upper bound as described below; (2)
constructively, by exhibiting all 70.

(1) Les Reid was correct about K_4 and K_3,2 being impossible to draw as
connected 6-edged planar graphs (with unit edges or not) per Kuratowski.
Extending that, there are exactly 7 forbidden graphs with 7 edges, meaning
that they are nonplanar.
(a) K_4 with an edge from one of the 4 totally connected points to a point
at infinity, well, a point distance 1 away;
(b) K_3,2 with an extra unit edge hanging from one of the 3;
(c) K_3,2 with an extra unit edge hanging from one of the 2;
(d) K_3,2 with an extra unit edgeconnecting 2 of the 3;
(e) K_3,2 with an extra unit edgeconnecting 2 of the 2;
(f) K_4 with one of the edges replaced by a 2-path (two unit edges with a
shared internal vertex);
(g) K_3,2 with one of the edges replaced by a 2-path (two unit edges with a
shared internal vertex).

There are also two topologically possible forbidden graphs, excluded by the
rigidity of Euclidean 2-space.

(h) Take a square with unit edges, make it rigid by attaching an equilateral
triangle (sharing an edge and 2 vertices with the square). The non-shared
vertex (apex) of the triangle cannot be joined in the plane by a unit length
edge to either of the two opposite vertices of the square, by Pythagorean
theorem;
(i) Start with 2 equilateral triangles sharing a base (edge and 2
vertices).  Now try to connect the two non-base (apex) vertices with a
distinct 2-path.  It coiuncides with existing vertcies and edges.  Since we
have grapohs and not multigraphs, that's excluded.

A046091(7) = 79.  Subtract the 9 described above, leaves upper bound of a(7)
= 70.

I drew 68 of those 70, then my 17-year-old son quickly drew #69  (pentagon
with 2-path internally connecting 2 vertices of the pentagon) and #70
(square with an edge and a 2-path branching from the same vertex).

The 70 can be classified in various ways that suggest integer sequences.

For example, we have the well-known 23 trees (8 unlabeled vertices connected
by 7 edges) all of which are obviously possible as planar and unit-edge.
There are 47 connected unit-edge graphs with from 1 to 3 polygons.  31 with
7 nodes (1 heptagon, 1 hexagon, 4 with pentagon, 10 with square, 15 with
triangle). These can also be described as skeletons of cycloheptane; methyl
cyclohexane; ethyl or dimethyl cyclopentane; propyl or isopropyl, or ethyl
methyl, or trimethyl cyclobutane; 15 cyclopropane derivatives.  There are 15
with 6 nodes, based on: 1 pentagon-adjoining triangle; 1 square adjoining
square; 10 triangle adjoining triangle (7 with shared edge, 1 with 2
vertices bridged by an edge, 2 with shared apex); 3 square adjoining
triangle. There is 1 with 5 nodes, as 3 equilateral triangles in a "truss
bridge." 31+23+15+1 = 70 with 5 to 7 nodes.  Cannot have more than 8 nodes
and still be connected with 7 edges.  Cannot have fewer than 5 nodes under
constraints.

Someone want to try a(8)? We know how many are trees, and know loose
bounding above by total number of connected graphs with 8 edges.  The same
integer sequences can be done for number with k nodes, or number with j same
or different k-gons, or classification by vertex degrees.

Would by nice to draw these with graphics program, and link to it after
submitting extension.

Interesting to code, I suspect, given that organic chemistry algorithms
don't care much about bond lengths, graph theory algorithms don't care about
edge length, the planarity constraint itself is easy by Kuratowski graph
minors.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20070105/d084c6d0/attachment.htm>