##### Document Text Contents

Page 2

I NTRODUCTION TO GRAPH THEORY

No part of this digital document may be reproduced, stored in a retrieval system or transmitted in any form or

by any means. The publisher has taken reasonable care in the preparation of this digital document, but makes no

expressed or implied warranty of any kind and assumes no responsibility for any errors or omissions. No

liability is assumed for incidental or consequential damages in connection with or arising out of information

contained herein. This digital document is sold with the clear understanding that the publisher is not engaged in

rendering legal, medical or any other professional services.

Page 78

Planar Graphs 65

3. AreG1 and G2 planar graphs?

4. Connect the two lower vertices in graphG1 (Figure 4.2) by an edge and, if possible,

find a plane embedding of the obtained graph.

5. Connect the two upper vertices in graphG2 (Figure 4.2) by an edge and, if possible,

find a plane embedding of the obtained graph.

6. Find at least two different plane embeddings of the prism, cube,K2,3 andWn (n≥ 4).

7. Find a drawing of the Petersen graph with the smallest number of edge-intersections.

Computer Projects 4.1. Using an appropriate graph representation, write a program

for the following algorithmic problems.

1. Given a drawing of a graph in the plane (vertices = points, edges = straight line

segments) find out if it is a plane graph.

2. Given a drawing of a graph in the plane (vertices = points, edges = arc segments) find

out if it is a plane graph.

3. Given a drawing of a graph in the plane (vertices = points, edges = straight line

segments) find the number of edge-intersections.

4.2. Euler’s Formula

Theorem 4.2.1 (Euler, 1750)If G is a connected plane graph with n vertices, m edges and

f faces, then

n−m+ f = 2.

Proof. Let T be a spanning tree ofG. Evidently, m(T) = n− 1, f (T) = 1, son(T)−

m(T)+ f (T) = n− (n−1)+1= 2, and the formula holds forT.

Now add sequentially the remaining edges ofG to T: each such adding increases the

number of edges and the number of faces by 1. Since in the formulam and f are of the

opposite signs, the equality holds forG itself. �

Corollary 4.2.1 If a graph G is planar, then all of its plane embeddings have the same

number of faces equal to m−n+2.

Proof. Indeed, sincen(G) andm(G) are constant, Euler’s formula implies thatf (G) =

m−n+2.

�

Page 79

66 Vitaly I. Voloshin

Corollary 4.2.2 If G is a connected planar graph without parallel edges, then

m(G) ≤ 3n(G)−6.

Proof. Consider a plane embedding ofG. Since there are no parallel edges, the size of

each face is at least 3. Count the edges around each face. The minimum number that we

can obtain is 3f . In fact, each edge is counted twice, so we obtain 2m. Therefore, 3f ≤ 2m.

From Euler’s formula,f = 2−n+m. Hence, 3(2−n+m) ≤ 2mwhat givesm≤ 3n−6. �

Corollary 4.2.3 Every connected planar graph without parallel edges contains a vertex of

degree at most5.

Proof. If the graph contains at most 6 vertices, then every vertex has degree at most 5.

Therefore, it remains to consider the case when the graph has at least 7 vertices. Suppose

each vertex has degree at least 6. Counting edges around each vertex results in 6n ≤ 2m,

or, equivalently, 3n ≤ m. Combining this inequality with Corollary 4.2.2 we obtain the

following: 3n≤ m≤ 3n−6, which leads to contradiction 0≤−6. �

For any plane graphGand every its bounded facef , there exists such a plane embedding

of G that facef becomes unbounded. This can be shown using the so calledstereographic

projection.

Suppose we have a plane embedding ofG. Put a sphere tangent to the plane and map

the plane onto the sphere “to the north pole” as shown in Figure 4.3. In this way we obtain

an image ofG on the surface of the sphere. We now rotate the sphere in such a way that the

desired face contains the north pole. From the new north pole, we then project the sphere

back onto the plane. A new plane embedding ofG is obtained; the face that was bounded

in the first embedding, becomes unbounded in this new plane embedding. Therefore, the

following proposition holds.

b

b

b

b

1

2

1’

2’

N

Figure 4.3. Stereographic projection.

Proposition 4.2.1 A graph can be drawn on the sphere without intersections of edges if

and only if it is planar.

The statement above leads to the following observation about polyhedra (3-dimensional

figures bounded by the intersections of planes):

Page 156

Index 143

initial vertex, 12

interval graph, 7

intractable problem, 132

isolated vertex, 11

isomorphic graphs, 18

isomorphism, 19

Jordan curve, 63

König’s theorem, 41, 44

Kempe chain, 102, 103

Kempe’s proof, 100

Kruskal’s algorithm for minimum span-

ning tree, 39

Kuratowski’s theorem, 70

latticed graph, 58

leaf, 37

length of a path, 14

length of the cycle, 15

line graph,L(G), 108

linear-time, 131

logarithmic complexity, 132

loop, 11

matching, 27

matching covering, 43

maximal (minimal) versus maximum

(minimum), 27

maximal by inclusion complete subgraph,

26

maximal clique, 26

maximal coloring, 116

maximal planar graph, 72

maximum degree,∆, 2

Menger’s theorem, 32

Meyniel graph, 107

minimal separator, 30

minimum (maximum) spanning tree

problem, 39

minimum cut, 123

multigraph, 12

multiple edges, 12

multiplicity, 12

multiplicity of a graph,µ(G), 111

Mycielski’s construction, 104

neighbor, 3

neighborhood, 3

neighborhood of a subset, 42

network, 123

network flow, 123

node, 123

NP-complete problems, 132

odd cycle, 15

online coloring, 91

outcoming arc, 123

parallel edges, 12

path, 14

pendant vertex, 37

perfect elimination ordering, 50

perfect graph, 105

perfect matching, 27

Petersen graph, 17

planar graph, 63

planarity testing algorithm, 71

plane embedding, 63

plane graph, 63

plane triangulation, 72

polynomial-time, 131

prism, 17

properλ-coloring, 76

proper coloring, 76

proper edgeλ-coloring, 108

quasi-triangulated graph, 58

radius, 37

reducible configuration, 103

regular graph, 17

root in a tree, 42

satisfied vertex, 113

saturated arc, 123

separator, 30

simple cycle, 26

simple graph, 12

simplicial decomposition, 50

simplicial elimination ordering, 50

simplicial vertex, 47

sink, 123

size of a face, 63

Page 157

144 Index

source, 123

spanning subgraph, 27

spanning tree, 27

stability (independence) number,α(G),

26

stable (independent) set, 26

stereographic projection, 66

Stirling numbers of the first kind, 86

Stirling numbers of the second kind, 85

strict i-coloring, 77

strict edge coloring, 112

strong perfect graph conjecture, 107

strongly perfect graph, 107

subgraph, 25

symmetric matrix, 10

Szekeres-Wilf number, 53

terminal vertex, 12

tractable problem, 132

trail, 119

transposition of a matrix, 9

transversal, 27

transversal number,τ(G), 27

traversal, 119, 121, 137

tree, 16

triangle, 15

trivial graph, 37

unavoidable configuration, 103

unbounded face, 63

undirected graph, 12

universal vertex, 104

unsaturated arc, 123

upper chromatic index,̄χ′(G), 112

value of the network flow, 123

vertex, 1

vertex cover, 27

vertex cut, 30

Vizing’s theorem, 109

walk, 119

weak perfect graph conjecture, 106

weakly chordal graph, 107

weakly cyclic vertex, 58

weight of a tree,w(T), 39

weight of an edge, 39

weighted graph, 39

wheel, 15

Whitney’s theorem, 86

I NTRODUCTION TO GRAPH THEORY

No part of this digital document may be reproduced, stored in a retrieval system or transmitted in any form or

by any means. The publisher has taken reasonable care in the preparation of this digital document, but makes no

expressed or implied warranty of any kind and assumes no responsibility for any errors or omissions. No

liability is assumed for incidental or consequential damages in connection with or arising out of information

contained herein. This digital document is sold with the clear understanding that the publisher is not engaged in

rendering legal, medical or any other professional services.

Page 78

Planar Graphs 65

3. AreG1 and G2 planar graphs?

4. Connect the two lower vertices in graphG1 (Figure 4.2) by an edge and, if possible,

find a plane embedding of the obtained graph.

5. Connect the two upper vertices in graphG2 (Figure 4.2) by an edge and, if possible,

find a plane embedding of the obtained graph.

6. Find at least two different plane embeddings of the prism, cube,K2,3 andWn (n≥ 4).

7. Find a drawing of the Petersen graph with the smallest number of edge-intersections.

Computer Projects 4.1. Using an appropriate graph representation, write a program

for the following algorithmic problems.

1. Given a drawing of a graph in the plane (vertices = points, edges = straight line

segments) find out if it is a plane graph.

2. Given a drawing of a graph in the plane (vertices = points, edges = arc segments) find

out if it is a plane graph.

3. Given a drawing of a graph in the plane (vertices = points, edges = straight line

segments) find the number of edge-intersections.

4.2. Euler’s Formula

Theorem 4.2.1 (Euler, 1750)If G is a connected plane graph with n vertices, m edges and

f faces, then

n−m+ f = 2.

Proof. Let T be a spanning tree ofG. Evidently, m(T) = n− 1, f (T) = 1, son(T)−

m(T)+ f (T) = n− (n−1)+1= 2, and the formula holds forT.

Now add sequentially the remaining edges ofG to T: each such adding increases the

number of edges and the number of faces by 1. Since in the formulam and f are of the

opposite signs, the equality holds forG itself. �

Corollary 4.2.1 If a graph G is planar, then all of its plane embeddings have the same

number of faces equal to m−n+2.

Proof. Indeed, sincen(G) andm(G) are constant, Euler’s formula implies thatf (G) =

m−n+2.

�

Page 79

66 Vitaly I. Voloshin

Corollary 4.2.2 If G is a connected planar graph without parallel edges, then

m(G) ≤ 3n(G)−6.

Proof. Consider a plane embedding ofG. Since there are no parallel edges, the size of

each face is at least 3. Count the edges around each face. The minimum number that we

can obtain is 3f . In fact, each edge is counted twice, so we obtain 2m. Therefore, 3f ≤ 2m.

From Euler’s formula,f = 2−n+m. Hence, 3(2−n+m) ≤ 2mwhat givesm≤ 3n−6. �

Corollary 4.2.3 Every connected planar graph without parallel edges contains a vertex of

degree at most5.

Proof. If the graph contains at most 6 vertices, then every vertex has degree at most 5.

Therefore, it remains to consider the case when the graph has at least 7 vertices. Suppose

each vertex has degree at least 6. Counting edges around each vertex results in 6n ≤ 2m,

or, equivalently, 3n ≤ m. Combining this inequality with Corollary 4.2.2 we obtain the

following: 3n≤ m≤ 3n−6, which leads to contradiction 0≤−6. �

For any plane graphGand every its bounded facef , there exists such a plane embedding

of G that facef becomes unbounded. This can be shown using the so calledstereographic

projection.

Suppose we have a plane embedding ofG. Put a sphere tangent to the plane and map

the plane onto the sphere “to the north pole” as shown in Figure 4.3. In this way we obtain

an image ofG on the surface of the sphere. We now rotate the sphere in such a way that the

desired face contains the north pole. From the new north pole, we then project the sphere

back onto the plane. A new plane embedding ofG is obtained; the face that was bounded

in the first embedding, becomes unbounded in this new plane embedding. Therefore, the

following proposition holds.

b

b

b

b

1

2

1’

2’

N

Figure 4.3. Stereographic projection.

Proposition 4.2.1 A graph can be drawn on the sphere without intersections of edges if

and only if it is planar.

The statement above leads to the following observation about polyhedra (3-dimensional

figures bounded by the intersections of planes):

Page 156

Index 143

initial vertex, 12

interval graph, 7

intractable problem, 132

isolated vertex, 11

isomorphic graphs, 18

isomorphism, 19

Jordan curve, 63

König’s theorem, 41, 44

Kempe chain, 102, 103

Kempe’s proof, 100

Kruskal’s algorithm for minimum span-

ning tree, 39

Kuratowski’s theorem, 70

latticed graph, 58

leaf, 37

length of a path, 14

length of the cycle, 15

line graph,L(G), 108

linear-time, 131

logarithmic complexity, 132

loop, 11

matching, 27

matching covering, 43

maximal (minimal) versus maximum

(minimum), 27

maximal by inclusion complete subgraph,

26

maximal clique, 26

maximal coloring, 116

maximal planar graph, 72

maximum degree,∆, 2

Menger’s theorem, 32

Meyniel graph, 107

minimal separator, 30

minimum (maximum) spanning tree

problem, 39

minimum cut, 123

multigraph, 12

multiple edges, 12

multiplicity, 12

multiplicity of a graph,µ(G), 111

Mycielski’s construction, 104

neighbor, 3

neighborhood, 3

neighborhood of a subset, 42

network, 123

network flow, 123

node, 123

NP-complete problems, 132

odd cycle, 15

online coloring, 91

outcoming arc, 123

parallel edges, 12

path, 14

pendant vertex, 37

perfect elimination ordering, 50

perfect graph, 105

perfect matching, 27

Petersen graph, 17

planar graph, 63

planarity testing algorithm, 71

plane embedding, 63

plane graph, 63

plane triangulation, 72

polynomial-time, 131

prism, 17

properλ-coloring, 76

proper coloring, 76

proper edgeλ-coloring, 108

quasi-triangulated graph, 58

radius, 37

reducible configuration, 103

regular graph, 17

root in a tree, 42

satisfied vertex, 113

saturated arc, 123

separator, 30

simple cycle, 26

simple graph, 12

simplicial decomposition, 50

simplicial elimination ordering, 50

simplicial vertex, 47

sink, 123

size of a face, 63

Page 157

144 Index

source, 123

spanning subgraph, 27

spanning tree, 27

stability (independence) number,α(G),

26

stable (independent) set, 26

stereographic projection, 66

Stirling numbers of the first kind, 86

Stirling numbers of the second kind, 85

strict i-coloring, 77

strict edge coloring, 112

strong perfect graph conjecture, 107

strongly perfect graph, 107

subgraph, 25

symmetric matrix, 10

Szekeres-Wilf number, 53

terminal vertex, 12

tractable problem, 132

trail, 119

transposition of a matrix, 9

transversal, 27

transversal number,τ(G), 27

traversal, 119, 121, 137

tree, 16

triangle, 15

trivial graph, 37

unavoidable configuration, 103

unbounded face, 63

undirected graph, 12

universal vertex, 104

unsaturated arc, 123

upper chromatic index,̄χ′(G), 112

value of the network flow, 123

vertex, 1

vertex cover, 27

vertex cut, 30

Vizing’s theorem, 109

walk, 119

weak perfect graph conjecture, 106

weakly chordal graph, 107

weakly cyclic vertex, 58

weight of a tree,w(T), 39

weight of an edge, 39

weighted graph, 39

wheel, 15

Whitney’s theorem, 86