WorksMathematics
Counterexamples to coefficient conjectures for plane Penrose polynomials
Abstract
We give counterexamples to coefficient-sign alternation and coefficient nonvanishing for the plane Penrose polynomial . Here is a graph embedded in the sphere, and counts boundary components after replacing vertices by disks and edges by bands and half-twisting the bands in . Weak alternation means that coefficients, read in descending powers from a positive leading coefficient, are alternately nonnegative and nonpositive. We construct a simple bridgeless plane graph on ten vertices whose Penrose polynomial is monic of degree eight and has linear coefficient , contrary to weak alternation. A bridgeless plane multigraph on eleven vertices has zero linear coefficient. We also give a simple bridgeless cubic example on twelve vertices, where cubic means that every vertex has degree three; its linear and quadratic coefficients both have the wrong signs. These examples answer Aigner's questions on coefficient nonvanishing and sign alternation negatively. Replacing each degree- vertex of the first two examples by a -cycle, with the incident edges attached in their embedding order, gives counterexamples to both coefficient conjectures of Kauffman, Silver and Williams. A known triangle-replacement identity gives infinite families, and connected sums give arbitrarily many vanishing initial coefficients for the Penrose–Kauffman polynomial. The cycle matroid of the ten-vertex example is an explicit planar minor-minimal obstruction to coefficient alternation, answering Aigner's question about minor-minimal binary-matroid obstructions negatively.
Introduction
The Penrose polynomial has its origins in Penrose’s tensor approach to graph coloring [8]. A plane graph is a finite graph embedded in the sphere. Following Aigner, call it normal if it is 2-connected and any two distinct faces share at most one boundary edge; 2-connected means that there are at least three vertices and deleting any one vertex leaves a connected graph. For a normal plane graph with faces, write . In this setting Aigner’s questions [1 Problems 1–2], restated in our notation, are as follows.
Problem 1 asks whether for every ; in particular, whether , with the stronger proposed inequality .
Problem 2 asks whether the coefficients weakly alternate, for every . It also asks whether , with the stronger proposed inequality .
The Eulerian case was proved by Aigner [1 Corollary 5]; his survey also records the series-parallel and outerplanar cases, citing Mielke’s thesis [2 pp. 65–66]. The graph terminology is recalled in Section 2.1. The motivation includes the Four Color Theorem: for a connected bridgeless plane graph, weak coefficient alternation implies four-face-colorability, meaning that faces sharing an edge receive different colors from a set of four [A, Corollary 11]; [A00, Theorem 16]. Further background appears in [3].
For a cubic graph , in which every vertex has degree three, a perfect matching is a set of edges meeting every vertex exactly once. The Penrose–Kauffman polynomial , at a positive integer , counts colorings of the edges outside with named colors: the two colors at each vertex must be distinct, and the unordered pairs at the two ends of every matching edge must agree. Section 2.3 gives the polynomial construction. Kauffman, Silver and Williams (KSW) conjecture, for every connected cubic plane graph with specified perfect matching , that (1) the linear coefficient of is nonzero and (2) its coefficients weakly alternate [7 Section 8, p. 24].
We begin with two explicit normal plane graphs. The tetragonal trapezohedron violates both weak alternation and the proposed strict sign of the linear coefficient.1 Splitting one of its two degree-four vertices gives , whose zero linear coefficient refutes both nonvanishing assertions. Their cycle expansions, defined in Section 2.3, refute KSW Conjectures (2) and (1), respectively. We then give a full treatment of the twelve-vertex cubic graph , obtained by splitting both degree-four vertices of . Its ordinary Penrose polynomial violates weak alternation in both the linear and quadratic coefficients, as well as the proposed strict linear sign, so the failure persists even for simple bridgeless cubic plane graphs. All three families satisfy , as shown in Section 7.
Sections 3–4 construct and and prove their polynomial formulas by exact reproducible calculations. Section 5 applies the known triangle-replacement identity [5 Theorem 4.1, equation (4.5)] to obtain infinite families. Section 6 gives the cubic example and its entire cubic family. Section 7 records the conjecture consequences, connected sums with arbitrarily many initial zero coefficients, and the planar minor-minimality of the cycle matroid , defined below, which answers Aigner’s classification question [2 p. 66] negatively. These results do not contradict the Four Color Theorem and supply no new proof of it.
Preliminaries
Ribbon surfaces and coefficient signs
A plane graph means a finite graph embedded in the sphere. A graph is simple if it has no loops or parallel edges, cubic if every vertex has degree three, and bridgeless if deleting any edge preserves its number of connected components. The graphs constructed below are connected and loopless; has two parallel edges. We use the definition of normality from Section 1. The dual has one vertex for each face of , and one edge crossing each edge of and joining its two incident faces.
A graph is Eulerian if every vertex degree is even. A graph minor is obtained by edge deletions, vertex deletions, and edge contractions. The graph is the complete graph on four vertices; series-parallel graphs have no minor. An outerplanar graph admits an embedding with every vertex on one face boundary.
Replace the vertices of a plane graph by disjoint disks and its edges by narrow bands attached in the embedding’s cyclic order. This gives a compact surface with boundary, called a ribbon neighborhood. For , insert one half twist in each band indexed by , leaving all attaching orders fixed. Let be the number of boundary components of the resulting surface. We use the ribbon-surface expression of Ellis-Monaghan–Moffatt [6 Proposition 5.1], which for plane graphs gives Aigner’s Penrose polynomial [1]:
For a polynomial with , weak sign alternation means
We write for the coefficient of in .
Aigner indexes the signs from the number of faces. In all three base examples the degree equals that number, so there is no indexing ambiguity. The constant term in (1) is zero; the nonvanishing question concerns the coefficients of .
The binary-Laplacian formula
Work over the field , with addition and multiplication modulo two. Let be a finite loopless multigraph on vertices. For an edge , let have a one in positions and zero elsewhere. Define
Each edge toggles its two off-diagonal entries and the two corresponding diagonal entries. Parallel edges are separate elements of and contribute separately to this sum.
We recall the binary-matroid definitions needed both for the formula and for the final consequence. A binary matroid is specified by a finite set and a subspace , its cycle space. The support of a vector is the set of its nonzero coordinates. The nonempty supports of vectors in that are minimal under inclusion are the circuits. The dual has cycle space , the orthogonal complement for the usual mod-two dot product. An element is a coloop if it belongs to no circuit; a matroid is bridgeless if it has no coloops. Deleting an element restricts to cycles with zero in that coordinate and then removes the coordinate; contracting it projects all cycles onto the remaining coordinates. A matroid minor is obtained by a sequence of these operations.
For a graph , its cycle matroid has the even-degree edge subsets as its binary cycle space, with addition given by symmetric difference. A matroid is graphic if it is a graph’s cycle matroid, and planar if that graph can be chosen planar. For , let denote the vector equal to on and zero elsewhere. Set
We use the binary-matroid Penrose polynomial of Aigner and Mielke [4], in the cycle-space form recorded in [2 equation (4.5)]. The letter distinguishes its normalization from the graph polynomial.
Proposition 1 (Binary-Laplacian formula). Let be the number of connected components of the loopless multigraph . Then
If for a connected bridgeless plane graph , then .
The boundary-count identity underlying the plane-graph formula is known [9 Theorem 1.1] and is used in the proofs of [7 Proposition 6.2 and Theorem 6.3]. We recall a short derivation from Aigner’s characterization [1 Proposition 1].
Proof. Let be the vertex-edge incidence matrix of over , whose columns are the . The cycle space of is the cut space , and its orthogonal complement is . For , the condition is exactly . The map has kernel of dimension , consisting of vectors constant on each component. Since implies for every edge , it also implies . Thus . The restricted map is surjective and has kernel of dimension . Rank-nullity now gives , proving the first identity. For a connected plane graph , plane duality gives , and the closed paths in Aigner’s construction can be identified with ribbon boundaries. For every , his closed paths with changing set correspond to the boundary components of the ribbon surface twisted along : both follow the face-boundary pairing at edges outside and the crossing pairing at edges in [1 Section 2]; [6 proof of Proposition 5.1]. Thus his path count is for each . Aigner’s boundary-count identity then gives . Substitution into (1) and (4) proves the remaining identities.
If is simple, only the empty subset has , because the off-diagonal entries record the selected edges. Hence is monic of degree . Also , so . For normal plane graphs this recovers [1 Corollary 3]; the corresponding PK statement is [7 Proposition 6.2]. For comparison, a graph on two vertices with two parallel edges has .
Cycle expansion and the Penrose–Kauffman polynomial
A perfect matching of a cubic graph is a set of edges meeting each vertex exactly once. A Tait -coloring of assigns one of named colors to every edge outside , so that the two colors at each vertex are distinct and the unordered pairs at the two ends of every matching edge agree. The Penrose–Kauffman polynomial counts these colorings at every positive integer [7 Definition 3.1].
To see that this is a polynomial with integer coefficients, define a state to be a choice, at each matching edge, of one of the two bijections between the pairs of incident nonmatching edges. The two local pairings are shown in Figure 1. Following the pairings gives closed circuits. A state is uncolorable if the two local strands selected by the pairing at some matching edge belong to the same circuit. Otherwise its component graph is the simple graph with one vertex per circuit, with two vertices adjacent when the circuits meet at a matching edge. A proper coloring assigns different colors to adjacent vertices; its counting polynomial is the chromatic polynomial. Summing these chromatic polynomials over the colorable states counts every Tait coloring once, since distinct colors determine a unique compatible pairing at each matching edge [7 Theorem 3.4]. Uncolorable states contribute zero. A related expansion for plane Penrose polynomials is given in [6 Theorem 7.2].
Figure 1. Local matching and band rules. In (a), the central matching edge is uncolored and its endpoints have the same unordered pair of distinct incident colors. Panels (b) and (c) show the two possible pairings of the four nonmatching strands incident with the matching edge in (a). These correspond respectively to an untwisted band and a half-twisted band. The labels correspond respectively to the upper-left, lower-left, upper-right and lower-right strands in (a). For the displayed colors , only pairing (c) joins strands of equal color. The crossing in (c) is not a graph vertex.
For a loopless plane graph of minimum degree at least three, let its cycle expansion (also called truncation) be the graph obtained by replacing each vertex of degree by a -cycle and attaching its incident edges in cyclic order. The original edges form a perfect matching , and is a cubic plane graph. Thus degree-three vertices become triangles and degree-four vertices become quadrilaterals.
Proposition 2 (Identity for cycle expansion). For every connected loopless plane graph of minimum degree at least three,
Identity (6) is stated in [7 Section 4], where the cycle expansion is called a blow-up; the same construction is used in [5 Section 1]. We give a direct proof from the ribbon sum (1).
Proof. At a positive integer , expand each term in (1) by assigning a color to each boundary circuit. Regroup by fixed colors on the corner arcs, the portions of the vertex-disk boundaries between consecutive edge bands. The corner arcs around a degree- vertex of correspond to the edges of its replacement -cycle in . The band of an original edge corresponds to the matching edge in ; the two corner arcs at either end correspond to the two nonmatching edges incident with that endpoint. For each such coloring, the signed sum factors over the edge bands: a local pairing is compatible when joined ends have the same color, and the untwisted and twisted pairings have weights and . If all four ends at a band have the same color, both pairings are compatible and their local contribution is . These assignments therefore cancel.
Every surviving compatible assignment has two distinct colors at every band and exactly one compatible pairing there. Its unordered pairs at the two ends agree, precisely the Tait-coloring rule for . Its total sign is positive: each twisted pairing is a crossing between two differently colored closed curves in the sphere. For each pair of colors, the total number of crossings is even, because closed mod-two cycles on the sphere have zero intersection number. Summing over color pairs makes the number of selected twists even. For every positive integer , the sum therefore counts the Tait -colorings. Equality at all positive integers proves the polynomial identity. □
The first two counterexamples
Construct from the cycle . Put a vertex inside the cycle and join it to ; put a vertex outside and join it to . We call and the two hubs. This is the tetragonal trapezohedron graph, shown in Figure 2. The construction specifies its sphere embedding.
Figure 2. The two plane graphs. The left panel shows , and the right panel shows the split hub and the two parallel edges of . The cycle labels agree in both panels.
It is simple and connected, has eight degree-three vertices and two degree-four vertices, and has sixteen edges and eight quadrilateral faces. Every edge lies on a cycle, so it is bridgeless.
To obtain , split into , , keeping adjacent to , and adjacent to , , and join , by two parallel edges bounding a digon. All other edges and their embedding are unchanged. This connected graph has eleven vertices, eighteen edges, and nine faces: six quadrilaterals, two pentagons and the digon. Its vertices have degrees three or four, and every edge again lies on a cycle. Both graphs are 2-connected: deleting a hub leaves the cycle connected, and deleting a cycle vertex leaves a path to which every remaining hub is attached. Their duals described below are simple, so both graphs are normal.
Theorem 1. The graphs just constructed have Penrose polynomials
and
Thus fails weak sign alternation, and .
The calculation proving (7)–(8) is given next. Both dual graphs are simple. The dual is the square antiprism: on vertices , its edges are the unordered pairs and , with indices modulo eight. Explicitly, for , label the face by and the face by , taking all numerical labels modulo eight. Then is obtained from by adding vertex and edges , . The two pentagons retain labels , , and the new digon receives label . These descriptions also give the input for the short calculation in Appendix § 8.
Proof of Theorem and independent checks
For the graph in (3), define , setting outside . These numbers remove the expected alternating signs: weak alternation is equivalent to for every . The rank formula gives
Proof of Theorem 1. By Proposition 1, the required coefficients are given by binary-Laplacian ranks. Table 1 records all subsets for and all subsets for . The even and odd columns count subsets of the given rank by the parity of , so by (9). The dash denotes a rank outside the range for .
| rank | : even | odd | : even | odd | ||
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 16 | 16 | 0 | 18 | 18 |
| 2 | 130 | 16 | 114 | 166 | 16 | 150 |
| 3 | 232 | 664 | 432 | 272 | 980 | 708 |
| 4 | 2545 | 1688 | 857 | 4325 | 2352 | 1973 |
| 5 | 6504 | 7248 | 744 | 11424 | 14602 | 3178 |
| 6 | 13148 | 13088 | 60 | 35236 | 32536 | 2700 |
| 7 | 10208 | 10048 | 49280 | 50200 | 920 | |
| 8 | — | — | — | 30368 | 30368 | 0 |
Table 1. Exact edge-subset counts by binary-Laplacian rank and edge-count parity for and ; .
Taking even minus odd as the coefficient of proves (7)–(8). For , degree eight requires a nonpositive linear coefficient, whereas that coefficient is 160. For , the equally sized even and odd classes with one boundary component cancel. Appendix A exhausts every edge subset and computes these counts in exact integers. Thus exhibits failure of weak alternation, whereas records the vanishing linear coefficient.
Independent checks
The supplement, described under Supplementary material, contains the verification program (verify.py), reproduction instructions (README.md), and exact output with the program SHA-256 (verification.json). The program verify.py reconstructs the embeddings from the cycle-and-hubs description, checks the sphere and duals, and obtains both polynomials by three computations: the binary-Laplacian sum, direct tracing of twisted-ribbon boundary components in (1), and set partitions of the corner arcs in Proposition 2. The last calculation enumerates color classes of the 32 or 36 nonmatching edges of the cycle expansion. A partition into nonempty classes has assignments of distinct named colors. This gives the general falling-factorial expansion of [7 equation (8.2)]. Processing arcs in a fixed order and assigning either an existing class or the next unused class enumerates each partition once; the local pair constraints reject incompatible assignments. Our enumerated counts give
Since , the coefficient formula [7 Corollary 8.4] gives the direct checks
For each graph, the coefficient of in (10) is the count of colorings up to renaming in [7 equation (8.2)]. The number of colorings using all named colors is , as used in [7 Corollary 8.4]. Direct enumeration of color partitions provides an independent check of the rank calculation. The supplement also checks numerical evaluations from Aigner’s formulas, the dual cancellation for triangle replacement on a nine-edge test graph, and the matroid-minimality calculation below. Its README gives a standalone reproduction command and explains the exact outputs. All these calculations use integer arithmetic.
Triangle replacement and infinite families
We call replacing one degree-three vertex by a triangle, with the incident edges attached in their embedding order, a triangle replacement. The following is its dual form. Let be a finite simple plane graph with a triangular face , and form by placing a new vertex inside that face and joining it to , , . We give a short algebraic proof of the known recurrence [5 Theorem 4.1, equation (4.5)]. For a selected edge set , write and , the set of selected neighbors of .
Lemma 1 (Triangle recurrence). In this setting,
where missing coefficient indices have value zero.
Proof. We pair terms in the full sum indexed by , allowing the old subset to change. Choose as a distinguished vertex. The following pairing cancels all terms except those with :
If , toggle the old edge joining the two vertices in .
If , change to and toggle all three old triangle edges; reverse this rule when .
Every rule is its own inverse and reverses the edge-count parity. The second rule changes two spokes and three old edges. We check that both preserve binary rank.
For , let be the binary Laplacian of the selected edge set in , let be the coordinate vector at , and put . The vector has ones exactly at the two selected neighbors. Since has two selected incident edges, over , so . Toggling the edge between those neighbors changes to , and
The right factor is invertible, proving rank preservation.
For odd , put coordinate first, let be the neighbor indicator, and use the diagonal entry 1 as a pivot. The resulting Schur complement is . For the last two terms cancel. For they are the binary Laplacian of the old triangle. Toggling that triangle makes the two pivoted matrices identical. Both full matrices have rank one more than this Schur complement.
The unpaired choices are . For an old subset of rank , the empty choice has rank on vertices and contributes times its old monomial. Each remaining singleton has rank and the opposite edge-count sign, hence contributes minus its old monomial. Their sum is times the old contribution. Comparing coefficients, with the degree increased by one, gives the second identity in (11).
The same argument proves (11) for any finite loopless multigraph containing a triangle , with obtained by adjoining a new vertex joined once to each of . If parallel edges occur, fix one edge for each side of the triangle and use those edges in the toggles. Planarity and the facial condition are needed only for the dual interpretation as triangle replacement.
Let be either or . For an integer , write for any graph obtained by successive triangle replacements. At each step any degree-three vertex may be chosen, including one created by an earlier replacement. In each base graph a degree-three vertex meets three distinct faces. Dually, its replacement inserts a vertex into a triangular face, preserving simplicity of the dual and the sphere embedding. The new degree-three vertices also have triangular dual faces, so this argument applies at every step. The replacement also preserves 2-connectedness: after deleting any one vertex, paths through the replaced vertex can be routed through the surviving triangle. Thus the resulting graphs remain normal and bridgeless; those starting from remain simple.
Each replacement adds two vertices, three edges and one face. Equation (11) therefore gives
In particular,
To see this directly from the coefficient recurrence, let have vertices. Its constant coefficient is zero, since every has the all-ones vector in its kernel. Equation (11) gives : the sign-adjusted linear coefficient doubles at each replacement. Starting from and 0 gives (13).
The cubic counterexample and its family
The first two base graphs have degree-four vertices. We now construct a simple cubic example for the ordinary Penrose polynomial. Starting from , split into adjacent vertices , with joined to and to . Split into adjacent vertices , with joined to and to . Each split uses a single joining edge and inherits the plane embedding. Denote the resulting graph by ; see Figure 3.
The graph has twelve vertices, eighteen edges and eight faces: four quadrilaterals and four pentagons. Every vertex has degree three, and the edge list has no loops or parallel edges. Deleting a cycle vertex leaves a path with both split hub pairs attached; deleting a hub vertex leaves the original cycle and all other hubs attached. Thus is 2-connected and bridgeless. Its dual is obtained from the labelled square antiprism of § 3 by adding edges and . The first splits the northern square face of the dual and the second the southern square face. The dual is simple, so is normal.
Theorem 2 (A cubic counterexample and an infinite cubic family). The graph has Penrose polynomial
Figure 3. The cubic plane graph . Both hubs of are split into adjacent pairs, each joined by a single edge. The cycle labels are the same as in Figure 2.
For every integer , let be any graph obtained from by successive triangle replacements. Then is normal, simple, connected, bridgeless and cubic, with vertices, edges and faces, and
Its linear and quadratic coefficients both have the wrong signs:
Proof. Apply Proposition 1 to the dual just specified. Table 2, computed by the exhaustive integer calculation in Appendix § 8, gives (14).
| rank | even | odd | |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 18 | 18 |
| 2 | 192 | 30 | 162 |
| rank | even | odd | |
| 3 | 591 | 1344 | 753 |
| 4 | 7204 | 5512 | 1692 |
| 5 | 24700 | 26152 | 1452 |
| 6 | 54064 | 54272 | |
| 7 | 44320 | 43744 |
Table 2. Exact edge-subset counts for ; all subsets are included, and .
The construction and the preservation argument in § 5 prove the graph properties at every step. Each replacement adds two vertices, three edges and one face and preserves degree three. Lemma 1 gives (15). Put and . The coefficient recurrence in (11) gives and , with and . Induction gives (16).
The supplement reconstructs this embedding and verifies (14) by the same three computations used for and . The color-class enumeration gives the further check
A proper edge three-coloring assigns one of three named colors to each edge, with different colors on edges sharing a vertex. Direct enumeration gives eighteen such colorings of . Triangle replacement preserves this number: the three external edge colors at a replacement triangle must be distinct, and then each internal edge has the color missing at its two endpoints. Indeed, for each color, counting its incidences at the three triangle vertices forces an odd number of external edges of that color; hence there is exactly one of each. This gives a bijection with colorings before replacement. Consequently every has eighteen proper edge three-colorings.
The evaluations and agree with the standard cubic formulas [1 Corollaries 8 and 10]. More generally, (15) gives and . The value at is recorded with those of the other two families in § 7.
Thus weak alternation and the proposed strict linear sign fail even for the ordinary Penrose polynomial of simple bridgeless cubic plane graphs. Since , this example does not refute linear nonvanishing.
Consequences for the coefficient conjectures
The graphs answer Aigner’s weak-alternation question and his proposed strict sign for the linear coefficient negatively [1 Problems 1–2]. The graphs answer both his linear-nonvanishing question and his question whether every coefficient from the linear through the leading term is nonzero negatively. The polynomial of itself does satisfy weak alternation; its purpose here is the distinct nonvanishing conclusion.
The graphs and are simple, connected, bridgeless cubic plane graphs on and vertices, respectively, with the specified perfect matchings. Propositions 1–2 and (13) refute [7 Conjecture (2)] and [7 Conjecture (1)], respectively. The replacement cycles have length at least three, and each original edge joins different cycles, so the expansions are simple. Each new cycle edge lies on its replacement cycle; a cycle containing an original edge lifts to a cycle in the expansion. This proves bridgelessness.
The ordinary families and retain degree-four vertices and are not cubic; Theorem 2 supplies the separate cubic ordinary-Penrose family. Every retains its digon. This family therefore does not settle coefficient nonvanishing for the ordinary Penrose polynomial of simple normal plane graphs, or for the associated diagrams without bigons. The simple bridgeless cubic expansions already refute nonvanishing for the matching-dependent polynomial .
The diagram associated with lies in the class of [7 Theorem 6.6]. In the construction of [7 Section 4], contract each matching edge to a crossing to obtain the medial projection, whose vertices correspond to edges of and whose arcs join consecutive edges around its vertices. The associated crossing choices make the diagram alternating. A diagram is reduced if no crossing is isolated from the remainder by a simple closed curve through that crossing, and prime if any simple closed curve meeting the projection transversely twice bounds a disk containing only an arc on at least one side. Because is 2-connected, each vertex occurs only once on the boundary of each incident face. A two-edge cut in its medial projection would admit a separating simple closed curve crossing precisely the two cut edges once each. Between crossings, the curve lies in one vertex region and one face region, so the cut edges would represent distinct corners of the same vertex in the same face, a contradiction. A separating vertex would also yield a two-edge cut: in a connected 4-regular graph, every component left after deleting a vertex meets it in a positive even number of edges. Thus the diagram is reduced and prime. Its regions have lengths given by vertex degrees and face lengths of , namely three or four, so it has no bigon regions. Weak alternation fails even for this diagram class.
The diagrams associated with , , also belong to this class. Each is simple, cubic and 2-connected, so the same connectivity argument applies, vertex regions have length three and face regions have length at least three. By (6) and (16), weak alternation fails in both the linear and quadratic coefficients throughout this family.
All three base graphs have odd-degree vertices, so these examples do not contradict the Eulerian result [1 Corollary 5]. Their values at are , , and . For a base graph with faces, successive triangle replacements give
The three resulting values are , , and , respectively, all positive. All three families satisfy the sign-at-minus-one inequality proposed in [1 Problem 2].
There is also an arbitrarily long block of initial zero coefficients for the Penrose–Kauffman polynomial. A connected sum of diagrams cuts one arc in each and joins the ends across the two diagrams. Take copies of the diagram associated with and iterate precisely the joining of [7 Definition 3.6, Figure 7(c)]. Let be the corresponding connected cubic plane graph with its specified matching. Then [7 Proposition 3.7(3)] gives
Thus the coefficients of vanish, and the coefficient of is . This realizes the conditional consequence already noted in [7 p. 25].
An explicit planar matroid obstruction
Dividing a nonzero graph polynomial by decreases its degree and every nonzero exponent by one, preserving the difference between degree and exponent in (2): . By (5), has degree seven and constant coefficient 160, whereas weak alternation requires a non-positive constant coefficient. Aigner asks whether , , and are the only bridgeless minor-minimal binary matroids whose Penrose polynomials have non-alternating coefficients [A00, p. 66]. A positive answer would imply the Four Color Theorem. Theorem 3 answers this question negatively by providing a planar minor-minimal obstruction. Here is the Fano matroid whose cycle space is the kernel of the 3-by-7 matrix with all nonzero vectors of as columns. The Petersen graph has vertices , for modulo five and edges , , and . The graph is complete on five vertices.
Theorem 3 (Planar minor-minimal obstruction; computer-assisted). The 16-element planar matroid fails weak coefficient alternation, and every proper bridgeless minor has strictly alternating coefficients. Thus is a planar minor-minimal obstruction to coefficient alternation, distinct from all three examples listed by Aigner, none of which is planar.
Here minimality is within the bridgeless class. Strict alternation requires strict inequalities for every coefficient of , including its constant term. Minor-minimality holds for both strict and weak alternation: fails weak alternation, whereas every proper bridgeless minor satisfies strict alternation. As in Aigner’s list, we regard the zero polynomial as non-alternating.
Proof. It remains to verify minimality and the nonplanarity of the listed examples. Distinctness already follows from their sizes: has sixteen elements, whereas , , and have seven, fifteen and ten, respectively. Since for the square antiprism , its bridgeless minors are the matroids of loopless graph minors of . Contracted edges partition into connected blocks. Contract each block, delete the resulting loops, and retain any selection of edges between blocks. This describes every loopless minor, including disconnected ones and the empty matroid.
A class of parallel edges contributes times the contribution of a single edge to (3): its even and odd subsets each number and give, respectively, the zero and single-edge binary-Laplacian contributions. Let retain all vertices and one edge from each parallel class, and put . Then . Since , also . Thus simplification preserves both strict and weak alternation. In the plane-graph setting this is [7 Theorem 6.3], the dual form of [1 Corollary 2]. It suffices to examine every spanning subgraph of each simple quotient and test .
The supplement performs this finite exhaustive calculation. For each quotient with edge set , start with the signed nullity monomial at every . For each edge , add the entry for to that for whenever . After all edges have been processed, the entry at is exactly . Removing the factor and testing all coefficients gives strict alternation in every case except the original full square antiprism. Only the partition into singleton blocks can retain sixteen distinct edges, so this exception is precisely itself. The enumeration covers 1,511 partitions into connected blocks, 151 distinct labelled simple quotients, and 624,339 pairs consisting of a partition and a spanning subgraph of its simple quotient. The last count retains partition multiplicity; repeated labelled quotients are evaluated once. For each partition, we label its blocks 0, 1, . . . in increasing order of their least vertex; quotients are identified only when their resulting labelled vertex and edge sets agree. These are not counts of nonisomorphic matroids. This proves minimality.
None of Aigner’s three matroids is planar. By Whitney’s planarity criterion [10 Theorem 29], the dual of a graph’s cycle matroid is graphic if and only if the graph is planar. If admitted a planar graph representation, its dual would be graphic; Whitney’s criterion would imply that itself is planar, a contradiction. The same criterion makes nongraphic because is nonplanar. Also is nongraphic: its cycle space has dimension three, every nonzero vector has support of size four, and every two elements belong to a common circuit. A graphic representation would therefore be connected after removing isolated vertices, with seven edges and five vertices.
Its circuits force it to be simple and triangle-free, whereas such a graph on five vertices has at most six edges. Every minor of a planar matroid is planar, so none of these three matroids can be a minor of .
The Petersen example is not minor-minimal, contrary to its description in [2 p. 66]. Contract the outer edge in the labelling above. The resulting graph is bridgeless, and an exact cycle-space calculation in the supplement gives
Its positive linear coefficient and negative constant coefficient violate weak alternation. Thus a proper bridgeless minor of already fails.
The matroid does not contradict Tutte’s tangential 2-block conjecture in the formulation of [2 equation (5.3)], since
A complete calculation of the rank tables
The following program requires Python 3.10 or later and uses only integers and the standard library. Bits encode vectors over . The pivot dictionary stores independent rows with distinct highest set bits; each XOR is elementary row reduction. Every subset is visited once, and the four toggled entries per selected edge are exactly its binary-Laplacian contribution. The three edge lists are exactly the duals specified in Sections 3 and 6. The same exhaustive calculation gives Tables 1 and 2.
edges = sorted({tuple(sorted((i, (i+s) % 8)))
for i in range(8) for s in (1, 2)})
for name, n, es in [("G10", 8, edges),
("Z", 9, edges + [(3, 8), (7, 8)]),
("H0", 8, edges + [(3, 7), (0, 4)])]:
counts = [[0, 0] for _ in range(n)]
for mask in range(1 << len(es)):
rows = [0] * n
for j, (a, b) in enumerate(es):
if (mask >> j) & 1:
pair = (1 << a) | (1 << b)
rows[a] ^= pair
rows[b] ^= pair
pivots = {}
for row in rows:
while row:
lead = row.bit_length() - 1
if lead in pivots:
row ^= pivots[lead]
else:
pivots[lead] = row
break
counts[len(pivots)][mask.bit_count() & 1] += 1
assert sum(map(sum, counts)) == 1 << len(es)
print(name)
for r, (even, odd) in enumerate(counts):
print(r, even, odd, (-1)**r * (even - odd))
Supplementary material
The supplement contains a standalone exact verifier requiring Python 3.10 or later and only the standard library, together with its saved output and a README. The supplement, supplement-v7.tar.gz, is archived together with this paper on Zenodo at https://doi.org/10.5281/zenodo.24351582.
Acknowledgments
The proofs in this paper were developed by OpenAI’s GPT models (Sol and Astra) and Anthropic’s Claude Fable models under the author’s guidance. The author has reviewed the resulting proof arguments. The author takes full responsibility for the contents of this paper.
References
- [1]M. Aigner, The Penrose polynomial of a plane graph, Mathematische Annalen 307 (1997), 173–189. doi:10.1007/s002080050030. Author preprint A-96-12 (1996). Item numbering follows the linked author preprint.DOI
- [2]M. Aigner, Die Ideen von Penrose zum 4-Farbenproblem, Jahresbericht der Deutschen Mathematiker-Vereinigung 102 (2000), 43–68. Journal scan.
- [3]M. Aigner, The Penrose polynomial of graphs and matroids, in J. W. P. Hirschfeld (ed.), Surveys in Combinatorics, 2001, London Mathematical Society Lecture Note Series 288, Cambridge University Press (2001), 11–46. doi:10.1017/CBO9780511721328.004.DOI
- [4]M. Aigner and H. Mielke, The Penrose polynomial of binary matroids, Monatshefte für Mathematik 131 (2000), 1–13. doi:10.1007/s006050070020.DOI
- [5]S. Baldridge and B. McCarty, New relations for the Penrose polynomial, arXiv: 2606.06643v1, 4 June 2026.arxiv.org/abs/2606.06643
- [6]J. A. Ellis-Monaghan and I. Moffatt, A Penrose polynomial for embedded graphs, European Journal of Combinatorics 34 (2013), 424–445. doi:10.1016/j.ejc.2012.06.009; arXiv: 1106.5279v3. Item numbering follows arXiv v3.
- [7]L. H. Kauffman, D. S. Silver and S. G. Williams, The Penrose-Kauffman Polynomial, arXiv: 2604.16635v1, 17 April 2026.arxiv.org/abs/2604.16635
- [8]R. Penrose, Applications of Negative Dimensional Tensors, in D. J. A. Welsh (ed.), Combinatorial Mathematics and its Applications, Academic Press (1971), 221–244.
- [9]D. S. Silver and S. G. Williams, On the component number of links from plane graphs, Journal of Knot Theory and Its Ramifications 24 (2015), 1520002. doi:10.1142/S0218216515200023. arXiv:1408.6815.DOI
- [10]H. Whitney, Non-separable and planar graphs, Transactions of the American Mathematical Society 34 (1932), 339–362. doi:10.1090/S0002-9947-1932-1501641-2.DOI


