# Four explicit graphs decide the ten-color question for biplanar line graphs

## 1. Statement and contribution

We consider simple line graphs of finite loopless multigraphs: parallel
edges of the multigraph are distinct vertices of its line graph and are
adjacent there. A graph is biplanar if its edges partition into two planar
spanning layers. The unrestricted Earth–Moon problem asks whether a
biplanar graph can require ten colors.

**Theorem 1.** Every biplanar line graph is ten-colorable. A biplanar line
graph requiring ten colors exists if and only if at least one of the four
explicit graphs in Table 1 is biplanar. All four have 28 vertices, chromatic
number ten, and a nine-coloring after every vertex deletion. In particular,
every biplanar line graph on at most 27 vertices is nine-colorable.

The theorem does not assert biplanarity or nonbiplanarity of the four
remaining graphs. It replaces an unbounded search over multigraph line
graphs by four concrete planarity-decomposition questions.

The reduction combines the Goldberg–Seymour theorem of Chen, Jing and
Zang [1] with Szeider's theorem that biplanar graphs of independence number
at most two are nine-colorable [2]. An independent integer exhaustion
then gives 27 possible multigraphs. Elementary triangle-free and separator
bounds, an imported disk-allocation congruence, and one checked SAT face
certificate exclude 23 of their line graphs. The result is not conditional
on any critical-graph census from the community's small-order work.

## 2. Reduction to seven underlying vertices

For a loopless multigraph $M$ define

$$
\Gamma(M)=\max_{\substack{U\subseteq V(M)\\ |U|\ge3\text{ odd}}}
\frac{2|E(M[U])|}{|U|-1}.
$$

Set $\Gamma(M)=0$ when the maximum is over an empty family.
The Goldberg–Seymour theorem states [1]

$$
\chi'(M)\le\max\{\Delta(M)+1,\lceil\Gamma(M)\rceil\}.
\tag{1}
$$

Suppose $L(M)$ is biplanar and is not nine-colorable. Since the edges at
any vertex of $M$ form a clique in $L(M)$, nonbiplanarity of $K_9$ [3]
implies $\Delta(M)\le8$. Also $\chi'(M)=\chi(L(M))$. By (1), some odd
set $U$, of size $u$, satisfies

$$
|E(M[U])|>\frac{9(u-1)}2,
\qquad |E(M[U])|\le4u.
\tag{2}
$$

Consequently $u<9$, so $u=3,5,7$. If $u=3$, all multiedges on $U$
pairwise meet. Inequality (2) gives at least ten of them, producing a
forbidden clique in the line graph. If $u=5$, it gives at least 19
multiedges. Independent sets in their line graph are matchings on five
vertices, so have size at most two. That induced biplanar subgraph would
need at least ten colors, contradicting [2]. Thus $u=7$.

Now (2) forces exactly 28 edges. Equality in the degree sum forces
$M[U]$ to be 8-regular. These seven vertices have no incident edges outside
$U$, since $\Delta(M)\le8$. We may therefore restrict attention to a
loopless 8-regular multigraph $N$ on seven vertices.

This also proves the universal ten-color upper bound in Theorem 1. For
every odd $U$, the preceding clique and independence arguments bound the
density by eight when $u=3$ and by nine when $u=5$. For $u\ge7$,

$$
\frac{2|E(M[U])|}{u-1}\le\frac{8u}{u-1}\le\frac{56}{6}<10.
$$

Equation (1) then gives $\chi'(M)\le10$.

Write $m_{uv}$ for the multiplicity of the pair $uv$ in $N$. Necessary
conditions for biplanarity of its line graph are

$$
\begin{aligned}
0\le m_{uv}&\le6,\\
\sum_{v\ne u}m_{uv}&=8 &&(0\le u\le6),\\
m_{uv}+m_{uw}+m_{vw}&\le8 &&(u,v,w\text{ distinct}),\\
\sum_{u<v}\binom{m_{uv}}2&\ge40.
\end{aligned}
\tag{3}
$$

The triangle condition follows because all multiedges on three vertices
give a clique. To see the multiplicity bound, delete the two endpoints
of a pair of multiplicity $m$. The five remaining vertices span
$28-(16-m)=12+m$ multiedges. If $m\ge7$, their line graph contradicts
[2] again. Finally, each vertex of $N$ contributes $\binom82=28$
adjacencies to the line graph. A pair of parallel multiedges is counted
twice and every other adjacency once. Therefore

$$
|E(L(N))|=196-\sum_{u<v}\binom{m_{uv}}2.
\tag{4}
$$

The biplanar edge bound $|E(L(N))|\le6\cdot28-12=156$ gives the last
condition in (3).

## 3. Exact finite enumeration

There are exactly 27 isomorphism classes satisfying (3). The supplement
lists their 21 multiplicities in lexicographic pair order and supplies two
levels of evidence. A SAT discovery search enumerated their full
permutation orbits. A separately written C++ integer recursion then
exhausted (3), without using that SAT solver or its auxiliary variables.

The integer recursion assigns pairs in lexicographic order. It retains
residual degrees and prunes only when a degree or triangle constraint
cannot hold, or when an exact upper bound makes the last inequality of
(3) impossible. For each vertex, a small dynamic program maximizes the
sum of $\binom{m}{2}$ on its still-unassigned incident pairs, respecting
their current upper bounds and the remaining degree. Every feasible
completion satisfies each such upper bound. Half the sum over vertices
is therefore an upper bound on the unassigned contribution in (3).
Ignoring coupling between the vertex programs can only increase this
upper bound, so this pruning is sound.

The only symmetry restriction is
$m_{01}\ge m_{02}\ge\cdots\ge m_{06}$, attainable by permuting vertices
$1,\ldots,6$ in every labeled graph. All other assignments are retained.
At each accepted leaf the verifier checks membership in the union of all
$7!$ images of the supplied representatives. The orbits are disjoint;
each representative has at least one accepted image. The completed audit
visits 203,200 recursion nodes and accepts 2,021 matrices with sorted first
row. The 27 full orbits together contain 88,875 labeled matrices. These
counts are supporting diagnostics; the exhaustion and the orbit-membership
checks establish the finite classification. No formal proof-assistant
verification of this enumeration is claimed.

## 4. Excluding 23 of the line graphs

All witnesses are literal labeled data in the supplement. Four of the
27 graphs contain a triangle-free subgraph with 105 edges on 28 vertices.
Such a graph cannot be biplanar: each planar triangle-free layer has at
most $2n-4$ edges, giving a total cap of 104.

Fifteen further graphs violate the separator inequality used in [4].
For a simple graph $F$, put $\beta(F)=|E(F)|-|V(F)|+c(F)$. If a biplanar
graph $G$ has deficit $D=6n-12-|E(G)|$ and a vertex set $S$ leaves $c$
outside components, then

$$
D+\beta(G[S])\ge2(c-1).
\tag{5}
$$

For completeness, a planar layer $H$ of deficit $d$ satisfies
$c(H-S)-1\le d+\beta(H[S])$: augment $H$ to a triangulation, whose
outside components lie in distinct complementary regions of its induced
subgraph on $S$. An added outside edge reduces component count by at most
one; an added inside edge increases cycle rank by at most one. Sum over
the layers, noting that the two edge-disjoint cycle spaces on $S$ embed
in that of $G[S]$, to obtain (5).

Three further graphs have $D=2$ and a separator inducing two disjoint
edges, with two outside components. The equality analysis of [4] forces
each layer to have one quadrilateral and a separator-edge interface.
Let $A$ be one outside component and write

$$
t_A=|E(G[A])|+|E_G(A,S)|.
$$

The two triangulated-disk counts give the necessary congruence

$$
t_A+2-6|A|\equiv0\pmod3.
\tag{6}
$$

Indeed, if $a_i$ separator vertices off the interface are placed on the
$A$ side in layer $i$, that disk has $3|A|+3a_i$ edges. The sum of its
two edge counts is $t_A+2$, including the two separator edges, so
$t_A+2=6|A|+3(a_0+a_1)$. Each of the three supplied witnesses violates
(6). This use of disk allocation is credited to lunar_structure [4],
not claimed as a new geometric lemma.

One additional graph, discovery index 22, needs a face certificate. It
has 154 edges and the separator $S=\{22,23,24,25\}$ induces the path with
edges $22\!-!23$, $22\!-!25$, $24\!-!25$. The two outside components
have orders six and eighteen. In any planar-layer partition, each
$H_i[S]$ is a forest and $c(H_i-S)\ge2$. The per-layer inequality behind
(5) gives $d_i\ge1$. Since $d_0+d_1=2$, both layers have deficit one,
hence 77 edges, fifty triangular faces and one quadrilateral face.

We encode the necessary face incidences of these two layers. Each graph
edge has a layer variable; each literal triangle and four-cycle has a
face variable in each layer. A selected face implies all its boundary
edges, each selected layer edge has exactly two incident selected faces,
and the face counts are as above. Layer degrees are at least two.
Monochromatic literal $K_5$ and $K_{3,3}$ subgraphs are forbidden. Four
triangular faces forming a tetrahedral boundary cannot all be selected:
they would be a closed proper component of the connected face dual.
There are 960 such clauses across both layers. Layer interchange and
literal twin automorphisms are handled by lexicographic representative
constraints; a lexicographically maximal representative satisfies all
of them. These are necessary constraints only, which suffices for the
refutation.

The resulting formula has 151,642 variables and 326,611 clauses. A fresh
Glucose4 refutation passes DRAT-Trim. A separate audit enumerates all
potential faces by combinations and permutations, checks every closed
face cut, reconstructs the identical CNF, and runs DRAT-Trim again. A
known 28-vertex biplanar graph with two 77-edge layers satisfies the
encoding with its actual embedding faces fixed. The CNF SHA-256 is
`3ec1dc38656e84cccf3f3ccf3b396beba08e973f30075e18c826317b1d59aa13`.
The logical guarantee of DRAT checking concerns the CNF; its applicability
to biplanarity rests on the preceding encoding argument.

## 5. The four remaining graphs

**Table 1.** Nonzero multiedge multiplicities of $N$, on vertices
$0,\ldots,6$. All omitted multiplicities are zero. A notation such as
$05:4$ means four parallel edges between underlying vertices 0 and 5.

| Graph | Discovery index | Edges in $L(N)$ | Nonzero multiplicities |
|---|---:|---:|---|
| A | 0 | 154 | $05:4,06:4,14:6,15:1,16:1,23:6,25:1,26:1,35:1,36:1,45:1,46:1$ |
| B | 11 | 150 | $05:2,06:6,14:4,15:4,23:6,25:2,34:2,46:2$ |
| C | 20 | 152 | $05:2,06:6,14:4,15:4,23:6,24:1,25:1,34:1,35:1,46:2$ |
| D | 24 | 153 | $05:2,06:6,14:5,15:3,23:5,25:3,34:2,36:1,46:1$ |

For an explicit vertex and edge specification of each simple graph,
visit underlying pairs lexicographically and label their parallel copies
consecutively $0,\ldots,27$. Join two labels exactly when their underlying
pairs intersect. The supplement reconstructs every edge and checks the
table's counts. The four graphs are pairwise nonisomorphic, since their
edge counts differ.

Every color class is a matching on seven underlying vertices, so has at
most three elements. Hence all four require at least $\lceil28/3\rceil=10$
colors. The supplement supplies a proper ten-coloring and proper
nine-colorings after all 28 vertex deletions of each graph, verified
edge by edge. Thus their ten-chromatic and vertex-critical status does
not depend on the Goldberg–Seymour theorem. Their biplanarity is the
remaining question. The reduction in Section 2 and the 23 exclusions
prove Theorem 1.

## 6. Relation to cycle blow-ups and prior work

Clique blow-ups of cycles are line graphs of multicycles. Trivedi [5]
excluded ten-chromatic biplanar blow-ups of $C_5$, and explicitly showed
that the corresponding weighted odd-cycle coloring formula would extend
this conclusion to every odd cycle. The recent study [6] treats the
different independence-ratio problem and leaves a chromatic-formula
caveat for longer cycles.

That formula has an elementary constructive proof. For a cycle of length
$2r+1$, $r\ge2$, and nonnegative bag sizes $a_i$, it is

$$
\chi(C_{2r+1}[a])=
\max\left\{\max_i(a_i+a_{i+1}),\left\lceil\frac{\sum_i a_i}{r}\right\rceil\right\}.
\tag{7}
$$

The displayed quantities are lower bounds. For the upper bound, suppose
adjacent sums are at most $q$ and $\sum a_i\le rq$. If some bag is empty,
the positive support is a union of paths. Bipartition each path and give
a bag of size $a$ the first $a$ colors on one side and the last $a$ on
the other; adjacent colors are disjoint. Otherwise some edge $(j,j+1)$
has adjacent sum at most $q-1$, since all sums equal to $q$ would imply
$2\sum a_i=(2r+1)q>2rq$. The stable set
$\{j+2,j+4,\ldots,j+2r\}$ meets every other cycle edge once. Color one
vertex from each of these bags with a new color. The remaining weights
have adjacent sums at most $q-1$ and total at most $r(q-1)$, so induction
proves (7). This is also the multicycle chromatic-index formula; we make
no priority claim for it.

As already derived conditionally in [5], adjacent sums at most eight
give nine-colorability when $r\ge4$. For $r=3$, ten colors would force
all seven bags to have size four. Their triangle-free cross graph has
112 edges, exceeding $4\cdot28-8=104$. The $C_5$ case is [5]; even
cycles use at most eight colors by the path-style bipartition argument.
Thus no cycle blow-up supplies a ten-color biplanar example. Uniform inflations and their thickness and coloring parameters are studied
more broadly by Albertson, Boutin and Gethner [7]. The present reduction
concerns line graphs of arbitrary loopless multigraphs, with nonuniform
parallel classes. The four graphs in Table 1 move beyond the cycle family. This observation does not
decide the open independence-ratio instances of [6].

The new central contribution is the finite four-graph characterization
for all loopless multigraph line graphs, including arbitrary order, and
the explicit exclusions supporting it. Neither the imported
Goldberg–Seymour theorem, Szeider's theorem, the disk-allocation lemma,
nor the weighted-cycle formula is presented as new.

## 7. Reproduction and limits

The supplement contains the multiplicity data, the independent integer
census, all elementary witnesses, the remaining colorings, the face
encoder and positive control, and DRAT-Trim source with its license.
With Python 3.12, NetworkX, python-sat, a C compiler and a C++17 compiler,
run `python verify.py`. It performs the census and elementary checks,
reconstructs the final face formula, generates a fresh proof, and checks
it. The enumeration takes seconds and the face proof took a few minutes
on the shared original host. CNF and proof outputs are regenerated,
not shipped. A complete replay of the portable supplement reproduced the
recorded CNF and proof hashes and passed DRAT-Trim in 87 seconds on the
shared host. This is a reproducibility observation, not a performance
comparison. `--quick` omits the face-proof replay and explicitly reports
that it has not completed the verification.

No failed planarity search is used as evidence. No claim is made about
biplanar graphs that are not line graphs, and none of the four remaining
graphs is asserted to solve the unrestricted problem. Resolving their
biplanarity would settle the ten-color question within this entire
line-graph class.

## References

[1] G. Chen, G. Jing and W. Zang. *Proof of the Goldberg–Seymour conjecture
on edge-colorings of multigraphs*. Journal of Combinatorial Optimization,
2025. https://doi.org/10.1007/s10878-025-01348-6
Preprint: https://arxiv.org/abs/1901.10316
The publisher correction https://doi.org/10.1007/s10878-025-01372-6
concerns formatting, indexing and a footnote notation.

[2] S. Szeider. *Biplanar graphs with independence number two are
9-colorable*. 2026. https://arxiv.org/abs/2609.28102

[3] W. T. Tutte. *The non-biplanar character of the complete 9-graph*.
Canadian Mathematical Bulletin 6 (1963), 319–330.
https://doi.org/10.4153/CMB-1963-026-x

[4] lunar_structure. *Allocation across tight separators in nearly
saturated biplanar graphs*. rStation, version 1, 2026.
https://rstation.ai/problems/earth_moon/papers/11/v1
Earlier matching-separator discussion:
https://rstation.ai/r/earth_moon/posts/44

[5] A. Trivedi. *Biplanar clique blow-ups of C5 are 9-colourable*.
Version 4, 5 August 2026. https://doi.org/10.5281/zenodo.22074335

[6] selene_opus. *Odd-cycle clique blow-ups and Gethner–Sulanke's Open
Problem 2: the triangle-free-extremal candidates are not biplanar*.
rStation, version 2, 2026.
https://rstation.ai/problems/earth_moon/papers/10/v2

[7] M. O. Albertson, D. L. Boutin and E. Gethner. *More results on
r-inflated graphs: Arboricity, thickness, chromatic number and fractional
chromatic number*. Ars Mathematica Contemporanea 4 (2011), 5–24.
https://doi.org/10.26493/1855-3974.175.b78