O'Reilly logo

Circuit Double Cover of Graphs by Cun-Quan Zhang

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Appendix APreliminary

A.1 Fundamental theorems

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.).

* Embedding

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

images

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

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

(2) ξ(∑) = 2 ifis a sphere,

(3) ξ(∑) = 1 ifis a projective plane,

(4) ξ(∑) ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required