Mathematics for Computer Science

Chapter 12 Planar Graphs376

(a) (b) (c)

(d) (e) (f)

e 1

v 1

v 2

e 2

v 3

Figure 12.13 One method by which the graph in (a) can be reduced toC 3 (f),
thereby showing thatC 3 is a minor of the graph. The steps are: merging the nodes
incident toe 1 (b), deletingv 1 and all edges incident to it (c), deletingv 2 (d), delet-
inge 2 , and deletingv 3 (f).