arxiv: 2604.03433 · v1 · submitted 2026-04-03 · 🧮 math.CO

Recognition: 1 theorem link

· Lean Theorem

New minor minimal non-apex graphs

Andrei Pavelescu , Elena Pavelescu , Madeline Potter

Authors on Pith no claims yet

Pith reviewed 2026-05-13 18:01 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C8305C10

keywords apex graphsforbidden minorsminor-closed familiesJørgensen conjecturegraph enumerationK6 minor

0 comments

The pith

All forbidden minors for apex graphs with 12 or fewer vertices and 26 or fewer edges have been enumerated.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Apex graphs become planar after deletion of one vertex. The property is closed under taking minors, so the class is defined by a finite collection of forbidden minors. This paper computes the complete list of minor-minimal non-apex graphs on at most 12 vertices and on at most 26 edges. It also proves that every graph on 13 vertices with minimum degree 6 is either apex or contains a K6 minor, confirming Jørgensen's conjecture at that order.

Core claim

The paper lists every minor-minimal non-apex graph with 12 or fewer vertices and every such graph with 26 or fewer edges. It further establishes that any graph on 13 vertices with minimum degree at least 6 is apex unless it contains a K6 minor.

What carries the argument

The minor-minimal non-apex graphs, which act as the forbidden minors that characterize the minor-closed family of apex graphs.

If this is right

Explicit lists of small forbidden minors now exist for direct use in checking whether a graph is apex.
Jørgensen's conjecture holds for every graph on exactly 13 vertices.
The enumerated graphs supply a verified base set for extending the search to larger orders and edge counts.
Any future complete characterization of apex graphs must include these minimal examples.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same enumeration strategy could be scaled to push the known bounds on forbidden minors beyond 12 vertices and 26 edges.
The minimum-degree-6 condition used for order 13 may extend to higher orders and help resolve the full conjecture.
These lists provide concrete test instances for software that decides whether deleting one vertex yields a planar graph.

Load-bearing premise

The computational enumeration has examined every graph on 12 or fewer vertices and every graph with 26 or fewer edges and has found all minor-minimal non-apex examples without omissions.

What would settle it

A minor-minimal non-apex graph on 12 or fewer vertices that does not appear in the enumerated list, or a 13-vertex graph of minimum degree 6 that is neither apex nor contains a K6 minor.

Figures

Figures reproduced from arXiv: 2604.03433 by Andrei Pavelescu, Elena Pavelescu, Madeline Potter.

**Figure 1.** Figure 1: Minor of G. The vertices v1 and v8 are adjacent to a, b, c, d, e, and f. Assume that N is isomorphic to the prism graph, with labels as in [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** Figure 2: The neighborhood of v1. induce a clique in G, then contracting an edge connecting v to one of its neighbors in N and then contracting all edges of H \ {v} gives a minor that contains a subgraph isomorphic to the graph in [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: Minor of G. The vertices v1 and v8 are adjacent to a, b, c, d, e, and f. Assume that for all vertices v ∈ V (H), the set of neighbors of v in N induces a clique in G. In particular, v13 is adjacent to three vertices of N and degH(v13) = 5. Without loss of generality, assume that v13 is adjacent to v2, v4, and v6, as labeled in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: Graphs of order 6 and size 12 that have a vertex of degree 5. The first two graphs in [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗

read the original abstract

A graph is apex if it becomes planar after the deletion of one vertex. The family of apex graphs is closed under taking minors, so it is characterized by a finite set of forbidden minors. Determining the finite set of forbidden minors for apex graphs remains an open question. In this paper, we list all forbidden minors for apex graphs with 12 or fewer vertices and all forbidden minors for apex graphs with 26 and fewer edges. We also present graphs outside of these ranges. We show that a graph with 13 vertices and minimal degree 6 is either apex or contains a $K_6$ minor, proving J\o rgensen's conjecture for order 13.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the full lists of minimal non-apex graphs on ≤12 vertices and ≤26 edges plus a clean proof for the 13-vertex case of Jorgensen's conjecture.

read the letter

This paper lists every minor-minimal non-apex graph with at most 12 vertices and every one with at most 26 edges, and it proves that any 13-vertex graph with minimum degree 6 is either apex or contains a K6 minor. Those two pieces are the actual new content. The lists fill in the small-order cases that prior work left open, and the degree-6 argument for order 13 is self-contained and does not rely on the enumeration. Both results are concrete and usable by anyone working on the apex minor characterization. The computational part is where the main uncertainty sits. The claim that the lists are complete depends on the generation routine hitting every isomorphism class and on the planarity test being reliable for every candidate. If either step has a gap, the “all” statements are not quite right. The order-13 proof stands apart from that risk. This work is aimed at graph theorists who study minor-closed families and need the small cases pinned down. The lists themselves are worth having even while the full set of forbidden minors remains unknown. I would send it to peer review so the enumeration details and the 13-vertex argument can be checked directly.

Referee Report

3 major / 3 minor

Summary. The paper enumerates all minor-minimal non-apex graphs on at most 12 vertices and all such graphs with at most 26 edges. It additionally proves that every 13-vertex graph with minimum degree 6 is either apex or contains a K6 minor, thereby establishing Jørgensen's conjecture for this order.

Significance. The explicit lists of forbidden minors in the bounded vertex and edge ranges supply concrete data that can be used to test conjectures and to guide further theoretical work on the (still unknown) full set of apex forbidden minors. The order-13 proof is a self-contained theoretical contribution that stands independently of the enumeration and advances the conjecture in a verifiable way. The combination of exhaustive search with a direct proof is a standard and useful methodology in minor-closed graph families.

major comments (3)

[§3] §3 (Enumeration procedure): the manuscript asserts that the generation produces every non-isomorphic graph on ≤12 vertices and correctly classifies each by testing whether deletion of any vertex yields a planar graph, but supplies no explicit description of the canonical generator employed, the isomorphism filter, or the planarity oracle implementation; without these details the central claim that the listed graphs are exactly the forbidden minors cannot be independently verified.
[§4] §4 (Edge-bounded enumeration): the argument that all minimal non-apex graphs with ≤26 edges have been found rests on an implicit bound on the search space, yet the text does not state whether the edge-restricted search was performed independently of the vertex-restricted search or how graphs with more than 12 vertices but ≤26 edges were generated and checked for minimality.
[§5] §5 (Order-13 proof): the case analysis for a 13-vertex graph G with δ(G)≥6 that is not apex must explicitly construct a K6 minor from the non-planarity of every G−v; the current sketch leaves open whether the reduction uses only the minimum-degree hypothesis or invokes additional structural lemmas that are not stated.

minor comments (3)

[Abstract] The abstract states the two enumeration results but does not report the cardinalities of the two lists; adding these numbers would immediately convey the scale of the computational output.
[Figures] Figures displaying the enumerated graphs should include vertex labels or adjacency lists so that readers can directly confirm the claimed non-apex property and minimality.
[§3] A short table summarizing the number of graphs found per vertex count (or per edge count) would improve readability of the computational results.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We are grateful to the referee for the positive assessment of the significance of our work and for the detailed comments that will help improve the manuscript. We respond to each major comment below, agreeing to incorporate clarifications and expansions as suggested.

read point-by-point responses

Referee: [§3] §3 (Enumeration procedure): the manuscript asserts that the generation produces every non-isomorphic graph on ≤12 vertices and correctly classifies each by testing whether deletion of any vertex yields a planar graph, but supplies no explicit description of the canonical generator employed, the isomorphism filter, or the planarity oracle implementation; without these details the central claim that the listed graphs are exactly the forbidden minors cannot be independently verified.

Authors: We agree that additional details are necessary for independent verification. In the revised version, we will explicitly describe the canonical generator (based on the nauty library with specific parameters for generating non-isomorphic graphs up to 12 vertices), the isomorphism filter (using canonical labeling to eliminate duplicates), and the planarity oracle (implemented via the Boyer-Myrvold algorithm as provided in the Boost Graph Library). This will allow readers to reproduce the enumeration process. revision: yes
Referee: [§4] §4 (Edge-bounded enumeration): the argument that all minimal non-apex graphs with ≤26 edges have been found rests on an implicit bound on the search space, yet the text does not state whether the edge-restricted search was performed independently of the vertex-restricted search or how graphs with more than 12 vertices but ≤26 edges were generated and checked for minimality.

Authors: The edge-bounded enumeration was performed independently using a separate generation procedure that enumerates all graphs with at most 26 edges and up to a sufficient number of vertices (noting that for minimal non-apex graphs, the number of vertices is bounded by the edge count due to the structure of apex graphs). We will add a subsection clarifying this independence and the method for handling graphs with more than 12 vertices, including how minimality was verified by checking all proper minors. revision: yes
Referee: [§5] §5 (Order-13 proof): the case analysis for a 13-vertex graph G with δ(G)≥6 that is not apex must explicitly construct a K6 minor from the non-planarity of every G−v; the current sketch leaves open whether the reduction uses only the minimum-degree hypothesis or invokes additional structural lemmas that are not stated.

Authors: The case analysis in §5 relies exclusively on the minimum-degree condition δ(G) ≥ 6. We will expand the proof to provide a detailed, explicit construction of the K6 minor in each case, showing step-by-step how the non-planarity of each G−v, combined with the high minimum degree, guarantees the existence of the required disjoint paths and branch sets for the minor. No additional unstated structural lemmas are invoked; all steps follow directly from the degree hypothesis and basic minor theory. revision: yes

Circularity Check

0 steps flagged

No circularity: results rest on exhaustive enumeration and independent proof

full rationale

The paper claims to list all minor-minimal non-apex graphs on ≤12 vertices and ≤26 edges via computational enumeration, plus a direct proof that every 13-vertex graph of minimum degree 6 is apex or contains a K6 minor. No equations, fitted parameters, ansatzes, or self-citations appear in the derivation chain. The enumeration is asserted complete by the generation algorithm and planarity checks; the order-13 result is a separate combinatorial argument. These steps do not reduce to self-definition or to any prior result by the same authors that would create circularity. The claims are therefore self-contained against external verification of the enumeration procedure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the Robertson-Seymour theorem that every minor-closed family has a finite set of forbidden minors and on the assumption that exhaustive computational search up to the given bounds is feasible and complete.

axioms (1)

standard math Every minor-closed family of graphs has a finite set of forbidden minors (Robertson-Seymour theorem)
Invoked to guarantee that the set of forbidden minors for apex graphs is finite.

pith-pipeline@v0.9.0 · 5399 in / 1253 out tokens · 89864 ms · 2026-05-13T18:01:06.531856+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We list all forbidden minors for apex graphs with 12 or fewer vertices and all forbidden minors for apex graphs with 26 and fewer edges... Theorem 1. Let G be a simple graph of order 13 and minimal degree 6. Then either G contains a K6-minor or it is apex...

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Conway, J. H. and Gordon, McA.C. Knots and links in spatial graphs.J. Graph Theory7(4) (1983), 445–453

work page 1983
[2]

G., and Roy, A

Cai, J., Macready, W. G., and Roy, A. A practical heuristic for finding graph minors (2014),arXiv preprint arXiv:1406.2741

work page arXiv 2014
[3]

and Ke´ zdy, A.E

Jobson, A.S. and Ke´ zdy, A.E. All Minor-Minimal Apex Obstructions with Connectivity Two.Electron. J. Comb., Volume28, Issue 1 (2021)

work page 2021
[4]

Extremal graphs for contractions toK 7,Ars Combinat., vol

Jørgensen, L.K. Extremal graphs for contractions toK 7,Ars Combinat., vol. 25c (1988), 133–148

work page 1988
[5]

Contractions toK 8,J

Jørgensen, L.K. Contractions toK 8,J. Graph Theory18(1994), 431–448

work page 1994
[6]

Kawarabayashi,K., Norine,S., Thomas,R., Wollan,P.K 6 minors in large 6-connected graphs,J. Comb. Theory, Ser. B,Volume129(2018), 158-203. 12 ANDREI PA VELESCU, ELENA PA VELESCU, AND MADELINE POTTER

work page 2018
[7]

Sur le probl` eme des courbes gauches en Topologie.Fundam

Kuratowski, C. Sur le probl` eme des courbes gauches en Topologie.Fundam. Math.15(1) (1930), 271–283

work page 1930
[8]

Six variations on a theme: almost planar graphs.Involve - a journal of Mathematics11(2018), no

Lipton, M., Mackall, E., Mattman, T.W., Pierce, M., Robinson, S., Thomas, J., and Weinschelbaum, I. Six variations on a theme: almost planar graphs.Involve - a journal of Mathematics11(2018), no. 3, 413–448

work page 2018
[9]

Pavelescu, A., personal webpage, https://apaveles.wixsite.com/scientist-site/general-5

work page
[10]

Intrinsically knotted graphs and connected domination.Aus- tralasian Journal of Combinatorics94(1), 25–49

Li, G., Pavelescu, A., and Pavelescu, E. Intrinsically knotted graphs and connected domination.Aus- tralasian Journal of Combinatorics94(1), 25–49

work page
[11]

Homomorphies¨ atze f¨ ur graphen.Math

Mader, W. Homomorphies¨ atze f¨ ur graphen.Math. Ann.178(1968), 154–168

work page 1968
[12]

and Piperno, A

McKay, B.D. and Piperno, A. Practical Graph Isomorphism, II,J. Symb. Comp., Volume60(2014), 94–112

work page 2014
[13]

The complement problem for linklessly embed- dable graphs.J

Naimi, R., Odeneal, R., Pavelescu, A., and Pavelescu, E. The complement problem for linklessly embed- dable graphs.J. Knot Theory Ramif.31, No. 11 (2022), 2250075

work page 2022
[14]

New bounds on maximal linkless graphs.Algebraic & Geometric Topology23(6) (2023), 2545–2559

Naimi, R., Pavelescu, A., and Pavelescu, E. New bounds on maximal linkless graphs.Algebraic & Geometric Topology23(6) (2023), 2545–2559

work page 2023
[15]

Simple graphs of order 12 and minimum degree 6 contain K6 minors.Involve - a journal of Mathematics, 13(5) (2020), 829–843

Odeneal, R., Pavelescu, A. Simple graphs of order 12 and minimum degree 6 contain K6 minors.Involve - a journal of Mathematics, 13(5) (2020), 829–843

work page 2020
[16]

Maximal linklessly embeddable graphs,https://apaveles.wixsite.com/scientist-site/general- 5

Pavelescu, A. Maximal linklessly embeddable graphs,https://apaveles.wixsite.com/scientist-site/general- 5

work page
[17]

New minor minimal non-apex graphs.arxiv.org ancillary file

Pavelescu, A., Pavelescu, E., Potter, M. New minor minimal non-apex graphs.arxiv.org ancillary file

work page
[18]

Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs

Pierce, M. Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs. University of California, Chico, Senior Thesis (2014)

work page 2014
[19]

and Wilson, R.J

Read, R.C. and Wilson, R.J. An Atlas of Graphs, Oxford University Press, 2005

work page 2005
[20]

D., and Thomas, R

Robertson, N., Seymour, P. D., and Thomas, R. Linkless embeddings of graphs in 3-space.Bull. Amer. Math. Soc.28(1) (1993), 84–89

work page 1993
[21]

and Seymour, P

Robertson, N. and Seymour, P. D. Graph Minors. XX. Wagner’s conjecture,J. Comb.Theory, Ser. B 92(2), (2004), 325–357

work page 2004
[22]

On a spatial analogue of Kuratowski’s theorem on planar graphs - an open problem.Graph Theory, eds

Sachs, H. On a spatial analogue of Kuratowski’s theorem on planar graphs - an open problem.Graph Theory, eds. M. Borowiecki, J. W. Kennedy, and M. M. Syslo, Lecture Notes in Mathematics, vol. 1018, Springer (1983), 230–241

work page 1983
[23]

˜Aber eine Eigenschaft der ebenen Komplexe.Math

Wagner, K. ˜Aber eine Eigenschaft der ebenen Komplexe.Math. Ann.114(1) (1937), 570–590. andreipavelescu@southalabama.edu, Department of Mathematics and Statistics, University of South Alabama, Mobile, AL 36688, USA elenapavelescu@southalabama.edu, Department of Mathematics and Statistics, University of South Alabama, Mobile, AL 36688, USA mmp2123@jagmail....

work page 1937