
a 7vertex 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.
http://en.wikipedia.org/wiki/Adjacency_matrix
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 unitdistance 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 3cycles ("triangles"), ACE and ABD.
There are the 4cycles ("quadrangles") ABGC, ADFE, 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 7graph 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 3D 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 socalled highpoints D, E and F, all in quadrangle ADFE but not in the base quadrangle ABGC.
The presumed 3D 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 3D 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 7vertex, 11edge graph that looks like the graph of matrix M.
 http://www.bibliotecapleyades.net/sociopolitica/last_circle/1.htm

