《Discrete Mathematics II教学-华南理工》6.7 Planar graph.pptVIP

L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 3 2 1 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 4 3 1 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 4 4 2 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 5 5 2 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 6 6 2 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 7 7 2 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 8 8 2 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 8 9 3 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 8 10 4 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 8 11 5 2 L25 * Animated Invariance ofEuler Characteristic |V | |E | r c = r - |E | + |V | 8 12 6 2 Suppose that a connected planar simple graph has 20 vertices, each of degree 3. Into how many regions does a representation of this planar graph split the plane? Solution: This graph has 20 vertices, each of degree 3, so that v=20.Since the sum of the degrees of the vertices, 3v=60, is equals to twice the number of edges,2e, we have 2e=60, or e=30. Consequencetly, from Euler’s formula, the number of regions is r=e-v+2=30-20+2=12. Example Corollary 1: If G is a connected planar simple graph with e edges and v vertices where v≥3, then e≤3v-6. Hence, (2/3)e ≥r. Using r=e-v+2 we obtained e-v+2 ≤(2/3)e. It follows that e≤3v-6. Q. E. D. Proof: A connected planar simple graph drawn in the plane divides the plane into regions, say r of them. The degree of each region is at least 3(Since the graphs discussed here are simple graphs.) The degree of the unbounded region is at least 3 since there are at least three vertices in the graph . Corollary Show that K5 is nonplan