Regular matchstick graphs
A graph G=(V,E) is called a unit-distance graph in the plane if there is an injective embedding of V in the plane such that every pair of adjacent vertices are at unit distance apart. If additionally the corresponding edges are non-crossing and all vertices have the same degree r we talk of a regular matchstick graph. Due to Euler's polyhedron formula we have $r\le 5$. The smallest known 4-regular matchstick graph is the so called Harborth graph consisting of 52 vertices. In this article we prove that no finite 5-regular matchstick graph exists and provide a lower bound for the number of vertices of 4-regular matchstick graphs.
\section{Introduction}
\noindent
One of the possibly best known problems in combinatorial geometry asks how often the same distance can occur among
$n$ points in the plane. Via scaling we can assume that the most frequent distance has length $1$. Given any set $P$ of points in the plane, we can define the so called unit-distance graph in the plane, connecting two elements of $P$ by an edge if their distance is one. The known bounds for the maximum number $u(n)$ of edges of a unit-distance graph in the plane, see e.~g.{} \cite{1086.52001}, are given by
\[
  \Omega\!\left(ne^{\frac{c\log n}{\log\log n}}\right)\le u(n)\le O\!\left(n^{\frac{4}{3}}\right).
\]
For $n\le 14$ the exact numbers of $u(n)$ were determined in \cite{schade}, see also \cite{1086.52001}.

If we additionally require that the edges are non-crossing, then we obtain another class of geometrical and combinatorial objects:
A \textbf{matchstick graph} is graph drawn with straight edges in the plane  such that the edges have unit length, and non-adjacent edges do not intersect, see Figure~\ref{fig_configuration_1} for an example.

2014-01-20T02:08:36.000
1401
1401.4372
en
https://arxiv.org/abs/1401.4372
A graph G=(V,E) is called a unit-distance graph in the plane if there is an injective embedding of V in the plane such that every pair of adjacent vertices are at unit distance apart. If additionally the corresponding edges are non-crossing and all vertices have the same degree r we talk of a regular matchstick graph. Due to Euler's polyhedron formula we have $r\le 5$. The smallest known 4-regular matchstick graph is the so called Harborth graph consisting of 52 vertices. In this article we prove that no finite 5-regular matchstick graph exists and provide a lower bound for the number of vertices of 4-regular matchstick graphs.
Combinatorics (math.CO)
Regular matchstick graphs
Qwen/Qwen-72B
1. YES
2. YES

