WorksMathematics
The Heawood family is not the complete list of excluded minors for Colin de Verdière invariant at most 5
Abstract
We show that two intrinsically knotted graphs and with 23 edges, on 11 and 12 vertices, have Colin de Verdière invariant and no minor in the Heawood family, the 78 graphs obtained from and by - and -transformations. So the Heawood family is not the complete list of excluded minors for , as van der Holst proposed; Mattman and Pavelescu stated this proposal as a conjecture and derived from it that and have . More precisely, either the common minor of and , a 4-regular graph with 11 vertices and 22 edges, is an excluded minor for , or and both are. It follows that the following two conjectures of van der Holst cannot both hold: (a) a graph is 4-flat if and only if ; (b) the Heawood family is the complete list of excluded minors for 4-flat graphs. The lower bound is proved by explicit matrices certified in interval and exact rational arithmetic, and the minor exclusion by exhaustive enumeration. This work has not yet been reviewed by experts. The proofs, the computer checks and the text were produced by AI models, working under the author's direction.
Introduction
Main result
All graphs are finite and simple, with vertex set . Let be a graph on vertices. Following van der Holst, Lovász and Schrijver [3 1.1], the Colin de Verdière invariant is the largest corank of a real symmetric matrix such that
for , if and if , with no condition on the diagonal;
has exactly one negative eigenvalue, of multiplicity one;
(the Strong Arnold Property) no nonzero real symmetric matrix with whenever or satisfies .
A minor of a graph is a graph obtained from it by deleting vertices and edges and contracting edges, merging parallel edges and removing loops. Since does not increase under taking minors [1], the graphs with form a minor-closed class. An excluded minor for a minor-closed class is a graph outside the class all of whose proper minors lie in it; a graph is in the class if and only if it has no excluded minor as a minor. A graph is -apex if deleting at most vertices leaves a planar graph.
A -transformation replaces the three edges of a triangle by a new vertex adjacent to its three corners; a -transformation is the reverse, applied to a vertex of degree three. The Heawood family consists of the 78 graphs obtained from and by repeated - and -transformations [2 §1.1]: the 20 graphs of the family, with 21 edges, and the 58 of the family, with 22 edges.
Let and be the graphs with these edge sets:
has 11 vertices and 23 edges, nine of degree 4 and two of degree 5; has 12 vertices and 23 edges and arises from by a -transformation on the triangle (Figure 1). They are entries 90 and 332 (numbered from 0) of the list of 3028 obstructions to knotless embedding in Appendix A of Mattman and Pavelescu [8], and the graphs and of Kim and Mattman [5 §3]. Let be the graph with the edge deleted; it is 4-regular with 11 vertices and 22 edges. Mattman and Pierce found by a computer search, as one of two 4-regular graphs with 11 vertices and 22 edges that are not 2-apex while all their proper minors are [9 §2] (their second edge list, with labels shifted by one). Kim and Mattman call it and show that, up to isomorphism, is the only minor of or obtained by one edge deletion or contraction that is not 2-apex [5 §§3.1, 3.3].

Figure 1. Left, ; deleting the dashed edge gives . Right, , obtained from by a -transformation on the thick triangle ; the new vertex is 7 and the thick edges are its three edges. Vertices of carry their labels in . Drawn by checks/figure.py from data/graphs.g6, which also checks the drawing.
Theorem 1. , and neither nor has a minor in the Heawood family.
Corollary 2. The Heawood family is not the complete list of excluded minors for the class of graphs with . More precisely, if then is an excluded minor for , and otherwise and both are; in either case none of them is in the Heawood family.
The lower bound rests on two certificates, one explicit matrix for each graph, checked in exact rational and interval arithmetic, and the minor exclusion on an exhaustive enumeration (§ 6). The upper bound and the identification of the excluded minor are short arguments from known facts.
Background
Colin de Verdière proved that is minor-monotone and that exactly when is planar [1]; see [3 Theorem 2.4 and 1.4]. Lovász and Schrijver [7] and Robertson, Seymour and Thomas [11] showed that exactly when is linklessly embeddable, that is, embeddable in with no two disjoint cycles linked, so the excluded minors for are those for linkless embedding, the Petersen family [3 1.4]. As Georgakopoulos and Winter point out, the Petersen and Heawood families are both obtained from the Kuratowski graphs and “by forming suspensions, and then - and -transformations” [2 §1.1]; this analogy makes the Heawood family the natural candidate for .
Van der Holst introduced 4-flat graphs [4]: in the words of Georgakopoulos and Winter, “a graph is 4-flat if every 2-dimensional regular CW complex having as its 1-skeleton can be (piecewise linearly) embedded into ” [2 §1]. Van der Holst proved that for every graph of the Heawood family the complex obtained from by attaching a disk to each cycle does not embed in [4], so these graphs are not 4-flat. Two of van der Holst’s conjectures concern us, as Georgakopoulos and Winter record them: (a) a graph is 4-flat if and only if [4 Conjecture 3], [2, Conjecture 1.4]; and (b) the Heawood family is the complete list of excluded minors for 4-flat graphs, the second statement of [2 Conjecture 1.1], which by their footnote 1 combines (a) with van der Holst’s conjecture that the Heawood graphs are the excluded minors for [4 §4]. Georgakopoulos and Winter prove that each Heawood graph is an excluded minor for 4-flat graphs [2 Theorem 6.1] and note that all Heawood graphs have [2 §1.1].
A graph is intrinsically knotted if every embedding of it in contains a knotted cycle, and minor-minimal intrinsically knotted (MMIK) if moreover no proper minor is intrinsically knotted; the MMIK graphs are the excluded minors for knotless embedding. Mattman and Pavelescu state the classification for directly: “Conjecture 4 ([vdH]). The graphs in the and families are the obstructions to ” [8 p. 3]. Assuming it, they list the MMIK graphs with through 24 edges, noting that “the MMIK graphs in our list are 3-apex” [8 §3]. Of the three MMIK graphs with 23 edges, found by Kim and Mattman [5], they write that “they do not have a minor in the family. By van der Holst’s conjecture these three have ” [8 §3]. Theorem 1 shows that two of them, and , have .
What is new
The new step is the lower bound . A corank-6 matrix with the sign pattern of has to satisfy one polynomial equation for each non-adjacent pair of vertices, and it must also have the Strong Arnold Property; such matrices are found numerically and then certified rigorously. Minor exclusion and the upper bound are routine, and the non-2-apex minors of follow from the work of Mattman and Pierce [9] and of Kim and Mattman [5] cited above; we recheck them (Lemma 8). Corollary 2 has the following consequence for 4-flat graphs.
Corollary 3. Conjectures (a) and (b) of § 1.2 cannot both hold: (a) a graph is 4-flat if and only if ; (b) the Heawood family is the complete list of excluded minors for 4-flat graphs.
Proof. If (a) holds, the two classes coincide and so have the same excluded minors; by Corollary 2 these include a graph outside the Heawood family, so (b) fails.
We do not decide which of (a) and (b) fails, whether is 4-flat, or the value of . The third 23-edge graph of [8 §3], entry 24 of its Appendix A, is not treated here.
Proof overview
For the lower bound we exhibit, for each , a matrix satisfying (i)–(iii) with corank 6. We split the vertices into a set of six vertices and the rest , choose the block and most of the block as explicit rationals, and set the block to . Then the corank of is at least 6 automatically (Lemma 4), and (ii) reduces to an inertia statement about . The pattern condition (i) on asks that for each non-adjacent pair ; we leave exactly as many entries of free as there are such pairs and solve this square polynomial system numerically. Krawczyk’s test proves that an exact solution lies in a box of radius around the numerical one (Lemma 5); the remaining sign conditions hold on the whole box; and the Strong Arnold Property, an injectivity statement, is proved at the box center with a margin that survives the perturbation to the exact solution (Lemma 6).
For minor exclusion, every Heawood graph has at least 21 edges and has 23, so a Heawood minor would arise from at most two deletions or contractions (Lemma 7), and these are enumerated.
Certificates for
Order the vertices so that comes first and write
Lemma 4. If is invertible and , then has the eigenvalue 0 with multiplicity 6 plus that of , and has as many negative and as many positive eigenvalues as .
Proof. With one has , and is invertible. Sylvester’s law of inertia gives the claim.
The entries of on non-edges are 0. On the edges between and , all but entries are fixed negative rationals and the remaining are unknowns , where is the number of non-adjacent pairs in . For each such pair let , where is the row of indexed by . Write and for its Jacobian matrix.
The following is Krawczyk’s test [6] in the form of Moore [10], with inclusion in the interior, which makes the choice of free.
Lemma 5. Let be a box with sides of positive lengths , let , let be a real matrix, and let be an interval matrix containing for every . If the interval vector lies in the interior of , then has a zero in .
Proof. Let and . The interval vector contains for every , and as ranges over this box the -th coordinate of ranges over an interval of length . Since lies in the interior of , this is less than for every . So has norm less than for the norm on , and and hence are invertible. For , , where is the average of along the segment from to ; it lies in because interval matrices are convex. So lies in . By Brouwer’s fixed-point theorem has a fixed point , and gives . □
Here is a point near the center of , a floating-point approximation of , and and are enclosed in interval arithmetic.
Lemma 6. Let be the space of real symmetric matrices with whenever or , with coordinates for the non-edges , so that . Suppose that for all , for some . If , then has the Strong Arnold Property.
Proof. For nonzero , . □
The hypothesis on says that the Gram matrix of the linear map on , in the coordinates , minus is positive definite; for a rational this is an exact computation.
Proof of . For take , which spans five edges, so ; for take , which spans three edges, so . The certificate files give , the fixed entries of , and a rational point ; let be the box of radius about in every coordinate. The following are verified.
has the pattern (i) of the subgraph induced by ; the fixed entries of are negative; every edge between and carries a fixed entry or an unknown, and every non-edge the entry .
The test of Lemma 5 succeeds on , so there is with .
On all of , each unknown is negative and for each edge inside .
is invertible with exactly one negative eigenvalue: its characteristic polynomial has rational coefficients and only real roots, so Descartes’ rule of signs counts its positive and negative roots exactly. The inertia is for and for .
For the matrix built from and , the hypothesis of Lemma 6 holds, and is at most for every built from a point of .
Let be the matrix built from . By (1)–(3) it satisfies (i), since vanishes on the non-adjacent pairs in by . By (4) and Lemma 4 it has corank exactly and one negative eigenvalue, which is (ii). By (5) and Lemma 6 it satisfies (iii). Hence . □
Excluding Heawood minors
Lemma 7. Let have edges and let be a minor of with at least edges. Then is obtained from by at most edge deletions and edge contractions followed by deleting isolated vertices.
Proof. A minor is obtained by deleting and contracting edges and deleting vertices. Deleting a vertex of positive degree can be replaced by deleting its edges and then the isolated vertex. Every deletion or contraction of an edge lowers the number of edges by at least one, and deleting an isolated vertex does not change it. So at most edge operations occur, and since isolated vertices take part in no edge operation, their deletions can be postponed to the end.
Proof that has no Heawood minor. Every Heawood graph has 21 or 22 edges and no isolated vertex. By Lemma 7 with , a Heawood minor of would be isomorphic to a graph obtained from by at most two edge deletions or contractions, with isolated vertices removed and parallel edges merged, that has at least 21 edges. The bound of 21 edges loses no Heawood graph; it excludes some graphs, since contracting an edge of a triangle removes two edges. Up to isomorphism there are 354 graphs with at least 21 edges obtained in this way from and 455 from , and none is isomorphic to a graph of the Heawood family.
The family itself is regenerated from and by closing under and under those -transformations whose result is simple; this gives 20 graphs with 21 edges and 58 with 22 edges, the counts of [2 §1.1] and [8 §3].
Proofs of Theorem 1 and Corollary 2
Proof of Theorem 1. § 3 and § 4 give and the absence of Heawood minors. For the upper bound, deleting a vertex lowers by at most one [3 Theorem 2.7] and planar graphs have [3 1.4], so a graph that becomes planar after deleting vertices has . Deleting leaves a planar graph in both and , so .
By the same bound a 2-apex graph has , and every minor of a 2-apex graph is 2-apex: if is planar with , deleting an edge or vertex keeps this, contracting an edge avoiding contracts it in , and contracting an edge with into a vertex gives a graph in which deleting and leaves . A graph is 2-apex if and only if the graph obtained by removing its isolated vertices is, since isolated vertices do not affect planarity.
Lemma 8. Up to isomorphism, the minors of that are not 2-apex are and , and the minors of that are not 2-apex are and .
Proof. For a graph write for with its isolated vertices removed. Starting from , apply every single edge deletion and contraction, remove isolated vertices, keep the results that are not 2-apex, and repeat. The search finds, up to isomorphism, exactly and ; for the second graph has 11 vertices and 22 edges and is isomorphic to .
Let be a minor of that is not 2-apex. First, is isomorphic to a graph found by the search. Indeed, by Lemma 7 there are graphs , each obtained from the previous one by an edge deletion or contraction, with . Each has as a minor, so it is not 2-apex, and neither is ; and is obtained from by one edge deletion or contraction followed by removing isolated vertices. By induction on the search reaches every . So is isomorphic to or , and has at least 22 edges. Second, has no isolated vertex. By Lemma 7 with , is obtained from by at most one edge deletion or contraction followed by deleting isolated vertices. The minimum degree of is 4 and that of is 3, and deleting or contracting one edge lowers no degree by more than one, except that the vertex formed by contracting has degree at least . So the graph before the last step has minimum degree at least 2, there is nothing to delete, and .
Proof of Corollary 2. Let . Since and the class is closed under minors, has a minor that is an excluded minor for . Then is not 2-apex, so by Lemma 8 it is isomorphic to or . If , the proper minors of are 2-apex by Lemma 8, so is an excluded minor. If , every proper minor of is , a minor of or 2-apex, so is an excluded minor, for and . These graphs are minors of or , so by Theorem 1 none of them lies in the Heawood family.
Computational verification
The certificates and programs are in the folders data and checks of the published files (linked below the title). The certificate for lists its graph, the split , the rational block , the fixed entries of , the positions of the unknowns and the rational center . The checker reads only the certificate. It recomputes the non-adjacent pairs in from the graph; runs the test of Lemma 5 at 300 bits in interval arithmetic, with enclosed from exact rationals; checks the signs of items (1) and (3) over the box; computes the characteristic polynomial of exactly; and verifies the Gram condition of Lemma 6 exactly, bounding over the box. A second checker, written separately from a description of the format, repeats these steps with different methods: Krawczyk’s test in exact rational arithmetic using the constant Hessian of the quadratic system , inertia by an factorization and by Descartes’ rule, and the Strong Arnold Property in two formulations, each with a Weyl perturbation bound. Both checkers accept both certificates, and each rejects its own suite of deliberately corrupted certificates, listed in the checker documentation.
The Heawood family is generated by two separate programs, which agree on the 78 graphs and the split 20 + 58. Minor exclusion is checked twice: by the enumeration of Lemma 7 with isomorphism tests, and by a search for branch sets of each Heawood graph in , cross-checked by deletion and contraction; both find the Heawood minors of three planted control graphs. The 3-apex and 2-apex statements, the minimum degrees used in Lemma 8 and Figure 1 are checked by the same programs. The whole check takes about half a minute on one core. The numerical search that produced the matrices is not part of the proof.
The graphs and certificates in graph6
In the graph6 format, is J?bFF`wNA{?, is K?BD@jguAsBo and is J?bFF`wN?{?. In the split is , , and the ten unknowns are entries of on edges between and ; in it is , , with twelve unknowns. The graph also arises from by a -transformation on the triangle . Deleting any of 105 vertex triples of , and any of 130 of , leaves a planar graph.
References
- [1]Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50 (1990), 11–21.DOI
- [2]A. Georgakopoulos and M. Winter, On 2-complexes embeddable in 4-space, and the excluded minors of their underlying graphs, arXiv:2408.12681v1 (2024).arxiv.org/abs/2408.12681
- [3]H. van der Holst, L. Lovász and A. Schrijver, The Colin de Verdière graph parameter, in Graph Theory and Combinatorial Biology (Balatonelle, 1996), Bolyai Soc. Math. Stud. 7, János Bolyai Math. Soc., Budapest, 1999, 29–85. Numbering as in the preliminary version of March 1997.
- [4]H. van der Holst, Graphs and obstructions in four dimensions, J. Combin. Theory Ser. B 96 (2006), 388–404, doi:10.1016/j.jctb.2005.09.004.DOI
- [5]H. Kim and T. W. Mattman, Dips at small sizes for topological graph obstruction sets, Discrete Appl. Math. 360 (2025), 139–166, doi:10.1016/j.dam.2024.08.022; section numbers as in arXiv:2205.14255v2.DOI
- [6]R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187–201.DOI
- [7]L. Lovász and A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126 (1998), 1275–1285.DOI
- [8]T. W. Mattman and A. Pavelescu, Three thousand obstructions to knotless embedding, arXiv:2607.01414v1 (2026).arxiv.org/abs/2607.01414
- [9]T. W. Mattman and M. Pierce, The Kₙ₊₅ and K₃₂,₁ⁿ families and obstructions to n-apex, in Knots, Links, Spatial Graphs, and Algebraic Invariants, Contemp. Math. 689, Amer. Math. Soc., Providence, RI, 2017, 137–158, doi:10.1090/conm/689/13856; section numbers as in arXiv:1603.00885v1.
- [10]R. E. Moore, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 14 (1977), 611–615.DOI
- [11]N. Robertson, P. Seymour and R. Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), 185–227.