Page 20 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 20
.2 Voltage graphs
Euler’s formula
We have a fundamental counting relationship for graphs with 2-cell embeddings on sur-
faces.
Euler’s formula: Suppose we have a 2-cell embedding of a connected graph G on a sur-
face Σ, where G has v vertices, e edges, and the embedding has f faces. Then
v −e +f =χ
where χ = χ(Σ) is a constant that depends only on the surface; in particular,
χ(Sh ) = 2 − 2h for h ≥ 0 and
χ(Nk ) = 2 − k for k ≥ 1.
Definition: χ(Σ) is the Euler characteristic and can often be used to handle both ori-
entable and nonorientable surfaces at the same time. But often convenient and more
intuitive to have a nonnegative number with the same property. Define the Euler
genus (Σ) by
(Sh ) = 2h for h ≥ 0 and
(Nk ) = k for k ≥ 1
so that χ(Σ) = 2 − (Σ).
Example: K5 on torus S1: v = 5, e = 10, f = 5, v − e + f = 5 − 10 + 5 = 0 = 2 − 2 × 1.
Important note: For Euler’s formula to work, graph must be connected and embedding
must be 2-cell. (There are more general versions that work if we relax these restric-
tions, but we need them for the basic formula above.)
Euler’s formula and face degrees: Euler’s formula gives an important implication in-
volving the degrees of faces (lengths of facial walks) in an embedding. Since =
2 − v + e − f , for a minimum genus embedding of a given graph G (meaning v and
e are fixed) we want to maximize f . Since the sum of the face degrees is 2e , which is
fixed, this means we want many faces of small degree. For a simple graph, we want
triangular faces.
Based on considerations like this we can often find obvious lower bounds on the
genus of embeddings of a given graph G . We then want to show that this lower bound
can be achieved by constructing an embedding.
Exercise: Consider the usual drawing of the prism K2 Cn , n ≥ 3, (cartesian product) in
the plane.
(a) If we make every K2 edge twisted, what is the Euler genus of the corresponding
embedding (use Euler’s formula!), and is it orientable or nonorientable?
(b) Suppose we instead make every edge of one copy of Cn twisted, but leave all other
edges untwisted. Answer the same question.
1.2 Voltage graphs
Note: Main reference for this section and next is Gross and Tucker’s book [GT]. My nota-
tion and setup is similar to [GT], but not exactly the same.
Euler’s formula
We have a fundamental counting relationship for graphs with 2-cell embeddings on sur-
faces.
Euler’s formula: Suppose we have a 2-cell embedding of a connected graph G on a sur-
face Σ, where G has v vertices, e edges, and the embedding has f faces. Then
v −e +f =χ
where χ = χ(Σ) is a constant that depends only on the surface; in particular,
χ(Sh ) = 2 − 2h for h ≥ 0 and
χ(Nk ) = 2 − k for k ≥ 1.
Definition: χ(Σ) is the Euler characteristic and can often be used to handle both ori-
entable and nonorientable surfaces at the same time. But often convenient and more
intuitive to have a nonnegative number with the same property. Define the Euler
genus (Σ) by
(Sh ) = 2h for h ≥ 0 and
(Nk ) = k for k ≥ 1
so that χ(Σ) = 2 − (Σ).
Example: K5 on torus S1: v = 5, e = 10, f = 5, v − e + f = 5 − 10 + 5 = 0 = 2 − 2 × 1.
Important note: For Euler’s formula to work, graph must be connected and embedding
must be 2-cell. (There are more general versions that work if we relax these restric-
tions, but we need them for the basic formula above.)
Euler’s formula and face degrees: Euler’s formula gives an important implication in-
volving the degrees of faces (lengths of facial walks) in an embedding. Since =
2 − v + e − f , for a minimum genus embedding of a given graph G (meaning v and
e are fixed) we want to maximize f . Since the sum of the face degrees is 2e , which is
fixed, this means we want many faces of small degree. For a simple graph, we want
triangular faces.
Based on considerations like this we can often find obvious lower bounds on the
genus of embeddings of a given graph G . We then want to show that this lower bound
can be achieved by constructing an embedding.
Exercise: Consider the usual drawing of the prism K2 Cn , n ≥ 3, (cartesian product) in
the plane.
(a) If we make every K2 edge twisted, what is the Euler genus of the corresponding
embedding (use Euler’s formula!), and is it orientable or nonorientable?
(b) Suppose we instead make every edge of one copy of Cn twisted, but leave all other
edges untwisted. Answer the same question.
1.2 Voltage graphs
Note: Main reference for this section and next is Gross and Tucker’s book [GT]. My nota-
tion and setup is similar to [GT], but not exactly the same.
