Mem. Fac. Sci. Eng. Shimane Univ.
Series B: Mathematical Science
35 (2002), pp. 43–47

GENERATING FUNCTIONS OF EULERIAN AND SEPARATINGEULERIAN SUBGRAPHS
MAKOTO IDZUMI(Received: January 31, 2002)
Abstract. Throughout this paper, all graphs are assumed to be embedded into
an orientable surface. A graph is Eulerian if the degree of every vertex is even.
An Eulerian graph is separating if the regions into which the surface is divided
by the graph are 2-colorable. Let G be a graph and G∗ its dual. We show anidentity which relates the generating function of Eulerian subgraphs of G and
the generating function of separating Eulerian subgraphs of G∗ .

1. Eulerian subgraphs
We define a graph G as a triple (V (G), E(G), φG ), where V (G) and E(G) are
finite sets and φG : E(G) → V (G) × V (G). The elements of V (G) and E(G)are called the vertices and edges, respectively, of G. i(e) and t(e) are defined byφG (e) = (i(e), t(e)) for e ∈ E(G); we say that the vertices i(e) and t(e) are on theedge e, and the edge e are on the vertices i(e) and t(e). The degree, degG (α), in Gof a vertex α ∈ V (G) is#{e ∈ E(G) | i(e) = α} + #{e ∈ E(G) | t(e) = α}.
A graph is Eulerian if the degree of every vertex is even. A subgraph H of G is agraph containing a subset of the edges of G and those vertices of G which on theseedges. A subgraph H of G is Eulerian if the graph H is Eulerian. E(G) denotes
the collection of all Eulerian subgraphs of G. Let u = {u(e) | e ∈ E(G)} be a setof commutative indeterminates. A polynomialX Y(1)S(G, u) =u(e).
H∈E(G) e∈E(H)is the generating function of Eulerian subgraphs of G. Define the Ising partition
function, Z(G, K), of G byX
X
(2)
Z(G, K) =exp K(e)σ(i(e))σ(t(e))
σ∈C(G)e∈E(G)

1991 Mathematics Subject Classification. 05C30, 05C45, 05A15, 05A19, 82B20.
Key words and phrases. Generating functions, Eulerian graphs, duality, Ising model.
43

44

MAKOTO IDZUMI

where C(G) denotes Map(V (G), {−1, 1}), and K is a complex-valued function onE(G). Expanding the exponential in (2) and noting, since σ takes values in {−1, 1},that(1if n is evenn(σ(i(e))σ(t(e))) =σ(i(e))σ(t(e))
if n is odd,
we haveexp (K(e)σ(i(e))σ(t(e))) = cosh K(e) + σ(i(e))σ(t(e)) sinh K(e)= cosh K(e) (1 + z(e)σ(i(e))σ(t(e)))
where(3)z(e) = tanh K(e).

We can then write the partition function (2) in the formYX YZ(G, K) = cosh K(e)
(1 + z(e)σ(i(e))σ(t(e))) .
e∈E(G)σ∈C(G) e∈E(G)We now expand the product. Since(XYnασ(α)=σ∈C(G) α∈V (G)

2#V (G)if all nα are even

0otherwise,

it follows that
(4)

Z(G, K) = 2#V (G) Ycosh K(e) S(G, z),e∈E(G)where z = {z(e) | e ∈ E(G)} and S(G, z) is the generating function of Eulerian
subgraphs (1).
2. Embedding into a surface, a dual graph, and separating Euleriansubgraphs
Let Fg be an orientable surface of genus g. Now, graphs are supposed to bedrawn on the surface (i.e. embedded into Fg ). An Eulerian graph is separating
if the regions into which the surface is divided by the graph are 2-colorable. An
Eulerian subgraph H of G is separating if the Eulerian graph H is separating.
Note that whether an Eulerian subgraph of G is separating or not depends onthe embedding of G we assumed. E0 (G) denotes the collection of all separating
Eulerian subgraphs of G. A polynomialXY(5)S0 (G, u) =u(e).
H∈E0 (G) e∈E(H)is the generating function of separating Eulerian subgraphs of G.

EULERIAN AND SEPARATING EULERIAN SUBGRAPHS

45

A graph G drawn on the surface Fg has a dual graph G∗ . The edges of G∗ are in
1–1 correspondence with the edges of G; so we shall identify them, E(G∗ ) = E(G).
Now we write the partition function (2) in the other form:
YX Y 
 1−σ(i(e))σ(t(e))K(e) −2K(e)2Z(G, K) =ee.
e∈E(G)σ∈C(G) e∈E(G)

Choose arbitrarily a vertex α0 ∈ V (G), and divide the sum over C(G) into two,according toC(G) = C+ + C−

where C± = {σ ∈ C(G) | σ(α0 ) = ±1},

we have
Z(G, K) = YeK(e) ·2X Y e−2K(e) 1−σ(i(e))σ(t(e))
2.

σ∈C+ e∈E(G)e∈E(G)

Observing that there is a 1–1 correspondence between C+ and E0 (G∗ ), the set of all
separating Eulerian subgraphs of G∗ , byσ 7→a subgraph of G∗ whose edge set is= 1},{e ∈ E(G) | 1−σ(i(e))σ(t(e))
2we obtain
(6)Z(G, K) = YeK(e)  · 2S0 (G∗ , x),e∈E(G)where x = {x(e) | e ∈ E(G)},x(e) = e−2K(e) ,(7)and S0 is the generating function defined in (5).
3. An identity which relates S and S0
We continue to suppose that graphs are drawn on the surface Fg . So far we haveobtained two different expressions, (4) and (6), for the Ising partition functon.
Combining the two expressions, we obtainYY2#V (G) cosh K(e) S(G, z) = eK(e)  · 2S0 (G∗ , x),e∈E(G)e∈E(G)

where z(e) and x(e) are defined in (3) and (7), respectively. Eliminating K(e)completely we have symmetric relations between these variables, z(e) and x(e),(8)z(e) =

1 − x(e),1 + x(e)x(e) =

1 − z(e),1 + z(e)e ∈ E(G),46

MAKOTO IDZUMI

and relations between S and S0 ,

1· S0 (G∗ , x),
1 + x(e)e∈E(G)Y 
1· S(G, z).
1 + z(e)−#V (G)+#E(G)+1S(G, z) = 2S0 (G∗ , x) = 2#V (G)−1Y e∈E(G)At this stage, we can forget what the variables z(e) and x(e) were — equations(3) and (7); instead, we can think of them as variables, related to each other byequation (8). We can write the result in more symmetric form; since #V (G) −#E(G) + #V (G∗ ) = 2 − 2g (g is the genus of the surface), (G∗ )∗ = G, andE(G∗ ) = E(G), we have
Theorem. Let Fg be an orientable surface of genus g, and G a graph embedded
into the surface. Then the generating function S of Eulerian subgraphs and thegenerating function S0 of separating Eulerian subgraphs are related by the identities
Y 
1−u
1
#V (G∗ )−1+2g(9)S(G,) = 2·· S0 (G∗ , u),
1+u
1 + u(e)∗e∈E(G )(10)

Y 
1−u
1
#V (G∗ )−1
S0 (G,) = 2·· S(G∗ , u),
1+u
1+u(e)∗e∈E(G )where
1 − u(e)1−u=| e ∈ E(G)
1+u1 + u(e)and u = {u(e) | e ∈ E(G)} is a set of indeterminates.

4. Remarks(i) When g = 0 (the surface is a sphere) Eulerian graphs on the surface arealways separating; hence E0 (G) = E(G), and S0 = S; in this case equations (4)and (6) yield the well-known Kramers–Wannier duality relation for the partition
function ([1]; this is described in any statistical mechanics textbook at advanced
level, e.g. [2]).
(ii) If a graph G is self-dual, G∗ ∼= G, then the theorem gives a relationshipbetween S and S0 for the same graph G.
(iii) If we specialize the variables: u(e) 7→ u for all e, then the coefficient of up in
S(G, u) is the number of Eulerian subgraphs of G with p edges, and the coefficientof up in S0 (G, u) is the number of separating Eulerian subgraphs of G with p edges.
(iv) In view of statistical mechanics, the expression (4) of the Ising partition
function is a high-temperature expansion, and equation (6) is a low-temperature
expansion for Z [since K is (ferromagnetic coupling constant)/(absolute temperature); and, therefore, z = tanh K is small at high temperature, and x = e−2K issmall at low temperature].

EULERIAN AND SEPARATING EULERIAN SUBGRAPHS

47References[1] H. A. Kramers and G. H. Wannier, Statistics of the two-dimensional ferromagnet, I and II,
Phys. Rev. 60 (1941), 252–262, 263–276.
[2] C. J. Thompson, Mathematical Statistical Mechanics (Princeton University Press, 1972).
Department of Mathematics, Faculty of Education, Shimane University, Matsue
690-8504 JAPANE-mail address: idzumi@edu.shimane-u.ac.jp