The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: a 7-vertex graph with an unusual 3D figure (very probable)
Replies: 11   Last Post: Dec 6, 2013 12:42 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
David Bernier

Posts: 3,892
Registered: 12/13/04
a 7-vertex graph with an unusual 3D figure (very probable)
Posted: Nov 30, 2013 1:23 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

I wrote a program that produces at random "adjacency matrices" for graphs.

I'm looking at undirected graphs with no loops and no double edges.

Some such graphs can be "embedded" in the Euclidean plane
in such a way that adjacent vertices are always exactly
a unit-distance apart, the unit distance graphs:

The adjacency matrix my program came up with (that passed two
admissibility tests that I'll explain below) is this:

M =
[0 1 1 1 1 0 0]
[1 0 0 1 0 0 1]
[1 0 0 0 1 0 1]
[1 1 0 0 0 1 0]
[1 0 1 0 0 1 0]
[0 0 0 1 1 0 1]
[0 1 1 0 0 1 0]

Following the usual order of rows, I label the vertices
A, B, C, D, E, F and G.

The vertex A has 4 adjacent vertices (B, C, D and E).
Other vertices have degree 3 (3 adjacent vertices).

The graph has 7 vertices and 11 edges.

There are the 3-cycles ("triangles"), ACE and ABD.

There are the 4-cycles ("quadrangles")
BDFG and

The two admissibility tests for candidate unit distance graphs in 2D are:

(a) Has no subgraph isomorphic to the complete graph on 4 vertices.

This is because in a unit distance graph in the Euclidean plane,
we can have 3 points at unit distance from each other, but not 4.

(b) If X and Y are distinct vertices of the graph, there can be
two distinct vertices v1 and v2, each adjacent to X and Y,
but there cannot be three distinct vertices v1, v2 and v3
each adjacent to X and Y.

Because in the plane, if C1 and C2 are radius 1 circles about
two distinct points X and Y, then C1 and C2 intersect in two
or fewer points.

I won't check that the 7-graph with the adjacency matrix
M has properties (a) and (b), as the program did it, and
it's routine.

The graph associated to M is connected also.

Numerically, I found 7 points in R^3 with unit distances
to within precision (say 10^(-12) ), for the 11 edges
required by the matrix M.

I don't think the graph for M can be for a planar Euclidean

Also, I doubt that the presumed 3-D figure is deformable, I rather
think it should be rigid.

If we view ABGC as some sort of base quadrangle, even though
it may not fit in a plane, then

upon side AB rises the equilateral triangle ABD to a high point
at D; upon side AC rises the equilateral triangle ACE to a
high point at E; connected to the quadrangular base ABGC
of the skeleton figure along side BG is the quadrangle BDFG;
also connected to base ABGC along side CG is the quadrangle
CEFG. The quadrangle ADFE contains the base point A and the
three so-called high-points D, E and F, all in quadrangle
ADFE but not in the base quadrangle ABGC.

The presumed 3-D figure may have a plane of symmetry
passing through the three points A, F and G.

This plane of symmetry would send B to C and C to B,
and send D to E and E to D. It would also keep fixed
the three points A, F and G. There might be no
plane of symmetry if the presumed 3D figure is deformable;
I doubt that it's deformable.

From my sketch of the graph, I think it's clear that there's
a graph isomorphism that fixes A, G and F and that
permutes B with C, and D with E.

It's only after much numerical computer work that I have some
confidence that there are 7 points in R^3 which are at distance
1 when implied by matrix M; if a matrix entry in M is zero,
the corresponding distance might or might not be 1: it doesn't
matter as I view the problem.

So, I'd be curious about ways to show the corresponding graph to M
can't be made a 2D unit distance graph, can be made a 3D equivalent of
a unit distance graph, and so on.

Here are the x, y and z coordinates for points A to G in the
presumed 3-D figure:

x y z
1.384667538045070848 1.382768373981428755 0.044412611314774557 // A
0.399833591130468233 1.520541863804588859 0.149866689028978084 // B
0.970226156884894247 1.649162807406999439 0.914626577774698943 // C
1.041203194674366289 2.053898061776666813 0.701388400056488421 // D
0.405996262469059331 1.582686954821862589 0.091689406861527141 // E
1.301674189203176470 1.182510983474254957 0.285648793118733590 // F
1.172171851884524849 2.151166533083443602 0.073668674144507970 // G

David Bernier

P.S. If we have a square base ABGC in R^2, and one unit above
it a square A'DFE, and add in the 12 edges, then
remove the edge AA' and glue A and A' while letting the
other edges stretch, we're left with a 7-vertex, 11-edge
graph that looks like the graph of matrix M.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.