Graph Theory: A NPTEL Course

1 Preliminaries (5 - 10 lectures)
1.1 Introduction: Discovery of graphs . . . . . . . . . . . . . . . . . . . . 2
1.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
• Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
• Pictorial representation of a graph . . . . . . . . . . . . . . . . 4
• Isomorphic graphs . . . . . . . . . . . . . . . . . . . . . . . . 6
• Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
• Matrix representations of graphs . . . . . . . . . . . . . . . . 9
• Degree of a vertex . . . . . . . . . . . . . . . . . . . . . . . . 11
• Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
• Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
• Larger graphs from smaller graphs . . . . . . . . . . . . . . . 16
Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . 17
Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3
Graphic sequences
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
• Graph theoretic model of the LAN problem . . . . . . . . . . 20
• Havel-Hakimi criterion . . . . . . . . . . . . . . . . . . . . . . 21
• Realization of a graphic sequence . . . . . . . . . . . . . . . . 22
• Erd ̈s-Gallai criterion . . . . . . . . . . . . . . . . . . . . . . . 25
 o 
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Connected graphs and shortest paths (4-8 lectures)
33
2.1 Walks, trails, paths, cycles . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
• Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
• Cut-vertices and cut-edges . . . . . . . . . . . . . . . . . . . . 44
• Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.4 Weighted graphs and shortest paths . . . . . . . . . . . . . . . . . . . 55
• Weighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . 56
• Dijkstra’s shortest path algorithm . . . . . . . . . . . . . . . . 57
• Floyd-Warshall shortest path algorithm . . . . . . . . . . . . . 61
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3 Trees (5 - 10 lectures)
71
3.1 Definitions and characterizations . . . . . . . . . . . . . . . . . . . . 72
3.2 Number of trees (Optional) . . . . . . . . . . . . . . . . . . . . . . . 75
• Cayley’s formula . . . . . . . . . . . . . . . . . . . . . . . . . 77
• Kircho↵-matrix-tree theorem . . . . . . . . . . . . . . . . . . . 79
Minimum spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . 83
• Kruskal’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . 84
• Prim’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 88
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.3
4 Special classes of graphs(6 - 12 lectures)
97
4.1 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
4.2 Line Graphs (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.3 Chordal Graphs (Optional) . . . . . . . . . . . . . . . . . . . . . . . . 107
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5 Eulerian Graphs (2 - 4 lectures)
119
5.1 Motivation and origin . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2 Fleury’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.3 Chinese Postman problem (Optional) . . . . . . . . . . . . . . . . . . 128
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6 Hamilton Graphs (4 - 8 lectures)
135
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.2 Necessary conditions and su cient conditions . . . . . . . . . . . . . 137
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7 Independent sets, coverings and matchings(8-16lectures)
151
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.2 Independent sets and coverings: basic equations . . . . . . . . . . . . 152
7.3 Matchings in bipartite graphs . . . . . . . . . . . . . . . . . . . . . . 159
• Hall’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 160
• K ̈nig’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 163
      o
7.4 Perfect matchings in graphs . . . . . . . . . . . . . . . . . . . . . . . 167
7.5 Greedy and approximation algorithms (Optional) . . . . . . . . . . . 172
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8 Vertex Colorings (4 - 8 lectures)
179
8.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.2 Cliques and chromatic number . . . . . . . . . . . . . . . . . . . . . . 182
•
8.3
Mycielski’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 182
Greedy coloring algorithm . . . . . . . . . . . . . . . . . . . . . . . . 184
• Coloring of chordal graphs (Optional) . . . . . . . . . . . . . . 187
• Brooks theorem (Optional) . . . . . . . . . . . . . . . . . . . . 188
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9 Edge Colorings (8 - 16 lectures)
195
9.1 Introduction and Basics . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.2 Gupta-Vizing theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 198
9.3 Class-1 and Class-2 graphs . . . . . . . . . . . . . . . . . . . . . . . . 201
• • Class-2 graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
• 
9.4
Edge-coloring of bipartite graphs . . . . . . . . . . . . . . . . 202
Hajos union and Class-2 graphs (Optional) . . . . . . . . . . . 208
A scheduling problem and equitable edge-coloring (Optional) . . . . . 210
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
10 Planar Graphs (10 - 20 lectures)
217
10.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
10.2 Euler’s formula and its consequences . . . . . . . . . . . . . . . . . . 223
10.3 Polyhedrons and planar graphs (Optional) . . . . . . . . . . . . . . . 226
MODULES
v
10.4 Characterizations of planar graphs . . . . . . . . . . . . . . . . . . . 231
• Subdivisions and Kuratowski’s characterization . . . . . . . . 231
• Minors and Wagner’s theorem . . . . . . . . . . . . . . . . . . 241
10.5 Planarity testing (Optional) . . . . . . . . . . . . . . . . . . . . . . . 242
•
D-M-P-planarity algorithm . . . . . . . . . . . . . . . . . . . . 243
10.6 5-Color-theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
11 Directed Graphs (8 - 16 lectures)
255
11.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
• Underlying graph of a digraph . . . . . . . . . . . . . . . . . . 257
• Out-degrees and in-degrees . . . . . . . . . . . . . . . . . . . . 258
• Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11.2 Directed walks, paths and cycles . . . . . . . . . . . . . . . . . . . . . 259
•
Connectivity in digraphs . . . . . . . . . . . . . . . . . . . . . 261
11.3 Orientation of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . 265
11.4 Eulerian and Hamilton digraphs . . . . . . . . . . . . . . . . . . . . . 268
• Eulerian digraphs . . . . . . . . . . . . . . . . . . . . . . . . . 268
• Hamilton digraphs . . . . . . . . . . . . . . . . . . . . . . . . 269
11.5 Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278