Can the Petersen graph be embedded into the 3-dimensional Euclidean space such that every edge is a segment and has unit length

graph theoryplanar-graphs

By embedding I mean that its edges may intersect only at their endpoints. The precise definition can be found here.

We know that the Petersen graph can be drawn in the plane such that every edge is a segment and has unit length, but that's not an embedding; the edges forming a star-shape intersect each other. We also know that every finite graph can be embedded into the 3-dimensional space with edges not necessarily of unit length.

So I'm interested in the question in the title: is it possible to embed the Petersen graph into the 3-dimensional Euclidean space such that every edge is a segment and has unit length. But it occurred to me that the vertex-position of a pentagon with sides of unit length in the 3D space may be very complicated. So is there any way to handle this?

Best Answer

There are many embeddings; playing around with this problem, I get the sense that for a typical 3-regular graph, the problem is not very constrained. The only difficulty is that if we look for a particularly symmetric embedding, we increase the risk of intersecting edges. Still, here is one solution I consider particularly nice, in which $7$ of the $10$ vertices are vertices of the unit cube:

enter image description here

The $6$ red vertices are placed at $(1,0,0)$, $(1,0,1)$, $(0,0,1)$, $(0,1,1)$, $(0,1,0)$, $(1,1,0)$. They can be any $6$-cycle you like in the Petersen graph. For concreteness, let's say that they are vertices $\{1,2\}$, $\{3,4\}$, $\{1,5\}$, $\{2,3\}$, $\{1,4\}$, $\{3,5\}$ in the usual construction of the Petersen graph (vertices are $2$-subsets of $\{1,2,3,4,5\}$, disjoint subsets are adjacent).

Opposite vertices of the $6$-cycle have one common neighbor; for this $6$-cycle, these are $\{4,5\}$ (for $\{1,2\}$ and $\{2,3\}$), $\{2,5\}$ (for $\{3,4\}$ and $\{1,4\}$), and $\{2,4\}$ (for $\{1,5\}$ and $\{3,5\}$). These are the purple vertices in the embedding; they are placed at $(\frac12, \frac{2-\sqrt2}{4}, \frac{2+\sqrt2}{4})$, $(\frac{2-\sqrt2}{4}, \frac{2+\sqrt2}{4}, \frac12)$, and $(\frac{2+\sqrt2}{4}, \frac12, \frac{2-\sqrt2}{4})$.

The three purple vertices have one final common neighbor: $\{1,3\}$, which is placed at point $(0,0,0)$.

Here is some Mathematica code for generating a (slightly differently styled) picture of this embedding:

Graph3D[PetersenGraph[], VertexCoordinates -> {
    1 -> {1, 0, 0}, 2 -> {1, 1, 1}, 3 -> {1, 0, 1},
    4 -> {1/2, 1/2 - 1/Sqrt[8], 1/2 + 1/Sqrt[8]},
    5 -> {1/2 + 1/Sqrt[8], 1/2, 1/2 - 1/Sqrt[8]},
    6 -> {1, 1, 0},
    7 -> {1/2 - 1/Sqrt[8], 1/2 + 1/Sqrt[8], 1/2},
    8 -> {0, 0, 1}, 9 -> {0, 1, 1}, 10 -> {0, 1, 0}}]

Unfortunately, the default view of this embedding is not a particularly flattering one, but you can rotate it.

Related Question