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