Graph Theory
Benny Sudakov
18 August 2016
,Acknowledgement
Much of the material in these notes is from the books Graph Theory by Reinhard Diestel and
Introduction to Graph Theory by Douglas West.
1
,Contents
1 Basic notions 4
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Graph isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 The adjacency and incidence matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Walks, paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.9 Graph operations and parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Trees 10
2.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Equivalent definitions of trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Cayley’s formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Connectivity 17
3.1 Vertex connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 2-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Menger’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Eulerian and Hamiltonian cycles 24
4.1 Eulerian trails and tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Hamilton paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Matchings 28
5.1 Real-world applications of matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Hall’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Matchings in general graphs: Tutte’s Theorem . . . . . . . . . . . . . . . . . . . . . . 31
6 Planar Graphs 34
6.1 Platonic Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7 Graph colouring 38
7.1 Vertex colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.2 Some motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.3 Simple bounds on the chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.4 Greedy colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.5 Colouring planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8 More colouring results 43
8.1 Large girth and large chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.1.1 Digression: the probabilistic method . . . . . . . . . . . . . . . . . . . . . . . 45
8.1.2 Proof of Theorem 8.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.2 Chromatic number and clique minors . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.3 Edge-colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2
, 8.4 List colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9 The Matrix Tree Theorem 52
9.1 Lattice paths and determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
10 More Theorems on Hamiltonicity 57
10.1 Pósa’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
10.2 Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
11 Kuratowski’s Theorem 61
11.1 Convex drawings of 3-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . 62
11.2 Reducing the general case to the 3-connected case . . . . . . . . . . . . . . . . . . . . 65
12 Ramsey Theory 68
12.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
12.2 Bounds on Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
12.3 Ramsey theory for integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
12.4 Graph Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
13 Extremal problems 73
13.1 Turán’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
13.2 Bipartite Turán Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3
Benny Sudakov
18 August 2016
,Acknowledgement
Much of the material in these notes is from the books Graph Theory by Reinhard Diestel and
Introduction to Graph Theory by Douglas West.
1
,Contents
1 Basic notions 4
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Graph isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 The adjacency and incidence matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Walks, paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.9 Graph operations and parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Trees 10
2.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Equivalent definitions of trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Cayley’s formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Connectivity 17
3.1 Vertex connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 2-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Menger’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Eulerian and Hamiltonian cycles 24
4.1 Eulerian trails and tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Hamilton paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Matchings 28
5.1 Real-world applications of matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Hall’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Matchings in general graphs: Tutte’s Theorem . . . . . . . . . . . . . . . . . . . . . . 31
6 Planar Graphs 34
6.1 Platonic Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7 Graph colouring 38
7.1 Vertex colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.2 Some motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.3 Simple bounds on the chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.4 Greedy colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.5 Colouring planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8 More colouring results 43
8.1 Large girth and large chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.1.1 Digression: the probabilistic method . . . . . . . . . . . . . . . . . . . . . . . 45
8.1.2 Proof of Theorem 8.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.2 Chromatic number and clique minors . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.3 Edge-colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2
, 8.4 List colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9 The Matrix Tree Theorem 52
9.1 Lattice paths and determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
10 More Theorems on Hamiltonicity 57
10.1 Pósa’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
10.2 Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
11 Kuratowski’s Theorem 61
11.1 Convex drawings of 3-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . 62
11.2 Reducing the general case to the 3-connected case . . . . . . . . . . . . . . . . . . . . 65
12 Ramsey Theory 68
12.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
12.2 Bounds on Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
12.3 Ramsey theory for integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
12.4 Graph Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
13 Extremal problems 73
13.1 Turán’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
13.2 Bipartite Turán Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3
