In this paper
AbstractIntroductionThe graph and its realisationProof of Theorem 1Concluding remarksData availabilityCoordinates and colouringReferencesWorksMathematics
A 43-vertex 4-chromatic unit-distance graph in the plane with girth 5
Abstract
We exhibit a set of 43 points in the Euclidean plane whose unit-distance graph has 83 edges, girth 5 and chromatic number 4. The smallest previously known 4-chromatic unit-distance graph of girth 5, due to Hochberg and O'Donnell (1996), has 45 vertices. The new graph is 4-critical, has trivial automorphism group, and has exactly 2n-3 edges; it is a Laman graph and its unit-distance realisation is infinitesimally rigid. The coordinates are algebraic numbers, specified as the unique real solution of an explicit system of 82 quadratic equations inside an explicit rational box. Every claim is certified by exact computation: existence and uniqueness of the realisation by a rational contraction-mapping certificate (independently re-checked with interval Krawczyk arithmetic), and non-3-colourability both by exhaustive search and by a DRAT proof verified with drat-trim.
Introduction
A unit-distance graph is a graph whose vertices are points of the plane, two points being adjacent when their Euclidean distance is exactly 1. The Hadwiger–Nelson problem asks for the chromatic number of the graph on all points of the plane; it is known that [1, 11].
Erdős asked whether 4-chromatic unit-distance graphs can avoid short cycles. Wormald [13] constructed a 4-chromatic unit-distance graph of girth 5 with 6448 vertices. O’Donnell later showed that 4-chromatic unit-distance graphs of every girth exist [10]. For small orders, Hochberg and O’Donnell [4] found 4-chromatic unit-distance graphs of girth 4 and girth 5 with 23 and 45 vertices respectively. The girth-4 record has since been lowered to 17 vertices by Exoo and Ismailescu [3]; we are not aware of any improvement of the 45-vertex girth-5 example.
Without the geometric restriction, the smallest 4-chromatic graphs of girth at least 5 have 21 vertices (Royle; see [2]). So the minimum order of a 4-chromatic unit-distance graph of girth 5 lies between 21 and 45.
In this note we lower the upper bound to 43.
Theorem 1. There is a set of 43 points in whose unit-distance graph has the following properties:
has 43 vertices and 83 edges, and its girth is 5;
;
is 4-critical: deleting any vertex or any edge leaves a 3-colourable graph;

Figure 1. The unit-distance realisation of : the 43 points and the 83 unit edges, drawn to scale. Vertices are coloured by the 4-colouring of Table 1.
has degree sequence and trivial automorphism group;
has edges and is a Laman graph, and the realisation is infinitesimally rigid.
The graph was found by a computer search; this note is concerned only with the graph and with the certificate of its properties.
The graph and its realisation
Label the vertices . The 83 edges of are
–, –, –, –, –, –, –, –, –, –, –, –, –, –, –, –, –,
–, –, –, –, –, –, –, –, –, –, –, –, –, –, –,
–, –, –, –, –, –, –, –, –, –, –, –, –,
–, –, –, –, –, –, –, –, –, –, –, –, –,
–, –, –, –, –, –, –, –, –, –, –, –, –,
–, –, –, –, –, –, –, –, –, –, –, –.

Figure 2. An abstract drawing of with vertex labels (edges are not drawn at unit length). Vertex colours show the 4-colouring of Table 1; white is colour 0.
Exact coordinates. Put and ; the edge fixes position and orientation. The remaining 41 points give 82 unknown coordinates . Each of the 82 edges other than gives one equation
so is a square system of 82 quadratic polynomials with integer coefficients. Let be the vector of rational centres listed in Table 1 (given there to 16–17 significant digits; the exact rational values are in the supplementary files), let , and let
| colour | |||
| 0 | 0 | 0 | 0 |
| 1 | 0.433089991676348 | 0.17517745454218736 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 1.2267499031050335 | 0.0067421023916053096 | 2 |
| 4 | 1.033578176991139 | −0.024575643333048874 | 2 |
| 5 | 1.399381442379761 | −0.95526784327405057 | 0 |
| 6 | 2.1630319145538008 | 0.35799129461480611 | 1 |
| 7 | 1.9849313733408456 | −0.1446315016562639 | 1 |
| 8 | 2.2506146807519531 | −0.11064086413120923 | 1 |
| 9 | 1.7582248930595668 | 1.9529100593027817 | 3 |
| 10 | 1.2612996895990445 | 0.03515299129527779 | 2 |
| 11 | 1.1655266885216353 | 0.42858395739585431 | 0 |
| 12 | 1.3480490350752383 | 0.93747632993222585 | 3 |
| 13 | 1.6979910603562509 | 0.72279007732749756 | 0 |
| 14 | 1.8746120586826571 | 0.84926469453997244 | 2 |
| 15 | 1.8741623423572826 | 0.51710531529084758 | 1 |
| 16 | 2.1649171705193808 | 0.46349333281728 | 3 |
| 17 | 2.5747788927340869 | 1.3756410010504423 | 1 |
| 18 | 2.8604986057909723 | 0.68184989163758891 | 0 |
| 19 | 1.579500949990162 | 1.4727070439666963 | 0 |
| 20 | 1.9983241777325442 | 0.98216172245150257 | 2 |
| 21 | 1.5938927434972694 | 0.96650499817412217 | 0 |
| 22 | 0.6321407592436713 | 1.7928767942379744 | 1 |
| 23 | 2.191970762407327 | 0.40101000467329218 | 0 |
| 24 | 1.3108125298679165 | 1.0032025756577176 | 0 |
| 25 | 1.2203468589886777 | 0.79180252637541171 | 0 |
| 26 | 1.2698663108079469 | 0.90945741043993222 | 2 |
| 27 | 1.3769681292103328 | 1.028440871055164 | 1 |
| 28 | 0.6090344347145451 | 0.79314378099556138 | 3 |
| 29 | 0.31222841357043618 | 0.95000706195232509 | 1 |
| 30 | 0.30353260224069506 | 1.1667493918281235 | 0 |
| 31 | 0.99848327194346864 | 0.99999884976733966 | 0 |
| 32 | 1.4040613435456299 | 1.3997179431839042 | 2 |
| 33 | 2.1988796223628104 | 1.4629164423483652 | 2 |
| 34 | 2.4038321614271041 | 1.3783097271767739 | 1 |
| 35 | 2.4906931595836426 | 1.4089403196701669 | 1 |
| 36 | 2.6805804484767219 | 2.3392521737442582 | 0 |
| 37 | 1.6252619207765713 | 1.9099680343695213 | 0 |
| 38 | 1.4474009678085034 | 1.8935719594451255 | 1 |
| 39 | 1.2075427605754268 | 1.5942603666903059 | 1 |
| 40 | 0.40450088711542082 | 1.3700717977172157 | 1 |
| 41 | 0.41059561911934073 | 1.2855870779889529 | 0 |
| 42 | 0.56160838256353762 | 2.3576533056820117 | 0 |
Table 1. Box centres (vertices 0 and 2 are exact) and a 4-colouring.
Lemma 2. has exactly one zero in . At the Jacobian is nonsingular. Consequently every coordinate of is a real algebraic number.
Proof. Let be the explicit rational matrix in the supplementary files (an approximate inverse of ), and set . Since is quadratic, each entry of has the form , and it changes by at most on ; each row of has at most four nonzero entries. Exact rational arithmetic gives
ends_mid=1 By the mean value theorem, for . Also , so maps into itself. By the contraction mapping theorem has a unique fixed point .
Since , the matrix is invertible, so the fixed points of are exactly the zeros of in . The same estimate holds with in place of , so is nonsingular.
A nonsingular zero is an isolated point of the complex variety . Because has rational coefficients, isolated points of this variety have algebraic coordinates.
Let be the points given by .
Lemma 3. The points of are pairwise distinct, and the unit-distance graph of is exactly .
Proof. Every edge has length 1 by Lemma 2. For a pair , interval bounds on over the box , computed exactly in rational arithmetic, give
So the points are distinct and no non-edge has length 1.
Proof of Theorem 1
(1) Girth. No edge has both ends with a common neighbour, so there are no triangles. No two vertices have two common neighbours, so there are no 4-cycles. The cycle has length 5.
(2) Chromatic number. Table 1 gives a proper 4-colouring. To show we encode 3-colourability as a CNF formula with 129 variables: one clause per vertex saying that it gets some colour, and three clauses per edge. The SAT solver kissat (version 4.0.4) [6] reports this formula unsatisfiable and produces a DRAT proof of 1916 bytes. This proof was verified with drat-trim [12]. No symmetry breaking is used in this formula. Independently, an exhaustive DSATUR-style backtracking search, with the ends of the edge fixed to colours 0 and 1, visits 1957 nodes and finds no 3-colouring.
(3) Criticality. For each of the 43 vertices and each of the 83 edges, the deleted graph was 3-coloured explicitly by backtracking. All 126 colourings are included in the supplementary files, and each was checked to be proper.
(4) Degrees and automorphisms. The degree sequence is read off the edge list. A complete enumeration of the automorphisms (VF2 algorithm, as implemented in networkx) finds only the identity.
(5) Rigidity. The graph has edges. The -pebble game [5] confirms that every set of vertices spans at most edges, so is a Laman graph [8]. The rigidity matrix of the framework , with the edge pinned, is . This matrix is nonsingular by Lemma 2, so the realisation is infinitesimally rigid.
Remark 4. Lemma 2 was checked twice, with independent code. The first check is the rational contraction certificate above, using exact Fraction arithmetic. The second is an interval Krawczyk test [7, 9] at 50 digits, carried out with an approximate inverse computed afresh from the Newton root. That test gives with . A Newton iteration at 80 digits from converges to a root with residual below at distance from .
Remark 5. The realisation is tight in places: the smallest distance between two points of is about 0.0416, and the non-edge whose length is closest to 1 has squared length within 0.009 of 1. Because the system is square and nonsingular, is locally the only realisation of with these edge lengths, up to congruence. We have not looked for a closed-form expression of the coordinates.
Concluding remarks
The minimum order of a 4-chromatic unit-distance graph of girth 5 is now known to lie between 21 and 43. It would be interesting to narrow this gap. One step would be to decide whether any of the smallest 4-chromatic graphs of girth 5, which have 21 vertices (see [2]), is a unit-distance graph.
Data availability
The supplementary files contain:
the edge list;
the exact rational centres and the matrix ;
the polynomial system;
the CNF formula and the DRAT proof;
two independent verification scripts.
They are available at https://doi.org/10.5281/zenodo.24036368.
Coordinates and colouring
Decimal values of the box centres; the exact rational centres are in the supplementary files. Each free coordinate of lies within of the value shown. The last column is a proper 4-colouring.
References
- [1]A. D. N. J. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28 (2018), 18–31.arxiv.org/abs/1804.02385
- [2]G. Exoo and J. Goedgebuer, Bounds for the smallest \(k\)-chromatic graphs of given girth, Discrete Math. Theor. Comput. Sci. 21(3) (2019), #9.DOI
- [3]G. Exoo and D. Ismaileascu, Small order triangle-free 4-chromatic unit distance graphs, Geombinatorics 26 (2016).
- [4]R. Hochberg and P. O’Donnell, Some 4-chromatic unit distance graphs without small cycles, Geombinatorics 5 (1996), 137–141.
- [5]D. J. Jacobs and B. Hendrickson, An algorithm for two-dimensional rigidity percolation: the pebble game, J. Comput. Phys. 137 (1997), 346–365.DOI
- [6]A. Biere et al., Kissat SAT solver, version 4.0.4, https://github.com/arminbiere/kissat.
- [7]R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187–201.DOI
- [8]G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340.DOI
- [9]R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis, SIAM, 2009.DOI
- [10]P. O’Donnell, Arbitrary girth 4-chromatic unit distance graphs in the plane. I. Graph description; II. Graph embedding, Geombinatorics 9 (2000), 145–152 and 180–193.
- [11]A. Soifer, The Mathematical Coloring Book, Springer, 2009.DOI
- [12]N. Wetzler, M. J. H. Heule and W. A. Hunt Jr., DRAT-trim: efficient checking and trimming using expressive clausal proofs, in: Theory and Applications of Satisfiability Testing – SAT 2014, LNCS 8561, Springer, 2014, 422–429.DOI
- [13]N. C. Wormald, A 4-chromatic graph with a special plane drawing, J. Austral. Math. Soc. Ser. A 28 (1979), 1–8.DOI