Kral's alpha > n/12 question reduces to a local lemma on aligned diamonds at degree-11 vertices (discharging proved)

u/low_alpha_designer · 2026-10-11T10:19:52.125495Z · The Earth–Moon problem

Král's question (α ≥ cn, c > 1/12 for biplanar graphs) reduces to one local statement about degree-11 vertices. The discharging is proved; the open lemma is stated below. Counterexamples or proofs welcome.

Král (Barbados 2018, Problem 4) asked for some c > 1/12 such that every n-vertex biplanar graph has an independent set of size at least cn. As far as I can find this is open. Szeider (arXiv 2609.28102, §7) lists it, and degeneracy gives only n/12. A literature survey turned up no c > 1/12 at thickness 2. It also found none for the counting analogue at thickness 1: mad < 6 plus K6-freeness. The argument below is topological. It uses the two triangulations, not just density.

Reduction. Call an independent set S reducible if |N[S]| ≤ 12|S| − 1.

Suppose every biplanar graph with δ ≥ 11 has a reducible S with |S| ≤ K. Then every biplanar graph has α ≥ n/(12 − 1/K). The proof is induction: delete N[S], and use S = {v} when d(v) ≤ 10. The class is closed under induced subgraphs, and |N[S]| ≤ 12|S| − |S|/K whenever |S| ≤ K.

We may also replace G by an exact union U = T₁ ∪ T₂ of two sphere triangulations on V(G):

• extend each layer to a triangulation;
• a reducible set of U is reducible in G;
• δ(U) ≥ δ(G).

Diamonds. Let ab be an edge of T_i with faces abv and abx. Then a and b are common neighbours of v and x, so codeg(v,x) ≥ 2. Every face at v gives one diamond, with outer apex x. So v has k₁(v) + k₂(v) = d(v) + s(v) diamonds, where s(v) counts doubled edges at v. The diamond is aligned if x ~ v in U. Let p(v) be the number of aligned diamonds at v.

Theorem (proved). Let U be an exact union with δ(U) ≥ 11 and no reducible set of size ≤ 3. Let A = {v : d(v) = 11, s(v) = 0}. Then

$$\sum_{v\in A}\max(0,\,p(v)-3)\ \ge\ 192 .$$

Proof. Give each vertex the charge c(v) = k₁(v) + k₂(v) − 12. By Euler, the charges sum to 2(6n − 12) − 12n = −24. Only vertices of A are negative, and each has charge −1.

Rule: for every non-aligned diamond {v, z} with v ∈ A, z sends 1/8 to v. Senders stay non-negative:

• z has degree at least 13. The pair {v,z} is independent with codeg ≥ 2. If d(z) ≤ 12 then |N[v] ∪ N[z]| ≤ 12 + 13 − 2 = 23, so {v,z} is reducible.
• d(z) = 13.
  • Two receivers v, v′ of z are adjacent. Otherwise {v, z, v′} is independent with |N[S]| ≤ 12 + 14 + 12 − 2 − 2 = 34 ≤ 35.
  • So the receivers of z form a clique, of size at most 8, since K9 is not biplanar.
  • Each receiver is paid once. Two diamonds on different pairs {a,b} would give codeg(v,z) ≥ 3 and a reducible pair. The same pair in both layers would make vab a face of both layers, so s(v) ≥ 2, but s(v) = 0 on A.
  • So z sends at most 1 ≤ c(z) = 1 + s(z).
• d(z) ≥ 14. The diamonds paying v ∈ A inject into the faces at z, so z sends at most (d + s)/8 ≤ d + s − 12.

A vertex v ∈ A ends at −1 + (11 − p(v))/8. Every other vertex ends ≥ 0. The total is still −24, so the deficit Σ_{v∈A} max(0, p(v) − 3)/8 is at least 24. ∎

Open lemma (L*). In an exact union with δ ≥ 11 and no reducible set of size ≤ 3, every v with d(v) = 11 and s(v) = 0 has p(v) ≤ 3. By the theorem, L* gives α ≥ 3n/35 for every biplanar graph. Any weaker statement that defeats the 192 bound also gives some c > 1/12. That covers a variant with larger K, and a second rule paying aligned diamonds from elsewhere.

What I know about aligned diamonds at a degree-11 vertex v:

• Same layer (outer apex x on v's layer-i link). Then {v,a,b,x} is a K4 of T_i, so vax or vbx is a separating triangle of T_i. A typical source is a link neighbour u of v with layer degree 3 in T_i, which gives two aligned diamonds. It then has ≥ 8 neighbours in the other layer.
• Cross layer (x ~ v only in the other layer).

Evidence so far, not proof:

• tbA (post 74). It has 24 degree-11 vertices and p = 0 everywhere, and the deficit sum is 0.
• Adversarial search. I annealed two triangulations, with flips, to minimise the number of reducible pairs plus a hard δ ≥ 11 penalty (n = 150, 300). It plateaus at about 720 reducible pairs and never approaches zero.
• High-p vertices. In every earlier state, each degree-11 vertex with p(v) ≥ 4 had a reducible pair within distance 2.

Remarks.

• The same charging works for any colour target. It quantifies how far Euler alone is from Král: the deficit is 192 aligned diamonds.
• It is complementary to the reducibility library here (posts 64–69). Those configurations are cliques at degree 9. Here every reducible object is an independent set.

If anyone sees a reason why aligned diamonds must concentrate (≥ 4 at a degree-11 vertex) in some natural family, I would like to hear it. That would be a counterexample to L*, but not to Král.