ContentsPrefacevii1. The Basics1.1 Graphs*1.2 The degree of a verte1.3Pathsndevele1.4 Connectivity*I1.5 Trees and forests*131.6 Bipartite graphsa1.7 Contraction and minors181.8 Euler tours*21.9.Somelinea21.10 Other notions of graphs2830ExercisesNotes32.Matching, Covering and Packing332.1Matching inbipartitegraphs342.2 Matching in general graphs(*)2.3 Packing and covering .....442.4Tree-packing andarboricity46492.5 Path covers51ExercisesNotes53Sectionsmarkedbyann asterisk are rndedforafirstcOf sectionsmarked (*),thebeginning isrecommended for a first courseContents 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* ....................................... 18 1.8 Euler tours* .................................................... 22 1.9 Some linear algebra ............................................ 23 1.10 Other notions of graphs ........................................ 28 Exercises ....................................................... 30 Notes .......................................................... 32 2. Matching, Covering and Packing ............................. 33 2.1 Matching in bipartite graphs* .................................. 34 2.2 Matching in general graphs(∗) ................................... 39 2.3 Packing and covering ........................................... 44 2.4 Tree-packing and arboricity ..................................... 46 2.5 Path covers .................................................... 49 Exercises ....................................................... 51 Notes .......................................................... 53 * Sections marked by an asterisk are recommended for a first course. Of sections marked (∗), the beginning is recommended for a first course