Erdős Problem #99

Erdős Problem #99

1) ROUND-2 OBJECTIVE

I pursue path (A): continue the proof attempt by sharpening the exact small-$n$ theory beyond Round-1. Round-1 proved the sharp $n=4$ statement, but did not determine what happens at $n=5,6,7$. The Round-2 goal is to settle these next cases exactly.

2) Round-1 FOUNDATION USED

I use the following Round-1 result without re-proving it.

• Round-1 proposition: $D(4)=\sqrt2$, and the unit square is a diameter-minimising $4$-point set with no unit equilateral triangle.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is an exact small-$n$ transfer from known results on plane-width / minimum diameter configurations.

Round-2 shows:

• $n=5$: every diameter-minimiser is a regular pentagon of side $1$, so no unit equilateral triangle occurs;
• $n=6$: there exists a diameter-minimiser consisting of the center and vertices of a regular pentagon of circumradius $1$, and it contains no unit equilateral triangle;
• $n=7$: every diameter-minimiser is the center plus the vertices of a regular hexagon of side $1$, so a unit equilateral triangle is forced.

Thus the Round-1 picture "false at $n=4$" sharpens to: \[ \text{false at }n=4,5,6,\qquad \text{true at }n=7. \]

4) ATTACK PLAN (ROUND-2)

The exact gap after Round-1 was the absence of any sharp information between $n=4$ and the asymptotic regime.

To advance, I prove three precise claims:

• determine $D(5)$ and the unique minimiser;
• exhibit a diameter-minimising $6$-point set with no unit equilateral triangle;
• determine the unique minimiser for $n=7$ and verify that it contains a unit equilateral triangle.

This directly addresses the strongest unresolved local obstruction left by Round-1: perhaps the statement already fails at several further small values of $n$.

5) WORK (ROUND-2)

A preliminary observation.

Proposition 1.

Proof.

Now inspect that configuration. In a regular pentagon of side length $1$, the only pairs at distance $1$ are adjacent pairs; every nonadjacent pair is at distance \[ \frac{1+\sqrt5}{2}>1. \] Therefore, among any three vertices, at least one pair is nonadjacent, so the triangle cannot be equilateral of side $1$. Hence every diameter-minimising $5$-point set has no unit equilateral triangle. End of proof.

Proposition 2.

Proof.

So it remains only to verify the absence of a unit equilateral triangle in that specific minimiser. For the regular pentagon of circumradius $1$, \[ |Ov_i|=1 \qquad\text{for all }i, \] the side length is \[ |v_i v_{i+1}|=2\sin 36^\circ>1, \] and the diagonal length is \[ |v_i v_{i+2}|=2\sin 72^\circ>1. \] Therefore the only unit distances in the whole configuration are the five center--vertex distances. Any equilateral triangle of side $1$ would need three unit edges, but no pair of distinct outer vertices is at distance $1$. Hence no unit equilateral triangle exists in this diameter-minimising $6$-point set. End of proof.

Proposition 3.

Proof.

In that configuration, let $v_i,v_{i+1}$ be two adjacent vertices of the regular hexagon. Then \[ |Ov_i|=|Ov_{i+1}|=1 \] because the circumradius of a regular hexagon equals its side length, and also \[ |v_i v_{i+1}|=1. \] Hence the triangle $Ov_i v_{i+1}$ is an equilateral triangle of side $1$. Because the minimiser is unique up to similarity, every diameter-minimising $7$-point set contains such a triangle. End of proof.

Conclusion of the Round-2 work.

6) ADVERSARIAL VERIFICATION

• Did I use the exact external theorems correctly? Yes. For $n=5$ I used the exact value and uniqueness of the plane-width of $K_5$; for $n=6,7$ I used the exact diameter values and the extremal configurations from Bateman--Erdős.
• Could there still be a unit equilateral triangle in the $n=5$ or $n=6$ extremisers? No. In the regular pentagon, nonadjacent pairs have length $\frac{1+\sqrt5}{2}>1$, so no three vertices form a unit equilateral triangle. In the $n=6$ pentagon-plus-center configuration, the only unit edges are center--vertex edges, so three mutually unit distances are impossible.
• Does the $n=7$ argument really give a forced triangle in every minimiser? Yes, because the extremiser is unique up to similarity.
• Interaction with Round-1. Round-1 only handled $n=4$. Round-2 settles the next three cases exactly.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round-2 proves exact new information: \[ n=5,6 \text{ are counterexample sizes},\qquad n=7 \text{ is a positive size}. \] So the first four nontrivial cases are now completely understood: \[ n=4,5,6 \text{ fail},\qquad n=7 \text{ holds}. \] The original asymptotic question remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

1. P. Bateman and P. Erdős, Geometrical extrema suggested by a lemma of Besicovitch, Amer. Math. Monthly 58 $1951$, no. 5, 306--314.
2. M. Kamiński, P. Medvedev, and M. Milanič, The plane-width of graphs, J. Graph Theory 68 $2011$, no. 3, 229--245.

Erdős Problem #99: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 99.tex. The supplied attempt concerns only the small cases $4\le n\le7$ and imports exact optimization and uniqueness theorems. I do not extrapolate those cases. The following is a self-contained necessary structure theorem for any putative triangle-free minimizer.

2) WORK

A triangle in this graph is exactly the desired unit equilateral triangle. Thus any counterexample has a simple planar triangle-free contact graph. For $n\ge3$, it has \[ e\le2n-4. \] For a connected component containing a cycle, each face boundary walk has length at least four; hence $2e\ge4f$, and Euler's formula gives the bound. Tree components have even fewer edges; joining components by noncrossing bridges if necessary gives the same global inequality. In particular some vertex has contact degree at most three, since the average degree is less than four.

This suggests examining low-contact vertices of an optimal configuration, but the geometric objective includes maximal-distance constraints as well as contacts.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

Erdős Problem #99

1. Formal Restatement.

   For a finite set $A\subset\mathbb{R}^2$, define \[ \delta(A):=\min\{\|x-y\|:x,y\in A,\ x\ne y\}\quad\text{(minimum pairwise distance)}, \] \[ \operatorname{diam}(A):=\max\{\|x-y\|:x,y\in A\}\quad\text{(diameter)}. \] For each $n\ge 2$, let \[ D(n):=\inf\{\operatorname{diam}(A): A\subset\mathbb{R}^2,\ |A|=n,\ \delta(A)\ge 1\}. \] By scaling, this is equivalent to restricting to $\delta(A)=1$. A set $A$ is diameter-minimising if $|A|=n$, $\delta(A)\ge 1$, and $\operatorname{diam}(A)=D(n)$.

   Question $\#99$. For all sufficiently large $n$, must every diameter-minimising $A$ contain three points that form an equilateral triangle of side length $1$?

2. Quick literature/context check.

   The Erdős Problems page lists this as open (last edited date not shown on the page extract above, but accessed 2026-01-17).[ErdosProblems99] It notes that asymptotically the minimal diameter is achieved by points arranged like a triangular (hexagonal) lattice intersected with a disk ("Thue's theorem" on densest circle packing underlies this asymptotic picture).[ErdosProblems99] It also notes the statement is false for $n=4$ (a diameter-minimising configuration can be a unit square, which has no unit equilateral triangle) and that small $n$ are studied by Bezdek--Fodor $1999$.[ErdosProblems99,BeFo99]

3. Attack plan.

   Proof track. Show that any diameter-minimiser must be "close enough" to the triangular lattice that it forces at least one exact unit equilateral triangle. A possible route is to study the contact graph of unit distances (tangencies of radius-$1/2$ disks), show many contacts are forced in an extremiser, and then prove that sufficiently dense unit-circle packings necessarily contain a triangular face (a $3$-cycle) which corresponds to a unit equilateral triangle.

   Disproof track. Construct, for arbitrarily large $n$, a diameter-minimising configuration whose unit-distance graph is triangle-free (equivalently, has no triple of pairwise unit distances), hence contains no unit equilateral triangle. The difficulty is that being diameter-minimising is a global extremal condition, so one must match the true optimum $D(n)$.

   Phase 1 small cases. Check $n=3$ (equilateral triangle is optimal) and $n=4$ (square configuration) to understand behaviour at the first nontrivial sizes.

4. Work.

   I did not resolve the "sufficiently large $n$" question. I provide a fully proved sharp statement for $n=4$ (consistent with the remark in the problem statement) as a concrete verified base case.

   A proved base case: $n=4$.

   Proposition: Let $A\subset\mathbb{R}^2$ be a set of $4$ points with $\delta(A)\ge 1$. Then $\operatorname{diam}(A)\ge \sqrt{2}$. Moreover, equality is achieved (for example) by the vertices of a unit square. Consequently, there exists a diameter-minimising $4$-point set with $\delta(A)=1$ that contains no unit equilateral triangle.
   Proof: Let $A=\{p_1,p_2,p_3,p_4\}$ with all pairwise distances $\ge 1$. Let $\operatorname{diam}(A)=D$. Consider the convex hull $\operatorname{conv}(A)$.

   Case 1: $\operatorname{conv}(A)$ is a quadrilateral. Then all four points are vertices of a convex quadrilateral. In any convex quadrilateral, at least one interior angle is $\ge 90^\circ$ (otherwise the sum of four angles would be $<4\cdot 90^\circ=360^\circ$). Assume without loss of generality that the angle at vertex $p_2$ in the quadrilateral $p_1p_2p_3p_4$ is $\angle p_1p_2p_3\ge 90^\circ$. In the triangle $p_1p_2p_3$, by the law of cosines, \[ \|p_1-p_3\|^2 =\|p_1-p_2\|^2+\|p_2-p_3\|^2-2\|p_1-p_2\|\,\|p_2-p_3\|\cos(\angle p_1p_2p_3) \ge \|p_1-p_2\|^2+\|p_2-p_3\|^2, \] because $\cos(\angle p_1p_2p_3)\le 0$. Since $\|p_1-p_2\|\ge 1$ and $\|p_2-p_3\|\ge 1$, we obtain \[ \|p_1-p_3\|^2 \ge 1^2+1^2 =2, \] so $\|p_1-p_3\|\ge \sqrt{2}$. Therefore $D\ge \sqrt{2}$.

   Case 2: $\operatorname{conv}(A)$ is a triangle. Then three of the points, say $p_1,p_2,p_3$, are the triangle's vertices and the remaining point $p_4$ lies strictly inside that triangle. Because $p_4$ is inside, the rays from $p_4$ to $p_1,p_2,p_3$ partition the full angle $2\pi$ around $p_4$ into three angles whose sum is $2\pi$. Hence at least one of these angles is $\ge 2\pi/3$; without loss of generality, \[ \angle p_1p_4p_2 \ge \frac{2\pi}{3}. \] Using the law of cosines in triangle $p_1p_4p_2$ and the distance bounds $\|p_1-p_4\|\ge 1$, $\|p_2-p_4\|\ge 1$, we get \[ \|p_1-p_2\|^2 =\|p_1-p_4\|^2+\|p_2-p_4\|^2-2\|p_1-p_4\|\,\|p_2-p_4\|\cos(\angle p_1p_4p_2) \ge 1+1-2\cdot 1\cdot 1\cos\left(\frac{2\pi}{3}\right)=3. \] Thus $\|p_1-p_2\|\ge \sqrt{3}$, and in particular $D\ge \sqrt{3}>\sqrt{2}$.

   In both cases, $\operatorname{diam}(A)=D\ge \sqrt{2}$. Equality is achieved by the vertices of a unit square, which satisfy $\delta(A)=1$ and $\operatorname{diam}(A)=\sqrt{2}$. A unit square contains no equilateral triangle of side $1$ (any triple of vertices has side lengths $\{1,1,\sqrt{2}\}$). ∎

   Remarks toward large $n$ (not a solution).

   The conjecture "large $n$ forces a unit equilateral triangle in every diameter-minimiser" can be interpreted as a rigidity statement about optimal finite circle packings: asymptotically optimal packings resemble the triangular lattice, which has abundant unit equilateral triangles. The challenge is to bridge from an asymptotic density statement to the existence of an exact unit equilateral triangle in the finite extremiser.

5. Verification.

   Proposition Proposition is self-contained and checks both combinatorial hull cases. It also cleanly separates the two geometric possibilities for four points. The conclusion about absence of a unit equilateral triangle in a unit square is immediate by inspection of distances.

6. FINAL: UNRESOLVED.
   • (i) Strongest fully proved partial result: Proposition Proposition: $D(4)=\sqrt{2}$ and there exists a diameter-minimising configuration (unit square) with no unit equilateral triangle.
   • (ii) Most plausible route forward: Relate diameter-minimisation to forced structure in the unit-distance (tangency) graph of the associated circle packing; prove that sufficiently optimal finite packings must contain a triangular face (a $3$-cycle) in the contact graph, which would be a unit equilateral triangle.
   • (iii) First place the proof attempt breaks: Current arguments from asymptotic optimality (triangular lattice density) do not directly imply the existence of an exact unit equilateral triangle in the finite extremiser, because one may imagine perturbations that preserve diameter while breaking exact unit-triangle equalities.
   • (iv) What a counterexample would have to look like: An infinite family of diameter-minimising sets $A_n$ with $\delta(A_n)=1$ and no triple of points forming an equilateral triangle of side $1$.

7. Completion estimate.

   COMPLETION: 20%.

References

• [Er86] P. Erdős, On some metric and combinatorial geometric problems, Discrete Mathematics 60 $1986$, 147--153.
• [FiRe92] P. C. Fishburn and J. A. Reeds, Unit distances between vertices of a convex polygon, Computational Geometry 2 $1992$, no. 2, 81--91.
• [EFPR93] P. Erdős, Z. Füredi, J. Pach, and I. Z. Ruzsa, The grid revisited, Discrete Mathematics 111 $1993$, 189--196.
• [GK15] L. Guth and N. H. Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics 181 $2015$, 155--190.
• [BeFo99] A. Bezdek and F. Fodor, Minimal diameter of certain sets in the plane, Journal of Combinatorial Theory, Series A 85 $1999$, no. 1, 105--111.