Harborth's Conjecture

Harborth’s Integer-Length Drawing Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A straight-line planar drawing maps distinct vertices to distinct plane points and draws every edge as the segment between its endpoints, with disjoint edge interiors except for allowed common endpoints. Require the Euclidean length of every edge to be a positive integer. Rational-length drawings are equivalent by a common scaling because the graph has finitely many edges. [S1] [S2]

Statement recorded in the supplied source.

Can every planar graph be drawn with integer edge lengths? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Handle unrestricted planar graphs, in particular the unresolved degree-five insertion geometry in triangulations. [S1]

Short English statement

Can every finite planar graph be drawn without crossings using straight edges that all have integer lengths?

Research attempt

Status: UNRESOLVED. We construct rational-coordinate, rational-length plane drawings of every finite tree, prove the scaling equivalence for rational edge lengths, and analyze why rational coordinate approximation does not solve the general planar case. The missing step is simultaneous rational-distance insertion with several neighbours.

Literature and scope check.

Kintali [S3], version 2 primary abstract consulted 1 October 2026, reports progress through rational-distance insertion in quadrilateral configurations and explicitly leaves further polygon cases for subsequent work. We do not treat that paper as a full solution. The canonical target requires integer edge lengths, without requiring integer vertex coordinates. Our tree construction proves the stronger coordinate property for that special class only.

Finite rational lengths can be scaled at once.

If a finite crossing-free straight-line drawing has positive rational edge lengths $a_e/b_e$, choose a positive common multiple $M$ of their denominators. Scaling every point by $M$ multiplies each edge length by $M$ and preserves distinct vertices and all incidences and nonintersections. The new lengths are positive integers. No assertion about the coordinates is needed for this equivalence. If the coordinates are rational too, enlarge $M$ to include their finitely many denominators and obtain integer coordinates as well.

The word finite matters: a single common denominator need not exist for an infinite family. Scaling also cannot turn a general irrational length into an integer merely because its squared length is rational.

Rational directions are dense.

For rational $t$, put \[ u(t)=\left(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\right). \] Both coordinates are rational and $|u(t)|=1$, as follows by expanding the sum of their squares. This parametrizes the unit circle except one point as $t$ ranges over the real numbers. Since rational numbers are dense and the parametrization is continuous on finite parameter intervals, rational unit directions meet every nonempty open arc of the circle. This gives exact rational-length steps in arbitrarily small selected angular sectors.

Inductive construction for trees.

Start with the one-vertex drawing at the origin. Suppose a smaller tree has already been drawn with rational coordinates, rational positive edge lengths, and no crossings. Attach a new leaf at an existing vertex $v$. Because the drawing is finite, choose a sufficiently small disk about $v$ containing no other vertex and meeting no nonincident edge. The finitely many incident edge directions leave a nonempty open angular sector at $v$ disjoint from all those edges.

Choose a rational unit direction $u(t)$ in that sector and a positive rational length $\varepsilon$ smaller than the disk radius. Place the new vertex at $v+\varepsilon u(t)$. Its coordinates are rational, its distance to $v$ is exactly $\varepsilon$, and its segment to $v$ stays inside the chosen disk and sector. It meets no old edge except at the allowed common endpoint $v$. The new vertex is distinct from all old vertices.

Every finite tree can be built by adding leaves in a rooted order, so induction completes the construction. A final common scaling gives a plane integer-length drawing with integer vertex coordinates. For a forest, draw its components separately and translate them by sufficiently large rational vectors to obtain disjoint containing disks before scaling. This is an exact existence proof, not an assertion that a preselected unit length works at every insertion.

Why coordinate approximation is insufficient.

The set of crossing-free placements of a fixed finite straight-line drawing with no degeneracies contains a neighborhood of that placement. Rational coordinate tuples are dense, so one can approximate the drawing by a rational-coordinate plane drawing. However a segment with rational endpoint coordinates has length $\sqrt q$ for rational $q\ge0$, and that need not be rational. The segment from $(0,0)$ to $(1,1)$ has length $\sqrt2$. Thus density of rational coordinates does not imply density of simultaneously rational edge lengths.

Independently changing an edge length is not a free operation either: its endpoints are shared with other edges. The one-neighbour leaf insertion succeeds because a rational circle parametrization controls its only new length. Two or more fixed neighbours impose simultaneous circle-distance equations.

An algebraic diagnostic for multiple neighbours.

Let $A,B,C$ be three noncollinear rational points and suppose a point $P=(x,y)$ has rational distances $r_A,r_B,r_C$ to them. Subtracting the squared-distance equations for $A$ and $B$, and then for $A$ and $C$, eliminates $x^2+y^2$ and gives two independent linear equations in $x,y$ with rational coefficients and rational right sides. Noncollinearity makes their coefficient matrix invertible, so $x,y$ are rational.

This is a necessary consequence, not an existence theorem. Selecting arbitrary rational values for the three distances solves the two linear differences but may fail the remaining quadratic equation, and may place the point outside the required face. With additional neighbours there are further compatibility constraints. A local insertion lemma must meet all those equations and preserve the geometry simultaneously.

Verification and exact remaining gap.

The tree induction explicitly excludes crossings with both incident and nonincident edges, retains positive lengths, and allows rational choices at every finite step. No exhaustive planar-graph computation or formal verification is claimed. The algebraic check on three distances uses noncollinearity; for collinear centres the two linear equations can be dependent.

The unresolved step is a general simultaneous rational-distance construction compatible with insertion inside the relevant faces of planar graphs. Approximating coordinates, multiplying denominators, or appealing to the tree argument does not provide it. The full Harborth conjecture remains unresolved by this attempt.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1405 (GRAPH-018), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 D. J. Chang and T. Sun, Harborth's Conjecture for 4-Regular Planar Graphs, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), LIPIcs 320, Article 38. https://doi.org/10.4230/LIPIcs.GD.2024.38. Bibliographic information from the supplied record.

• S3 S. Kintali, On the Harborth Conjecture. Part I, arXiv:2607.02535 $2026$. https://arxiv.org/abs/2607.02535. Bibliographic information from the supplied record.