ContentsDrefaceVI1. The Basics1.1 Graphs*1.2 The degree ofL1.3 Paths and cycles*1.4Connectivity10131.5 TreesO441.6 Bipartite graphs*117-1.8 Euler tours*a231.9SorJinearalo1.10 Other27notionsofgraphsExercises30Note2. Matching, Covering and Packing352.1 Matching in bipartite graphs*362.2 Matching in general graphs(412.3 The Erd&s-P6sa theorem452.4 Tree packing and arboricity522.5 Path covers+++++++++++Exercises53SectionsmaarerecommendedfoOf.ionemarthelxinninmencedfohrstContents Preface ................................................................ vii 1. The Basics ...................................................... 1 1.1 Graphs* ........................................................ 2 1.2 The degree of a vertex* ......................................... 5 1.3 Paths and cycles* .............................................. 6 1.4 Connectivity* .................................................. 10 1.5 Trees and forests* .............................................. 13 1.6 Bipartite graphs* ............................................... 17 1.7 Contraction and minors* ....................................... 19 1.8 Euler tours* .................................................... 22 1.9 Some linear algebra ............................................ 23 1.10 Other notions of graphs ........................................ 27 Exercises ....................................................... 30 Notes .......................................................... 33 2. Matching, Covering and Packing ............................. 35 2.1 Matching in bipartite graphs* .................................. 36 2.2 Matching in general graphs(∗) ................................... 41 2.3 The Erd˝os-P´osa theorem ....................................... 45 2.4 Tree packing and arboricity ..................................... 48 2.5 Path covers .................................................... 52 Exercises ....................................................... 53 Notes .......................................................... 56 * Sections marked by an asterisk are recommended for a first course. Of sections marked (∗), the beginning is recommended for a first course