Search All of the Math Forum:

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

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

 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

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:

http://en.wikipedia.org/wiki/Unit_distance_graph

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")
ABGC,
BDFG and
CEFG.

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
figure.

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.

--

Date Subject Author
11/30/13 David Bernier
11/30/13 fom
11/30/13 David Bernier
11/30/13 David Bernier
11/30/13 David Bernier
12/1/13 quasi
12/1/13 David Bernier
12/1/13 Brian Q. Hutchings
12/3/13 David Bernier
12/6/13 David Bernier
12/6/13 fom
12/1/13 Ken.Pledger@vuw.ac.nz