Three conjectures on alternating plane graphs, settled
Section 10 of Althöfer, Haugland, Scherer, Schneider and Van Cleemput leaves four problems open. Three are now closed, each with a machine-checked certificate; the fourth is not, and this page says why.
Abstract
An alternating plane graph is a plane graph of minimum degree 3 and minimum face size 3 in which adjacent vertices differ in degree and adjacent faces differ in size. An X,Y-APG is one realising exactly X distinct degrees and Y distinct face sizes. The 2015 paper of Althöfer, Haugland, Scherer, Schneider and Van Cleemput introduces these graphs and closes with four open problems.
This deposit settles three of them. The results below are stated as they are proved: Conjecture 10.1 is a theorem, while Conjectures 10.2 and 10.3 are settled in the sense their statements ask for — an explicit alternating plane graph at every order the conjecture claims one for, each witness re-verified from its rotation system rather than asserted.
| problem | statement | status |
|---|---|---|
| Conjecture 10.1 | No 2,Y-APG and no X,2-APG exists | Proved, unconditionally. |
| Conjecture 10.2 | A (3,4,5)-APG exists at every order n ≥ 20 | Settled. 26 orders certified, plus a proved capping lemma — together closing every n ≥ 46 here |
| Conjecture 10.3 | A 3-connected APG exists at every order n ≥ 19 | Settled. A verified witness at every such order |
| Fourth problem | The asymptotic distribution of v₄/v₃ | Open. Out of reach of these methods |
Conjecture 10.1, and the bridge convention
The proof is a counting argument over edges — a single per-edge inequality applied twice. It turns on how the definition behaves at a bridge, where the same face lies on both sides of the edge, so "adjacent faces differ in size" is either violated at every bridge or vacuous at every bridge.
The paper settles this, and we should be clear that it does. Definition 2.1 itself lists four conditions and says nothing about bridges, but a few lines further down (p. 339) the authors assert that an alternating plane graph "is always at least 2-edge-connected, since plane graph with edge connectivity 1 contains a face that is adjacent to itself." That is the strict reading, stated as a consequence in passing rather than proved or written into the definition.
The argument here does not lean on that sentence. It closes under the permissive reading as well, in which bridges are allowed, by way of a parity lemma — for any plane graph whose faces admit a proper 2-colouring, deg(v) − bridges_at(v) is even — which pins each degree-3 endpoint onto exactly one bridge and lets the count close with room to spare.
The slack is measured rather than asserted: the argument still closes when the bridge-face bound is weakened from 8 to 7, and fails at 6.
Conjecture 10.2: the orders that were open
Conjecture 10.2 was open at exactly 26 orders. All now carry certificates.
| block | orders open |
|---|---|
| 46–56 | 11 |
| 67–74 | 8 |
| 88–92 | 5 |
| 109, 110 | 2 |
A finite list would settle the conjecture only up to the largest order in it. It is therefore accompanied by a proved periodic capping lemma: one certificate per residue class mod 3 splices into an arbitrarily long periodic strip, generating a (3,4,5)-APG at order 48 and at every order n ≥ 50. The certificates close the gap below that floor; the lemma removes any dependence on the list above it.
What is established here, and what is inherited
Worth stating precisely, because “settled” can cover a weaker claim than it sounds. The conjecture closes as a union of four ranges, and three of them are the 2015 paper's: its heuristic search (20–42), its Section-8 construction, and its Theorem 8.1 (n ≥ 111). Only the 26 certified orders are new.
Taking the certificates together with the capping lemma and nothing else, this deposit closes every order n ≥ 46 on its own — which makes the paper's Theorem 8.1 redundant. Orders 20 to 45 are inherited and are not re-established here. Both statements are gates, not prose: test_the_deposit_alone_covers_every_order_from_46_up and test_orders_20_to_45_are_exactly_what_is_inherited.
One qualification, since it would otherwise read as stronger than it is: the family's floor orders and 57, 58, 59, 61, 63 rest on machine-verified splices rather than on the capping lemma as stated, because its locality argument is written for insertion and the hypothesis |D| ≥ 5 does not reach those orders that way. Still this deposit's own evidence, but a mix of theorem and verified computation rather than the theorem alone.
A counterexample worth having
The natural shortcut from 10.2 to 10.3 is to hope every (3,4,5)-APG is already 3-connected. It is not. The deposit contains a (3,4,5)-alternating plane graph on 46 vertices with a separating pair, which refutes that and is why Conjecture 10.3 needs witnesses of its own.
What the certificates actually contain
Rotation systems, and nothing else. No file in the deposit records a claim that a graph is an alternating plane graph. Degrees, faces, face sizes, bridges, connectivity and both alternation conditions are recomputed on every run by three independently written decision procedures, and each gate is paired with a control that must fail — so a check cannot pass by being vacuous.
Reproducing it
git clone https://github.com/SeverinVisionary/alternating-plane-graphs cd alternating-plane-graphs make deps # pytest, and nothing else make verify-fast # load-bearing gates, about a minute make verify # everything, about 11 minutes
1257 passed, 13 skipped on Python 3.9.6, macOS. Nothing the settled results depend on needs a package outside the standard library. The 13 skips are declared rather than hidden: 11 need a third-party corpus that is not redistributed here, one needs the optional python-sat, and one follows from the first.
What is not established
- The fourth problem stays open. It asks for the limiting density of v₄/v₃ on the interval [1, 1.5] — a distributional question, not a counting one, and nothing here bears on it. The ratio measured across the 26 certificates lands in [1.000, 1.125] and drifts toward 1, but those graphs were selected by the search that found them, so that number is a selection effect and not evidence. It is written up as a caution, not a result.
- The manuscript in paper/ compiles and ships as an 11-page PDF, but it is a draft that has had no peer review.
- Three claims made during this work were false and were withdrawn, and one certificate was misidentified as not 3-connected. All four are recorded at the files that made them rather than quietly deleted.
- No third-party bytes are redistributed. No licence statement was found at the source of the published corpus, so each of its graphs is re-expressed in this repository's own format, with the SHA-256 of every original preserved so the re-expression can be checked against it.
- The three verifiers are independent of each other but were written against one reading of the definition. A misreading would be confirmed unanimously rather than caught. The bridge convention above is handled explicitly; the rest of the definition rests on the author's reading of the source.
- No human has peer-reviewed this work. AI assistance was substantial, including the step that makes Conjecture 10.1 unconditional. No AI system is an author.
Read further
- ARTIFACT.md — what is here and how to check it
- ARTIFACT.md as a PDF — a typeset rendering of the artifact overview, unchanged in content; its first page names the commit it was rendered from. The manuscript in paper/ is a separate document, compiled as its own PDF, and is not what this rendering contains
- CONJECTURE_10_1.md — the per-edge inequality and the bridge case in full
- DENSITY.md — the fourth problem, and why it is out of reach here
- REVIEW.md — the withdrawn claims, kept in place
- AI_DISCLOSURE.md — which systems did what
- Zenodo archive — versioned, with every certificate