Tutte polynomial
The Tutte polynomial is a two-variable polynomial invariant in graph theory and matroid theory that encodes a wide array of combinatorial structures and properties of graphs and matroids, serving as a universal generating function from which many classical graph polynomials can be derived.[1] Introduced by the British mathematician W. T. Tutte in his 1947 paper "A ring in graph theory," it encodes information about combinatorial structures including those related to nowhere-zero flows and chromatic polynomials but evolved into a foundational object with applications across mathematics, physics, and computer science.[2][3] The polynomial T(M; x, y) for a matroid M (or graph G, viewed as the cycle matroid of its edges) admits a recursive definition based on deletion and contraction operations: if M has no elements, then T(M; x, y) = 1; for a non-loop, non-bridge element e, T(M; x, y) = T(M \setminus e; x, y) + T(M / e; x, y); if e is a loop, T(M; x, y) = y \cdot T(M / e; x, y); and if e is a bridge (or isthmus), T(M; x, y) = x \cdot T(M \setminus e; x, y).[1] This recursion is independent of the order of operations, ensuring well-definedness; this recursion was further developed in Tutte's subsequent work on dichromatic polynomials (1954, 1967), where a related form was formalized.[3] An equivalent rank-nullity expansion expresses it as T(M; x, y) = \sum_{A \subseteq E} (x-1)^{r(E) - r(A)} (y-1)^{|A| - r(A)}, summing over subsets A of elements, where r denotes the rank function.[1] Key properties include its multiplicativity under disjoint union (T(M_1 \sqcup M_2; [x, y](/page/X&Y)) = T(M_1; [x, y](/page/X&Y)) \cdot T(M_2; [x, y](/page/X&Y))) and duality for matroids (T(M^*; [x, y](/page/X&Y)) = T(M; y, x), where M^* is the dual matroid), which reflect structural symmetries.[1][3] Notable evaluations include T(G; 1, 1), which counts the number of bases (spanning trees for graphs); T(G; 2, 0), the number of acyclic orientations; and specializations yielding the chromatic polynomial P_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T(G; 1 - \lambda, 0) (where k(G) is the number of connected components) and the flow polynomial F_G(\lambda) = (-1)^{|E| - |V| + k(G)} T(G; 0, 1 - \lambda).[1][3] Beyond enumeration, the Tutte polynomial finds applications in statistical mechanics (as the partition function of the Potts model), network reliability analysis (via R(G; p) = p^{|V|-k(G)} (1-p)^{|E|-|V|+k(G)} T(G; 1, 1/(1-p))), knot theory (linking to the Jones polynomial through ribbon graphs), and computational complexity (where evaluating it is #P-hard in general, though tractable at points like (1,1) or (-1,-1)).[1] Its universality theorem states that any graph invariant satisfying deletion-contraction satisfies a linear relation with the Tutte polynomial, underscoring its role as a complete invariant for such reductions.[3]Definitions and basics
Formal definition
The Tutte polynomial is defined for a graph G = (V, E), where V is the set of vertices and E is the set of edges (allowing for multigraphs, in which multiple edges between the same pair of vertices are permitted). A spanning subgraph of G is obtained by selecting a subset A \subseteq E of edges while retaining all vertices in V, resulting in the graph (V, A). The rank function r: 2^E \to \mathbb{N} assigns to each subset A \subseteq E the value r(A) = |V| - k(A), where k(A) denotes the number of connected components in the graph (V, A); this rank arises from the rank-nullity theorem applied to the cycle matroid of the graph, measuring the size of a maximum spanning forest in (V, A). The formal definition of the Tutte polynomial T(G; x, y) is the bivariate polynomial given by the sum over all spanning subgraphs: T(G; x, y) = \sum_{A \subseteq E} (x-1)^{r(E) - r(A)} (y-1)^{|A| - r(A)}, where r(E) is the rank of the full edge set (equal to |V| - k(G), with k(G) the number of connected components of G). An equivalent rank-based formulation expresses the exponents in terms of corank and nullity: the corank of A is \operatorname{corank}(A) = r(E) - r(A), quantifying the connectivity deficiency relative to the full graph, while the nullity of A is \nu(A) = |A| - r(A), representing the cyclomatic number or excess edges beyond a forest in (V, A). Thus, T(G; x, y) = \sum_{A \subseteq E} (x-1)^{\operatorname{corank}(A)} (y-1)^{\nu(A)}. This form highlights the polynomial's role in encoding connectivity and cycle structure across all edge subsets. This sum formulation is equivalent to W. T. Tutte's original 1947 definition, which counted spanning trees weighted by their internal and external activities—measures of edges that break or preserve cycles and components relative to a fixed ordering of the edges. The equivalence follows by partitioning the sum over subgraphs according to bases (spanning trees) and grouping terms by activity counts, yielding the same generating function.[2] The polynomial is well-defined for multigraphs, as the definition depends only on the edge set without assuming simplicity, and extends naturally to matroids by replacing the graph's rank function with the matroid rank on the ground set E.[4]Equivalent formulations
The Tutte polynomial admits several equivalent formulations that underscore its combinatorial significance and algebraic universality. An equivalent expression is T(G; x, y) = \sum_{A \subseteq E} (x-1)^{r(E) - r(A)} (y-1)^{|A| + k(A) - |V|}, where the sum ranges over all subsets A of the edge set E(G), r(\cdot) denotes the rank function (the size of a maximum spanning forest in the subgraph induced by A), k(A) is the number of connected components in that subgraph, and |V| is the number of vertices in G. This formulation encodes the distribution of edge subsets by their corank r(E) - r(A) and nullity |A| + k(A) - |V| = |A| - r(A). Tutte formulated the dichromatic polynomial \chi(G; x, y) in 1954, defined recursively via deletion and contraction of edges, generalizing both the chromatic and flow polynomials of graphs; this recursive definition coincides with the modern Tutte polynomial up to variable substitution.[5] The Tutte polynomial also possesses a universal property: it is the unique graph invariant (up to scalar multiple) that satisfies the deletion-contraction recurrence T(G; x, y) = T(G - e; x, y) + T(G / e; x, y) for any edge e that is neither a loop nor a bridge, along with the normalization conditions T(\emptyset; x, y) = 1 for the edgeless graph on any number of vertices and T(K_2; x, y) = x for the single-edge graph on two vertices (with adjustments for loops and bridges via multiplication by y or x, respectively). This universality extends a generalization of the matrix-tree theorem, wherein the evaluation T(G; 1, 1) equals the number of spanning trees in G, computable as the determinant of any cofactor of the graph Laplacian matrix L(G); more broadly, the specialization T(G; x, 1) generates the numbers of spanning forests in G by their number of components (specifically, the coefficient of x^{|V| - k} is the number of spanning forests with k components), and these forest counts relate directly to determinants of modified Laplacians such as \det(\lambda I - L(G)), whose characteristic polynomial yields the forest enumeration up to sign and scaling. Equivalence among these formulations—the rank-generating sum, the recursive dichromatic definition, and the universal property—follows from proofs by induction on the number of edges, reducing arbitrary graphs to the base cases of edgeless or single-edge graphs via repeated application of the deletion-contraction relation, which preserves the polynomial under both the sum and recursive perspectives.Examples
The Tutte polynomial provides a concrete way to encode structural properties of graphs via explicit computations on simple examples. For the empty graph K_0 with no vertices or edges, the polynomial evaluates to T(K_0; x, y) = 1, as there are no subsets to sum over in the expansion.[1] Consider the graph consisting of two vertices connected by a single edge, often denoted as the path graph P_2. This is a tree with two vertices, and its Tutte polynomial is T(P_2; x, y) = x. More generally, any tree with n vertices has Tutte polynomial T(G; x, y) = x^{n-1}, reflecting the absence of cycles and the unique spanning tree structure. For the cycle graph C_3, a triangle with three vertices and three edges, the Tutte polynomial is T(C_3; x, y) = x^2 + x + y. This can be computed step-by-step using the subset expansion formula, T(G; x, y) = \sum_{A \subseteq E} (x-1)^{r(G) - r(A)} (y-1)^{|A| - r(A)}, where r denotes the rank function (number of vertices minus the number of connected components in the spanning subgraph induced by A). Here, |V| = 3 and r(G) = 2. The subsets are:- A = \emptyset: r(A) = 0, |A| = 0, contribution (x-1)^2.
- Single-edge subsets (3 choices): r(A) = 1, |A| = 1, each contributes x-1, total $3(x-1).
- Two-edge subsets (3 choices, each forming a path): r(A) = 2, |A| = 2, each contributes $1, total $3.
- A = E (the full cycle): r(A) = 2, |A| = 3, contribution y-1.
Properties
Algebraic properties
The Tutte polynomial T(G; x, y) of a graph G is a polynomial invariant in the variables x and y.[6] The Tutte polynomial is multiplicative with respect to disjoint unions of graphs: for graphs G and H, T(G \sqcup H; x, y) = T(G; x, y) \cdot T(H; x, y).[6] It is also normalized such that for the edgeless graph E_n on n vertices, T(E_n; x, y) = 1.[6] As a graph invariant, T(G; x, y) remains unchanged under graph isomorphisms, preserving its value for structurally equivalent graphs.[6] A defining algebraic feature is its uniqueness: the Tutte polynomial is the unique polynomial in x and y that satisfies the base cases for edgeless graphs (yielding 1), graphs consisting of a single loop (yielding y), and graphs with a bridge (yielding x times the polynomial of the contracted graph), along with the weak deletion-contraction recurrence for ordinary edges (neither loops nor bridges).[6] Specifically, for an ordinary edge e in G, T(G; x, y) = T(G \setminus e; x, y) + T(G / e; x, y), where G \setminus e is G with e deleted and G / e is G with e contracted.[6] This recurrence, combined with the base cases, ensures the polynomial's full invariance under the deletion-contraction operations that characterize graph minors.Recurrence relations
The deletion-contraction recurrence is a cornerstone of the Tutte polynomial, providing a recursive method to compute it by reducing the graph through edge operations. For a multigraph G and an edge e that is neither a loop nor a bridge (termed an ordinary edge), the Tutte polynomial satisfies T(G; x, y) = T(G - e; x, y) + T(G / e; x, y), where G - e denotes the deletion of e (removing it without altering vertices), and G / e denotes the contraction of e (merging its endpoints into a single vertex and removing any self-loops created). This relation was originally established by W. T. Tutte as part of his development of graph invariants via ring structures. The recurrence is supported by specific base cases that handle loops, bridges, and edgeless graphs. If e is a loop, then T(G; x, y) = y \cdot T(G - e; x, y), because contraction of a loop yields a graph isomorphic to the deletion. If e is a bridge (an edge whose deletion increases the number of connected components), then T(G; x, y) = x \cdot T(G / e; x, y), reflecting the contribution to connectivity. For an edgeless graph G (possibly disconnected), the polynomial evaluates to T(G; x, y) = 1, though the recurrence typically normalizes to 1 for the single-vertex case and builds from there. More generally, a graph reducible solely to i bridges and j loops (with no other edges) has T(G; x, y) = x^i y^j. These cases ensure the recurrence terminates.[3] A proof of the deletion-contraction recurrence follows from the subset expansion (also known as the rank-nullity generating function) of the Tutte polynomial, T(G; x, y) = \sum_{A \subseteq E(G)} (x-1)^{r(G) - r(A)} (y-1)^{|A| - r(A)}, where r(\cdot) denotes the rank function (size of a maximum forest in the subgraph induced by the edge set). To verify the recurrence for an ordinary edge e, partition the sum into subsets A not containing e (which match the expansion for G - e) and those containing e (let A' = A \setminus \{e\}). For the latter, since e is ordinary, r(A) = r(A') + 1 and the nullity adjusts by 1 relative to G / e, leading to the contributions aligning with the expansion for G / e. This partitioning confirms the additive relation. The same expansion underpins the base cases, as loops increase nullity without rank, contributing the y factor, while bridges increase rank without nullity, contributing x.[3] The recurrence exhibits multiplicativity in certain structural reductions, particularly for parallel edges and series connections. For a graph consisting of k parallel edges between two vertices (with k \geq 1), repeated application of the recurrence yields T(G; x, y) = x + y + y^2 + \cdots + y^{k-1}, derived inductively: the single-edge case (k=1, a bridge) is x, and adding a parallel edge e gives T_k = T_{k-1} + y^{k-1} since contraction turns the remaining k-1 edges into loops. This formula highlights how parallel multiples introduce powers of y, encoding cycle structures. For series reductions—replacing two collinear edges sharing a degree-2 vertex with a single edge—the Tutte polynomial of the original graph equals that of the reduced graph, preserving the invariant under this operation. Parallel reductions similarly merge multiple edges between the same vertices into one, adjusting via the above formula. These reductions are formalized such that the polynomial satisfies specific arithmetic rules for the compositions.[3] For series-parallel graphs, which are built from a single edge via repeated series and parallel connections (equivalently, graphs with no K_4 minor), the deletion-contraction recurrence combined with these reduction formulas enables explicit, efficient computation of the Tutte polynomial. By systematically applying series and parallel simplifications, the graph reduces to a base case in linear time relative to the number of edges, avoiding the full exponential branching of general deletion-contraction. This structure underlies the polynomial's evaluability for such graphs without needing the full recursive tree.[3]Duality and symmetry
One of the key symmetry properties of the Tutte polynomial concerns its behavior under graph duality. For a connected planar graph G and its plane dual G^*, the Tutte polynomial satisfies the relation T(G; x, y) = T(G^*; y, x). [1][3] This formula highlights the interchangeability of the variables x and y, which corresponds to the primal-dual swap: features encoded by x in the original graph are captured by y in the dual, and vice versa.[3] Combinatorially, this symmetry arises from the interpretations of the variables in terms of the graph's cycle space and cocycle space (also known as the cut space or coboundary space). The variable x primarily accounts for connectivity and internally active edges relative to spanning trees, linking to coboundaries or cutsets that preserve components. In contrast, y relates to cycles and externally active edges, encoding dependencies within the cycle space. Duality interchanges these spaces: cycles in G become cocycles in G^*, and vice versa, thereby swapping the roles of x and y.[3][1] For self-dual planar graphs, where G is isomorphic to its dual G^*, the relation implies T(G; x, y) = T(G; y, x).[1] This symmetry means that when expanded as T(G; x, y) = \sum_{i,j \geq 0} a_{i,j} x^i y^j, the coefficients satisfy a_{i,j} = a_{j,i}, resulting in a palindromic structure.[7][3] The duality relation generalizes beyond graphs to arbitrary matroids. For a matroid M on ground set E with dual matroid M^*, the Tutte polynomial obeys T(M; x, y) = T(M^*; y, x). [1][8] Here, the symmetry reflects the matroid duality between the cycle space of M (spanning sets modulo circuits) and the cocycle space of M^* (spanning sets modulo cocircuits), providing a unified framework for the polynomial's behavior across combinatorial structures.[1][3]History
Discovery by Tutte
The Tutte polynomial originated from the work of William T. Tutte during and after World War II, where his efforts at Bletchley Park in code-breaking influenced his algebraic approach to graph enumeration problems. While his wartime contributions focused on cryptanalysis of the German Lorenz cipher using statistical and algorithmic methods, Tutte's subsequent academic pursuits shifted toward formalizing graph-theoretic structures, motivated by the need to enumerate spanning trees, colorings, and network configurations through linear algebraic tools. This background in applied mathematics during military applications, including the development of early computing aids for code-breaking, underscored the practical importance of systematic graph counting. Tutte first introduced foundational ideas for the polynomial in his 1947 paper "A Ring in Graph Theory," where he established deletion-contraction relations for graphs and formed a ring structure to facilitate enumeration. These relations provided a recursive framework for computing graph invariants, emerging from his PhD thesis work on an algebraic theory of graphs. In this early formulation, Tutte treated graphs as representing binary matroids, defining rank polynomials based on the rank function of the cycle matroid to capture connectivity and spanning substructures. A key advancement came in Tutte's 1954 paper "A Contribution to the Theory of Chromatic Polynomials," which explicitly linked his rank-generating function to graph colorings and formalized the polynomial now known as the Tutte polynomial. Here, he demonstrated how the polynomial evaluates to the chromatic polynomial under specific substitutions, bridging enumeration of proper colorings with broader matroidal properties. This work built directly on his 1948 Cambridge PhD thesis, "An Algebraic Theory of Graphs," which extended the polynomial to binary matroids via rank-nullity considerations, emphasizing its role in generalizing linear dependence in vector spaces over GF(2). Tutte's ideas gained wider formalization in subsequent publications, including his 1965 paper "Menger's Theorem for Matroids," which refined the polynomial's application to matroid connectivity. Overall, these contributions established the Tutte polynomial as a universal invariant for graphs and matroids, rooted in Tutte's wartime-inspired drive for algebraic efficiency in combinatorial analysis.Subsequent developments
In the 1970s, the Tutte polynomial gained recognition as a universal invariant among graph polynomials that satisfy deletion-contraction recurrences, a property formalized by Brylawski who demonstrated that it serves as the free object in the category of such invariants. This universality underscored its role in encoding a wide array of graph properties, influencing subsequent theoretical advancements. Brylawski also conjectured that the Tutte polynomial of a connected matroid is irreducible over the integers, a claim verified by Merino, de Mier, and Noy in 2001 using structural characterizations. During the 1980s, connections emerged between the Tutte polynomial and knot theory, particularly through the Jones polynomial introduced by Jones in 1985. Thistlethwaite's 1987 theorem established that the Jones polynomial of an alternating link can be computed from the Tutte polynomial of its associated graph, bridging graph theory with topological invariants. The Tutte polynomial's generalization to matroids built on precursors from Whitney's 1935 introduction of matroids as abstractions of linear independence and graph cycles. This extension, formalized by Crapo in 1969 and inherent in Tutte's earlier work, allowed the polynomial to apply beyond graphs to broader combinatorial structures, including oriented matroids. Tutte himself formalized the modern two-variable form in his 1967 paper "On dichromatic polynomials." The 1990s saw increased focus on computational aspects, driven by complexity results showing that evaluating the Tutte polynomial is #P-hard for most points in the complex plane, as proven by Jaeger, Vertigan, and Welsh in 1990. Recent developments up to 2025 have expanded the Tutte polynomial to quantum contexts, including applications to topological data analysis leveraging matroid generalizations for persistent homology computations. Additionally, connections to quantum graphs appear in 2024 work linking Dirac traces in quantum field theory to Tutte evaluations.[9]Specializations
Chromatic polynomial
The chromatic polynomial of a graph G, denoted P(G; \lambda), counts the number of proper vertex colorings of G using \lambda colors, where adjacent vertices receive distinct colors. Its coefficients provide information about the number of ways to partition the vertices into independent sets of specified sizes. This polynomial satisfies a deletion-contraction recurrence: for any edge e, P(G; \lambda) = P(G \setminus e; \lambda) - P(G / e; \lambda), mirroring the structure of the Tutte polynomial's defining relation.[10] The chromatic polynomial arises as a specialization of the Tutte polynomial T(G; x, y). Specifically, P(G; \lambda) = (-1)^{|V(G)| - k(G)} \lambda^{k(G)} T(G; 1 - \lambda, 0), where k(G) is the number of connected components of G. This evaluation at (1 - \lambda, 0) yields the number of proper \lambda-colorings directly, with the sign and power adjustments accounting for the graph's connectivity and vertex structure. The relation unifies the combinatorial interpretations of subgraphs in the Tutte polynomial with coloring constraints.[1] Hassler Whitney introduced the chromatic polynomial in 1932 as a tool for studying graph colorings, establishing its basic properties and recurrence.[11] W. T. Tutte extended this in the 1950s by developing the dichromatic polynomial—now known as the Tutte polynomial—as a bivariate generalization that encompasses both chromatic and flow polynomials, providing a unified framework for these invariants.[10] For the complete graph K_n, the chromatic polynomial is the falling factorial P(K_n; \lambda) = \lambda (\lambda - 1) \cdots (\lambda - n + 1), which counts the permutations of \lambda colors assigned to n vertices with no repetitions. This follows from evaluating the Tutte polynomial of K_n at (1 - \lambda, 0) and applying the specialization formula, confirming the exact number of proper colorings as \lambda! when \lambda \geq n.[1]Flow polynomial
The flow polynomial of a graph G is a univariate specialization of the Tutte polynomial that enumerates nowhere-zero flows on the edges of G. It is defined by the relation F(G; \lambda) = (-1)^{|E| - |V| + k(G)} T(G; 0, 1-\lambda), where |E| is the number of edges in G, |V| is the number of vertices, k(G) is the number of connected components of G, and T(G; x, y) is the Tutte polynomial of G.[1] This polynomial provides a count of the number of nowhere-zero \lambda-flows over the integers on G, where a nowhere-zero \lambda-flow is an assignment of integer values to the edges satisfying the Kirchhoff current law at each vertex (with values bounded appropriately by \lambda) and non-zero on every edge. By a theorem of Tutte, this count coincides with the number of nowhere-zero flows modulo \lambda, i.e., using the cyclic group \mathbb{Z}_\lambda.[1] For cubic graphs (3-regular graphs), the flow polynomial evaluates the cyclomatic number \beta(G) = |E| - |V| + k(G) as its degree, reflecting the dimension of the cycle space over which flows are defined; this degree determines the leading term \lambda^{\beta(G)} and provides key structural insight into the graph's cyclic complexity.[1] The evaluation of the Tutte polynomial along the line x = 0 is dual to the chromatic polynomial via the relation T(G; 0, y) = (-1)^{|E| - |V| + k(G)} F(G; 1 - y), which underscores the symmetry between flow and coloring interpretations in the broader framework of the Tutte polynomial, particularly for planar graphs where flows on G correspond to colorings on the dual.[1]Reliability polynomial
The reliability polynomial of an undirected graph G = (V, E) with |V| = n vertices and |E| = m edges, denoted R(G; p), is defined as the sum \sum p^{|A|} (1-p)^{m - |A|} over all subsets A \subseteq E such that the spanning subgraph (V, A) is connected.[12] This polynomial represents the probability that G remains connected when each edge fails independently with probability $1-p (or, equivalently, is present with probability p \in [0,1]).[1] For a connected graph, the reliability polynomial can be expressed in terms of the Tutte polynomial T(G; x, y) as R(G; p) = p^{n-1} (1-p)^{m - n + 1} T\left(G; 1, \frac{1}{1-p}\right). [12][1] This relation allows the reliability polynomial to inherit properties and computational techniques from the Tutte polynomial, such as its evaluation along the line x=1.[1] Computing R(G; p) is feasible in polynomial time for series-parallel graphs using reliability-preserving reductions or direct evaluation of the Tutte polynomial, which admits linear-time algorithms in such cases.[13] However, for general graphs, determining the reliability polynomial (or even evaluating it at a fixed p) is #P-complete, reflecting the inherent difficulty of enumerating connected spanning subgraphs.[14] The reliability polynomial originated in the 1950s as a probabilistic model for network functionality and gained prominence in the 1970s through applications in operations research, particularly for assessing connectivity in communication and transportation networks under edge failures.[15]Evaluations at specific points
The Tutte polynomial T(G; x, y) of a graph G yields a variety of combinatorial invariants when evaluated at specific points, particularly integer coordinates. These evaluations often correspond to counts of subgraphs, orientations, or other structural features, providing insights into the graph's connectivity, acyclicity, and spanning properties. Such interpretations stem from the polynomial's rank-nullity expansion and have been extensively studied since the 1970s, with key results appearing in seminal works on graph theory and matroids.[1] For connected graphs, the evaluation at (1,1) counts the number of spanning trees, linking directly to Kirchhoff's matrix-tree theorem. At (2,1), it enumerates all forests (acyclic subgraphs), while (1,2) tallies connected spanning subgraphs. Points on the axes, such as (2,0) and (0,2), relate to orientations: the former to acyclic ones and the latter to totally cyclic (Eulerian) orientations. These counts generalize to matroids and have applications in network reliability and statistical mechanics.[1][16] Further evaluations at points like (2,2) simply yield $2^{|E(G)|}, the total number of subgraphs. For planar graphs, T(G; 3, 3) admits interpretations in terms of claw coverings (spanning subgraphs without K_{1,3} components) or, in grid graphs, T-tetromino tilings. At (0, -2), for 4-regular graphs, it counts ice configurations, which are perfect matchings of the hexagonal lattice dual with specific dimer placements. These specialized counts highlight the polynomial's versatility, though interpretations grow more context-dependent away from the principal axes.[3][17][18]| Evaluation point | Combinatorial interpretation | Reference |
|---|---|---|
| (1,1) | Number of spanning trees (for connected G) | [1] |
| (2,1) | Number of forests (acyclic subgraphs) | [1] |
| (1,2) | Number of connected spanning subgraphs (for connected G) | [1] |
| (2,0) | Number of acyclic orientations | [16] |
| (0,2) | Number of totally cyclic orientations (for connected G) | [16] |
| (2,2) | $ 2^{ | E(G) |
| (3,3) | Number of claw coverings (for planar G) | [17] |
| (0,-2) | Number of ice configurations (for 4-regular G) | [18] |