Erdős Problem #705

Erdős Problem 705: large girth and unit distances

Statement and status of this reconstruction.

Sources and the geometric qualification.

An explicit graph construction from a hypergraph.

Start with one independent foundation vertex for each vertex of $\mathcal H$. For every hyperedge $E=\{v_1,\ldots,v_k\}$, introduce a fresh cycle $u_{E,1},\ldots,u_{E,k}$ of length $k$, and add the matching edges $v_i u_{E,i}$. Cycles belonging to different hyperedges have disjoint new vertices; foundation vertices may belong to several hyperedges. Call the resulting graph $G$.

Its chromatic number is exactly four.

Its girth is exactly $k$.

Project these successive paths to the incidence graph of $\mathcal H$, replacing each by foundation vertex--hyperedge--foundation vertex. Consecutive hyperedges in this projected closed walk are different: at a fixed foundation vertex there is only one matching edge into each particular attached cycle, so using the same hyperedge immediately twice would repeat that matching edge in the simple cycle $C$. The foundation vertices on $C$ are also distinct. Thus the projected closed walk has no immediate reversal. It contains a cycle in the incidence graph, whose length is at least $2g$ by the Berge-girth assumption. If $C$ has $t$ foundation vertices, its projection has length $2t$, so $t\geq g$ and $|C|\geq3t\geq3g>k$. This proves the girth assertion without assuming that all projected hyperedges are distinct.

What the external embedding result supplies.

Remaining gap for the displayed stronger convention.

Completion estimate.

1) FORMAL RESTATEMENT

Does there exist an integer $k\ge 3$ such that the following holds?

For every finite set $P\subset \mathbb{R}^2$, let $G(P)$ be the graph with vertex set $P$ and an (undirected, simple) edge $\{x,y\}$ between distinct points $x,y\in P$ iff $\|x-y\|_2=1$. If the girth of $G(P)$ is at least $k$ (i.e. $G(P)$ has no cycle of length $<k$; with the convention that an acyclic graph has girth $\infty$), must it follow that the chromatic number satisfies $\chi(G(P))\le 3$?

Edge cases/conventions: - Graphs are finite, simple, undirected. - Girth$(G)=\infty$ if $G$ has no cycles.

2) QUICK LITERATURE/CONTEXT CHECK

I will only use facts explicitly stated in the problem text. The text notes: - There are unit distance graphs with $\chi=4$ and girth $3$ (e.g. Moser spindle). - de Grey constructed a unit distance graph with $\chi=5$. - O'Donnell constructed a unit distance graph with $\chi=4$ and girth $4$. - Wormald constructed a unit distance graph with $\chi=4$ and girth $5$. Hence, if such a $k$ exists, it must satisfy $k\ge 6$.

3) ATTACK PLAN

Disproof strategy: construct, for each $k$, a finite unit distance graph in $\mathbb{R}^2$ with girth $\ge k$ but $\chi\ge 4$. This would show no such universal $k$ exists.

Proof strategy: show that large girth forces enough geometric/graph sparsity (e.g. bounded degeneracy) to imply $3$-colorability for unit distance graphs. A plausible approach would be to derive a structural constraint on unit distance graphs of large girth beyond purely abstract graph theory.

I do not see a route to complete either track here, so I record rigorous partial facts.

4) WORK

Lemma 705.1 (No $K_4$ in a planar unit-distance representation). If $P\subset\mathbb{R}^2$ is any set of points, then the unit distance graph $G(P)$ has clique number at most $3$. Equivalently, there do not exist four distinct points in $\mathbb{R}^2$ with all pairwise distances equal to $1$.

Proof. Assume for contradiction that there exist distinct points $x_1,x_2,x_3,x_4\in\mathbb{R}^2$ with $\|x_i-x_j\|_2=1$ for all $i\ne j$. Then $x_1,x_2,x_3$ form an equilateral triangle of side length $1$. By applying a rigid motion of the plane, we may assume \[ x_1=(0,0),\qquad x_2=(1,0),\qquad x_3=\left(\tfrac12,\tfrac{\sqrt3}{2}\right). \] The condition $\|x_4-x_1\|_2=\|x_4-x_2\|_2=1$ means that $x_4$ lies in the intersection of the two circles of radius $1$ centered at $x_1$ and $x_2$. Solving \[ \|x_4-(0,0)\|_2^2=1,\qquad \|x_4-(1,0)\|_2^2=1 \] shows this intersection consists of the two points \[ \left(\tfrac12,\tfrac{\sqrt3}{2}\right)=x_3\quad\text{and}\quad\left(\tfrac12,-\tfrac{\sqrt3}{2}\right). \] Since $x_4$ is distinct from $x_3$, we must have $x_4=(\tfrac12,-\tfrac{\sqrt3}{2})$. But then \[ \|x_4-x_3\|_2^2=\left(\tfrac12-\tfrac12\right)^2+\left(-\tfrac{\sqrt3}{2}-\tfrac{\sqrt3}{2}\right)^2 = ( -\sqrt3 )^2 = 3, \] so $\|x_4-x_3\|_2=\sqrt3\ne 1$, contradicting the assumed pairwise unit distances. Therefore no such 4-tuple exists, and $\omega(G(P))\le 3$. $\square$

Lemma 705.2 (Moore-type lower bound from girth). Let $G$ be a finite simple graph of minimum degree $\delta\ge 2$ and girth $g\ge 3$. Write $g=2r+1$ (odd) or $g=2r$ (even), where $r\ge 1$. Then \[ |V(G)|\ge \begin{cases} 1+\delta\sum_{i=0}^{r-1}(\delta-1)^i,& g=2r+1,\\ 2\sum_{i=0}^{r-1}(\delta-1)^i,& g=2r. \end{cases} \]

Proof. Fix a vertex $v\in V(G)$. Consider a breadth-first search (BFS) exploration of $G$ starting from $v$. Let $L_i$ be the set of vertices at graph distance exactly $i$ from $v$.

Claim 1: If $g\ge 2r+1$ (odd girth), then the induced subgraph on $\bigcup_{i=0}^r L_i$ is a tree (i.e. has no cycles), and in particular each vertex in $L_i$ ($1\le i\le r$) has at most one neighbor in $L_{i-1}$.

Indeed, if some vertex in $L_i$ had two distinct neighbors in $L_{i-1}$, those two paths back to $v$ together with the two edges into the vertex would create a cycle of length at most $2i\le 2r$, contradicting girth $\ge 2r+1$. Similarly, if there were an edge within $L_i$ for some $i\le r$, combining it with shortest paths to $v$ would create a cycle of length at most $2i+1\le 2r+1$; for $i\le r-1$ this is at most $2r-1$, contradicting the girth bound. (For $i=r$, this would create a cycle of length $2r+1=g$, which is allowed; so for the odd case we only need tree structure up to level $r$ and use the argument below that only counts new vertices, not edges within $L_r$.)

Now we lower bound $|L_i|$ for $i\le r$. We have $|L_0|=1$. Since $\deg(v)\ge\delta$, we have $|L_1|\ge\delta$. For $1\le i\le r-1$, each vertex in $L_i$ has at least $\delta$ neighbors total, at most one in $L_{i-1}$ by Claim 1, and no neighbors in $\bigcup_{j\le i-1}L_j$ other than possibly $L_{i-1}$ (else a shorter path to $v$ exists). Therefore each vertex in $L_i$ contributes at least $\delta-1$ neighbors in $L_{i+1}$, and these neighbors must be distinct (otherwise two vertices in $L_i$ sharing a neighbor in $L_{i+1}$ would create a cycle of length at most $2(i+1)\le 2r$, again contradicting girth $\ge 2r+1$). Hence $|L_{i+1}|\ge (\delta-1)|L_i|$ for $i=1,\dots,r-1$. By induction, $|L_i|\ge \delta(\delta-1)^{i-1}$ for $1\le i\le r$. Summing gives \[ |V(G)|\ge \sum_{i=0}^r |L_i| \ge 1+\sum_{i=1}^r \delta(\delta-1)^{i-1} = 1+\delta\sum_{j=0}^{r-1}(\delta-1)^j, \] which is the claimed bound in the odd case.

Claim 2: If $g\ge 2r$ (even girth), then performing BFS simultaneously from the two endpoints of an edge yields a similar bound.

Pick an edge $uv\in E(G)$. Explore BFS layers outward from the set $\{u,v\}$. Define $L_0=\{u,v\}$ and $L_i$ = vertices at distance exactly $i$ from $\{u,v\}$. A standard girth argument (as above) shows that up to distance $r-1$, these layers form two disjoint trees rooted at $u$ and $v$, so there are no identifications that would create a cycle of length $<2r$. Then $|L_0|=2$, $|L_1|\ge 2(\delta-1)$, and for $1\le i\le r-2$ we again have $|L_{i+1}|\ge (\delta-1)|L_i|$. Thus for $0\le i\le r-1$, $|L_i|\ge 2(\delta-1)^i$. Summing yields \[ |V(G)|\ge \sum_{i=0}^{r-1} |L_i| \ge 2\sum_{i=0}^{r-1}(\delta-1)^i, \] the even case bound. $\square$

Lemma 705.3 (Acyclic case implies $2$-colorable). If $G$ is a graph with girth $\infty$ (i.e. a forest), then $\chi(G)\le 2$.

Proof. Every forest is bipartite: each connected component is a tree, and fixing a root, color vertices by parity of distance from the root. Adjacent vertices differ in distance parity, so edges are properly colored. Thus two colors suffice. $\square$

5) VERIFICATION

- Lemma 705.1 used an explicit coordinate model for an equilateral triangle and checked the only candidates for the fourth point; the distance computation gives $\sqrt3$, so the contradiction is quantitative. - Lemma 705.2: The only subtle point is avoiding short cycles via vertex identifications in BFS layers. The proof explicitly argues that a collision in the BFS tree creates a cycle of length $\le 2r$ (odd case) or $\le 2r-1$ (even case), contradicting the stated girth lower bounds. - Lemma 705.3 is standard and fully verified.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. From the examples stated in the problem text, any such $k$ (if it exists) must satisfy $k\ge 6$ (since there is a unit distance graph with $\chi=4$ and girth $5$). Independently, I proved structural facts: unit distance graphs in $\mathbb{R}^2$ have clique number $\le 3$ (Lemma 705.1), and any graph of minimum degree $\delta\ge 2$ and girth $g$ must have many vertices (Lemma 705.2).

(ii) First gap (crisp). Decide whether there exists a finite unit distance graph $G\subset\mathbb{R}^2$ with girth $\ge 6$ and $\chi(G)\ge 4$.

(iii) Top 3 next moves. 1. Try to build a unit-distance gadget that forces $4$ colors while forbidding cycles up to length $5$, then compose it to raise girth. 2. Try a computational search for small $(\chi=4,\,\text{girth}\ge 6)$ unit distance graphs using constrained coordinate templates (e.g. enforce distances via algebraic coordinates). 3. Seek a geometric sparsity theorem: prove that a unit distance graph in $\mathbb{R}^2$ with girth $\ge k$ must be $3$-degenerate for some absolute $k$.

(iv) Minimal counterexample structure. A minimal counterexample (if it exists for some $k$) can be assumed $4$-critical (removing any vertex drops chromatic number) and to have girth $\ge k$. Such graphs have minimum degree at least $3$ (for $4$-criticality), so Lemma 705.2 would force a rapidly growing vertex count as $k$ increases.