% LaTeX source for Counterexamples to coefficient conjectures for plane Penrose polynomials. \documentclass[11pt,letterpaper]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=1in]{geometry} \usepackage{graphicx,float,xcolor} \usepackage{longtable,booktabs,array,calc} \usepackage[colorlinks=true,linkcolor=black,citecolor=black,urlcolor=blue!60!black]{hyperref} \hypersetup{ pdftitle={Counterexamples to coefficient conjectures for plane Penrose polynomials}, pdfauthor={Yair Lavi}, pdfkeywords={Penrose polynomial, Penrose--Kauffman polynomial, plane graph, coefficient signs, binary matroid} } \newtheorem{proposition}{Proposition} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \providecommand{\tightlist}{% \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} \setlength{\emergencystretch}{3em} \urlstyle{same} \title{Counterexamples to coefficient conjectures for plane Penrose polynomials} \author{Yair Lavi} \date{18 November 2026} \newcommand{\SupplementDOIURL}{https://doi.org/10.5281/zenodo.24351582} \newcommand{\SupplementArchive}{supplement-v7.tar.gz} \newcommand{\SupplementLink}{\expandafter\url\expandafter{\SupplementDOIURL}} \begin{document} \maketitle \begin{abstract} We give counterexamples to coefficient-sign alternation and coefficient nonvanishing for the plane Penrose polynomial \(P_H(q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{c_H(A)}\). Here \(H\) is a graph embedded in the sphere, and \(c_H(A)\) counts boundary components after replacing vertices by disks and edges by bands and half-twisting the bands in \(A\). 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 \(160\), 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-\(k\) vertex of the first two examples by a \(k\)-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. \end{abstract} \textbf{Keywords.} Penrose polynomial; Penrose--Kauffman polynomial; plane graph; coefficient signs; binary matroid. \textbf{2020 Mathematics Subject Classification.} Primary 05C31; Secondary 05B35, 05C10, 05C15. \section{Introduction}\label{sec:introduction} The Penrose polynomial has its origins in Penrose's tensor approach to graph coloring \cite{P}. A \emph{plane graph} is a finite graph embedded in the sphere. Following Aigner, call it \emph{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 \(H\) with \(f\) faces, write \(P_H(q)=\sum_{i=1}^{f}a_iq^i\). In this setting Aigner's questions \cite[Problems 1--2]{A}, restated in our notation, are as follows. Problem 1 asks whether \(a_i\ne0\) for every \(1\leq i\leq f\); in particular, whether \(a_1\ne0\), with the stronger proposed inequality \((-1)^{f-1}a_1>0\). Problem 2 asks whether the coefficients weakly alternate, \((-1)^{f-i}a_i\geq0\) for every \(1\leq i\leq f\). It also asks whether \(P_H(-1)\ne0\), with the stronger proposed inequality \((-1)^fP_H(-1)>0\). The Eulerian case was proved by Aigner \cite[Corollary 5]{A}; his survey also records the series-parallel and outerplanar cases, citing Mielke's thesis \cite[pp.~65--66]{A00}. The graph terminology is recalled in Section \ref{sec:ribbons}. 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 \cite[Corollary 11]{A}; \cite[Theorem 16]{A00}. Further background appears in \cite{A01}. For a cubic graph \(G\), in which every vertex has degree three, a \emph{perfect matching} \(M\) is a set of edges meeting every vertex exactly once. The Penrose--Kauffman polynomial \(\operatorname{PK}_{G,M}(q)\), at a positive integer \(q\), counts colorings of the edges outside \(M\) with \(q\) 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 \ref{sec:cycle-expansion} gives the polynomial construction. Kauffman, Silver and Williams (KSW) conjecture, for every connected cubic plane graph \(G\) with specified perfect matching \(M\), that (1) the linear coefficient of \(\operatorname{PK}_{G,M}\) is nonzero and (2) its coefficients weakly alternate \cite[Section 8, p.~24]{KSW}. We begin with two explicit normal plane graphs. The tetragonal trapezohedron \(G_{10}\) violates both weak alternation and the proposed strict sign of the linear coefficient.\footnote{Aigner reports the expected coefficient behavior for ``all graphs with up to 10 vertices'' \cite[discussion preceding Problems 1--2]{A}. Taken literally, this statement is contradicted by \(G_{10}\), which has ten vertices. The passage gives no computational details that would explain the discrepancy.} Splitting one of its two degree-four vertices gives \(Z\), whose zero linear coefficient refutes both nonvanishing assertions. Their cycle expansions, defined in Section \ref{sec:cycle-expansion}, refute KSW Conjectures (2) and (1), respectively. We then give a full treatment of the twelve-vertex cubic graph \(H_0\), obtained by splitting both degree-four vertices of \(G_{10}\). 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 \((-1)^fP_H(-1)>0\), as shown in Section \ref{sec:consequences}. Sections \ref{sec:base-graphs}--\ref{sec:checks} construct \(G_{10}\) and \(Z\) and prove their polynomial formulas by exact reproducible calculations. Section \ref{sec:triangle-replacement} applies the known triangle-replacement identity \cite[Theorem 4.1, equation (4.5)]{BM} to obtain infinite families. Section \ref{sec:cubic-family} gives the cubic example \(H_0\) and its entire cubic family. Section \ref{sec:consequences} records the conjecture consequences, connected sums with arbitrarily many initial zero coefficients, and the planar minor-minimality of the cycle matroid \(M(G_{10})\), defined below, which answers Aigner's classification question \cite[p.~66]{A00} negatively. These results do not contradict the Four Color Theorem and supply no new proof of it. \section{Preliminaries}\label{sec:preliminaries} \subsection{Ribbon surfaces and coefficient signs}\label{sec:ribbons} A \emph{plane graph} means a finite graph embedded in the sphere. A graph is \emph{simple} if it has no loops or parallel edges, \emph{cubic} if every vertex has degree three, and \emph{bridgeless} if deleting any edge preserves its number of connected components. The graphs constructed below are connected and loopless; \(Z\) has two parallel edges. We use the definition of normality from Section \ref{sec:introduction}. The \emph{dual} \(H^*\) has one vertex for each face of \(H\), and one edge crossing each edge of \(H\) and joining its two incident faces. A graph is \emph{Eulerian} if every vertex degree is even. A graph minor is obtained by edge deletions, vertex deletions, and edge contractions. The graph \(K_4\) is the complete graph on four vertices; \emph{series-parallel} graphs have no \(K_4\) minor. An \emph{outerplanar} graph admits an embedding with every vertex on one face boundary. Replace the vertices of a plane graph \(H\) 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 \(A\subseteq E(H)\), insert one half twist in each band indexed by \(A\), leaving all attaching orders fixed. Let \(c_H(A)\) be the number of boundary components of the resulting surface. We use the ribbon-surface expression of Ellis-Monaghan--Moffatt \cite[Proposition 5.1]{EM}, which for plane graphs gives Aigner's Penrose polynomial \cite{A}: \begin{equation}\label{eq:ribbon-sum} P_H(q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{c_H(A)}. \end{equation} For a polynomial \(P(q)=\sum_{k=0}^{d}a_kq^k\) with \(a_d>0\), \emph{weak sign alternation} means \begin{equation}\label{eq:weak-alternation} (-1)^{d-k}a_k\geq0\qquad(0\leq k\leq d). \end{equation} We write \([q^k]P(q)\) for the coefficient of \(q^k\) in \(P(q)\). 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 \eqref{eq:ribbon-sum} is zero; the nonvanishing question concerns the coefficients of \(q,\ldots,q^d\). \subsection{The binary-Laplacian formula}\label{sec:laplacian} Work over the field \(\mathbb F_2=\{0,1\}\), with addition and multiplication modulo two. Let \(T\) be a finite loopless multigraph on \(d\) vertices. For an edge \(e=uv\), let \(b_e\) have a one in positions \(u,v\) and zero elsewhere. Define \begin{equation}\label{eq:laplacian-sum} L_A=\sum_{e\in A}b_eb_e^{\mathsf T},\qquad r(A)=\operatorname{rank}_{\mathbb F_2}L_A,\qquad F_T(q)=\sum_{A\subseteq E(T)}(-1)^{|A|}q^{d-r(A)}. \end{equation} Each edge toggles its two off-diagonal entries and the two corresponding diagonal entries. Parallel edges are separate elements of \(E(T)\) 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 \(\mathcal N=(E,C)\) is specified by a finite set \(E\) and a subspace \(C\subseteq\mathbb F_2^E\), its \emph{cycle space}. The support of a vector is the set of its nonzero coordinates. The nonempty supports of vectors in \(C\) that are minimal under inclusion are the \emph{circuits}. The dual \(\mathcal N^*\) has cycle space \(C^\perp\), the orthogonal complement for the usual mod-two dot product. An element is a \emph{coloop} if it belongs to no circuit; a matroid is \emph{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 \(H\), its cycle matroid \(M(H)\) has the even-degree edge subsets as its binary cycle space, with addition given by symmetric difference. A matroid is \emph{graphic} if it is a graph's cycle matroid, and \emph{planar} if that graph can be chosen planar. For \(A\subseteq E\), let \(x|_A\) denote the vector equal to \(x\) on \(A\) and zero elsewhere. Set \begin{equation}\label{eq:matroid-polynomial} \mathcal B_{\mathcal N}(A)=\{x\in C:x|_A\in C^\perp\},\qquad Q_{\mathcal N}(q)=\sum_{A\subseteq E}(-1)^{|A|}q^{\dim\mathcal B_{\mathcal N}(A)}. \end{equation} We use the binary-matroid Penrose polynomial of Aigner and Mielke \cite{AM}, in the cycle-space form recorded in \cite[equation (4.5)]{A00}. The letter \(Q\) distinguishes its normalization from the graph polynomial. \begin{proposition}[Binary-Laplacian formula]\label{prop:binary-laplacian} Let \(c(T)\) be the number of connected components of the loopless multigraph \(T\). Then \begin{equation}\label{eq:matroid-normalization} F_T(q)=q^{c(T)}Q_{M^*(T)}(q). \end{equation} If \(T=H^*\) for a connected bridgeless plane graph \(H\), then \(P_H(q)=F_T(q)=qQ_{M(H)}(q)\). \end{proposition} The boundary-count identity underlying the plane-graph formula is known \cite[Theorem 1.1]{SW} and is used in the proofs of \cite[Proposition 6.2 and Theorem 6.3]{KSW}. We recall a short derivation from Aigner's characterization \cite[Proposition 1]{A}. \begin{proof} Let \(D\) be the vertex-edge incidence matrix of \(T\) over \(\mathbb F_2\), whose columns are the \(b_e\). The cycle space of \(M^*(T)\) is the cut space \(\operatorname{im}D^{\mathsf T}\), and its orthogonal complement is \(\ker D\). For \(x=D^{\mathsf T}y\), the condition \(x|_A\in\ker D\) is exactly \(L_Ay=0\). The map \(y\mapsto D^{\mathsf T}y\) has kernel of dimension \(c(T)\), consisting of vectors constant on each component. Since \(D^{\mathsf T}y=0\) implies \(b_e^{\mathsf T}y=0\) for every edge \(e\), it also implies \(L_Ay=0\). Thus \(\ker D^{\mathsf T}\subseteq\ker L_A\). The restricted map \(D^{\mathsf T}:\ker L_A\to\mathcal B_{M^*(T)}(A)\) is surjective and has kernel of dimension \(c(T)\). Rank-nullity now gives \(\dim\mathcal B_{M^*(T)}(A)=d-r(A)-c(T)\), proving the first identity. For a connected plane graph \(H\), plane duality gives \(M(H)=M^*(H^*)\), and the closed paths in Aigner's construction can be identified with ribbon boundaries. For every \(A\subseteq E(H)\), his closed paths with changing set \(A\) correspond to the boundary components of the ribbon surface twisted along \(A\): both follow the face-boundary pairing at edges outside \(A\) and the crossing pairing at edges in \(A\) \cite[Section 2]{A}; \cite[proof of Proposition 5.1]{EM}. Thus his path count is \(c_H(A)\) for each \(A\). Aigner's boundary-count identity then gives \(\dim\mathcal B_{M(H)}(A)=c_H(A)-1\). Substitution into \eqref{eq:ribbon-sum} and \eqref{eq:matroid-polynomial} proves the remaining identities. \end{proof} If \(T\) is simple, only the empty subset has \(L_A=0\), because the off-diagonal entries record the selected edges. Hence \(F_T\) is monic of degree \(d\). Also \(L_A\mathbf1=0\), so \(r(A)\leq d-1\). For normal plane graphs this recovers \cite[Corollary 3]{A}; the corresponding PK statement is \cite[Proposition 6.2]{KSW}. For comparison, a graph on two vertices with two parallel edges has \(F_T(q)=2q^2-2q\). \subsection{Cycle expansion and the Penrose--Kauffman polynomial}\label{sec:cycle-expansion} A \emph{perfect matching} \(M\) of a cubic graph \(G\) is a set of edges meeting each vertex exactly once. A \emph{Tait \(n\)-coloring of \((G,M)\)} assigns one of \(n\) named colors to every edge outside \(M\), 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 \(\operatorname{PK}_{G,M}(q)\) counts these colorings at every positive integer \(q=n\) \cite[Definition 3.1]{KSW}. To see that this is a polynomial with integer coefficients, define a \emph{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 \ref{fig:local-pairings}. 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 \emph{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 \emph{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 \cite[Theorem 3.4]{KSW}. Uncolorable states contribute zero. A related expansion for plane Penrose polynomials is given in \cite[Theorem 7.2]{EM}. \begin{figure} \centering \includegraphics[width=0.95\linewidth,height=\textheight,keepaspectratio,alt={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 \textbackslash ell\_1,\textbackslash ell\_2,r\_1,r\_2 correspond respectively to the upper-left, lower-left, upper-right and lower-right strands in (a). For the displayed colors i\textbackslash ne j, only pairing (c) joins strands of equal color. The crossing in (c) is not a graph vertex.}]{local-pairings.pdf} \caption{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 \(\ell_1,\ell_2,r_1,r_2\) correspond respectively to the upper-left, lower-left, upper-right and lower-right strands in (a). For the displayed colors \(i\ne j\), only pairing (c) joins strands of equal color. The crossing in (c) is not a graph vertex.}\label{fig:local-pairings} \end{figure} For a loopless plane graph \(H\) of minimum degree at least three, let its \emph{cycle expansion} (also called truncation) \(\Delta H\) be the graph obtained by replacing each vertex of degree \(k\) by a \(k\)-cycle and attaching its incident edges in cyclic order. The original edges form a perfect matching \(M_H\), and \(\Delta H\) is a cubic plane graph. Thus degree-three vertices become triangles and degree-four vertices become quadrilaterals. \begin{proposition}[Identity for cycle expansion]\label{prop:cycle-expansion} For every connected loopless plane graph \(H\) of minimum degree at least three, \begin{equation}\label{eq:cycle-expansion} P_H(q)=\operatorname{PK}_{\Delta H,M_H}(q). \end{equation} \end{proposition} Identity \eqref{eq:cycle-expansion} is stated in \cite[Section 4]{KSW}, where the cycle expansion is called a blow-up; the same construction is used in \cite[Section 1]{BM}. We give a direct proof from the ribbon sum \eqref{eq:ribbon-sum}. \begin{proof} At a positive integer \(q=n\), expand each term in \eqref{eq:ribbon-sum} by assigning a color to each boundary circuit. Regroup by fixed colors on the \emph{corner arcs}, the portions of the vertex-disk boundaries between consecutive edge bands. The corner arcs around a degree-\(k\) vertex of \(H\) correspond to the edges of its replacement \(k\)-cycle in \(\Delta H\). The band of an original edge \(e\) corresponds to the matching edge \(e\) in \(M_H\); 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 \(+1\) and \(-1\). If all four ends at a band have the same color, both pairings are compatible and their local contribution is \(1-1=0\). 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 \((\Delta H,M_H)\). 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 \(n\), the sum therefore counts the Tait \(n\)-colorings. Equality at all positive integers proves the polynomial identity. \end{proof} \section{The first two counterexamples}\label{sec:base-graphs} Construct \(G_{10}\) from the cycle \(c_0c_1\cdots c_7c_0\). Put a vertex \(N\) inside the cycle and join it to \(c_0,c_2,c_4,c_6\); put a vertex \(S\) outside and join it to \(c_1,c_3,c_5,c_7\). We call \(N\) and \(S\) the two \emph{hubs}. This is the tetragonal trapezohedron graph, shown in Figure \ref{fig:base-graphs}. The construction specifies its sphere embedding. 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 \(Z\), split \(N\) into \(N_1,N_2\), keeping \(N_1\) adjacent to \(c_0,c_2\) and \(N_2\) adjacent to \(c_4,c_6\), and join \(N_1,N_2\) 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. \begin{theorem}\label{thm:base-graphs} The graphs just constructed have Penrose polynomials \begin{figure}[H] \centering \includegraphics[width=0.95\linewidth,height=\textheight,keepaspectratio,alt={The two plane graphs. The left panel shows G\_\{10\}, and the right panel shows the split hub and the two parallel edges of Z. The cycle labels agree in both panels.}]{graphs.pdf} \caption{The two plane graphs. The left panel shows \(G_{10}\), and the right panel shows the split hub and the two parallel edges of \(Z\). The cycle labels agree in both panels.}\label{fig:base-graphs} \end{figure} \begin{equation}\label{eq:g10-polynomial} \begin{aligned} P_{G_{10}}(q)={}&q^8-16q^7+114q^6-432q^5\\ &{}+857q^4-744q^3+60q^2+160q, \end{aligned} \end{equation} and \begin{equation}\label{eq:z-polynomial} \begin{aligned} P_Z(q)={}&q^9-18q^8+150q^7-708q^6+1973q^5\\ &{}-3178q^4+2700q^3-920q^2. \end{aligned} \end{equation} Thus \(P_{G_{10}}\) fails weak sign alternation, and \([q]P_Z(q)=0\). \end{theorem} The calculation proving \eqref{eq:g10-polynomial}--\eqref{eq:z-polynomial} is given next. Both dual graphs are simple. The dual \(T=G_{10}^*\) is the square antiprism: on vertices \(0,\ldots,7\), its edges are the unordered pairs \(\{i,i+1\}\) and \(\{i,i+2\}\), with indices modulo eight. Explicitly, for \(i=0,1,2,3\), label the face \(Nc_{2i}c_{2i+1}c_{2i+2}\) by \(2i+1\) and the face \(Sc_{2i+1}c_{2i+2}c_{2i+3}\) by \(2i+2\), taking all numerical labels modulo eight. Then \(Z^*\) is obtained from \(T\) by adding vertex \(8\) and edges \(38,78\). The two pentagons retain labels \(3,7\), and the new digon receives label \(8\). These descriptions also give the input for the short calculation in Appendix \ref{app:rank-tables}. \section{\texorpdfstring{Proof of Theorem \ref{thm:base-graphs} and independent checks}{Proof of Theorem and independent checks}}\label{sec:checks} For the graph \(T\) in \eqref{eq:laplacian-sum}, define \(B_r(T)=(-1)^r[q^{d-r}]F_T(q)\), setting \(B_r(T)=0\) outside \(0\leq r\leq d\). These numbers remove the expected alternating signs: weak alternation is equivalent to \(B_r(T)\geq0\) for every \(r\). The rank formula gives \begin{equation}\label{eq:rank-counts} \begin{aligned} B_r(T)={}&\#\{A:r(A)=r,\ |A|\equiv r\pmod2\}\\ &{}-\#\{A:r(A)=r,\ |A|\not\equiv r\pmod2\}. \end{aligned} \end{equation} \begin{proof}[Proof of Theorem \ref{thm:base-graphs}] By Proposition \ref{prop:binary-laplacian}, the required coefficients are given by binary-Laplacian ranks. Table \ref{tab:base-ranks} records all \(2^{16}\) subsets for \(G_{10}^*\) and all \(2^{18}\) subsets for \(Z^*\). The even and odd columns count subsets of the given rank by the parity of \(|A|\), so \(B_r=(-1)^r(\text{even}-\text{odd})\) by \eqref{eq:rank-counts}. The dash denotes a rank outside the range for \(G_{10}^*\). {\setlength{\LTcapwidth}{\linewidth} \begin{longtable}[]{@{} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}} >{\raggedleft\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.142857}}@{}} \caption{Exact edge-subset counts by binary-Laplacian rank and edge-count parity for \(G_{10}^*\) and \(Z^*\); \(B_r=(-1)^r(\text{even}-\text{odd})\). \label{tab:base-ranks}}\tabularnewline \toprule\noalign{} \begin{minipage}[b]{\linewidth}\raggedleft rank \(r\) \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(G_{10}^*\): even \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft odd \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(B_r\) \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(Z^*\): even \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft odd \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(B_r\) \end{minipage} \\ \midrule\noalign{} \endfirsthead \toprule\noalign{} \begin{minipage}[b]{\linewidth}\raggedleft rank \(r\) \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(G_{10}^*\): even \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft odd \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(B_r\) \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(Z^*\): even \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft odd \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedleft \(B_r\) \end{minipage} \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot 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 & \(-160\) & 49280 & 50200 & 920 \\ 8 & --- & --- & --- & 30368 & 30368 & 0 \\ \end{longtable} } Taking even minus odd as the coefficient of \(q^{d-r}\) proves \eqref{eq:g10-polynomial}--\eqref{eq:z-polynomial}. For \(G_{10}\), degree eight requires a nonpositive linear coefficient, whereas that coefficient is \(160\). For \(Z\), the equally sized even and odd classes with one boundary component cancel. Appendix \ref{app:rank-tables} exhausts every edge subset and computes these counts in exact integers. Thus \(B_7(G_{10}^*)=-160\) exhibits failure of weak alternation, whereas \(B_8(Z^*)=0\) records the vanishing linear coefficient. \end{proof} \textbf{Independent checks.} The supplement, described under \hyperref[sec:supplement]{Supplementary material}, contains the verification program (\texttt{verify.py}), reproduction instructions (\texttt{README.md}), and exact output with the program SHA-256 (\texttt{verification.json}). The program \texttt{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 \eqref{eq:ribbon-sum}, and set partitions of the corner arcs in Proposition \ref{prop:cycle-expansion}. The last calculation enumerates color classes of the \(32\) or \(36\) nonmatching edges of the cycle expansion. A partition into \(m\) nonempty classes has \((q)_m=q(q-1)\cdots(q-m+1)\) assignments of distinct named colors. This gives the general falling-factorial expansion of \cite[equation (8.2)]{KSW}. 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 \begin{equation}\label{eq:falling-factorials} \begin{aligned} P_{G_{10}}(q)={}&8(q)_3+48(q)_4+88(q)_5+44(q)_6+12(q)_7+(q)_8,\\ P_Z(q)={}&24(q)_3+184(q)_4+404(q)_5+300(q)_6\\ &{}+108(q)_7+18(q)_8+(q)_9. \end{aligned} \end{equation} Since \([q](q)_m=(-1)^{m-1}(m-1)!\), the coefficient formula \cite[Corollary 8.4]{KSW} gives the direct checks \[ \begin{aligned} {}[q]P_{G_{10}}&=16-288+2112-5280+8640-5040=160,\\ {}[q]P_Z&=48-1104+9696-36000+77760-90720+40320=0. \end{aligned} \] For each graph, the coefficient of \((q)_m\) in \eqref{eq:falling-factorials} is the count \(e_m\) of colorings up to renaming in \cite[equation (8.2)]{KSW}. The number of colorings using all \(m\) named colors is \(c_m=m!e_m\), as used in \cite[Corollary 8.4]{KSW}. 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. \section{Triangle replacement and infinite families}\label{sec:triangle-replacement} We call replacing one degree-three vertex by a triangle, with the incident edges attached in their embedding order, a \emph{triangle replacement}. The following is its dual form. Let \(T\) be a finite simple plane graph with a triangular face \(abc\), and form \(T'\) by placing a new vertex \(v\) inside that face and joining it to \(a,b,c\). We give a short algebraic proof of the known recurrence \cite[Theorem 4.1, equation (4.5)]{BM}. For a selected edge set \(A'\subseteq E(T')\), write \(A=A'\cap E(T)\) and \(J=\{x\in\{a,b,c\}:vx\in A'\}\), the set of selected neighbors of \(v\). \begin{lemma}[Triangle recurrence]\label{lem:triangle-recurrence} In this setting, \begin{equation}\label{eq:triangle-recurrence} F_{T'}(q)=(q-2)F_T(q),\qquad B_r(T')=B_r(T)+2B_{r-1}(T), \end{equation} where missing coefficient indices have value zero. \end{lemma} \begin{proof} We pair terms in the full sum indexed by \((A,J)\), allowing the old subset \(A\) to change. Choose \(a\) as a distinguished vertex. The following pairing cancels all terms except those with \(J=\varnothing,\{b\},\{c\}\): \begin{itemize} \tightlist \item If \(|J|=2\), toggle the old edge joining the two vertices in \(J\). \item If \(J=\{a,b,c\}\), change \(J\) to \(\{a\}\) and toggle all three old triangle edges; reverse this rule when \(J=\{a\}\). \end{itemize} 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 \(|J|=2\), let \(L=L_{A'}\) be the binary Laplacian of the selected edge set \(A'\) in \(T'\), let \(e_v\) be the coordinate vector at \(v\), and put \(z=Le_v\). The vector \(z\) has ones exactly at the two selected neighbors. Since \(v\) has two selected incident edges, \(L_{vv}=0\) over \(\mathbb F_2\), so \(z^{\mathsf T}e_v=L_{vv}=0\). Toggling the edge between those neighbors changes \(L\) to \(L+zz^{\mathsf T}\), and \[ L+zz^{\mathsf T}=L(I+e_vz^{\mathsf T}),\qquad (I+e_vz^{\mathsf T})^2=I. \] The right factor is invertible, proving rank preservation. For odd \(|J|\), put coordinate \(v\) first, let \(s\) be the neighbor indicator, and use the diagonal entry \(1\) as a pivot. The resulting Schur complement is \(L_A+\operatorname{diag}(s)+ss^{\mathsf T}\). For \(J=\{a\}\) the last two terms cancel. For \(J=\{a,b,c\}\) 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 \(J=\varnothing,\{b\},\{c\}\). For an old subset of rank \(r\), the empty choice has rank \(r\) on \(d+1\) vertices and contributes \(q\) times its old monomial. Each remaining singleton has rank \(r+1\) and the opposite edge-count sign, hence contributes minus its old monomial. Their sum is \((q-2)\) times the old contribution. Comparing coefficients, with the degree increased by one, gives the second identity in \eqref{eq:triangle-recurrence}. \end{proof} The same argument proves \eqref{eq:triangle-recurrence} for any finite loopless multigraph \(T\) containing a triangle \(abc\), with \(T'\) obtained by adjoining a new vertex joined once to each of \(a,b,c\). 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 \(H\) be either \(G_{10}\) or \(Z\). For an integer \(t\geq0\), write \(H^{(t)}\) for any graph obtained by \(t\) 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 \(G_{10}\) remain simple. Each replacement adds two vertices, three edges and one face. Equation \eqref{eq:triangle-recurrence} therefore gives \begin{equation}\label{eq:base-families} P_{H^{(t)}}(q)=(q-2)^tP_H(q),\qquad \deg P_{G_{10}^{(t)}}=8+t,\qquad \deg P_{Z^{(t)}}=9+t. \end{equation} In particular, \begin{equation}\label{eq:base-linear-coefficients} (-1)^{7+t}[q]P_{G_{10}^{(t)}}(q)=-160\cdot2^t<0, \qquad [q]P_{Z^{(t)}}(q)=0. \end{equation} To see this directly from the coefficient recurrence, let \(T\) have \(d\) vertices. Its constant coefficient \(B_d(T)\) is zero, since every \(L_A\) has the all-ones vector in its kernel. Equation \eqref{eq:triangle-recurrence} gives \(B_d(T')=2B_{d-1}(T)\): the sign-adjusted linear coefficient doubles at each replacement. Starting from \(-160\) and \(0\) gives \eqref{eq:base-linear-coefficients}. \section{The cubic counterexample and its family}\label{sec:cubic-family} The first two base graphs have degree-four vertices. We now construct a simple cubic example for the ordinary Penrose polynomial. Starting from \(G_{10}\), split \(N\) into adjacent vertices \(N_1,N_2\), with \(N_1\) joined to \(c_0,c_2\) and \(N_2\) to \(c_4,c_6\). Split \(S\) into adjacent vertices \(S_1,S_2\), with \(S_1\) joined to \(c_1,c_3\) and \(S_2\) to \(c_5,c_7\). Each split uses a single joining edge and inherits the plane embedding. Denote the resulting graph by \(H_0\); see Figure \ref{fig:cubic}. 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 \(H_0\) is \(2\)-connected and bridgeless. Its dual \(T_0\) is obtained from the labelled square antiprism of Section \ref{sec:base-graphs} by adding edges \(\{3,7\}\) and \(\{0,4\}\). The first splits the northern square face of the dual and the second the southern square face. The dual is simple, so \(H_0\) is normal. \begin{theorem}[A cubic counterexample and an infinite cubic family]\label{thm:cubic-family} The graph \(H_0\) has Penrose polynomial \begin{figure}[H] \centering \includegraphics[width=0.48\linewidth,height=\textheight,keepaspectratio,alt={The cubic plane graph H\_0. Both hubs of G\_\{10\} are split into adjacent pairs, each joined by a single edge. The cycle labels are the same as in Figure .}]{cubic.pdf} \caption{The cubic plane graph \(H_0\). Both hubs of \(G_{10}\) are split into adjacent pairs, each joined by a single edge. The cycle labels are the same as in Figure \ref{fig:base-graphs}.}\label{fig:cubic} \end{figure} \begin{equation}\label{eq:h0-polynomial} \begin{aligned} P_{H_0}(q)={}&q^8-18q^7+162q^6-753q^5\\ &{}+1692q^4-1452q^3-208q^2+576q. \end{aligned} \end{equation} For every integer \(t\geq0\), let \(H_t\) be any graph obtained from \(H_0\) by \(t\) successive triangle replacements. Then \(H_t\) is normal, simple, connected, bridgeless and cubic, with \(12+2t\) vertices, \(18+3t\) edges and \(8+t\) faces, and \begin{equation}\label{eq:cubic-family} P_{H_t}(q)=(q-2)^tP_{H_0}(q). \end{equation} Its linear and quadratic coefficients both have the wrong signs: \begin{equation}\label{eq:cubic-coefficients} \begin{aligned} (-1)^{7+t}[q]P_{H_t}(q)&=-576\cdot2^t<0,\\ (-1)^{6+t}[q^2]P_{H_t}(q)&=-(208+288t)2^t<0. \end{aligned} \end{equation} \end{theorem} \begin{proof} Apply Proposition \ref{prop:binary-laplacian} to the dual \(T_0\) just specified. Table \ref{tab:cubic-ranks}, computed by the exhaustive integer calculation in Appendix \ref{app:rank-tables}, gives \eqref{eq:h0-polynomial}. \begin{longtable}[]{@{}rrrr@{}} \caption{Exact edge-subset counts for \(T_0=H_0^*\); all \(2^{18}\) subsets are included, and \(B_r=(-1)^r(\text{even}-\text{odd})\). \label{tab:cubic-ranks}}\tabularnewline \toprule\noalign{} rank \(r\) & even & odd & \(B_r(T_0)\) \\ \midrule\noalign{} \endfirsthead \toprule\noalign{} rank \(r\) & even & odd & \(B_r(T_0)\) \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot 0 & 1 & 0 & \(1\) \\ 1 & 0 & 18 & \(18\) \\ 2 & 192 & 30 & \(162\) \\ 3 & 591 & 1344 & \(753\) \\ 4 & 7204 & 5512 & \(1692\) \\ 5 & 24700 & 26152 & \(1452\) \\ 6 & 54064 & 54272 & \(-208\) \\ 7 & 44320 & 43744 & \(-576\) \\ \end{longtable} The construction and the preservation argument in Section \ref{sec:triangle-replacement} prove the graph properties at every step. Each replacement adds two vertices, three edges and one face and preserves degree three. Lemma \ref{lem:triangle-recurrence} gives \eqref{eq:cubic-family}. Put \(\ell_t=(-1)^{7+t}[q]P_{H_t}\) and \(s_t=(-1)^{6+t}[q^2]P_{H_t}\). The coefficient recurrence in \eqref{eq:triangle-recurrence} gives \(\ell_{t+1}=2\ell_t\) and \(s_{t+1}=2s_t+\ell_t\), with \(\ell_0=-576\) and \(s_0=-208\). Induction gives \eqref{eq:cubic-coefficients}. \end{proof} The supplement reconstructs this embedding and verifies \eqref{eq:h0-polynomial} by the same three computations used for \(G_{10}\) and \(Z\). The color-class enumeration gives the further check \[ P_{H_0}(q)=3(q)_3+93(q)_4+207(q)_5+50(q)_6+10(q)_7+(q)_8. \] 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 \(H_0\). 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 \(H_t\) has eighteen proper edge three-colorings. The evaluations \(P_{H_0}(3)=18\) and \(P_{H_0}(-2)=73728=(-4)^6\cdot18\) agree with the standard cubic formulas \cite[Corollaries 8 and 10]{A}. More generally, \eqref{eq:cubic-family} gives \(P_{H_t}(3)=18\) and \(P_{H_t}(-2)=(-4)^{6+t}\cdot18\). The value at \(-1\) is recorded with those of the other two families in Section \ref{sec:consequences}. Thus weak alternation and the proposed strict linear sign fail even for the ordinary Penrose polynomial of simple bridgeless cubic plane graphs. Since \([q]P_{H_0}=576\ne0\), this example does not refute linear nonvanishing. \section{Consequences for the coefficient conjectures}\label{sec:consequences} The graphs \(G_{10}^{(t)}\) answer Aigner's weak-alternation question and his proposed strict sign for the linear coefficient negatively \cite[Problems 1--2]{A}. The graphs \(Z^{(t)}\) 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 \(Z\) itself does satisfy weak alternation; its purpose here is the distinct nonvanishing conclusion. The graphs \(\Delta G_{10}^{(t)}\) and \(\Delta Z^{(t)}\) are simple, connected, bridgeless cubic plane graphs on \(32+6t\) and \(36+6t\) vertices, respectively, with the specified perfect matchings. Propositions \ref{prop:binary-laplacian}--\ref{prop:cycle-expansion} and \eqref{eq:base-linear-coefficients} refute \cite[Conjecture (2)]{KSW} and \cite[Conjecture (1)]{KSW}, 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 \(G_{10}^{(t)}\) and \(Z^{(t)}\) retain degree-four vertices and are not cubic; Theorem \ref{thm:cubic-family} supplies the separate cubic ordinary-Penrose family. Every \(Z^{(t)}\) 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 \(\Delta Z^{(t)}\) already refute nonvanishing for the matching-dependent polynomial \(\operatorname{PK}_{G,M}\). The diagram associated with \((\Delta G_{10},M_{G_{10}})\) lies in the class of \cite[Theorem 6.6]{KSW}. In the construction of \cite[Section 4]{KSW}, contract each matching edge to a crossing to obtain the medial projection, whose vertices correspond to edges of \(G_{10}\) and whose arcs join consecutive edges around its vertices. The associated crossing choices make the diagram alternating. A diagram is \emph{reduced} if no crossing is isolated from the remainder by a simple closed curve through that crossing, and \emph{prime} if any simple closed curve meeting the projection transversely twice bounds a disk containing only an arc on at least one side. Because \(G_{10}\) 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 \(G_{10}\), namely three or four, so it has no bigon regions. Weak alternation fails even for this diagram class. The diagrams associated with \((\Delta H_t,M_{H_t})\), \(t\geq0\), also belong to this class. Each \(H_t\) 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 \eqref{eq:cycle-expansion} and \eqref{eq:cubic-coefficients}, 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 \cite[Corollary 5]{A}. Their values at \(-1\) are \(P_{G_{10}}(-1)=2064\), \(P_Z(-1)=-9648\), and \(P_{H_0}(-1)=3294\). For a base graph \(H\) with \(f_H\) faces, successive triangle replacements give \begin{equation}\label{eq:minus-one} (-1)^{f_H+t}P_{H^{(t)}}(-1) =3^t(-1)^{f_H}P_H(-1). \end{equation} The three resulting values are \(2064\cdot3^t\), \(9648\cdot3^t\), and \(3294\cdot3^t\), respectively, all positive. All three families satisfy the sign-at-minus-one inequality proposed in \cite[Problem 2]{A}. 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 \(s\geq1\) copies of the diagram associated with \((\Delta Z,M_Z)\) and iterate precisely the joining of \cite[Definition 3.6, Figure 7(c)]{KSW}. Let \((\Gamma_s,M_s)\) be the corresponding connected cubic plane graph with its specified matching. Then \cite[Proposition 3.7(3)]{KSW} gives \begin{equation}\label{eq:connected-sums} \operatorname{PK}_{\Gamma_s,M_s}(q)=\frac{P_Z(q)^s}{q^{s-1}} =q^{s+1}(-920+qR(q))^s,\qquad R(q)\in\mathbb Z[q]. \end{equation} Thus the coefficients of \(q,\ldots,q^s\) vanish, and the coefficient of \(q^{s+1}\) is \((-920)^s\ne0\). This realizes the conditional consequence already noted in \cite[p.~25]{KSW}. \subsection{An explicit planar matroid obstruction}\label{sec:matroid-obstruction} Dividing a nonzero graph polynomial by \(q\) decreases its degree and every nonzero exponent by one, preserving the difference between degree and exponent in \eqref{eq:weak-alternation}: \((d-1)-(k-1)=d-k\). By \eqref{eq:matroid-normalization}, \(Q_{M(G_{10})}\) has degree seven and constant coefficient \(160\), whereas weak alternation requires a nonpositive constant coefficient. Aigner asks whether \(F_7^*\), \(M(\mathrm{Pet})\), and \(M^*(K_5)\) are the only bridgeless minor-minimal binary matroids whose Penrose polynomials have non-alternating coefficients \cite[p.~66]{A00}. A positive answer would imply the Four Color Theorem. Theorem \ref{thm:matroid-obstruction} answers this question negatively by providing a planar minor-minimal obstruction. Here \(F_7\) is the Fano matroid whose cycle space is the kernel of the \(3\)-by-\(7\) matrix with all nonzero vectors of \(\mathbb F_2^3\) as columns. The Petersen graph \(\mathrm{Pet}\) has vertices \(u_i,v_i\) for \(i\) modulo five and edges \(u_i u_{i+1}\), \(u_i v_i\), and \(v_i v_{i+2}\). The graph \(K_5\) is complete on five vertices. \begin{theorem}[Planar minor-minimal obstruction; computer-assisted]\label{thm:matroid-obstruction} The \(16\)-element planar matroid \(M(G_{10})\) fails weak coefficient alternation, and every proper bridgeless minor has strictly alternating coefficients. Thus \(M(G_{10})\) is a planar minor-minimal obstruction to coefficient alternation, distinct from all three examples listed by Aigner, none of which is planar. \end{theorem} Here minimality is within the bridgeless class. Strict alternation requires strict inequalities for every coefficient of \(Q\), including its constant term. Minor-minimality holds for both strict and weak alternation: \(Q_{M(G_{10})}\) fails weak alternation, whereas every proper bridgeless minor satisfies strict alternation. As in Aigner's list, we regard the zero polynomial \(Q_{F_7^*}=0\) as non-alternating. \begin{proof} It remains to verify minimality and the nonplanarity of the listed examples. Distinctness already follows from their sizes: \(M(G_{10})\) has sixteen elements, whereas \(F_7^*\), \(M(\mathrm{Pet})\), and \(M^*(K_5)\) have seven, fifteen and ten, respectively. Since \(M(G_{10})=M^*(T)\) for the square antiprism \(T\), its bridgeless minors are the matroids \(M^*(U)\) of loopless graph minors \(U\) of \(T\). Contracted edges partition \(V(T)\) 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 \(k\geq1\) parallel edges contributes \(2^{k-1}\) times the contribution of a single edge to \eqref{eq:laplacian-sum}: its even and odd subsets each number \(2^{k-1}\) and give, respectively, the zero and single-edge binary-Laplacian contributions. Let \(\bar U\) retain all vertices and one edge from each parallel class, and put \(p=|E(U)|-|E(\bar U)|\geq0\). Then \(F_U(q)=2^pF_{\bar U}(q)\). Since \(c(U)=c(\bar U)\), also \(Q_{M^*(U)}=2^pQ_{M^*(\bar U)}\). Thus simplification preserves both strict and weak alternation. In the plane-graph setting this is \cite[Theorem 6.3]{KSW}, the dual form of \cite[Corollary 2]{A}. It suffices to examine every spanning subgraph \(R\) of each simple quotient and test \(Q_{M^*(R)}=F_R/q^{c(R)}\). The supplement performs this finite exhaustive calculation. For each quotient with edge set \(E\), start with the signed nullity monomial \((-1)^{|A|}q^{d-r(A)}\) at every \(A\subseteq E\). For each edge \(e\), add the entry for \(R\smallsetminus\{e\}\) to that for \(R\) whenever \(e\in R\). After all edges have been processed, the entry at \(R\) is exactly \(F_R\). Removing the factor \(q^{c(R)}\) 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 \(M(G_{10})\) 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,\ldots\) 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 \cite[Theorem 29]{W}, the dual of a graph's cycle matroid is graphic if and only if the graph is planar. If \(M(\mathrm{Pet})\) admitted a planar graph representation, its dual would be graphic; Whitney's criterion would imply that \(\mathrm{Pet}\) itself is planar, a contradiction. The same criterion makes \(M^*(K_5)\) nongraphic because \(K_5\) is nonplanar. Also \(F_7^*\) 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 \(M(G_{10})\). \end{proof} The Petersen example is not minor-minimal, contrary to its description in \cite[p.~66]{A00}. Contract the outer edge \(e=u_0u_1\) in the labelling above. The resulting graph is bridgeless, and an exact cycle-space calculation in the supplement gives \begin{equation}\label{eq:petersen-contraction} Q_{M(\mathrm{Pet})/e}(q) =q^6-14q^5+84q^4-235q^3+248q^2+12q-96. \end{equation} Its positive linear coefficient and negative constant coefficient violate weak alternation. Thus a proper bridgeless minor of \(M(\mathrm{Pet})\) already fails. The matroid \(M(G_{10})\) does not contradict Tutte's tangential \(2\)-block conjecture in the formulation of \cite[equation (5.3)]{A00}, since \begin{equation}\label{eq:matroid-at-four} Q_{M(G_{10})}(4)=P_{G_{10}}(4)/4=336\ne0. \end{equation} \clearpage \appendix \section{A complete calculation of the rank tables}\label{app:rank-tables} The following program requires Python 3.10 or later and uses only integers and the standard library. Bits encode vectors over \(\mathbb F_2\). 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 \ref{sec:base-graphs} and \ref{sec:cubic-family}. The same exhaustive calculation gives Tables \ref{tab:base-ranks} and \ref{tab:cubic-ranks}. {\small \begin{verbatim} 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)) \end{verbatim} } \section*{Supplementary material}\label{sec:supplement} \addcontentsline{toc}{section}{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, \texttt{\SupplementArchive}, is archived together with this paper on Zenodo at \SupplementLink. \section*{Acknowledgments}\label{sec:acknowledgments} \addcontentsline{toc}{section}{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. \addcontentsline{toc}{section}{References} \clearpage \begin{thebibliography}{KSW} \bibitem[A]{A} M. Aigner, \emph{The Penrose polynomial of a plane graph}, Mathematische Annalen \textbf{307} (1997), 173--189. \href{https://doi.org/10.1007/s002080050030}{\nolinkurl{doi:10.1007/s002080050030}}. \href{https://ftp.mi.fu-berlin.de/pub/math/publ/pre/1996/pr-a-96-12.ps}{Author preprint A-96-12 (1996)}. Item numbering follows the linked author preprint. \bibitem[A00]{A00} M. Aigner, \emph{Die Ideen von Penrose zum 4-Farbenproblem}, Jahresbericht der Deutschen Mathematiker-Vereinigung \textbf{102} (2000), 43--68. \href{https://www.math.uni-bielefeld.de/JB_DMV/JB_DMV_102_2.pdf}{Journal scan}. \bibitem[A01]{A01} M. Aigner, \emph{The Penrose polynomial of graphs and matroids}, in J. W. P. Hirschfeld (ed.), \emph{Surveys in Combinatorics, 2001}, London Mathematical Society Lecture Note Series \textbf{288}, Cambridge University Press (2001), 11--46. \href{https://doi.org/10.1017/CBO9780511721328.004}{\nolinkurl{doi:10.1017/CBO9780511721328.004}}. \bibitem[AM]{AM} M. Aigner and H. Mielke, \emph{The Penrose polynomial of binary matroids}, Monatshefte für Mathematik \textbf{131} (2000), 1--13. \href{https://doi.org/10.1007/s006050070020}{\nolinkurl{doi:10.1007/s006050070020}}. \bibitem[BM]{BM} S. Baldridge and B. McCarty, \emph{New relations for the Penrose polynomial}, \href{https://arxiv.org/abs/2606.06643v1}{arXiv:\allowbreak 2606.06643v1}, 4 June 2026. \bibitem[EM]{EM} J. A. Ellis-Monaghan and I. Moffatt, \emph{A Penrose polynomial for embedded graphs}, European Journal of Combinatorics \textbf{34} (2013), 424--445. \href{https://doi.org/10.1016/j.ejc.2012.06.009}{\nolinkurl{doi:10.1016/j.ejc.2012.06.009}}; \href{https://arxiv.org/abs/1106.5279v3}{arXiv:\allowbreak 1106.5279v3}. Item numbering follows arXiv v3. \bibitem[KSW]{KSW} L. H. Kauffman, D. S. Silver and S. G. Williams, \emph{The Penrose-Kauffman Polynomial}, \href{https://arxiv.org/abs/2604.16635v1}{arXiv:\allowbreak 2604.16635v1}, 17 April 2026. \bibitem[P]{P} R. Penrose, \emph{Applications of Negative Dimensional Tensors}, in D. J. A. Welsh (ed.), \emph{Combinatorial Mathematics and its Applications}, Academic Press (1971), 221--244. \bibitem[SW]{SW} D. S. Silver and S. G. Williams, \emph{On the component number of links from plane graphs}, Journal of Knot Theory and Its Ramifications \textbf{24} (2015), 1520002. \href{https://doi.org/10.1142/S0218216515200023}{\nolinkurl{doi:10.1142/S0218216515200023}}. \href{https://arxiv.org/abs/1408.6815}{arXiv:\allowbreak 1408.6815}. \bibitem[W]{W} H. Whitney, \emph{Non-separable and planar graphs}, Transactions of the American Mathematical Society \textbf{34} (1932), 339--362. \href{https://doi.org/10.1090/S0002-9947-1932-1501641-2}{\nolinkurl{doi:10.1090/S0002-9947-1932-1501641-2}}. \end{thebibliography} \end{document}