7
$\begingroup$

Make an as small as possible three dimensional structure of matchsticks, all of which have equal length, such that the end of each matchstick meets exactly five other ends. A matchstick is not allowed to cross another matchstick.

I got the inspiration for this question from this question. Similarly a matchstick can be thought of as mathematical line segment, connecting two points in $\mathbb{R}^3$, such that in each point six line segments meet. And with "as small as possible structure" I am referring to the number of used matches/line segments.


Example: If the number of line segments, which have to meet in each node, would be equal to four, then the smallest structure would be an octahedron:
$\hspace{5cm}$octahedron

$\endgroup$
  • $\begingroup$ A E's new title doesn't make sense to me. Are we optimizing the volume of the convex hull? I think the question's wording of "smallest possible" was ambiguous. @fibonatic, what should the puzzle be? $\endgroup$ – Lopsy Feb 3 '15 at 17:29
  • $\begingroup$ I don't know if we'll be able to say for sure that any structure we find is the smallest. The currently accepted answer on the linked question, the Harborth Graph, has been known for almost 30 years, and is still not known to be optimal. $\endgroup$ – KSmarts Feb 3 '15 at 17:43
9
$\begingroup$

Here's a way to do it 48 edges.

A regular tetrahedron has four vertices each connected to the three other vertices by an edge of length one. Take four of these tetrahedra, and place four translated copied so that their centers themselves form a regular tetrahedron of edge length $1$.

Then, the corresponding vertices of each tetrahedron themselves form a regular tetrahedron with edge length $1$. So, each vertex is one away from $6$ other vertices -- three in its own tetrahedron, and the three corresponding points in other tetrahedra. This is a solution with $48$ edges -- each of $16$ vertices connects to $6$ other vertices, and $(16\times 6)/2 = 48$. If the original tetrahedron is rotated randomly, no edges cross with probability $1$

Mathematically, we've taken the Cartesian graph product $T\times T$, whose vertices correspond to pairs $(v,w)$ of vertices of $T$, and two vertices are connected by an edge, written $(v,w) \leftrightarrow (v',w')$, if either $v=v'$ and $w \leftrightarrow w'$, or $w=w'$ and $v \leftrightarrow v'$ in $T$. We've realized it as a unit distance graph in 3D as follows by taking the vector sum $v+w$ corresponding to each pair of vertices $(v,w)$, with a different tetrahedron embedding for $v$ and $w$.

This type of construction lets us create a unit distance graph with arbitrary many edges per vertex. If we have a solution for $n_1$ edges per vertex using $V_1$ vertices and likewise for $n_2$ and $V_2$, then taking the Cartesian product gives a solution for $n_1 + n_2$ edges per vertex that uses $V_1 V_2$ vertices. Note that minimizing vertices is equivalent to minimizing edges due to the relation $E=nV/2$.

$\endgroup$
  • 6
    $\begingroup$ I also found this solution, here is an animation I made of it, in case people wonder how it can look like. But can it be proven that this is the smallest? It should be clear that this would be the smallest graph product, but are there also solutions which aren't a product? $\endgroup$ – fibonatic Feb 3 '15 at 12:01
  • 2
    $\begingroup$ For instance the smallest graph product which forms a graph with 4 edges per vertex, would be that of a triangle times a triangle, which has 9 vertices. However a octahedron would be a smaller solution, which has only 6 vertices. $\endgroup$ – fibonatic Feb 3 '15 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.