Pith. sign in

REVIEW 3 major objections 3 minor 11 references

On the number of edges of restricted matchstick graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that triangle-free matchstick graphs have at most $2n-(\sqrt{2}/5)\sqrt{n}$ edges and that matchstick graphs in a radius-$r$ disk have at most $(2-\varepsilon(r))n$ edges.

desk verdict A creative paper with a false central theorem: the bounded-disk upper bound fails on small triangular-lattice patches, and Theorem 1's proof has an algebra slip; the ideas are worth engaging but the manuscript needs major correction. read the letter →

arxiv 2506.01589 v1 pith:P7FMYEBO submitted 2025-06-02 math.CO

Panna Gehér , János Pach , Konrad Swanepoel , Géza Tóth This is my paper
classification math.CO MSC 05C1005C3552C10
keywords matchstickgraphstriangle-freeunitdistanceplanarrhombuschainsextremaledgecountboundeddisk
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Matchstick graphs draw $n$ points in the plane and connect some pairs by unit-length segments that do not cross. This paper proves two deficits caused by restricting such drawings. In a triangle-free matchstick graph the edge count is at most $2n-(\sqrt{2}/5)\sqrt{n}$, and a rhombus-tiling construction reaches $2n-\sqrt{2n}-O(1)$, so the true maximum is $2n-\Theta(\sqrt{n})$. For matchstick graphs inside a disk of radius $r$, the paper claims a linear deficit: some positive $c(r)$ exists with $e\le (2-c(r))n$, while a skew-lattice construction gives $e\ge (2-5/r-o(1))n$. These results say the unit-length noncrossing constraint, not just planarity, controls how many edges a sparse drawing can carry.

What carries the argument

The main objects are rhombus chains: maximal strips of congruent unit rhombi stacked across a common direction, where each rhombus shares an opposite side with the next. Theorem 1's upper bound uses a counting theorem that any two maximal rhombus chains meet in at most one rhombus, which bounds the number of quadrilateral faces $f_4$ by $\binom{C}{2}$ and forces a deficit $F=\sum_{i\ge 5}(i-4)f_i$ of order $\sqrt{n}$. Theorem 2's mechanism is the neighborhood graph $N$ whose vertices are edges of the triangle-free, fat-rhombus-free graph; Lemma 5 asserts every regular edge, one adjacent only to rhombi, has an irregular edge within distance $16r^2$, and counting paths in $N$ of length at most $16r^2$ converts this into one irregular edge per at most $2\cdot 3^{16r^2}$ regular edges, yielding the linear deficit.

What would settle it

Count the vertices and edges of a hexagonal patch of the regular triangular lattice of side length $k=r$: it has $n=3k^2+3k+1$ vertices and $e=9k^2+3k$ edges, all of unit length, and the patch fits in a disk of radius $r$; since $e/n=3-O(1/k)$, for every fixed positive $\varepsilon$ and all sufficiently large $r$ this gives $e>(2-\varepsilon)n$, contradicting the claimed upper bound in Theorem 2.

Watch

Extended reading notes

Core claim

On its own terms the paper establishes two extremal statements. First, for triangle-free matchstick graphs on $n$ vertices, the maximum number of edges $e(n)$ satisfies $2n-\sqrt{2n}-O(1)\le e(n)\le 2n-(\sqrt{2}/5)\sqrt{n}$; the upper bound is obtained by counting maximal rhombus chains and showing that a triangle-free drawing needs many non-rhombus faces. Second, for any fixed $r>0$ and every $n$, a matchstick graph contained in a disk of radius $r$ has at most $(2-\varepsilon(r))n$ edges for a positive $\varepsilon(r)$, with an explicit lower construction achieving $(2-5/r-o(1))n$. The paper's intended message is that both a ban on triangles and confinement to a bounded region force a structural price, missing edges proportional to $\sqrt{n}$ or to $n$, that planar graphs alone do not pay.

Load-bearing premise

The bounded-disk upper bound rests on Lemma 5's claim that a chain of thin rhombi can only turn by the tiny angle $\pi/(50r^2)$, never by the complementary angle $\pi-\theta$; if some rhombus turns the other way, the projection of the path no longer has to exceed $2r$, and the contradiction with the disk radius disappears.

Editorial extensions

If this is right

  • The extremal triangle-free matchstick graph is not a square grid: a centrally symmetric $2k$-gon tiled by rhombi gives the same $2n-\Theta(\sqrt{n})$ count with the conjecturally optimal constant $\sqrt{2}$.
  • General matchstick graphs can have about $3n-\sqrt{12n}$ edges; banning triangles lowers the linear coefficient from 3 to 2, the same coefficient as triangle-free planar graphs, but with a provable $\sqrt{n}$ deficit.
  • Inside a disk of radius $r$, Euler's formula only forbids $O_r(1)$ missing edges, but the unit-length constraint actually forces a linear fraction of edges to be missing, and the paper's lower bound shows this linear deficit is achievable.
  • The explicit constants $c_1(r)=5/r+o(1)$ and $c_2(r)=20/(316r^2)$ leave a wide gap; the paper conjectures the true deficit constant is $\Theta(1/r)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Read literally, the uniform statement of Theorem 2 cannot hold for $n$ comparable to $r^2$: a hexagonal patch of the triangular lattice of side length $r$ sits in a radius-$r$ disk and has $e/n\to 3$, violating any bound of the form $(2-\varepsilon)n$ with positive $\varepsilon$; the intended statement is likely asymptotic with $r$ fixed and $n$ large, or with $\varepsilon$ depending on $n/r^2$.
  • The rhombus-chain counting in Theorem 1 should transfer to matchstick graphs of girth $g\ge 5$, giving $e\le \frac{g}{g-2}(n-2)-c(g)\sqrt{n}$; the odd-girth case follows from the unit-area lower bound cited in the concluding remarks, and the same chain-intersection bound may handle even $g$.
  • The path-counting step in Theorem 2 is a loose overcount; replacing $3^{16r^2}$ by a sharper enumeration of non-backtracking rhombus paths should move $c_2(r)$ from exponentially small toward the conjectured $\Theta(1/r)$ scale.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies extremal edge counts of matchstick graphs under two restrictions. Theorem 1 claims that every triangle-free matchstick graph on n vertices has at most 2n - (sqrt(2)/5) sqrt(n) edges and that the lower bound 2n - sqrt(2) sqrt(n) - O(1) is attainable. The proof uses maximal rhombus chains and a cited bound of Gehér and Tóth to control the number of rhombus faces. Theorem 2 claims that, for every fixed disk radius r, any matchstick graph on n vertices inside a disk of radius r has at most (2 - epsilon(r))n edges for some epsilon(r) > 0. The proof removes triangular faces and fat rhombi, then uses monotone paths and a lemma asserting that every regular edge has a nearby irregular edge. The paper concludes with open problems about strengthening these results.

Significance. The lower-bound construction for triangle-free matchstick graphs in Proposition 3 is explicit and interesting, and the heuristic that the square grid is extremal is usefully challenged. If the rhombus-chain counting argument can be made fully rigorous, Theorem 1 would be a valuable contribution to a problem that has remained open for penny graphs as well. However, the central upper-bound claim of Theorem 2 is false as stated, and the proof of Lemma 5 contains an unjustified angle assertion. These are load-bearing defects, so the paper cannot be accepted in its present form. No machine-checked proofs or reproducible code are supplied; the paper's contributions are purely theoretical.

major comments (3)
  1. [Theorem 2 and Abstract] The upper bound in Theorem 2 is false as stated. Let H_2 be the hexagonal patch of the unit triangular lattice with side length 2: it has n = 3*2*3 + 1 = 19 vertices, e = 9*4 + 3*2 = 42 edges, and all vertices lie in the disk of radius 2 centered at the hexagon's center. Therefore e/n = 42/19 > 2, so no positive epsilon(2) can satisfy e <= (2 - epsilon(2))n. This is not a small-n artifact: for the side-length-k hexagonal patches, n = 3k(k+1)+1 and e = 9k^2+3k, so e/n tends to 3 as k tends to infinity, and for every r >= 2 one can choose k <= r to obtain arbitrarily large counterexamples. A repair would require either restricting the graph class or imposing n much larger than r^2, neither of which appears in the manuscript.
  2. [Section 3, proof of Lemma 5, final paragraph] The assertion that 'two edges of a rhombus determine an angle at most pi/(50r^2)' is false: in a rhombus with acute angle theta, adjacent edges meet at theta or at pi - theta, and the assumption that the rhombus is not fat bounds only theta, not pi - theta. If a monotone path turns through the large angle pi - theta at some vertex, the cumulative angular difference between alpha and later edges of P_{4r} need not be less than pi/3, and the projection argument proving that the path is longer than 2r collapses. This is an independent gap in the proof of the upper bound, not merely a matter of choosing a smaller constant.
  3. [Section 2, equations (3) and the following paragraph] Equation (3) correctly gives e = 2n - 4 - F/2 from Euler's formula, but two paragraphs later the text uses e = 2n - 2 - F/2, both in the inequality f4 >= n - 3F/2 and in the final line e = 2n - 2 - F/2. With the correct expression (3), the derivation gives f4 >= n - 2 - 3F/2 and a final additive constant of -97/25 instead of -47/25; the claimed sqrt(n) term survives, so this inconsistency is repairable, but it must be corrected.
minor comments (3)
  1. [Theorem 2 statement] The notation c1(r) = 5/r + o(1) is confusing because c1 is supposed to depend only on r; the o(1) presumably refers to n tending to infinity, and this should be stated explicitly.
  2. [Proposition 4] The proposition mixes 'let n tend to infinity' with 'for every n'; the construction should clarify that the bound is asymptotic and that the extra vertices added inside the disk can always be chosen without creating unit distances.
  3. [Definition 1] The definition of the convexity number refers to 'epsilon_1 has smaller slope than epsilon_2' without specifying whether slopes are measured for the oriented edges of the monotone path; a convention for vertical edges would make the definition unambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and the one overlapping citation is independent evidence.

full rationale

The proof of Theorem 1 reduces the upper bound to Euler's formula plus a rhombus-chain count. The only load-bearing external input is the cited lemma "Gehér and Tóth [4, Claim 5]" that two maximal rhombus chains have at most one rhombus in common. Although that paper shares two authors with the present manuscript, the lemma is a parameter-free combinatorial statement about rhombus faces in unit-distance drawings; it does not assume or contain the triangle-free edge bound being proved, and it is externally checkable independently of any fitted values in this paper. Under the rules, such a citation is real evidence and does not constitute circularity. The proof of Theorem 2 is likewise self-contained: after deleting edges from triangular faces and fat rhombi, the estimates use only area bounds, Euler's formula, and a counting argument over shortest paths in the neighborhood graph. The lower-bound construction is explicit rather than fitted to the theorem's constants. The possible flaw in Lemma 5's angle estimate and the apparent counterexample to the universal statement of Theorem 2 are correctness risks, not circular reductions: neither makes a derived quantity equal to an input by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard planar graph counting, area bounds, a self-cited rhombus-chain lemma, and an unproved connectivity assertion. No fitted constants or new physical entities are introduced.

assumptions (4)
  • standard math Euler's formula for planar graphs
    Used to derive e = 2n - 4 - F/2 in Section 2, equation (3).
  • domain assumption Disjoint triangular faces in a disk of radius r have total area at most πr^2
    Used in Section 3 to bound the number of triangular faces by O(r^2).
  • domain assumption Two maximal rhombus chains that are not contained in each other share at most one rhombus (Gehér-Tóth [4, Claim 5])
    Self-cited lemma used to bound f4 ≤ C choose 2 in Theorem 1. Not proven in this paper.
  • domain assumption A maximal triangle-free matchstick graph on n vertices is connected
    Stated at the start of the Theorem 1 proof without justification. If a counterexample were disconnected, the counting argument might not apply.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the number of edges of restricted matchstick graphs." pith.science (2026). https://pith.science/paper/P7FMYEBO

@misc{pith2026250601589,
  author       = {Pith},
  title        = {Pith review of: On the number of edges of restricted matchstick graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P7FMYEBO}},
  note         = {Machine review of arXiv:2506.01589}
}
abstract

A graph whose vertices are points in the plane and whose edges are noncrossing straight-line segments of unit length is called a \emph{matchstick graph}. We prove two somewhat counterintuitive results concerning the maximum number of edges of such graphs in two different scenarios. First, we show that there is a constant $c>0$ such that every triangle-free matchstick graph on $n$ vertices has at most $2n-c\sqrt{n}$ edges. This statement is not true for any $c>\sqrt2.$ We also prove that for every $r>0$, there is a constant $\varepsilon(r)>0$ with the property that every matchstick graph on $n$ vertices contained in a disk of radius $r$ has at most $(2-\varepsilon(r))n$ edges.

Figures

Figures reproduced from arXiv: 2506.01589 by the authors.

Figure 1
Figure 1. The √ n × √ n piece of the integer lattice defines a triangle-free matchstick graph with n vertices and 2n − 2 √ n − O(1) edges. Theorem 1. The maximum number of edges e(n) in a triangle-free matchstick graph on n vertices satisfies 2n − √ 2 √ n − O(1) ≤ e(n) ≤ 2n − √ 2 5 √ n. A different constraint that we can put on a matchstick graph is that it must be contained in some fixed bounded region, such as a disk of rad… view at source ↗
Figure 2
Figure 2. Triangle-free matchstick graph on n vertices and j 2n − q 2n − 7 4 − 3 2 k edges for 16 ≤ n ≤ 22. We next prove the upper bound in Theorem 1. Consider a triangle-free matchstick graph G on n vertices and e edges, where e is the maximum among all such graphs on n vertices. By maximality, G is connected. Let fi denote the number of faces of G with i boundary edges, i ≥ 4, where we count a boundary edge twice if the sa… view at source ↗
Figure 3
Figure 3. P is a piece of the lattice generated by vectors ¯a and ¯b. The unit distance graph G defined on these points is a matchstick graph and it has n vertices and e = (2 − 5/r − o(1)) n edges. We continue with the upper bound in Theorem 2. Let G be a matchstick graph on n vertices in D. A triangular face has area √ 3/4 and the area of D is r 2π, therefore, there are at most 4r 2π/√ 3 < 8r 2 triangular faces. Remove an ed… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    B¨ or¨ oczky, K., Kert´ esz, G., Makai, E. Jr. (1999).The minimum area of a simple polygon with given side lengths.Periodica Mathematica Hungarica, 39(1–3), 33–49

    work page 1999

  2. [2]

    (2017).Triangle-free penny graphs: degeneracy, choosability, and edge count.In International Symposium on Graph Drawing and Network Visualization (pp

    Eppstein, D. (2017).Triangle-free penny graphs: degeneracy, choosability, and edge count.In International Symposium on Graph Drawing and Network Visualization (pp. 506–513). Cham: Springer International Publishing

    work page 2017

  3. [3]

    (1946).On sets of distances ofnpoints.The American Mathematical Monthly, 53(5), 248–250

    Erd˝ os, P. (1946).On sets of distances ofnpoints.The American Mathematical Monthly, 53(5), 248–250

    work page 1946

  4. [4]

    (2024).1-planar unit distance graphs.In 32nd International Sympo- sium on Graph Drawing and Network Visualization

    Geh´ er, P., T´ oth, G. (2024).1-planar unit distance graphs.In 32nd International Sympo- sium on Graph Drawing and Network Visualization. Leibniz International Proceedings in Informatics (LIPIcs), Vol. 320, pp. 6:1–6:9, Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik

    work page 2024

  5. [5]

    (1974).Solution to problem 664A.Elemente der Mathematik, 29, 14–15

    Harborth, H. (1974).Solution to problem 664A.Elemente der Mathematik, 29, 14–15

    work page 1974

  6. [6]

    Harborth, H. (1981).Point sets with equal numbers of unit-distant neighbors.(Abstract), Discrete Geometry, 12–18 July 1981, Oberwolfach, Tagungsbericht 31/1981, Mathema- tisches Forschungsinstitut Oberwolfach. pp. 11–12

    work page 1981

  7. [7]

    (1994).Match sticks in the plane.In The Lighter Side of Mathematics

    Harborth, H. (1994).Match sticks in the plane.In The Lighter Side of Mathematics. Proceedings of the Eug` ene Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986., edited by R. K. Guy and R. E. Woodrow, 281–288. Mathematical Association of America, Washington, D.C

    work page 1994

  8. [8]

    (1992).Tiling polygons with parallelograms.Discrete and Com- putational Geometry, 7(2), 175–188

    Kannan, S., Soroker, D. (1992).Tiling polygons with parallelograms.Discrete and Com- putational Geometry, 7(2), 175–188

    work page 1992

Show all 11 references
  1. [9]

    (1993).Tiling a polygon with parallelograms.Algorithmica, 9, 382–397

    Kenyon, R. (1993).Tiling a polygon with parallelograms.Algorithmica, 9, 382–397

    1993

  2. [10]

    Lavoll´ ee, J., Swanepoel, K. J. (2024).A tight bound for the number of edges of matchstick graphs.Discrete and Computational Geometry, 72(4), 1530–1544

    2024

  3. [11]

    Swanepoel, K. J. (2009).Triangle-free minimum distance graphs in the plane.Geombi- natorics, 19(1), 28–30. 10

    2009

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.