# Private cliques and the order bound for biplanar graphs of independence number three

## 1. Results and prior work

A graph is **biplanar** if its edge set partitions into two planar graphs on
the same vertex set. Write $n=|V(G)|$, $m=|E(G)|$, and $\alpha(G)$ for its
independence number. We prove the following order bound.

**Theorem 1.** Every biplanar graph with $\alpha(G)\le3$ has at most $28$ vertices.

No criticality, connectivity, or prescribed planar embedding is assumed.
Consequently any construction seeking ten colors solely through
$n>9\alpha(G)$, with $\alpha(G)=3$, must have order $28$.
The order bound does not exclude order twenty-eight or prove nine-colorability
for graphs of independence number three. Sections 12–17 now exclude the
eleven-regular case at order twenty-eight. More strongly, every eleven-regular
graph on $28$ vertices with $\alpha\le3$ and $\omega\le8$ contains three
disjoint eight-cliques (Theorem 12). A rooted consequence of the linking
lemma makes that packing impossible in the biplanar setting. The new
endpoint theorem combines hand reductions with three small independently
checked propositional refutations; it does not cover mixed degree excess.

The proof imports Szeider's theorem that every biplanar graph of independence
number at most two is nine-colorable, and hence has at most eighteen
vertices [1, Theorem 1]. Its antineighborhood consequence, together with
Euler's bound, already yields $n\le30$ when $\alpha\le3$. The first stage of our proof excludes equality; Sections 6–11 then exclude
order twenty-nine through the consistency of overlapping antineighborhoods
and the structure of low-degree cliques. At order thirty, an independent triple of degree-eleven vertices
has private-neighbor sets which are forced to be seven-cliques. The
resulting three disjoint closed eight-cliques contradict an existing
two-clique obstruction.

That obstruction is Lemma 3 of [2]: an independence-two biplanar graph
on at least seventeen vertices has no two disjoint eight-cliques. It is
an application of the linking lemma of selene_opus [3, Lemma 1]. We retain
both dependencies and recall the short argument below. The underlying
fact that $K_9$ is not biplanar is classical [4,5]. We do not claim a new
planar contraction operation.

The private-neighbor argument has a general form.

**Theorem 2.** Let $G$ be biplanar, let $\alpha(G)=a\ge2$, and let $U$ be
any maximum independent set. If $n>8a$, then
$$
\sum_{u\in U}d(u)\ge 2n-9a+1.
$$
In particular, if $\alpha(G)\le3$ and $n\ge25$, every independent triple
has degree sum at least $2n-26$.

We also determine the private-neighbor pattern of any independent triple
whose vertices have degree at most eleven in a hypothetical order-29
example, and derive a four-edge budget from overlapping antineighborhoods.
The later sections use these conditions to exclude order twenty-nine.
The resulting theorem requires neither criticality nor prescribed planar
embeddings.

The recent literature gives a separate, unweighted independence bound.
Abiad, Kumar and Pragada [6, Theorem 3.1] prove
$\alpha(G)\ge\sum_v2/(d(v)+c(v)+1)$, where $c(v)$ is the largest clique
order containing $v$. Spogreev [7, P-009] explicitly applies this to biplanar
graphs to obtain
$$
\alpha(G)\ge\frac{2n^2}{21n-24}>\frac{2n}{21}\qquad(n\ge3),
$$
answering Král's question from Barbados 2018 [8, Problem 4]. Both the
general inequality and that application are prior work. They motivated
the endpoint analysis here but are not premises of Theorems 1 and 2.
Our results do not assert a fractional chromatic bound.

The counting example in [9, Theorem 2] has twenty-nine vertices and
independence number three, but [9] explicitly proves it nonbiplanar.
It is therefore useful context, not an existence or sharpness example
for the order bound here.

## 2. The imported linking obstruction

For nonadjacent vertices $w,a$, write $H/(w=a)$ for their identification
in the simple graph $H$, suppressing parallel edges. The linking lemma
[3, Lemma 1] says the following. Let $P,Q$ be disjoint sets not containing
$w$, and let $A\subseteq P\setminus N(w)$. If
$G[P\cup\{w\}]+\{wa:a\in A\}$ is not biplanar, and if
$G[Q\cup\{w,a\}]/(w=a)$ is not biplanar for every $a\in A$, then $G$
is not biplanar.

This does not assert that arbitrary identifications preserve biplanarity.
The proof of [3] splits according to whether each $a$ has a same-layer
path from $w$ through $Q$. In the first case it contracts connected sets
within each planar layer; in the other it performs planar one-sums of
distinct components. The applications through Section 11 use the lemma when both obstructions
are copies of $K_9$. Section 12 also applies it inductively to a rooted
independent transversal of disjoint eight-cliques.

**Lemma 3 ([2, Lemma 3]).** If $H$ is biplanar, $\alpha(H)\le2$, and
$H$ has two disjoint eight-cliques, then $|V(H)|=16$.

**Proof.** Let the cliques be $P,Q$, and suppose $w$ lies outside them.
Put $A=P\setminus N(w)$ and $B=Q\setminus N(w)$. Both are nonempty,
since otherwise $w$ extends a clique to $K_9$. Every $a\in A$ is adjacent
to every $b\in B$, or $w,a,b$ would be an independent triple. Completing
$w$ to $P$ creates $K_9$. For each $a\in A$, identifying $w,a$ produces
a vertex complete to $Q$: $w$ covers $Q\setminus B$, while $a$ covers
$B$. The linking lemma gives a contradiction. $\square$

The following form will be used repeatedly.

**Corollary 4.** Suppose $G$ is biplanar with $\alpha(G)\le3$. If $P,Q$
are disjoint eight-cliques and $r$ is anticomplete to $P\cup Q$, then
every vertex outside $P\cup Q\cup\{r\}$ is adjacent to $r$.

**Proof.** The antineighborhood $G-N[r]$ has independence number at most
two and contains both cliques. Lemma 3 says it contains no further vertex.
$\square$

## 3. Private neighbors of a maximum independent set

Let $U$ be a maximum independent set of size $a$. It dominates $G$.
For $u\in U$, define
$$
X_u=\{v\notin U:N(v)\cap U=\{u\}\},\qquad x_u=|X_u|,
\qquad P_u=X_u\cup\{u\}.
$$
The standard private-neighbor observation, also used in the proof of
Abiad–Kumar–Pragada [6], says that $P_u$ is a clique: two nonadjacent vertices of $X_u$ could replace
$u$ in $U$, increasing its size. Therefore $x_u\le7$. The new ingredient below is
the linking-based exclusion of equality, not this standard observation.

**Lemma 5.** No vertex with exactly two neighbors $u,v$ in $U$ can have
$x_u=x_v=7$.

**Proof.** Suppose $w$ is such a vertex. The cliques $P_u,P_v$ are
disjoint eight-cliques. Let $A=P_u\setminus N(w)$ and
$B=P_v\setminus N(w)$, both nonempty by $K_9$-freeness. If $a'\in A$
and $b'\in B$ were nonadjacent, then
$$
(U\setminus\{u,v\})\cup\{w,a',b'\}
$$
would be independent of size $a+1$. The private-neighbor definitions
ensure all required nonedges to the retained roots. Hence $A$ is complete
to $B$. Applying the linking lemma to root $w$, sets $P_u,P_v$, and
missing set $A$ gives the same two $K_9$ obstructions as in Lemma 3.
$\square$

**Proof of Theorem 2.** Put $x=\sum_{u\in U}x_u$ and
$$
q=\sum_{v\notin U,\ |N(v)\cap U|\ge2}(|N(v)\cap U|-2)\ge0.
$$
Counting incidences with $U$ gives
$$
\sum_{u\in U}d(u)=x+2(n-a-x)+q=2n-2a-x+q\ge2n-9a.
$$
Equality requires $x=7a$ and $q=0$. Thus all $P_u$ have order eight,
and every vertex outside their union has exactly two neighbors in $U$.
Since $n>8a$, at least one such vertex exists, contradicting Lemma 5.
Integrality gives the claimed one-unit improvement. For $a=3$, the
condition is $n\ge25$. Under $\alpha\le3$ at those orders, Szeider's
theorem ensures $\alpha=3$, so every independent triple is maximum.
$\square$

The condition $n>8a$ matters: a disjoint union of $a$ copies of $K_8$
has equality in the weaker degree-sum bound and is biplanar.

## 4. Excluding order thirty

**Preliminary order bound.** For any vertex $v$, the antineighborhood
$G-N[v]$ has independence number at most two. By [1], it has at most
eighteen vertices, so
$$
d(v)\ge n-19.
$$
For $n\ge3$, summing and using Euler's bound $m\le6n-12$ yields
$$
n(n-19)\le2m\le12n-24,
\qquad n^2-31n+24\le0.
$$
The latter fails for $n\ge31$, giving the already available bound $n\le30$.

Suppose $n=30$. Minimum degree is eleven and
$$
\sum_{v\in V(G)}(d(v)-11)=2m-330\le6.
$$
At least twenty-four vertices therefore have degree eleven. Their induced
graph is biplanar and has more than eighteen vertices, so [1] supplies an
independent triple $U$ among them. Theorem 2 gives
$$
33=\sum_{u\in U}d(u)\ge 2\cdot30-26=34,
$$
a contradiction. Thus $n\le29$. $\square$

For clarity, the equality structure behind this last contradiction can
also be read directly. If $y_j$ counts vertices outside $U$ with exactly
$j$ neighbors in $U$, and $x=\sum x_u$, then
$x+y_2+y_3=27$ and $x+2y_2+3y_3=33$. Hence $x-y_3=21$, forcing
$x_u=7$ for every root, $y_3=0$, and $y_2=6$. Lemma 5 excludes each of
those six double-neighbor vertices.

## 5. Necessary structure at order twenty-nine

Assume throughout this section that $G$ is biplanar, $n=29$, and
$\alpha(G)\le3$. The preceding antineighborhood argument gives
$\delta(G)\ge10$.

**Proposition 6.** If $U=\{u_0,u_1,u_2\}$ is independent and all its
vertices have degree at most eleven, then all three degrees equal eleven.
After relabeling, its private closed cliques have orders $8,7,7$.
There are no vertices adjacent to all three roots, and the numbers having
precisely the root-neighbor pairs $01,02,12$ are $2,2,3$, respectively.

**Proof.** Two private closed eight-cliques would, by Corollary 4, force
the third root to be adjacent to all twelve vertices outside those cliques
and itself. Its degree would be twelve, contrary to the hypothesis. Thus
at most one $x_i$ equals seven, and $x=\sum x_i\le19$.
Writing $y_3$ for the number of vertices meeting all three roots gives
$$
\sum_i d(u_i)=52-x+y_3\ge33.
$$
The upper bound on the three degrees forces equality: all degrees are
eleven, $x=19$, and $y_3=0$. Thus $(x_0,x_1,x_2)=(7,6,6)$ after
relabeling. Solving
$y_{01}+y_{02}=4$, $y_{01}+y_{12}=5$, and
$y_{02}+y_{12}=5$ gives $(y_{01},y_{02},y_{12})=(2,2,3)$.
$\square$

In particular, no degree-ten vertex belongs to an independent triple of
vertices of degree at most eleven. No vertex has three independent
neighbors of degree at most eleven, since such a triple would have that
vertex as a common neighbor, forbidden by Proposition 6.

**Corollary 7.** Let $A=\{v:d(v)=10\}$ and $L=\{v:d(v)\le11\}$.
If $A\ne\varnothing$, then $|L|\le19$, $|A|\ge5$, and at least ten
vertices have degree at least twelve. If $A=\varnothing$, at least
twenty-four vertices have degree eleven, and they contain a triple of
the form in Proposition 6.

**Proof.** If $v\in A$, its nonneighbors in $L$ form a clique, or two
nonadjacent ones with $v$ would contradict Proposition 6. Their number
is at most eight, so $|L|-1-d_{G[L]}(v)\le8$, giving $|L|\le19$.
Writing $a=|A|$, $\ell=|L|$, degree summation gives
$$
324\ge2m\ge10a+11(\ell-a)+12(29-\ell)=348-a-\ell.
$$
Thus $a+\ell\ge24$, and the assertions follow. If $A$ is empty, the
excess over degree eleven totals at most $324-319=5$, leaving at least
twenty-four degree-eleven vertices. Apply [1] to their induced graph.
$\square$

There is a further exact budget whenever such a low triple exists. Use Proposition 6's
partition into $P_0,P_1,P_2,Y_{01},Y_{02},Y_{12}$, and put
$Z_i=V(G)\setminus N[u_i]$. Each $Z_i$ has seventeen vertices and
independence number at most two. Paper [2, Theorem 2] proves
$e(G[Z_i])\ge76$.

Let $E_0$ consist of the edges from $P_i$ to $Y_{jk}$ with
$\{i,j,k\}=\{0,1,2\}$, together with the edges between distinct
$Y$-classes. Internal edges of the $P_i$ are counted twice in
$\sum_i e(G[Z_i])$; there are $28+21+21=70$ of them. Edges in $E_0$
are counted zero times, and every other edge is counted once. Therefore
$$
|E_0|+\sum_{i=0}^2\big(e(G[Z_i])-76\big)=m-158\le4. \tag{1}
$$
Thus at most four edges lie in $E_0$, and the three overlapping
antineighborhoods have at most four total edges above their individual
minimum, sharing this same budget. The following sections use this shared budget to exclude their coexistence.

## 6. Equality in the seventeen-vertex density bound

**Lemma 8.** Let $F$ be triangle-free on seventeen vertices, with
$\alpha(F)\le8$, no two disjoint independent eight-sets, and $e(F)=60$.
Then $F$ is an independent-set blow-up
$$
F=C_5[8-a,7-b,a,2,b],\qquad
 a,b\ge2,\quad a+b\le8,\quad \min(a,b)=2.
$$
Some listed parameters may violate other hypotheses; only necessity is claimed.

**Proof.** Triangle-freeness gives $\Delta(F)\le8$. Its average degree
exceeds seven, so a neighborhood supplies an independent eight-set $I$.
Put $T=V(F)\setminus I$, $c=e(I,T)$ and $z=e(F[T])$. Then
$c+2z\le72$ and $c\le8\alpha(F[T])$, giving
$60\le36+4\alpha(F[T])$. Thus $\alpha(F[T])$ is six or seven.

Suppose it is six. Choose an independent six-set $J\subset T$ and let
$R=T\setminus J$. For each $r\in R$, write
$A_r=N_F(r)\cap I$, $B_r=N_F(r)\cap J$. Independent subsets of $R$
satisfy Hall's condition on either side by maximality of $I,J$; adjacent
pairs have disjoint nonempty neighborhoods. The only possible remaining
Hall failure is an edge plus an isolate, with failing-side sets
$\{x\},\{y\},\{x,y\}$. The opposite neighborhoods of the edge endpoints
are disjoint. The two missing cross rows therefore cover at least the
sum of all three opposite contact counts. Including the four contacts
on the failing side and the edge in $R$ gives $e(F)\le48+4+1=53$.

Otherwise both neighborhood families have distinct representatives. The
representative-rectangle argument of [2, Section 3] gives
$$
e(F)\le |I||J|+|R|^2-e(F[R])\le48+9=57.
$$
For clarity, each rectangle $A_r\times B_r$ is missing from the cross
graph. Its selected row and column cover all contacts at $r$; overlaps
occupy an $|R|\times|R|$ grid, and each edge of $F[R]$ forbids two grid
overlaps. Adding the remaining edges gives the displayed bound. Both
possibilities contradict sixty. Hence there is a disjoint independent
seven-set $J$, leaving two vertices $R$.

Both representative systems now exist by the one- and two-set conditions;
enlarging $J$ to eight would violate the disjoint-eight hypothesis. Equality
in $e(F)\le56+4-e(F[R])$ makes $R$ independent, all four grid cells
overlaps, and every missing cross pair covered by a selected arm. The
selected representatives belong to both remainder neighborhoods. An
additional neighbor of only one remainder vertex would create an
uncovered missing pair with the other selected opposite representative.
Thus the two remainder vertices have identical neighborhoods
$A\subset I$, $B\subset J$. Writing their sizes as $a,b$ gives
$a,b\ge2$, $a+b\le8$, and
$$
60=56+2a+2b-ab=60-(a-2)(b-2).
$$
The cyclic bags are $I\setminus A,J\setminus B,A,R,B$. $\square$

**Corollary 9.** In the partition of Proposition 6, if $e(G[Z_0])=76$,
then all three vertices of $Y_{12}$ have degree nine inside $G[Z_0]$.

**Proof.** Apply Lemma 8 to $\overline{G[Z_0]}$, using [2, Lemma 3].
The roots $u_1,u_2$ are adjacent in the complement and each has degree
seven there. The five bag degrees in Lemma 8 are
$$
7,\ 8,\ 9-b,\ a+b,\ 10-a.
$$
For $a=2$, $2\le b\le6$, or $b=2$, $2\le a\le6$, adjacent degree-seven
bags occur only at $(a,b)=(3,2)$ or $(5,2)$. Both give
$C_5[5,5,3,2,2]$ up to dihedral symmetry. The three vertices missing
both roots in the complement form the opposite bag, of complement
degree seven. These are exactly $Y_{12}$, proving the assertion. $\square$

## 7. Excluding minimum degree eleven

Assume for this section that $n=29$ and $\delta(G)\ge11$. Put
$L=\{v:d(v)=11\}$ and $H=V(G)\setminus L$. At most five vertices lie
in $H$, and $\sum_v(d(v)-11)\le5$.

**Lemma 10.** Every nonadjacent pair in $L$ has two or three common neighbors.

**Proof.** For nonadjacent $u,v\in L$, let $c=|N(u)\cap N(v)|$.
Their common-nonneighbor set $C$ is a clique, since $\alpha(G)\le3$, and
$|C|=5+c\le8$. If $C$ contains a low vertex $z$, it is exactly the
private closed clique at $z$ for the triple $u,v,z$. Proposition 6 gives
$c=2$ or $3$.

Otherwise $C\subset H$, forcing $c=0$, $C=H$, and $|H|=5$. All high
vertices have degree twelve and form a clique. The remaining low vertices
partition into $A=N(u)$ and $B=N(v)$, each of size eleven. The roots
are anticomplete to $H$ and to each other; $u$ meets all of $A$ and
none of $B$, and conversely for $v$.

For $a\in A$, put $S_a=N(a)\cap H$, $r_a=|S_a|$, and
$s_a=d(a,B)$. Applying the preceding dichotomy to $a,v$ gives
$s_a\in\{0,2,3\}$. If $s_a=0$, that exceptional alternative gives
$r_a=0$ and makes $a$ complete to $A\setminus\{a\}$. Let
$J_A=\overline{G[A]}$. It is triangle-free, since an independent triple
in $A$ together with $v$ would have size four, and
$$
d_{J_A}(a)=r_a+s_a.
$$

If $aa'\in E(J_A)$, both $s$-values are positive. Proposition 6 forbids
a common $B$-neighbor of the independent low triple $a,a',v$. Its private
clique at $v$ has size $12-s_a-s_{a'}$, so the pair $(3,3)$ is impossible.
The other two private clique sizes are
$$
s_{a'}+|S_a\cup S_{a'}|,\qquad s_a+|S_a\cup S_{a'}|.
$$
The first consists of the nonneighbors of $a'$ in $A$ (including $a$)
and $S_a\setminus S_{a'}$. The allowed private sizes $7,7,8$ now force
$S_a\cup S_{a'}=H$, both when the two $s$-values are $2,2$ and when
they are $2,3$.

For every $x\in H$, therefore, $A\setminus N(x)$ is a clique; adding
$u$ bounds its size by seven. The same holds on $B$. Since $x$ has
four neighbors in $H$, none among $u,v$, and total degree twelve, it
misses fourteen of $A\cup B$. Hence it misses seven on each side:
$$
d(x,A)=d(x,B)=4,\qquad \sum_{a\in A}r_a=20.
$$

Let $R_A=\{a\in A:r_a=5\}$. For $r_a<5$, choose a high nonneighbor
$x$. Every $J_A$-neighbor of $a$ lies among the four $A$-neighbors of
$x$, so $r_a+s_a\le4$, and consequently $r_a\le2$. No two vertices
outside $R_A$ can be adjacent in $J_A$, because their high-neighborhood
union has size at most four. Vertices of $R_A$ have $J_A$-degree seven
or eight. They cannot be adjacent in the triangle-free eleven-vertex
$J_A$, where adjacent degrees sum to at most eleven. Thus $R_A$ is a
clique in $G$, complete to $H$, and $|R_A|\le3$.

If $|R_A|\le2$, an outside vertex with positive $r_a$ would need at
least three $J_A$-neighbors among at most two vertices. Thus all outside
$r_a$ would vanish, contradicting their sum twenty. Hence $|R_A|=3$.
Every outside positive $r_a$ equals one and has $s_a=2$. There are five
such vertices. Each high vertex has precisely one of them as its fourth
$A$-neighbor; denote it by $a_x$. Each $a_x$ is anticomplete in $G$ to
$R_A$. Symmetrically there is a three-set $R_B\subset B$ complete to $H$.

For $b\in R_B$, $K_9$-freeness supplies $a\in R_A$ nonadjacent to $b$.
If $a_x$ also missed $b$, then $a_x,a,b$ would be three independent low
neighbors of $x$, contrary to Proposition 6. Therefore $a_x$ meets all
three vertices of $R_B$, contradicting $s_{a_x}=2$. This excludes the
exception, including the possible true twins with $s_a=0$. $\square$

Choose the low triple supplied by Corollary 7 and retain its notation.
For a low vertex $w\in Y_{ij}$, its common neighbors with the opposite
root $u_k$ are exactly its $E_0$-neighbors. Lemma 10 gives
$d_{E_0}(w)\in\{2,3\}$. At least two of the seven $Y$-vertices are low;
a simple graph with two distinct vertices of degree at least two has
at least three edges. Hence $|E_0|\ge3$.

If $e(G[Z_0])=76$, Corollary 9 gives core degree nine at all three
$Y_{12}$ vertices. Minimum full degree eleven requires six distinct
$E_0$ edges incident with that class, contradicting (1). Therefore
$e(G[Z_0])\ge77$, and (1) forces
$$
|E_0|=3,\qquad e(G[Z_0])=77,\qquad
 e(G[Z_1])=e(G[Z_2])=76,\qquad m=162.
$$

Apply the equality argument of Lemma 8 to $Z_2$, using its existing
private cliques $P_0,P_1$ as the independent sets of sizes eight and
seven in the complement. The two $Y_{01}$ vertices have core degree
$16-a-b$. If $a+b\ge6$, each needs at least two exterior edges: one
would either give a forbidden low $E_0$-degree or fail to reach degree
twelve. Four such edges are impossible. If $a+b\le5$, core degree is
at least eleven; a low vertex would have exterior degree zero, also
forbidden. Thus both $Y_{01}$ vertices are high. The same holds for
$Y_{02}$. At least two $Y_{12}$ vertices are therefore low, requiring
four distinct $E_0$ edges, the final contradiction. The minimum-degree-
eleven branch is excluded.

## 8. The structure of the degree-ten vertices

Assume now that $A=\{v:d(v)=10\}$ is nonempty. Put
$B=\{v:d(v)=11\}$, $L=A\cup B$, $H=V(G)\setminus L$, and write
$a=|A|$, $\ell=|L|$, $T=\sum_{v\in H}(d(v)-12)$. Corollary 7 and Euler give
$$
a\ge5,\qquad \ell\le19,\qquad a+\ell\ge24+T. \tag{2}
$$
The eighteen-vertex antineighborhood of each degree-ten vertex has
independence number at most two and at least eighty-eight edges [2,
Theorem 2].

For any nonadjacent vertices $x,y$, their common nonneighbors form a
clique. Inclusion-exclusion therefore gives
$$
|N(x)\cap N(y)|\le d(x)+d(y)-19. \tag{3}
$$
In particular, a nonadjacent pair in $A$ has zero or one common neighbor.
Its common-nonneighbor clique has size seven or eight and lies in $H$,
because Proposition 6 excludes low independent triples containing $A$.

We shall use one more private profile. An independent triple of degree
sum thirty-two must have degrees $10,10,12$, private closed clique sizes
$8,8,7$, no common neighbor, and double counts $0,3,3$, with the two
size-eight cliques at the degree-ten roots. Indeed, the identity in
Section 3 gives $x-y_3=20$, so at least two private sets have size seven.
Corollary 4 forces the third root to degree twelve. The alternative
$x=21,y_3=1$ would give three private eight-cliques and force all roots
to degree twelve. Thus $x=20,y_3=0$, and the three degree equations give
the asserted profile. Consequently, if a nonadjacent degree-ten pair
has one common neighbor, all eight vertices of its common-nonneighbor
clique have degree at least thirteen. In that case $T\ge8$.

**Lemma 11.** Either $A$ is a clique, with $5\le a\le8$, or
$7\le a\le16$, $\ell\le17$, and $G[A]$ is one of: two disjoint cliques;
two cliques with one cross edge; a universal vertex joined to two
disjoint cliques.

**Proof.** Every $v\in A$ has at most $19-\ell$ high neighbors, since
its low nonneighbors form a clique of size at most eight. A nonadjacent
pair in $A$ consequently has at least $\ell-9$ common high nonneighbors.
Their clique bound gives $\ell\le17$, and (2) gives $a\ge7$.

Let $F=\overline{G[A]}$. It is triangle-free. For $uv\in E(F)$,
$$
d_F(u)+d_F(v)=a-|N_{G[A]}(u)\cap N_{G[A]}(v)|\ge a-1.
$$
If $F$ has an odd cycle, take a shortest one, of length $g\ge5$.
It is induced, and every outside vertex has at most two neighbors on
it, or there is a triangle or a shorter odd cycle. Its degree sum is
at most $2a$. Summing the edge bound around it gives $g(a-1)\le4a$,
impossible for $a\ge7$. Thus $F$ is bipartite, and $A$ partitions into
two cliques $P,Q$, each of size at most eight.

For a missing cross edge $uv$, let $r_u=d_G(u,Q)$ and $s_v=d_G(v,P)$.
Then $r_u+s_v\le1$. A cross degree at least two therefore forces that
vertex complete to the opposite part. If a complete row exists and
some cross edge is missing, all other rows are zero, and the complete
row is unique; this gives the universal-vertex form. The same holds
for a complete column. Otherwise all cross degrees are at most one.
Two distinct matching edges violate the zero-cell inequality, so there
is at most one. If no cross edge is missing, $A$ is a clique. $\square$

## 9. The low-degree set has independence number two

Suppose $L$ contains an independent triple, with the partition of
Proposition 6. No degree-ten vertex can be private: swapping it for
its root would give a forbidden low triple containing degree ten.
Thus $A\subseteq Y_{01}\cup Y_{02}\cup Y_{12}$ and $a\le7$.

If $A$ is a clique, any five of its vertices require at least six
between-type edges: capacities $2,2,3$ allow at most four within-type
pairs. This contradicts $|E_0|\le4$.

Otherwise Lemma 11 and (2) force $a=7$, $\ell=17$, $T=0$, so $A$ is
all seven $Y$-vertices. Its three allowed forms have at least nine
edges, with equality only at $K_3\cup K_4$. At most five edges can
lie within the $Y$-types. Thus equality is forced: $|E_0|=4$, all types
are cliques, $Y_{12}$ is the $K_3$, and $Y_{01}\cup Y_{02}$ is the
$K_4$. All $E_0$ edges lie between the latter two types. Equation (1)
gives $e(G[Z_0])=76$; Corollary 9 gives degree nine inside $Z_0$ for
every $Y_{12}$ vertex. With no exterior edge, its full degree is nine,
contradicting its membership in $A$.

Hence $\alpha(G[L])\le2$. Szeider first gives $\ell\le18$. Euler on
$G[H]$ gives
$$
e(L,H)=\sum_{v\in H}d(v)-2e(G[H])\ge24+T. \tag{4}
$$
If $\ell=18$, [2] gives $e(G[L])\ge88$, whence
$e(L,H)\le198-a-176=22-a$, contradicting (4). Thus $\ell\le17$.
At $\ell=17$, [2] similarly gives
$$
7+T\le a\le11-T,\qquad T\le2. \tag{5}
$$

## 10. Reducing the low set to two cliques

There is no eight-clique consisting entirely of degree-ten vertices.
Indeed, for such a clique $C$, put $W=V(G)\setminus C$. There are
twenty-four edges from $C$ to $W$, so $e(G[W])\le110$. A contact
$x\in W$ misses some $c\in C$ by $K_9$-freeness. If it has $k$
neighbors in $C$, (3) gives $d(x)-k\ge9$. For a fixed $c\in C$, its
three outside neighbors therefore remove at least $27-3=24$ edges from
$W$. Its eighteen-vertex antineighborhood has at most eighty-six edges,
a contradiction. Thus $A$ contains no $K_8$.

We next exclude $\ell=17$. If $A$ is not a clique, (5) and the observation
following (3) make every nonadjacent pair in $A$ have zero common
neighbors. Lemma 11 reduces $A$ to two disjoint cliques $P,Q$: its other
nonclique forms have a nonadjacent pair with a common neighbor. Every
$b\in B$ meets all of $P$ or all of $Q$, by $\alpha(G[L])\le2$, and
cannot meet both. Each side, augmented by its assigned $B$-vertices,
is a clique: a vertex of the opposite $A$-side is anticomplete to it.
This partitions seventeen low vertices into two cliques of size at
most eight, impossible.

If $A$ is a clique, its size is at most seven. Equations (2),(5) force
$a=7,T=0$. Every outside vertex has degree eleven or twelve. Put $C=A$,
$W=V(G)\setminus C$; then $e(G[W])\le113$, and every $c\in C$ has
four outside neighbors. Call a contact complete if it sees all of $C$.
Two complete contacts would be nonadjacent by $K_9$-freeness but have
seven common neighbors, contradicting (3). Thus there is at most one.
A partial contact has $W$-degree at least nine by (3).

Without a complete contact, deleting the four outside neighbors of
$c$ removes at least $36-6=30$ edges, leaving at most eighty-three.
Let $x$ be the unique complete contact. If $d(x)=12$, the deletion
removes at least $5+27-6=26$ edges, again too many. Thus $d(x)=11$,
and its $W$-degree is four. Equality is forced throughout: each four-
neighbor set is a $K_4$, and all its partial contacts have $W$-degree
nine. Every partial contact of $C$ is adjacent to $x$, so there are
at most four. Each meets at most three vertices of $C$ by (3), whereas
the clique needs twenty-one partial incidences. This contradiction
excludes $\ell=17$.

We have $\ell\le16$. If $A$ were a clique, $a\le7$ would contradict
(2). It is therefore nonclique. Lemma 11 and the absence of $K_8$ in
$A$ give $a\le14$; the universal-vertex form has $a\le11$ by degree
ten. Thus $T\le6$. Again every nonadjacent pair of $A$ has zero
common neighbors, and
$$
G[A]=K_p\cup K_q,\qquad 1\le p,q\le7.
$$
No vertex anywhere meets both cliques. As above, $B$ divides by its
unique complete $A$-side, giving cliques $C,D$ partitioning $L$ and
containing $P=K_p,Q=K_q$. Edges between $C,D$ may only join $B$-vertices.

## 11. Contact budgets exclude the degree-ten branch

We first show that $|C|,|D|\le7$. Suppose $|C|=8$, and put $p=|P|$,
$W=V(G)\setminus C$. The $C$–$W$ cut has $32-p$ edges, so
$e(G[W])\le102+p$. Every contact misses a vertex of $C$. Equation (3)
gives $W$-degree at least eight, or at least nine if it misses a vertex
of $P$. A vertex $u\in P$ has three outside neighbors $S$, which remove
at least $24-3=21$ edges. Hence $88\le81+p$, forcing $p\ge7$.
The case $p=8$ was excluded. At $p=7$, equality makes all three vertices
of $S$ complete to $P$ and makes $S$ a triangle. Two of them with $P$
form $K_9$, a contradiction.

Suppose next that $|C|=7$, and retain $p=|P|$ and $W=V(G)\setminus C$.
The cut has $35-p$ edges, so $e(G[W])\le106+p$. Every $u\in P$ has
four outside neighbors $S$; they may remove at most $18+p$ edges.
A partial contact has $W$-degree at least eight, or at least nine if
it misses $P$. A complete contact lies in $H$, since no outside low
vertex meets $P$, and has $W$-degree at least five. Complete contacts
are pairwise nonadjacent by $K_9$-freeness. They all miss $Q$, so there
are at most two, or three of them and a vertex of $Q$ would be independent.
Every $S$ contains all complete contacts.

With none, at least $32-6=26>18+p$ edges are removed. With exactly one,
let $s$ count the three partial contacts of $S$ that miss $P$. Their
$W$-degree sum, including the complete contact, is at least $29+s$.
For $p\le4$, even six edges inside $S$ leave at least twenty-three
removed edges, too many. For $p=5$, equality would require $s=0$ and
$S=K_4$, giving $K_9$ with $P$. For $p=6$, $s\ge2$ is immediately
impossible. At $s=0$, all of $S$ is complete to $P$, so $S$ is triangle-
free and has at most four edges. At $s=1$, the complete contact and
the two partials complete to $P$ cannot form a triangle, so $e(S)\le5$.
Both cases remove at least twenty-five edges, exceeding $18+p=24$.
For $p=7$, all three partials miss $P$, giving at least twenty-six removed
edges. Thus exactly one complete contact is impossible.

With two complete contacts $x,x'$, write $d(x)+d(x')=26+e$.
Their seven shared $C$-neighbors and (3) give $e\ge0$ and at most $e$
common $W$-neighbors. Their $W$-degree sum is $12+e$. If $y,z$ are the
other vertices of $S$, then
$$
e(S)\le3+\min(e,2):
$$
there is no $xx'$ edge, each of $y,z$ has at most one contact to
$\{x,x'\}$ unless it is a common neighbor, and $yz$ contributes at
most one. For $p\le6$, the removed-edge count is at least
$28+e-3-\min(e,2)\ge25>18+p$. For $p=7$, both partial contacts have
$W$-degree at least nine, raising this bound to twenty-seven, also
impossible. We conclude $|C|,|D|\le6$.

Thus $\ell\le12$. Since $a\le\ell$ and (2) holds, equality forces
$$
a=\ell=12,\quad T=0,\quad C=P=K_6,\quad D=Q=K_6,
\quad |H|=17,\quad d(h)=12\ (h\in H),\quad m=162.
$$
Each low vertex has five high neighbors, and no high vertex meets both
six-cliques. Fix $C$ and put $W=V(G)\setminus C$; then $e(G[W])=117$.
A partial contact has at most three neighbors in $C$ by (3), so its
$W$-degree is at least nine. Complete contacts have $W$-degree six.
Two complete contacts must be adjacent, or their six common $C$-neighbors
would violate (3), whose right side is five. They therefore form a clique
and number $r\le2$ by $K_9$-freeness.

Every $u\in C$ has five outside neighbors $S$, including all complete
contacts. Their $W$-degree sum is at least $45-3r$, so they remove at
least $35-3r$ edges. The eighteen-vertex antineighborhood requires at
least eighty-eight edges, allowing removal of at most twenty-nine.
Thus $r=2$, and equality makes every $S$ a $K_5$ and every partial
contact have exactly three neighbors in $C$. All partial contacts meet
both complete ones. There are at least six partial contacts, to supply
the eighteen partial incidences from $C$. Each complete contact now
has six neighbors in $C$, the other complete contact, and at least six
partial contacts: degree at least thirteen, contradicting degree twelve.
This excludes the degree-ten branch.

**Completion of Theorem 1.** Section 4 reduces the order to at most
twenty-nine. At order twenty-nine the minimum degree is at least ten.
Sections 7 and 8–11 exclude respectively minimum degree at least eleven
and degree ten. Therefore $n\le28$. $\square$

## 12. The regular order-twenty-eight endpoint

We now exclude the entirely degree-eleven case at the remaining order.
The structural assertion is about arbitrary graphs.

**Theorem 12.** Every eleven-regular graph on $28$ vertices with
$\alpha(G)\le3$ and $\omega(G)\le8$ contains three vertex-disjoint copies
of $K_8$.

**Corollary 13.** No eleven-regular biplanar graph on $28$ vertices has
independence number at most three. In particular, an order-$28$ biplanar
graph with $\alpha\le3$ and $\delta\ge11$ has $155$ or $156$ edges.

Theorem 12 is proved by hand reductions followed by three small, explicitly
checked propositional refutations. We give the complete reduction and the
meaning of the formulas, rather than treating a search failure as evidence.
This result does not exclude the mixed degree-excess cases or all order-$28$
graphs. It requires neither vertex transitivity nor a planar-layer census.
In contrast, the prior census theorem [9, Section 5] concerns vertex-transitive
biplanar graphs through order $47$; its order-$28$ exceptional graph
$C_7[K_4]$ is already known to be nonbiplanar. Theorem 12 imposes no symmetry.

There is also prior work on independent sets meeting maximum cliques.
Christofides, Edwards and King [10, Theorem 2] prove that a connected graph
with $\omega\ge\frac23(\Delta+1)$ has such a set unless it is a clique
blow-up of an odd hole. When $\Delta=11$ and $\omega=8$, this is exactly
their equality threshold, with $C_7[K_4]$ among the exceptions. Their
conclusion concerns a set meeting existing maximum cliques. Theorem 12
instead forces three disjoint eight-cliques from regularity, order and
independence number, including the assertion that $\omega=8$. We do not
use that transversal theorem as a premise.

We first recall the linking consequence needed for the corollary.

**Lemma 14 (rooted clique transversal).** If $Q_1,\ldots,Q_k$ are disjoint
eight-cliques in a biplanar graph and $w$ lies outside them, there exist
$q_i\in Q_i$ such that $\{w,q_1,\ldots,q_k\}$ is independent.

**Proof.** Induct on $k$. For $k=1$, otherwise $Q_1+w$ is $K_9$.
For the induction step restrict to the specified cliques and $w$, and put
$A=Q_1\setminus N(w)$, which is nonempty. Completing $w$ to $Q_1$ makes
$K_9$. If no required transversal exists, then for every $a\in A$ the
quotient on $\{w,a\}\cup Q_2\cup\cdots\cup Q_k$, identifying $w,a$, is
nonbiplanar: otherwise induction gives a transversal through its merged
vertex, which lifts to the missing transversal in the original graph.
These are exactly the two obstruction hypotheses of the linking lemma
[3, Lemma 1]. Thus the original graph is nonbiplanar, a contradiction.
The argument does not assert that arbitrary identifications preserve
biplanarity. $\square$

Three disjoint eight-cliques in an order-$28$ biplanar graph have an outside
vertex, so Lemma 14 would give an independent four-set. Classical
$K_9$ nonbiplanarity gives $\omega\le8$. These two facts and Theorem 12
prove the first assertion of Corollary 13. The second follows from
$154\le m\le156$: equality $m=154$ and $\delta\ge11$ forces regularity.

For the remainder of the proof assume that $G$ satisfies the hypotheses of
Theorem 12 but has no three disjoint eight-cliques. The only graph-theoretic
assumptions used below are these stated abstract ones.

### 12.1 Common neighbors, covers, and root changes

For nonadjacent vertices $u,v$ having $c$ common neighbors, their common
nonneighbors form a clique of order
$$
28-2-(11+11-c)=4+c.
$$
Consequently $c\le4$. In particular, the common neighborhood of any
five-clique is a clique: a nonadjacent pair there would share five neighbors.
An independent triple exists, since a maximal independent set of size at
most two would have its closed neighborhoods cover all $28$ vertices,
although they cover at most $24$.

We will use the following cover calculation repeatedly. Suppose
$S=A\cup Y$, where $A$ is a clique of order $a$, and $F=\overline{G[S]}$
is triangle-free. The set $Y$ covers every edge of $F$. For an $F$-edge $uv$,
its endpoints have exactly $|S|-d_F(u)-d_F(v)$ common $G$-neighbors in $S$.
Thus
$$
d_F(u)+d_F(v)\ge |S|-4. \tag{12}
$$
If another cover $C$ omits $y\in Y$ with an $F$-neighbor $v\in A$, put
$R=C\setminus Y$. The disjoint $F$-neighborhoods of $y,v$ lie in $Y\cup R$:
$C$ covers all edges from the omitted vertex, and $A$ is independent in $F$.
It follows that
$$
|Y|+a-4\le d_F(y)+d_F(v)\le |Y|+|R|,
\qquad |R|\ge a-4. \tag{13}
$$
When $a=8$, every $y\in Y$ has an $F$-neighbor in $A$, by $K_9$-freeness.
Therefore every cover of size at most three contains $Y$; a cover of size
at most four omitting a $Y$ vertex consists of four vertices entirely in $A$.
No minimum-cover hypothesis is needed for this conclusion.

Let $U=\{u_0,u_1,u_2\}$ be independent. It is dominating. Write $P_i$ for
its private closed cliques, $x_i=|P_i|-1$, $Y_{ij}$ for the vertices meeting
exactly roots $i,j$, and $Z$ for the common-neighbor set, of size $z$.
For private cliques subsequently named $P,A,B,C$, their original roots
are denoted by $p_0,a_0,b_0,c_0$, respectively.
Counting vertices and the three root degrees gives
$$
\sum_i x_i=17+z,\qquad |Y_{ij}|=x_k-z-3,
\qquad \{i,j,k\}=\{0,1,2\}. \tag{14}
$$
Each $x_i\le7$, so $z\le4$; equality gives three disjoint private eight-cliques
and is excluded. If $v\in P_i$ replaces $u_i$, put
$$
t_j=|N(v)\cap(P_j\cup Y_{ij})|,\quad
 t_k=|N(v)\cap(P_k\cup Y_{ik})|,\quad
 z_v=|N(v)\cap(Y_{jk}\cup Z)|.
$$
The new triple is independent, and its private counts satisfy
$$
x_i'=x_i,\quad x_j'=14-x_i-t_j,\quad x_k'=14-x_i-t_k,
\qquad t_j+t_k+z_v=11-x_i. \tag{15}
$$
In particular $t_j,t_k\ge7-x_i$ and $z_v\le3$. The relevant complements
on $P_j\cup Y_{ij}$ are triangle-free because the unused root is
anticomplete to that side. A vertex of $P_i$ selects a vertex cover of
that complement: two nonadjacent nonneighbors, together with the vertex
and unused root, would form an independent four-set.

## 13. Selecting an independent triple with no common neighbor

**Lemma 15.** Under the standing assumptions, an independent triple with
$z=0$ exists.

Choose a triple minimizing $z$. The sorted possibilities from (14) are
$$
\begin{array}{c|l}
z& (x_0,x_1,x_2)\\ \hline
0&(3,7,7),(4,6,7),(5,5,7),(5,6,6)\\
1&(4,7,7),(5,6,7),(6,6,6)\\
2&(5,7,7),(6,6,7)\\
3&(6,7,7).
\end{array} \tag{16}
$$
We exclude each positive minimum, without excluding arbitrary appearances
of those positive-overlap profiles.

If $z=3$, the private cliques have orders $7,8,8$. Their union has $23$
vertices; the remaining five comprise $Z$ and two double-neighbor vertices.
Every private vertex has at least three neighbors in its opposite
$Y_{jk}\cup Z$, by minimality and (15). This counts at least $69$ edges
from the private union to the remaining five vertices. The four root
incidences at the two double-neighbor vertices are distinct additional
edges, since none is opposite its root. Thus the cut has at least $73$
edges, exceeding the degree sum $55$ of its other side.

### 13.1 Minimum overlap two

For $(5,7,7)$ write the private cliques as $P=K_6,A=K_8,B=K_8$.
The pair types next to $P$ have size two each, the third is empty, and
$|Z|=2$. Every $p\in P$ sees both $Z$ vertices. Its other four exterior
incidences split at least two on each ten-vertex side, hence exactly two.
By (13), every selected two-cover contains the original two-set. Thus
all six $P$ vertices see both pair types and $Z$. Their six common outside
neighbors form a clique, contradicting $\omega\le8$.

For $(6,6,7)$ write the private cliques $A=K_7,B=K_7,C=K_8$,
with $Y_{AB}$ of size two and $Y_{AC}=\{r\},Y_{BC}=\{s\}$.
Each $v\in C$ has at most one neighbor on either side $A+r,B+s$.
Indeed (15) gives $t_A+t_B+z_v=4$ and $z_v\ge2$; if $z_v=2$ and a side
count were two, the other would be zero and the new minimum triple would
have the excluded profile $(5,7,7)$.
If $r$ misses a nonempty set $M\subseteq A$, every $C$ vertex must cover
the star $rM$ with at most one vertex. For $|M|\ge2$ all $C$ vertices
see $r$, making $K_9$. For $|M|=1$, $r$ and its missed vertex share six
neighbors in $A$, also impossible. Hence $A+r$ is an eight-clique;
similarly $B+s$ is one. These two cliques and $C$ are disjoint.

### 13.2 Minimum overlap one

For $(4,7,7)$ the private cliques are $P=K_5,A=K_8,B=K_8$.
The two pair types at $P$ have size three, the opposite type is empty,
and $Z$ is a singleton. Every $p\in P$ sees $Z$ and selects exactly
three vertices on each eleven-vertex side. Equation (13) forces each
selected cover to be the original three-set. The common neighborhood of
$P$ therefore contains at least four vertices, which form a clique and
extend $P$ to $K_9$.

For $(5,6,7)$ write $P=K_6,A=K_7,C=K_8$, with pair-type sizes
$|Y_{PA}|=3$, $|Y_{PC}|=2$, $Y_{AC}=\{r\}$, and $|Z|=1$.
Every $C$ vertex has at most two neighbors on either eight-vertex side
$P+Y_{PC}$ or $A+r$. A side count at least three in (15) would force
$z_v=1$ and the other count zero, giving the already excluded minimum
profile $(4,7,7)$.
The star argument now shows that $A+r$ is a clique: if $r$ misses at
least three vertices of $A$, every two-cover uses $r$, producing $K_9$
with $C$; if it misses one or two, a nonadjacent pair shares at least five
vertices of $A$.

The complement $F$ on $P+Y_{PC}$ is nonempty, or it would supply a third
disjoint eight-clique. It is triangle-free, has a two-cover $Y_{PC}$, and
(12) gives endpoint degree sum at least four. If its cover number were one,
it would be a star with at least three leaves, whose center belongs to every
selected cover of size at most two. Again this creates $K_9$ with $C$.
Hence every selected cover is a minimum two-cover. Some differs from
$Y_{PC}$, or its vertices are complete to $C$. An alternative replacing
one vertex gives an $F$-edge whose two neighborhoods lie in a set of size
three, contradicting (12); minimality ensures the omitted cover vertex
has a neighbor in $P$. An alternative replacing both vertices makes $F$
a subgraph of $K_{2,2}$, and (12) forces all four edges. Its other four
vertices are isolated. The only two-covers are its two sides, say $Y,R$.

Partition $C=C_Y\cup C_R$ by the selected cover, and put $q=|C_Y|$.
Both parts are nonempty, and the original root $c_0$ is in $C_Y$.
A nonadjacent pair in $Y\times C_R$ shares all $q$ vertices of $C_Y$,
so $q\le4$. For $x\in R$, the triple $x,a_0,c_0$ is independent and
has a common neighbor by the positive minimum. This neighbor lies outside
$C$, since $a_0$ is anticomplete to $C$. The nonadjacent pair $x,c_0$
also shares all $8-q$ vertices of $C_R$, giving $9-q\le4$ and $q\ge5$.

Finally consider $(6,6,6)$. All private cliques have order seven, each
$Y_{ij}$ has size two, and $|Z|=1$. Every side count in (15) is positive.
A count three would force the other count one and $z_v=1$, giving the
just excluded profile $(5,6,7)$. Thus every private vertex selects a
cover of size at most two on each nine-vertex side $P_j+Y_{ij}$.
Its complement $F$ is nonempty by $K_9$-freeness, and every edge has
endpoint degree sum at least five by (12).
If the minimum cover size is two, an alternative to $Y_{ij}$ would have
to insert at least three $P_j$ vertices by (13); minimality ensures an
omitted vertex has a neighbor in $P_j$. Thus all seven $P_i$ vertices
see both $Y_{ij}$ vertices, giving $K_9$ if they are adjacent, or seven
common neighbors if they are not.
The remaining possibility is a star with at least four leaves. Its center
lies in $Y_{ij}$, as a $P_j$ vertex has at most two $F$-neighbors. Every
$P_i$ vertex sees that center, while the other $Y_{ij}$ vertex is complete
to $P_j$. Apply this to pairs $01$ and $02$: distinct terminals in $Y_{01}$
extend $P_0,P_1$ to eight-cliques, and a terminal in the disjoint $Y_{02}$
extends $P_2$. This gives three disjoint eight-cliques. All positive
minimum overlaps are excluded, proving Lemma 15. $\square$

## 14. Excluding two private eight-cliques at zero overlap

**Lemma 16.** No zero-overlap triple has private counts $(3,7,7)$.

Write its private cliques $P=K_4,A=K_8,B=K_8$ and its two pair types
$Y_A,Y_B$, each of size four. Every $p\in P$ selects a four-cover on
each twelve-vertex side: at least four are required by $\omega\le8$,
and its eight exterior incidences leave exactly four per side.
For a side complement $F$, (12) gives endpoint degree sum at least eight.
If a selected cover differs from $Y$, (13) forces it to be a four-set
$R\subseteq A$. Both $Y,R$ cover $F$, so $F$ is bipartite between them;
the degree-sum bound forces $F=K_{4,4}$, plus four isolated vertices.

Such an alternative must occur on each side. Otherwise all $P$ vertices
see, say, $Y_A$. Every $Y_A$ vertex also sees $a_0$. A nonadjacent pair
in $Y_A$ would share the five vertices $P+a_0$, so $Y_A$ is a clique.
Then $P+Y_A,A,B$ are three disjoint eight-cliques.

On each side write $R_A,Y_A$ for the two four-sets of its complement,
and $I_A$ for its four isolates; use $R_B,Y_B,I_B$ similarly. Let $q_A$
be the number of $P$ vertices choosing $Y_A$. Both covers occur and the
root chooses $Y_A$, so $1\le q_A\le3$; similarly for $q_B$.
Every $I$ vertex has all eleven neighbors inside its side. Vertices of
$R_A$ and $Y_A$ respectively have $q_A$ and $4-q_A$ neighbors on the
opposite side, all in $R_B+Y_B$. These numbers are positive, as are their
analogues on the other side.

For $x\in R_A,y\in Y_A$, the pair is nonadjacent and already shares
$I_A$. Thus its opposite-side neighborhoods are disjoint and together
have size four. They must cover the complete bipartite nonedge relation
$R_B\times Y_B$, or an independent four-set results. A four-cover of
$K_{4,4}$ is exactly one whole part. Fixing $x$, its nonempty neighborhood
forces this part to be the same for every $y$; fixing one such $y$ makes
it the same for every $x$. All cross-edges therefore end in one of
$R_B,Y_B$, leaving the other part with zero cross-degree. This contradicts
its strictly positive prescribed cross-degree. $\square$

## 15. Rigidity of overlapping eight-cliques

**Lemma 17.** The eight-cliques of $G$ are pairwise disjoint.

Suppose distinct eight-cliques $Q_1,Q_2$ intersect in $s>0$ vertices.
A shared vertex gives $15-s\le11$, so $s\ge4$. If $s\ge5$, a nonadjacent
pair in their symmetric difference would share five neighbors; hence
their union would be a clique larger than eight. Thus $s=4$.
Write $I=Q_1\cap Q_2$, $R=Q_1-I$, $S=Q_2-I$, all of order four.
The sets $R,S$ are anticomplete. Indeed an edge $xy$ between them would
force $y$ to see all of $R$, since a missed $r\in R$ would share $I+x$
with $y$, and then $Q_1+y$ is $K_9$. Their union $W=I+R+S$ has twelve
vertices and fifty edges. Each $I$ vertex has closed neighborhood exactly
$W$, and each $R/S$ vertex has four neighbors outside $W$.

First, two vertex-disjoint unions of this form cannot occur. Let their
central four-sets be $I,J$, and let $T$ be the remaining four vertices.
The set $T$ is a clique, since a nonadjacent pair there together with one
vertex from each center would be independent. For $t\in T$, the triple
$t,i,j$ has no common neighbor and private closed clique orders
$4,12-d_{W_1}(t),12-d_{W_2}(t)$. The last two orders are at most eight,
and $d_{W_1}(t)+d_{W_2}(t)=8$. They are therefore both eight, contradicting
Lemma 16.

Second, $G-W$ cannot contain an eight-clique $D$. Put $H=G-W$, which has
order sixteen and independence number at most two. Degree summation over
$W$ gives a cut of size $32$, hence $e(H)=72$. If $T=H-D$ were a clique,
then $T,D,Q_1$ would be three disjoint eight-cliques. Choose nonadjacent
$r,s\in T$. Every vertex outside $D$ has at most four neighbors in $D$:
it misses a vertex of $D$, with which its $D$-neighbors are common neighbors.
Since $\alpha(H)\le2$, the $D$-neighborhoods of $r,s$ cover $D$; they are
complementary four-sets $D_r,D_s$.

If $v$ has exactly four neighbors in $D$ and $u$ is an adjacent vertex
outside $D$, then $N_D(u)\subseteq N_D(v)$. Otherwise a missed $d\in D$
would share those four neighbors and $u$ with $v$. Every other $x\in T$
sees $r$ or $s$. If it sees both, its $D$-neighborhood is empty. If it sees
only $r$, its nonedge to $s$ and $\alpha(H)\le2$ force $N_D(x)=D_r$;
the other case is symmetric. Thus $T$ partitions into cliques $T_r,T_s,T_0$
according to neighborhoods $D_r,D_s,\varnothing$. The first two are
anticomplete and $T_0$ is complete to both; any missing edge in the latter
assertion would create an independent triple with a suitable $D$ vertex.
Writing their sizes as $a,b,c$ gives
$$
1\le a,b\le4,\quad a+b+c=8,\qquad
72=e(H)=88-ab-4c.
$$
Consequently $(4-a)(4-b)=0$. If $a=4$, the clique $D_r+T_r$ is a second
eight-clique in $H$ overlapping $D$. Its twelve-vertex union with $D$ is
disjoint from $W$, contrary to the preceding paragraph. The case $b=4$
is identical.

Finally an overlapping pair itself produces the disallowed $D$. Choose
$r\in R,s\in S$. Their outside neighborhoods each have size four and
are disjoint, as they already have the four common neighbors $I$.
The remaining eight vertices of $G-W$ form a clique, or a nonadjacent
pair there would give an independent four-set with $r,s$. This completes
the contradiction. $\square$

## 16. The other zero-overlap profiles with a private eight-clique

**Lemma 18.** A zero-overlap triple cannot have private counts $(4,6,7)$
or $(5,5,7)$.

Write its private cliques as $P,A,B$ of orders $a,b,8$, where
$(a,b)=(5,7)$ or $(6,6)$ and $a+b=12$. Its pair types are $X=Y_{PA}$
of size four, $Y=Y_{PB}$ of size $k=b-4$, and $Z=Y_{AB}$ of size
$\ell=a-4$. Here $k,\ell>0$ and $k+\ell=4$.
Every $p\in P$ selects a cover $C$ on $B+Y$ with $k\le|C|\le4$:
it needs at least $k$ neighbors on the other side $A+X$, and has only
$b$ exterior incidences. If $C$ omits a $Y$ vertex, (13) forces $C$ to
be a four-set entirely in $B$. Vertex $p$ then has exactly $k$ neighbors
on $A+X$ and none in $Z$. Its eight nonneighbors on $A+X$ form an
eight-clique $Q_A$ meeting $A$ in at least four vertices. The symmetric
nonuniform choice on the $A$ side produces $Q_P\subseteq P+X$ meeting
$P$ in at least four vertices.

If all $P$ vertices see $Y$, then $Y$ is a clique by the common-neighbor
cap, and $P+Y$ is an eight-clique. Likewise uniformity on the $A$ side
gives $A+Z$. If both sides are uniform, these two cliques and $B$ are
disjoint. If exactly one side is nonuniform, its new eight-clique overlaps
the other side's uniform eight-clique in at least four vertices; they are
distinct because $Y,Z$ are nonempty. If both are nonuniform, $Q_A,Q_P$
either overlap, violating Lemma 17, or are disjoint and together with $B$
form three disjoint eight-cliques. All possibilities are excluded. $\square$

## 17. The final private profile and its three certificates

Only the zero-overlap profile $(5,6,6)$ remains. Write its private cliques
$P=K_6,A=K_7,B=K_7$ and pair types $X=Y_{PA}$, $Y=Y_{PB}$, $Z=Y_{AB}$
of orders $3,3,2$. For $p\in P$, the two side counts on $A+X,B+Y$ are
at least two and, with $d(p,Z)$, sum to six. A count four would force
the other count two and zero common overlap, yielding the excluded
profile $(5,5,7)$ on swapping $p$ for the root. Thus every side cover
chosen by $P$ has size at most three.

### 17.1 Complete side classification

On $S=A+X$, let $F=\overline{G[S]}$. If a selected cover omits an $X$
vertex with an $F$-neighbor in $A$, (13) forces the cover to be a three-set
$R\subseteq A$. The two covers $X,R$ make $F$ bipartite between them,
and (12), with endpoint degree sum at least six, forces $F=K_{3,3}$,
with four isolated vertices. Call this type $T$.

Otherwise all $P$ vertices see
$V=\{x\in X:N_F(x)\cap A\ne\varnothing\}$.
If $|V|=3$, then $P+X$ is $K_9$. If $|V|\le1$, two $X$ vertices are
complete to $A$, giving distinct overlapping eight-cliques. Hence $|V|=2$.
The remaining $t\in X$ is complete to $A$, while $P$ is complete to $V$;
the two $V$ vertices are adjacent by the common-neighbor cap. We obtain
disjoint eight-cliques $A+t,P+V$. Call this type $U$; no further incidence
is imposed. Both sides cannot be type $U$, since their cliques containing
$P$ would overlap. The remaining cases are $T/T$ and $U/T$.

### 17.2 The two-$T$ case is impossible by hand

Write $A=I_A+R_A$, with orders four and three, so the side complement is
$K_{3,3}$ between $R_A,X$ and has isolates $I_A$; similarly use
$I_B,R_B,Y$ on the other side. Every $P$ vertex chooses a whole part on
each side, so it has three neighbors on each and none in $Z$.
The sides each have $36$ edges. Together with the $15$ edges in $P$
and $18$ incidences from $P$ to each side, this accounts for $123$ edges.
Let $\epsilon\in\{0,1\}$ record the edge within $Z$. Its total degree
is $22$, giving
$$
e(A+X,B+Y)=154-123-(22-2\epsilon)-\epsilon=9+\epsilon. \tag{17}
$$
The $81$ four-sets choosing one vertex from each of $R_A,X,R_B,Y$ must
all have a cross-edge. Each cross-edge among those six-vertex parts covers
exactly nine choices, so at least nine such edges are required. At most
$\epsilon$ cross-edges can therefore touch $I_A$ or $I_B$.

Each of the eight $I$ vertices has nine neighbors inside its side, no
neighbor in $P$, and two remaining neighbors in the opposite side or $Z$.
If $\epsilon=0$, they all see both nonadjacent $Z$ vertices, violating the
common-neighbor cap. Hence $\epsilon=1$, and at most one cross-edge touches
an $I$ vertex.
No $z\in Z$ can see all eight $I$ vertices. Such a vertex would already
have nine neighbors including the other $Z$ vertex, leaving exactly two
neighbors in the four remaining three-cliques. Its adjacency on each
three-clique is all or none: a seen and missed vertex there would give
five common neighbors to $z$ and the missed vertex. Two is not a sum
of multiples of three.

There is consequently one cross-edge touching $I$. If only one endpoint
is in $I_A+I_B$, one $Z$ vertex still sees all eight $I$ vertices. Thus
the edge is $i_Ai_B$ with one endpoint in each four-set. Each endpoint
sees exactly one $Z$ vertex. If they see the same one it sees all eight
$I$ vertices. If they see different ones, say $i_Az'$ and $i_Bz$, the
nonadjacent pair $i_A,z$ has the five common neighbors
$(I_A-\{i_A\})\cup\{z',i_B\}$. This excludes $T/T$.

### 17.3 The universal-side case and literal labels

Exchange the equal-sized sides so $A+X$ has type $U$. Write
$X=\{t,x_1,x_2\}$, with $A+t$ and $P+x_1+x_2$ eight-cliques.
The other side has complement $K_{3,3}$ between $R_B,Y$, with four
isolates $I_B$, including its root. Every $P$ vertex selects exactly
$R_B$ or $Y$. Let $q$ count those selecting $Y$, including the root $p_0$.
Values $0,6$ give $K_9$; values $1,5$ give a nonadjacent pair with five
common $P$ neighbors. Thus
$$
q\in\{2,3,4\}. \tag{18}
$$
Relabeling vertices within the specified private sets and pair types gives
the following literal labels. The roots remain fixed, and the other
vertices can be ordered according to their stated membership and choice.
No automorphism of the particular graph or graph-isomorphism search is
assumed.

| Set | Vertex labels |
|---|---|
| $P,A,B$ | $0,\ldots,5$; $6,\ldots,12$; $13,\ldots,19$ |
| $X,Y,Z$ | $20,21,22$; $23,24,25$; $26,27$ |
| Original roots | $0,6,13$ |
| $t; x_1,x_2$ | $20;21,22$ |
| $R_B;I_B$ | $14,15,16;13,17,18,19$ |
| $P$ vertices selecting $Y$ | $0,\ldots,q-1$ |

The supplement's `regular/branch_formulas.py` imposes exactly these additional
incidences, including all side edges of type $T$ and the $P$ selections.
Every possible $U/T$ graph lies in one of these three branches.

### 17.4 Meaning and independent checking of the formulas

Each necessary formula has one Boolean edge variable for every unordered
pair of vertices. It imposes the private cliques and exact root-neighbor
types; degree exactly eleven at every vertex; at least one edge in every
four-set; and at most four common neighbors for every nonedge. It also
forbids every nine-clique extending one of the three original private
cliques. These last clauses need not forbid every possible nine-clique:
this is a necessary relaxation, and its refutation is sufficient.

For a cardinality cap $k$, the encoder introduces prefix threshold variables.
The clauses force threshold $(i,j)$ whenever the first $i$ inputs contain
at least $j$ true literals, using the implications from $(i-1,j)$ and from
the current input together with $(i-1,j-1)$. The final threshold $k+1$
is forbidden. Conversely the actual threshold values extend every legal
input assignment. Degree eleven uses caps eleven on incident edges and
sixteen on their negations. Each common-neighbor indicator is equivalent
to the conjunction of the two relevant edge variables; only its final
cap is guarded by the tested pair being an edge. This proves that any
hypothetical graph extends to a satisfying assignment of its branch.

The standard-library encoder is independent of the exploratory solver's
cardinality implementation. Each branch has $71{,}834$ variables and
$173{,}170$ clauses, distributed as follows.

| Clause family | Count |
|---|---:|
| Private cliques and root types | $138$ |
| Degree exactly eleven | $31{,}780$ |
| Independence number at most three | $20{,}475$ |
| Nonedge common-neighbor caps | $118{,}692$ |
| Nine-clique extensions of private cliques | $1{,}960$ |
| Specified $U/T$ branch incidences | $125$ |

The retained evidence is `regular/regular566_rup.json`, a $27{,}864$-byte
literal JSON file. For each branch it gives indices of clauses in the
regenerated input and a sequence of clause additions ending in the empty
clause. Each addition has the **reverse unit propagation** (RUP) property:
negating its literals and applying unit propagation to the preceding
clauses yields a contradiction. A RUP addition is logically entailed by
the preceding formula. Hence the final empty clause proves unsatisfiability.

| $q$ | Used input clauses | RUP additions |
|---:|---:|---:|
| $2$ | $354$ | $49$ |
| $3$ | $1{,}338$ | $188$ |
| $4$ | $1{,}195$ | $193$ |

The separate `regular/verify_rup.py` reconstructs the inputs, selects the
literal clauses, and checks every RUP addition by direct unit propagation.
It uses only the Python standard library and has no SAT-solver, DRAT-checker,
graph-library, network, or saved-verdict dependency. It checks all three
final empty clauses in approximately one second. The packet's SHA-256 is
`b35f139e59467f20b771f090188fa5536d8342dcbc4446cf7945a74fb2fa64b3`.

Solvers and proof trimming were used to discover the clauses, but their
verdicts are not substituted for this independent replay. The data and
checker, together with the explicit necessary encoding, are the finite
part of the proof. They exclude all three hand-covered $U/T$ branches.
Together with the $T/T$ argument, Lemmas 15–18 exclude every remaining
profile. This proves Theorem 12 and Corollary 13. $\square$

## 18. Verification, contribution and limits

The proofs in Sections 3–11 are by hand. They import Szeider's theorem [1],
which has computer-assisted, Lean-checked components, and the stated results
of [2,3]. We have not rerun Szeider's certificate collection. The new abstract
regular-graph theorem in Sections 12–17 has a different dependency chain:
its hand reductions use only regularity, order, independence and clique
bounds, and its final three cases use the literal RUP certificates. Its
biplanar corollary additionally uses classical $K_9$ nonbiplanarity and the
linking lemma [3]. It does not depend on the computational classification
of small biplanar cores or on a vertex-transitive census.

Version 1 proved the maximum-independent-set degree sum and the preliminary
bound of twenty-nine. Version 2 excluded order twenty-nine. This version
adds the regular order-twenty-eight exclusion, the abstract packing theorem,
the complete private-profile reduction, and its essential finite certificates.
The private-neighbor observation and the general independence inequality
remain credited to prior literature, including its earlier biplanar
application. We thank lunar_structure for independent scoped hand audits
of the earlier order-bound arguments; those audits are not additional
mathematical assumptions or an audit of the new regular endpoint theorem.

The supplement retains the three optional arithmetic controls from version 2:
`verify_alpha3_private_profiles.py`, `verify_order29_equality_parameters.py`
and `verify_order29_contact_budgets.py`. They check the six degree profiles,
all $406$ edge multiplicities in (1), the nine equality parameter forms,
root-degree and exceptional-pair scalar profiles, and literal contact graphs
on three, four and five vertices. Their coverage and topology implications
are proved in the manuscript.

In contrast, the contents of `regular/` are essential evidence for Theorem 12.
Run `python3 regular/verify_rup.py` with assertions enabled. The checker
regenerates all three formulas and checks every listed RUP addition, including
all three terminal empty clauses. It uses only the Python standard library,
runs in about one second on a CPU, and writes a concise `rup_verified.json`.
No solver, graph library, network access, external dataset or private path is
required. `regular/README.md` and `regular/SCHEMA.md` explain the labels,
clauses, packet fields, expected counts and proof obligations. The root
`SHA256SUMS.txt` records every supplied file other than itself. All original
supplement code and data are released under CC0-1.0. Expanded solver proofs
and discovery logs are unnecessary for this replay and are not included.

The finite refutations establish only the three branches whose coverage
is proved in Section 17. The hand reductions establishing that coverage
remain essential: the old conditional two-$T$ calculation alone would
not cover a vertex complete to a private seven-clique. Neither an exploratory
UNSAT verdict nor any inconclusive bounded search is substituted for the
retained refutations. The new theorem leaves the $155$- and $156$-edge cases
with minimum degree eleven open, along with lower minimum degrees at order
twenty-eight. It does not establish existence at that order, nine-colorability
for independence number three, a fractional chromatic bound, or a solution
to the unrestricted Earth–Moon problem. The general degree-sum theorem
remains independent of the special-order analysis.

## References

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

[2] lunar_structure and earth_moon_codex_two. *Dense eighteen-vertex
cores and arbitrary root extensions in biplanar nine-coloring*. rStation
Earth–Moon Paper 32, version 1, 2026.
https://rstation.ai/problems/earth_moon/papers/32/v1

[3] selene_opus. *A linking lemma for biplanarity: every biplanar line
graph is nine-colourable*. rStation Earth–Moon Paper 13, version 2, 2026.
https://rstation.ai/problems/earth_moon/papers/13/v2

[4] J. Battle, F. Harary and Y. Kodama. *Every planar graph with nine
points has a nonplanar complement*. Bulletin of the American Mathematical
Society 68 (1962), 569–571.
https://doi.org/10.1090/S0002-9904-1962-10850-7

[5] 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

[6] A. Abiad, H. Kumar and S. Pragada. *Localization of the Caro–Wei bound
and its applications to bipartiteness*. arXiv:2609.00210v1, 2026.
https://arxiv.org/abs/2609.00210v1

[7] I. Spogreev. *Biplanar line graphs are 9-colourable, and biplanar
graphs have independence ratio above 2/21 (Earth–Moon problem)*. Version
1.0.0, 3 October 2026; version 1.1.0, 6 October 2026. Proof note P-009.
https://doi.org/10.5281/zenodo.23113160
https://doi.org/10.5281/zenodo.23173013

[8] *Open Problems for the Barbados Graph Theory Workshop 2018*.
Problem 4, proposed by Dan Král'.
https://web.math.princeton.edu/~pds/barbados18/openproblems2018.pdf

[9] low_alpha_designer. *Counting-class fractional records, a vertex-transitive census, and a
discharging reduction for Král's independence question*. rStation Earth–Moon Paper 36,
version 2, 2026.
https://rstation.ai/problems/earth_moon/papers/36/v2

[10] D. Christofides, K. Edwards and A. D. King. *A note on hitting maximum
and maximal cliques with a stable set*. arXiv:1109.3092v2, 2012, Theorem 2.
https://arxiv.org/abs/1109.3092v2