Download Vitaly I. Voloshin-Introduction to Graph Theory-Nova (2009) PDF

TitleVitaly I. Voloshin-Introduction to Graph Theory-Nova (2009)
TagsDiscrete Mathematics Vertex (Graph Theory) Theoretical Computer Science Combinatorics
File Size858.0 KB
Total Pages157
Table of Contents
                            INTRODUCTION TO GRAPH THEORY
Contents
Preface
Chapter 1: Basic Definitions and Concepts
	1.1. Fundamentals
	1.2. Graph Modeling Applications
	1.3. Graph Representations
	1.4. Generalizations
	1.5. Basic Graph Classes
	1.6. Basic Graph Operations
	1.7. Basic Subgraphs
	1.8. Separation and Connectivity
Chapter 2: Trees and Bipartite Graphs
	2.1. Trees and Cyclomatic Number
	2.2. Trees and Distance
	2.3. Minimum Spanning Tree
	2.4. Bipartite Graphs
Chapter 3: Chordal Graphs
	3.1. Preliminary
	3.2. Separators and Simplicial Vertices
	3.3. Degrees
	3.4. Distances in Chordal Graphs
	3.5. Quasi-triangulated Graphs
Chapter 4: Planar Graphs
	4.1. Plane and Planar Graphs
	4.2. Euler’s Formula
	4.3. K5 and K3,3 Are not Planar Graphs
	4.4. Kuratowski’s Theorem and Planarity Testing
	4.5. Plane Triangulations and Dual Graphs
Chapter 5: Graph Coloring
	5.1. Preliminary
	5.2. Definitions and Examples
	5.3. Structure of Colorings
	5.4. Chromatic Polynomial
	5.5. Coloring Chordal Graphs
	5.6. Coloring Planar Graphs
	5.7. Perfect Graphs
	5.8. Edge Coloring and Vizing’s Theorem
	5.9. Upper Chromatic Index
Chapter 6: Graph Traversals and Flows
	6.1. Eulerian Graphs
	6.2. Hamiltonian Graphs
	6.3. Network Flows
Chapter 7: Appendix
	7.1. What Is Mathematical Induction
	7.2. Graph Theory Algorithms and Their Complexity
	7.3. Answers and Hints to Selected Exercises
	7.4. Glossary of Additional Concepts
References
Index
                        
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

Similer Documents