The Penrose Polynomial of a Plane Graph

Martin Aigner

1. Introduction

Let G(V, E) be a connected plane graph with vertex–set V, edge-set E, set of regions R, and let G^{∗}(R, E) be its dual graph. The 4–Color Theorem (4–CT for short) states that the regions of G can always be colored with 4 colors such that adjacent regions receive different colors [3,16]. It is well–known that it suffices to verify the 4–CT for connected 3–regular bridgeless plane graphs, and that in this case the number of 3–edge colorings equals the number of 4–region colorings with the outer region colored 0 (see e.g. [2]). Thus the number of 3–edge colorings is an important parameter to study. In [15] Penrose derived a number of remarkable expressions for this parameter, defining implicitly what is now called the Penrose polynomial P (G, λ) in the variable λ. Among other things he showed for a 3–regular connected plane graph:

(1) number of 3–edge colorings = \{ \begin{matrix}P (G, 3) \\ (−\frac{1}{4})^{\frac{|V |}{2}} P (G, −2) . \end{matrix}

Subsequently it was observed by several authors that P (G, λ) may be expressed as a so– called “transition polynomial” of the associated medial graph (see e.g. [10,13]), and that there is a strong relationship between P (G, λ) and the two–variable Tutte polynomial t(G, x, y) [7]. The medial graph (to be defined in the next section) is a 4–regular plane graph and can thus be viewed as the plane diagram of a knot or link in ℝ^{3} (see [10,11,22]).

It is the purpose of this paper to study the Penrose polynomial of an arbitrary connected plane graph and, in particular, to generalize the Penrose formulae to this case. In section 2, we give the definition of P (G, λ) and present an expression via cycles and cocycles of the graph G. In section 3 we look at some interesting coefficients of P (G, λ). Section 4 is devoted to the evaluation of P (G, λ) at integral λ, and section 5 deals with yet another formula of Penrose involving the rotation signs around the vertices (see [2]).

The graphs considered in this paper are finite and may have loops and multiple edges. We use the standard notation of graph theory. For all terms not defined see e.g. [1,4,14,22].

2. Definition of P (G, λ)

We will always deal with connected plane graphs G(V, E) with |V | ≥ 2. The set of regions is denoted by R, and R_{0} is the outer region. Let e ∈ E. If we choose a direction on e, then the edges f, g bounding the same regions as e and incident with e are called the right and left neighboring edges of e. It will be convenient to picture each edge e as subdivided into two half–edges e′, e′′, one incident to each end–vertex of e. In particular, if e is a loop at the vertex v, then both half–edges are incident to v. See [8] where this approach is taken. A direction of the edge e is thus obtained by choosing one half–edge as initial, the other as terminal half–edge. Every half–edge e′ has one right neighboring half–edge f′ and one left neighboring half–edge g′ (which may be equal and equal to e′). We denote this by e′Rf′, e′Lg′ (read from left to right). We apparently have e′Rf′ ⟺ f′Le′ (see figure 1)

[figure: j′; e′; h′; e′′; e; g′; f′; Figure 1; e′′Rf′, e′′Lj′; e′Rh′, e′Lg′]

Let A ⊆ E be a set of edges. We traverse G in the following way, regarding the edges of A as “changing” edges and those of E \ A as “non–changing” edges. We choose a starting half–edge e′ and an initial sense R (right) or L (left), suppose e′R. Then our sequence continues with the right neighboring half–edge of e′, say f′, followed by the other half f′′ of the edge f. If f ∈ A, then we change R to L, otherwise we keep R. Our sequence is now e′Rf′f′′L or e′Rf′f′′R. Next we choose the left (or right) neighboring half–edge of f′′, say g′, followed by the other half g′′ of the edge g, and change or keep the sense according to g ∈ A or g ∉ A. Continuing in this way, we eventually obtain a closed sequence of half–edges and senses, say e′Rf′f′′L… Rh′h′′Le′′. Since the closed sequence is uniquely determined by the initial choice of a half–edge and a sense, it follows that any half–edge in the sequence before a sign together with this sign yield the same sequence. The set of edges e, f, g,… corresponding to the sequence is called a closed path P_{1}. Note that the sequence e′Rf′f′′Lg′g′′… induces an orientation on the edges by regarding the half–edge following a sign as initial half–edge and the other as terminal. It follows from e′Rf′ ⟺ f′Le′ that we obtain the same closed path P_{1} (traversed in the opposite direction) by reversing the sequence of half–edges and interchanging the signs. Hence we identify these two sequences. If there are half–edges which have not been used twice, we start with such a half–edge and a sense which has not been used and construct a new closed path P_{2}. We continue in this way until every half–edge has been used twice. Let c(A) be the number of closed paths obtained in this way.

Definition. P (G, λ) := ∑_{A⊆E}(−1)^{|A|}λ^{c(A)} is the Penrose polynomial of G.

Remark. Since any half–edge has two neighboring half–edges it follows that every edge is traversed altogether twice (possibly in the same closed path).

Example. The edges of A are drawn in bold lines.

Figure 2

Let us compute the Penrose polynomial for the loop and the bridge.

[figure: e′; e′′; e′; e′′]

Figure 3

Consider the loop. If A = ∅, then we obtain the closed sequences e′Le′′, e′Re′′ and for A = {e} we obtain the single sequence e′Le′′e′Re′′, hence P ( [figure], λ) = λ(λ − 1). For the bridge we obtain for A = ∅ the closed sequence e′Le′e′′Le′′ and for A = {e} the sequence e′Le′e′′Re′′, thus P ( [figure], λ) = 0.

We obtain an equivalent definition of P (G, λ) by considering the medial graph G′(E, K) (see [14]). We place points in the interior of the edges of G (with the half–edges on each side), these are the vertices of G′. The edges correspond to all pairs of neighboring half– edges, where we draw the connecting edge along the boundary inside the common region (figure 4).

Example.

Figure 4

G′ is a 4-regular plane graph with two types of regions: the “black” regions v′ corresponding to the vertices v of G, and the “white” regions corresponding to the original regions of G (see fig.4). The black and white regions form a 2–coloring of the regions of G′. Two black regions have k vertices in common iff the corresponding vertices are joined by k edges in G, similarly for the white regions. Thus G′ determines G uniquely. A closed path P_{i} in the set–up of P (G, λ) now corresponds to a directed cycle in G′, where e ∈ A means that we cross at the vertex e in G′, and e ∉ A means that we continue along the white region. Thus we never go around a black region. We will return to the medial graph in the next section.

The following theorem is inspired by the theory of left–right paths as developed in [17,18,19]. Let 2^{E} be the vector space over GF (2) of all subsets of E with addition A + B being the symmetric difference. Let Z(G) and K(G) be the cycle space resp. cocycle space of G. We have

dim K(G) = |V | − 1 , dim Z(G) = |E| − |V | + 1 = |R| − 1 (2)

(by Euler’s formula), and Z(G) = K(G)^{⊥}.

With the usual identification of the edges of the graph G and its dual G^{∗}, we note

K(G^{∗}) = Z(G) , Z(G^{∗}) = K(G) (3)

(G ∖ A)^{∗} = G^{∗}/A , (G/A)^{∗} = G^{∗} ∖ A . (4)

The following Lemma is immediately verified by considering the cases e ∈ A and e ∉ A (see [19]).

Lemma 1. Let P_{1},…, P_{c(A)} be the closed paths of G with respect to A ⊆ E.

a) Let e ∈ P_{1} ∩ P_{2}, \overline{P}_{1} = P_{1} ∖ e, \overline{P}_{2} = P_{2} ∖ e. Then \overline{P}_{1} ∪ \overline{P}_{2}, P_{3},…, P_{c(A)} are the closed paths of G ∖ e with respect to A ∖ e.

b) Suppose c(A) = 1. If e is traversed twice in the same direction, then c(A ∖ e) = 1 in G ∖ e. If e is traversed in opposite directions, then c(A ∖ e) = 1 in G/e.

Lemma 2. Let A ⊆ E, e ∈ E, and suppose e is traversed twice in the same closed path P of G with respect to A.

a) If G is Eulerian, then e is traversed twice in the same direction.

b) If A ∈ K(G), then e is traversed in opposite directions.

Proof. a) If G is Eulerian, then the regions of G can be admissibly colored red and blue. Traversing P we can thus assume that the red regions are always on the left–hand side, whence e must be traversed in the same direction.

b) Let P = (e, R_{1}, e, R_{2}). Assume on the contrary that e is traversed twice in the same direction. Let S_{1} ⊆ R_{1} be the set of edges which are traversed only once in R_{1}, then e ∪ S_{1} ∈ Z(G). It follows that |(e ∪ S_{1}) ∩ A| ≡ 0 (mod 2) and hence |(e ∪ R_{1}) ∩ A| ≡ 0 (mod 2). The left–right sense changes therefore an even number of times in (e, R_{1}, e). Let R_{1} = e_{1},…, e_{s}, and assume wlog eLe_{1}. If e ∈ A, then e_{s}Re, and if e ∉ A then e_{s}Le. It follows that e is traversed in opposite directions, since otherwise the closed path (e, R_{1}) would result.

Let A ⊆ E, and P_{1},…, P_{c(A)} the closed paths. Let Q_{i} be the set of edges in P_{i} which are traversed once in P_{i}. Clearly Q_{i} ∈ Z(G) for all i. We set

B_{A}(G) = {C ∈ Z(G) : C ∩ A ∈ K(G)} . (5)

B_{A}(G) is clearly a subspace of Z(G). The following proposition generalizes the corresponding results in [17,18,19] about bicycle spaces, and can be proved in the same way. The main idea of this approach appears also in [9]. For completeness, we sketch the proof.

Proposition 1. Let G(V, E) be a connected plane graph, A ⊆ E. Let P_{1},…, P_{c(A)} be the closed paths, and Q_{1},…, Q_{c(A)} as defined above. Then any c(A) − 1 of the Q_{i}’s are linearly independent and span the subspace B_{A}(G). In particular,

dim B_{A}(G) = c(A) − 1 , |B_{A}(G)| = 2^{c(A)−1} . (6)

Proof. Let L be the boundary set of a region. The definition of the closed paths P_{i}

implies |(Q_{i} ∩ A) ∩ L| ≡ 0 (mod 2), and hence Q_{i} ∈ B_{A}(G) for all i. Clearly, ∑_{i=1}^{c(A)} Q_{i} = ∅.

Suppose, conversely, ∑_{i∈I} Q_{i} = ∅. If I ⫋ {1,…, c(A)} then by the connectivity of the graph

there must be a pair of neighboring edges e, f, e ≠ f, with e ∈ P_{r}, f ∈ P_{s} and r ∈ I, s ∉ I. But this means that e, f are in a common path P_{k}, whence k ∈ I and therefore s ∈ I by the assumption ∑_{i∈I} Q_{i} = ∅, contradiction. Hence any c(A)−1 sets Q_{i} are linearly

independent.

It remains to show that every C ∈ B_{A}(G) is a sum of Q_{i}’s. For |E| = 1, G is a bridge or a loop, and the assertion can be checked directly. Now we proceed by induction on |E|.

Case (i). c(A) ≥ 2. Let e ∈ Q_{1} ∩ Q_{2} and C ∈ B_{A}(G), C ≠ ∅. If e ∉ C, then C ∈ B_{A∖e} (G ∖ e), and we conclude C ∈ ⟨Q_{3},…, Q_{c(A)}⟩ by induction and Lemma 1 a). If e ∈ C, then C + Q_{2} ∈ B_{A}(G), e ∉ C + Q_{2}, and we obtain C ∈ ⟨Q_{2},…, Q_{c(A)}⟩.

Case (ii). c(A) = 1. We have to show B_{A}(G) = {∅}. Suppose, on the contrary, ∅ ≠ C ∈ B_{A}(G). If e ∉ C, then C ∈ B_{A∖e}(G ∖ e) ∩ B_{A∖e}(G/e), and we infer C = ∅ by Lemma 1 b) and induction. Hence we may assume C = E, i.e. G is Eulerian, and A = C ∩ A ∈ K(G). By Lemma 2, this gives a contradiction.

As easy corollaries we have the following two results.

Corollary 1. Let G_{1},…, G_{t} be the blocks of G, then

P (G, λ) = \frac{1}{λ^{t−1}} ∏_{i=1}^{t} P (G_{i}, λ) .

Corollary 2. Suppose G has two regions with two common boundary edges e and f. Then

P (G, λ) = 2 P (G/e, λ) .

In studying the behavior of P (G, λ) we may thus asume that G is plane, 2–connected, with any two regions having at most one common boundary edge. Let us call such graphs normal. The degree d(v) of any vertex v is then at least 3, and G has no loops or bridges.

Corollary 3. Let G be a normal graph. Then P (G, λ) is a polynomial of degree r = |R| with leading coefficient 1.

Proof. Since B_{A}(G) is a subspace of Z(G), we have c(A) ≤ r for all A by (2), and clearly c(∅) = r. Suppose A ≠ ∅ and c(A) = r. Then B_{A}(G) = Z(G), i.e. every region boundary C is in B_{A}(G). Let e ∈ A, and C, C′ the two region boundaries containing e. Since C ∩ A ∈ K(G), we have |(C ∩ A) ∩ C′| ≡ 0 (mod 2), but (C ∩ A) ∩ C′ = {e} as G is normal, contradiction.

Corollary 4. Let G be an arbitrary connected plane graph. Then P (G, λ) = 0 if and only if G contains a bridge.

3. The coefficients of P (G, λ)

Let G(V, E) be a normal graph with r ≥ 3 regions, and let us set P (G, λ) = ∑_{i=1}^{r} a_{i}λ^{i}. We

know a_{r} = 1. Let k_{4}^{∗} be the number of complete graphs K_{4} appearing as subgraphs of the dual graph G^{∗}.

Proposition 2. Let G(V, E) be a normal graph with r = |R| ≥ 3 regions. Then

a_{r−1} = −|E| + k_{4}^{∗} < 0 . (7)

Proof. Suppose c(A) = r − 1 and hence dim B_{A}(G) = r − 2. Let C_{1},…, C_{r} be the boundaries of the regions. If C_{i} ∩ A ≠ ∅, then C_{i} ∉ B_{A}(G) by the same argument as in the proof of Corollary 3. Hence we infer

∑_{k∈J} C_{k} ∩ A ∉ K(G) ⟺ (C_{i} + ∑_{k∈J} C_{k}) ∩ A ∈ K(G) (8)

for any subset J ⊆ {1,…, r} ∖ {i}, since B_{A}(G) contains exactly half of all the cycles.

Claim. Suppose C_{i} ∩ A ≠ ∅, C_{j} ∩ A ≠ ∅, i ≠ j, then C_{i} ∩ C_{j} ≠ ∅, C_{i} ∩ C_{j} = e ∈ A.

Assume on the contrary, C_{i} ∩ C_{j} = ∅ and let C_{i} ∩ C_{k} = f ∈ A for some k ≠ i, j, then (C_{k} + C_{j}) ∩ A ∈ K(G) by (8). But now

C_{i} ∩ ((C_{k} + C_{j}) ∩ A) = (C_{i} ∩ C_{k} + C_{i} ∩ C_{j}) ∩ A = f ,

in contradiction to |C_{i} ∩ ((C_{k} + C_{j}) ∩ A)| ≡ 0 (mod 2). If C_{i} ∩ C_{j} = e ∉ A and C_{i} ∩ C_{k} = f ∈ A, then we obtain the same contradiction.

We infer from the claim that the subgraph G^{∗}(A) of G^{∗} spanned by A is complete, and hence K_{2}, K_{3} or K_{4}, as G^{∗} is plane. If G^{∗}(A) = K_{2}, i.e. |A| = 1, then clearly c(A) = r −1, and we obtain the contribution −|E| to a_{r−1}. In the other two cases it is readily checked that c(A) = r − 2 for G^{∗}(A) = K_{3} and c(A) = r − 1 for G^{∗}(A) = K_{4}, whence we obtain the additional contribution k_{4}^{∗}.

The following result gives a characterization of Eulerian graphs in terms of the Penrose polynomial. First we state an easy Lemma.

Lemma 3. Let A ⊆ E be given. If G^{∗}(R, A) has k components, then c(A) ≥ k. In case that G^{∗}(R, A) is a forest, then c(A) = k. In particular, there exists a set A ⊆ E with c(A) = k for every k, 1 ≤ k ≤ |R|.

Proof. Let G_{1}^{∗},…, G_{k}^{∗} be the components of G^{∗}(R, A), and C_{i} the set of edges of G^{∗}(R, E) joining G_{i}^{∗} to the rest. Then C_{i} ∈ K(G^{∗}) = Z(G), C_{i} ∩ A = ∅ ∈ K(G), hence C_{i} ∈ B_{A}(G). Since any k − 1 of the C_{i}’s are linearly independent we conclude c(A) ≥ k from Proposition 1. The second assertion follows readily by induction on |A|.

Proposition 3. The plane connected graph G(V, E) is Eulerian if and only if

|A| + c(A) ≡ r (mod 2) for all A ⊆ E .

Proof. Suppose G is not Eulerian, then one of the blocks H of G is not Eulerian. Consider v ∈ V (H) with odd degree in H, and let A be the set of incident edges to v (in H) which are not loops. It is readily seen that c(A) = r − |A| + 1, and thus |A| + c(A) = r + 1.

Suppose G is Eulerian, and let G′(E, K) be its medial graph. We speak of the black and white regions of G′ as in the last section. Since G^{∗} is bipartite, the white regions can be partitioned into two classes X and Y such that no two regions in the same class have a vertex in common. Suppose the outer region is in Y. We orient the edges around the white regions in X and the outer region in clockwise sense, and the inner white regions in Y counterclockwise. In this way, the edges around the black regions receive alternate orientations (see fig. 5):

Figure 5

The closed paths P_{i} of G correspond therefore to oriented circuits in G′. Now we use induction on |A|. For |A| = ∅ the assertion is trivial. For e ∈ A it is immediately checked that c(A ∖ e) = c(A) + 1 or c(A ∖ e) = c(A) − 1, and the result follows.

Using this proposition and the last assertion of Lemma 3 we obtain the following result.

Corollary 5. Let G be an Eulerian connected plane graph, P (G, λ) = ∑_{i=1}^{r} a_{i}λ^{i}. Then the

coefficients a_{i} are all non–zero with alternating sign, and we have

(−1)^{r}P (G, −1) = 2^{|E|} .

If G is not Eulerian, then |P (G, −1)| < 2^{|E|}.

We shall see in the next section that the chromatic polynomial χ(G^{∗}, λ) of the dual graph is closely related to P (G, λ). It is well–known that the chromatic polynomial of any connected graph on at least two vertices has non–zero coefficients with alternating sign. However, for the Penrose polynomial this seems to be a stronger property, since it implies (even in the weak sense of Problem 2 below) the 4–CT as will follow from the results of the next section (see Corollary 11). Still, all examples checked (all graphs with up to 10 vertices and some random large graphs up to 20 vertices) have indeed these properties, so let us pose the following problems.

Problem 1. Are all coefficients a_{i} (1 ≤ i ≤ r) different from 0 for any plane connected graph G? Is a_{1} ≠ 0 for all G, and more precisely (−1)^{r−1}a_{1} > 0 ?

Problem 2. Do the coefficients a_{i} have alternating sign, at least in the weak sense a_{r} ≥ 0, a_{r−1} ≤ 0, a_{r−2} ≥ 0, … ? Is P (G, −1) ≠ 0, and more precisely (−1)^{r}P (G, −1) > 0 ?

4. Evaluation of P (G, λ) at integral λ

Let us evaluate P (G, k) for k ∈ ℕ. Clearly P (G, 0) = P (G, 1) = 0. The following result is known (see e.g. [10] and related results in [5, 12, 13]).

Definition. Let G′(E, K) be the medial graph of G. A k–valuation of G′ is a mapping f : K → {1, 2,…, k} such that at every e ∈ E any number i appears an even number of times, that is, the degree of e in the subgraph spanned by f^{−1}(i) is even.

Thus at every e ∈ E a number appears four times, or two numbers appear twice. Let f be a k–valuation. We classify the types (f, e) as follows (fig. 6):

Figure 6

A k–valuation f is called admissible, if (f, e) is white or crossing for all e ∈ E.

Proposition 4. P (G, k) equals the number of admissible k–valuations of the medial graph G′.

Corollary 6. We have χ(G^{∗}, k) ≤ P (G, k) (k ∈ ℕ).

Proof. Let f be a k–coloring of the regions of G. We obtain an admissible k–valuation of G′ by assigning f(L) to all boundary edges of the region L, for all white regions L of G′.

Corollary 7. We have

P (G, 2) = \{ \begin{matrix}2^{|V |} & If G is Eulerian \\ 0 & otherwise. \end{matrix}

Proof. If G is not Eulerian, then there exists a black region in G′ with an odd number of boundary edges. An admissible 2–valuation is therefore not possible. If G is Eulerian, then all black regions have an even number of boundary edges, and we may assign the numbers 1 and 2 alternately in two ways, for all black regions.

Corollary 8 (Penrose). Let G be a 3–regular connected plane graph. Then P (G, 3) equals the number of 3–edge colorings.

Proof. We regard 1, 2, 3 as the non–zero elements of the Klein four–group. Let f : E → \{1, 2, 3\} be a 3–edge coloring. Then \overline{f} : K → \{1, 2, 3\}, \overline{f}(k) = f(e)+f(e′) for k = ee′ ∈ K, is an admissible 3–valuation of G′. Since the map f ↦ \overline{f} is clearly bijective, the result follows.

We remarked in the introduction that in a 3–regular plane graph the number of 3–edge colorings equals the number of 4–region colorings f with f(R_{0}) = 0, where R_{0} is the outer region. Thus we have two expressions for P (G, 3). We now want to generalize both these counting results to arbitrary connected plane graphs. Let G(V, E) be a normal graph with set of regions R. We call f : V ∪ R → {0, 1, 2, 3} a special 4–coloring if f restricted to R is a 4–coloring with f(R_{0}) = 0, and if, in addition, incident vertices and regions receive different colors (adjacent vertices may, however, be colored alike). Note that for 3–regular graphs G the restriction of f to R already determines the coloring of V. Hence, in this case, the number of special 4–colorings is just P (G, 3).

Let Ĝ(P̂, Ê) be the 3–regular graph which arises from G by making the replacement as in fig.7 for all v ∈ V, and let R̂ be the set of regions of Ĝ.

Figure 7

We have |P̂| = ∑_{v∈V} d(v) = 2|E|, |Ê| = 3|E|, |R̂| = |V | + |R|.

Proposition 5. Let G be a normal graph, then P (G, 3) = number of special 4–colorings of G = P (Ĝ, 3).

Proof. The special 4–colorings of G are clearly in one–to–one correspondence with the 4–region colorings f of Ĝ with f(R_{0}) = 0, which proves the second equality. To prove the first equality we show that the number of admissible 3–valuations of the medial graph G′(E, K) equals the number of special 4–colorings of G. Let f be a special 4–coloring. We regard f as a coloring of the regions of G′, and construct \overline{f} : K → \{1, 2, 3\} by setting \overline{f}(k) = f(L) + f(L′) if k is the common boundary of L and L′ (see fig.8).

Figure 8

Since f is a special 4–coloring, we have a ≠ b, a ≠ c, b ≠ c, b ≠ d, c ≠ d. If a = d, then a + b = b + d ≠ a + c = c + d (white type), and if a ≠ d, then all 4 elements a, b, c, d are distinct whence a + b = c + d ≠ a + c = b + d (crossing type). Hence \overline{f} is an admissible 3–valuation of G′. Let, conversely, \overline{f} be an admissible 3–valuation of G′. Since numbers appear in pairs at the four edges incident with e, we have ∑_{e∈y} \overline{f}(y) = 0 (e ∈ E) where we

count \overline{f}(y) twice if y is a loop. For the dual graph H of G′ this means ∑_{y∈C} \overline{f}(y) = 0 for

all region boundaries C of H. Since any circuit in H is the sum of the boundaries of its interior regions, we infer

(9)  ∑_{y∈D} \overline{f}(y) = 0 for all circuits D of H.

Now we define f : V ∪ R → {0, 1, 2, 3} as follows. First we set f(R_{0}) = 0. Let L be an arbitrary region of G′, and P a path from R_{0} to L in H. Then we set

f(L) = ∑_{y∈P} \overline{f}(y) .

By (9), this is well–defined, and it is immediately verified that f is a special 4–coloring of G by identifying the black regions with V and the white regions with R. Since the map f ↦ \overline{f} is clearly bijective, the result follows. (See [14, ch. 7] where this method is used.)

Let us now generalize the notion of 3–edge coloring to arbitrary plane graphs G(V, E). Suppose f : E → {1, 2, 3} is any mapping. To v ∈ V we associate the cyclic sequence A(v) of colors around v in the clockwise sense. A(v) = a_{1}^{k_{1}} … a_{t}^{k_{t}} (read cyclically) means that k_{1} successive edges have color a_{1}, then k_{2} edges color a_{2}, and so on. Thus a_{1} ≠ a_{2} ≠ … ≠ a_{t} ≠ a_{1}, ∑_{i=1}^{t} k_{i} = d(v). We call A = a_{1}^{k_{1}} … a_{t}^{k_{t}} correct if the following conditions

hold:

If t = 1, then k_{1} ≡ 0 (mod 2)

If t ≥ 2, then for all i

(10) k_{i} ≡ \{ \begin{matrix}1 (mod 2) & & a_{i−1} ≠ a_{i+1} \\ & implies \\ 0 (mod 2) & & a_{i−1} = a_{i+1} . \end{matrix}

Definition. Let G(V, E) be a connected plane graph, then a mapping f : E → {1, 2, 3} is called a correct 3–edge coloring if A(v) is correct for all v ∈ V.

The following result is easily seen by induction on t.

Lemma 4. Let G(V, E) be a normal graph, and Ĝ its associated 3–regular graph. A mapping f : E → {1, 2, 3} can be extended to a 3–edge coloring of Ĝ (in the usual sense) if and only if f is a correct 3–edge coloring of G.

Proposition 6. Let G(V, E) be a normal graph. For a correct 3–edge coloring f of G we define s(f) = 2^{h} if f is constant on exactly h stars S(v). Then

P (G, 3) = ∑_{f} s(f) over all correct 3–edge colorings f.

Proof. If f is not constant on S(v), then f extends uniquely to the edges around the region v̂ (see fig. 7). On the other hand, if f is constant on S(v), then d(v) ≡ 0 (mod 2), and we can extend f in exactly two ways.

Now we turn to the value P (G, 4).

Proposition 7. Let G(V, E) be a connected plane graph. Then P (G, 4) > 0 if and only if G is 4–region colorable.

Proof. If R is 4–colorable, then we have P (G, 4) > 0 by Corollary 6. Suppose, conversely, P (G, 4) > 0. By Proposition 1 and (6)

P (G, 4) = ∑_{A⊆E}(−1)^{|A|}4^{c(A)} = 4 ∑_{A⊆E}(−1)^{|A|}(2^{dim B_{A}(G)})^{2}
= 4 ∑_{A⊆E}(−1)^{|A|}|B_{A}(G)|^{2} = 4 ∑_{A⊆E}(−1)^{|A|} ∑_{{C,C′∈Z(G) \atop C∩A,C′∩A∈K(G)}} 1
= 4 ∑_{C,C′∈Z(G)} ∑_{A∈K_{C,C′}(G)}(−1)^{|A|} ,

where K_{C,C′}(G) = {A : A ∩ C, A ∩ C′ ∈ K(G)}. K_{C,C′}(G) is a subspace. If K_{C,C′}(G) contains A_{0} with |A_{0}| ≡ 1 (mod 2), then K_{C,C′}(G) contains an equal number of odd– and even–sized subsets, whence ∑_{A∈K_{C,C′}(G)}(−1)^{|A|} = 0. Let us write (C, C′) ∈ Z̃(G) if

|A| ≡ 0 (mod 2) for all A ∈ K_{C,C′}(G). Since P (G, 4) > 0, there must exist a pair (C, C′) ∈ Z̃(G). Suppose C ∪ C′ ≠ E, e ∈ E ∖ (C ∪ C′), and set A = {e}. Then A ∩ C = A ∩ C′ = ∅ ∈ K(G), i.e. A ∈ K_{C,C′}(G), contradiction. Hence E is the union of two Eulerian subgraphs, and this implies the 4–region colorability of G by a well–known result (see e.g. [1]).

Corollary 9. The following statements are equivalent:

a) the 4–color theorem,

b) P (G, 3) > 0 for all connected bridgeless plane graphs,

c) P (G, 4) > 0 for all connected bridgeless plane graphs.

The most interesting formula derived by Penrose in [15] concerns the evaluation of P (G, λ) at λ = −2 for 3–regular graphs. The generalization to arbitrary plane graphs was given in [7,10]. We include a short discussion of these results. Consider the medial graph G′(E, K). At every e ∈ E these are three possible “transitions” as in fig. 9:

Figure 9

If we assign a transition τ(e) to every e ∈ E, then we call τ = (τ(e) : e ∈ E) a transition system. Every transition system decomposes G′ into edge–disjoint circuits; let c(τ) be the number of these circuits. To every transition type τ(e) we assign a weight W over ℤ by setting

(11) W (τ(e)) = \{ \begin{matrix}α & τ(e) & black \\ β & τ(e) & white \\ γ & τ(e) & crossing, \end{matrix}

and define W (τ) = ∏_{e∈E} W (τ(e)) as the weight of the transition system τ = (τ(e) : e ∈ E).

The transition polynomial of G′ with weight function W is now defined as

Q(G′, W, λ) = ∑_{τ} W (τ)λ^{c(τ)} . (12)

Comparing (12) to the definition of P (G, λ) we conclude Q(G′, W, λ) = P (G, λ) (13) for the weighting W with α = 0, β = 1, γ = −1. Let W_{α,β} be the weighting as in (11) with γ = 0, and α ≠ 0, β ≠ 0. It was proved in [7] that Q(G′, W_{α,β}, λ) is related to the Tutte polynomial t(G, x, y) of G as follows: Proposition 8 [7]. Let G(V, E) be a connected plane graph and G′ its medial graph. Then

Q(G′, W_{α,β}, λ) = α^{|R|−1}β^{|V |−1}λ t(G, 1 + \frac{α}{β}λ, 1 + \frac{β}{α}λ) . (14)

Penrose noticed the following property of Q(G′, W, λ). If two weightings W, \overline{W} differ only by an additive constant, i.e. \overline{W} = W + c, then Q(G′, \overline{W} , −2) = Q(G′, W, −2) . (15) Thus if we set α = 1, β = 2, γ = 0, then with c = −1 we have by (15) and (13)

Q(G′, W_{1,2}, −2) = P (G, −2) .

Using (14) we thus obtain

P (G, −2) = −2^{|V |}t(G, 0, −3) .

Now it is well–known that (−1)^{|R|−1}t(G, 0, 1−λ) equals the number of λ–regions colorings f of G with f(R_{0}) = 0 (see [6,20,22]), and we obtain the following result. Proposition 9 [7]. Let G(V, E) be a plane connected graph, then

P (G, −2) = (−1)^{|R|}2^{|V |} · (number of 4–region colorings f of G with f(R_{0}) = 0) .

Corollary 10 (Penrose). If G(V, E) is a 3–regular plane connected graph, then P (G, −2) = (−4)^{\frac{|V |}{2}} · (number of 3–edge colorings). Corollary 11. Let G be a connected bridgeless plane graph. If P (G, λ) has alternating coefficients a_{r} ≥ 0, a_{r−1} ≤ 0, a_{r−2} ≥ 0,…, then G is 4–region colorable. Example. Let us compute the Penrose polynomial of the 3–cube Q_{3}. Q_{3} is 3–regular with |V | = 8, |E| = 12, |R| = 6, and the dual graph is the octahedron. By Corollary 7, we have P (Q_{3}, λ) = ∑_{i=1}^{6} a_{i}λ^{i} = λ(λ − 1)(λ − 2)(λ^{3} + aλ^{2} + bλ + c), hence we need three conditions to determine a, b, c. The number of 3–edge colorings is 24, hence P (Q_{3}, 3) = 24, P (G, −2) = 2^{8} · 24 by Corollories 8 and 10. Furthermore, a_{5} = −12 by Proposition 2, and we obtain P (Q_{3}, λ) = λ(λ − 1)(λ − 2)(λ^{3} − 9λ^{2} + 54λ − 104). Note that P (Q_{3}, λ) has a real root in the interval [2, 3].

5. Rotation Signs

Recall the definition of a correct 3–edge coloring given in the last section. Let A = a_{1}a_{2} … a_{d} be the correct cyclic clockwise coloring around the vertex v with d(v) = d.

An admissible operation on A consists in removing two equal consecutive numbers a_{i} = a_{i+1} (i taken mod d), A → A′ = a_{1} … a_{i−1}a_{i+2} … a_{d}. We now perform an admissible operation on A′, and continue in this way until no further admissible operations are possible. Hence we eventually arrive at the empty set ∅ or at a sequence abcabc… abc with {a, b, c} = {1, 2, 3}. The following Lemma (whose easy proof is omitted) states that no matter which admissible operations are performed on A we always arrive at the same sequence \overline{A}.

Lemma 5. Let A = a_{1}a_{2} … a_{d} be a correct cyclic clockwise coloring. Then any sequence of admissible operations terminates at the same set \overline{A}, where \overline{A} = ∅ or \overline{A} = (abc)^{m} =

\underbrace{abc… abc}_{m}.

Let i = \sqrt{−1}. Following Penrose we define the sign σ(123) = i, σ(132) = −i. Let f be a correct 3–edge coloring of G, and A(v) the coloring around v ∈ V. Then we define the sign σ(v)

σ(v) = \{ \begin{matrix}1 & if \overline{A}(v) = ∅ \\ (σ(abc))^{m} & if \overline{A}(v) = (abc)^{m} , \end{matrix} (16)

and the sign σ(f) as

σ(f) = ∏_{v∈V} σ(v) . (17)

It is clear that \overline{A}(v) = (abc)^{m} with m odd arises precisely when d(v) is odd. Since G has an even number of vertices of odd degree, we conclude σ(f) ∈ {1, −1}. The following result for 3–regular graphs appears in [15] and was apparently first noticed in [21]. See also [8] where arbitrary 3–regular graphs are considered.

Proposition 10. Let G(V, E) be a connected plane graph. Then σ(f) = 1 for any correct 3–edge coloring of G.

Proof. Let f be a correct 3–edge coloring of G, and f̂ an extension to the associated 3–regular graph Ĝ(P̂, Ê). To f̂ we associate an admissible 3–valuation \overline{f} of Ĝ′ as in the last section (see fig. 10 for an example).

Figure 10

We note that the cyclic sense (abc) at the vertices around v̂ coincides with that of the corresponding black triangles in Ĝ′. We set σ(x) = i or −i for x ∈ P̂ if the sense is (123) resp. (132), and σ(v̂) = ∏ σ(x) over all vertices around v̂. Finally, we set σ(f̂) = ∏_{v∈V} σ(v̂).

Note that this expression is indeed the sign of the proper 3–edge coloring f̂of Ĝ as defined in (17).

Claim. We have σ(v̂) = σ(v) for all v ∈ V.

Let A(v) = a_{1}^{k_{1}} … a_{t}^{k_{t}} be the correct cyclic clockwise coloring at v. If t = 1, then \overline{A}(v) = ∅, i.e. σ(v) = 1. On the other hand, the cyclic sets (123), (132) alternate around v̂, and we obtain σ(v̂) = i^{d/2}(−i)^{d/2} = 1 with d = d(v) ≡ 0 (mod 2). The result is equally clear for d = d(v) = 3. The proof of the claim is now easily completed by induction on d.

By the claim we have σ(f̂) = σ(f) ∈ \{1, −1\}, and thus (σ(f̂))^{3} = σ(f̂). Let \overline{x} be the black triangle in Ĝ′ corresponding to x ∈ P̂. We again write σ(\overline{x}) = i or −i according to the cyclic coloring of \overline{f}, and we have σ(\overline{x}) = σ(x) as remarked above. Hence

σ(f̂)^{3} = ∏_{x∈_{P}}(σ(x))^{3} = ∏_{\overline{x}} σ(\overline{x})^{3} = ∏ σ(\overline{x})σ(\overline{y}) ,

where on the right–hand side we group in pairs black triangles \overline{x}, \overline{y} with a common vertex e_{xy} (see fig. 11).

Figure 11

According to fig. 11 we have σ(\overline{x}) = −σ(\overline{y}) in the white case and σ(\overline{x}) = σ(\overline{y}) in the crossing case. Thus σ(\overline{x})σ(\overline{y}) = 1 resp. σ(\overline{x})σ(\overline{y}) = −1, and we obtain

∏_{e_{xy}} σ(\overline{x})σ(\overline{y}) = (−1)^{m} ,

where m is the number of crossing pairs \overline{x}, \overline{y}. Let C_{i} be the collection of circuits in Ĝ′ induced by the edges labeled i (i = 1, 2, 3). By the Jordan curve theorem any two circuits C, D with C ∈ C_{i}, D ∈ C_{j} (i ≠ j) cross at an even number of points e_{xy}, and we infer that the total number of crossings m is even. This now yields

σ(f) = σ(f̂) = σ(f̂)^{3} = (−1)^{m} = 1,

and the proof is complete. □

Acknowledgement. Thanks are due to the referees for several valuable suggestions.

References

1. Aigner, M.: Combinatorial Theory. Springer 1979

2. Aigner, M.: Graphentheorie — eine Entwicklung aus dem 4–Farben Problem. Teubner 1984

3. Appel, K., Haken, W.: Every planar map is four–colorable. A.M.S. Contemporary Math. 98(1989)

4. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. MacMillan 1976

5. Bouchet, A.: Tutte–Martin polynomials and orienting vectors of isotropic systems. Graphs and Combinatorics 7, 235–252(1991)

6. Brylawski, T.H., Oxley, J.G.: The Tutte polynomial and its applications. In: Matroid Applications (White, ed.). Cambridge Univ. Press 123–225, 1992

7. Jaeger, F.: On Tutte polynomials and cycles of planar graphs. J. Combinatorial Theory B 44, 127–146(1988)

8. Jaeger, F.: On the Penrose number of cubic diagrams. Discrete Math. 74, 85– 97(1988)

9. Jaeger, F.: On edge–colorings of cubic graphs and a formula of Roger Penrose. Annals Discrete Math. 41, 267–280(1989)

10. Jaeger, F.: On transition polynomials of 4–regular graphs. In: Cycles and Rays (Hahn et al, eds.) Kluwer, 123–150, 1990

11. Kauffman, L.: State models and the Jones polynomial. Topology 26, 297–309(1987)

12. Las Vergnas, M.: Le polynôme de Martin d’un graphe Eulérien. Annals of Discrete Math. 17, 397–411(1983)

13. Martin, P.: Enumeration eulériennes dans les multigraphes et invariants de Tutte– Grothendieck. Thesis, Grenoble 1977

14. Ore, O.: The Four–Color Problem. Academic Press 1967

15. Penrose, R.: Applications of negative dimensional tensors. In: Combinatorial Mathematics and its Applications (Welsh, ed.). Academic Press, 221–244, 1971

16. Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: The four–color theorem. To appear

17. Rosenstiehl, P.: Bicycles et diagonales des graphes planaires. Cahiers de C.E.R.O. 17, 365–383(1975)

18. Rosenstiehl, P., Reed, R.C.: On the principal edge tripartion of a graph. Annals Discrete Math. 3, 195–226(1978)

19. Shank, H.: The theory of left–right paths. In: Combinatorial Mathematics III. Lecture Notes Math. 452, 42–54, Springer 1975

20. Tutte, W.T.: A contribution to the theory of chromatic polynomials. Canad. J. Math. 6, 80–91(1954)

21. Vigneron, L.: Remarques sur les réseaux cubiques de classe 3 associés au problème des quatre couleurs. C.R. Acad. Sc. Paris 223, 770–772(1946)

22. Welsh, D.J.A.: Complexity: Knots, Colorings, and Counting. London Math. Soc. Lecture Note Series 186, Cambridge Univ. Press 1993