Document Preview:

notes.pdf
MATH3301 Graph Theory and Design Theory Graph Theory 2011
Contents 1 Introduction 1 1.1 Denitions from MATH2302 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Important results from MATH2302 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Some more denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 Modications of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Walks, Paths and Cycles 4 2.1 Denitions from MATH2302 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Graph parameters involving distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.4 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4.1 Determining eu(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Connectivity 9 3.1 Denitions from MATH2302 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Cut-vertices and bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4 Trees 11 4.1 Denitions from MATH2302 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Factorisations 14 5.1 Denitions and results from MATH2302 . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2 One-factorisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.3 Existence Theorems for k-factors . . . . ….