In this chapter, we present some fundamental theorems that are used in the book. Note that the proofs of some theorems are not presented here if they can be found in some popular graph theory textbooks (for instance, [15], [18], [19], [34], [41], [92], and [242], etc.).

**Theorem A.1.1**(Euler formula) *Let G* = (*V*, *E*) *be a connected graph with a 2-cell embedding on a surface* ∑. *Then*

*where F*(*G*) *is the set of faces of G on* ∑, ξ(∑) *is the* Euler characteristic *of the surface* ∑ *such that*

(*1*) ξ(∑) ≤ 2 *for any surface* ∑,

(*2*) ξ(∑) = 2 *if* ∑ *is a sphere*,

(*3*) ξ(∑) = 1 *if* ∑ *is a projective plane*,

(*4*) ξ(∑) ...

Start Free Trial

No credit card required