《图论》课程教学资源（书籍文献）Graph Theory（Reinhard Diestel，5th Edition）

xviContents3. Connectivity59593.1 2-Connectedgraphsand sbgraph3.2The structure of 3-connected graphs(*62673.3Menger's theorem*...............3.4 Mader's theorem723.5 Link741182ExercisesNote4. Planar Graphs89904.1 Topological4.2Planegraphs*924.3Drawings984.4Planargraph02sistheor1074.5 Algebraic planarity criteria4.6 Plane duality110Exercises113*+++++ ++++++++++ +*++*+++Notes1175. Colouring1195.1 Colouring maps and planar graph201225.2 Colouring vertices*...................5.3 Colouring edges*1275.4.List colouring129+45.5 Perfect graphs135Exercise42Notes14626. Flows1491506.1 Circulations(6.2 Flows in networks*1516.3Grou154valued6.4 k-Flows for small k1596.5 Flow-colouring duality162....6.6 Tutte'sflow conject165169Exercises171

xvi Contents 3. Connectivity .................................................... 59 3.1 2-Connected graphs and subgraphs* ............................ 59 3.2 The structure of 3-connected graphs(∗) .......................... 62 3.3 Menger’s theorem* ............................................. 67 3.4 Mader’s theorem ............................................... 72 3.5 Linking pairs of vertices(∗) ...................................... 74 Exercises ....................................................... 82 Notes .......................................................... 85 4. Planar Graphs .................................................. 89 4.1 Topological prerequisites* ...................................... 90 4.2 Plane graphs* .................................................. 92 4.3 Drawings ....................................................... 98 4.4 Planar graphs: Kuratowski’s theorem* .......................... 102 4.5 Algebraic planarity criteria ..................................... 107 4.6 Plane duality ................................................... 110 Exercises ....................................................... 113 Notes .......................................................... 117 5. Colouring ........................................................ 119 5.1 Colouring maps and planar graphs* ............................. 120 5.2 Colouring vertices* ............................................. 122 5.3 Colouring edges* ............................................... 127 5.4 List colouring .................................................. 129 5.5 Perfect graphs .................................................. 135 Exercises ....................................................... 142 Notes .......................................................... 146 6. Flows ............................................................ 149 6.1 Circulations(∗) .................................................. 150 6.2 Flows in networks* ............................................. 151 6.3 Group-valued flows ............................................. 154 6.4 k-Flows for small k ............................................. 159 6.5 Flow-colouring duality .......................................... 162 6.6 Tutte’s flow conjectures ........................................ 165 Exercises ....................................................... 169 Notes .......................................................... 171

xviiContents7. Extremal Graph Theor1737.1 Subgraphs*1747.2 Minors(*)807.3 Hadwiger's conjectu1837.4 Szemeredi's regularity le87.5Applyingtheregularitylen195...RyereNotes2048. Infinite Graphs2098.1Bas2108.2 Paths,tres, and ends(*)..2198.3 Homogereneous and universal graphs*2288.4 Connectivity and matching2318.5 R2428.6 Graphs with ends: the complete picture..2458.7 The topological cycle spac25488Infinite graphs aslimitsoffinite258..261ExercisesNotes2739. RamTheory for Grapl2839.1 Ramsey's origina284heoret9.2Ramseynumbers(*)2872909.3InducedRamseythere9.4 Rar300ivit.303Exercises304Note10. Hamilton Cycles30730710.1Sufficientconditions*10.2Hamiltoncvcles311andde10.3Hamilton cycles in the square of a grap314.319Exercises++++++++++.320Notes+.++++

Contents xvii 7. Extremal Graph Theory ....................................... 173 7.1 Subgraphs* .................................................... 174 7.2 Minors(∗) ....................................................... 180 7.3 Hadwiger’s conjecture* ......................................... 183 7.4 Szemer´edi’s regularity lemma ................................... 187 7.5 Applying the regularity lemma ................................. 195 Exercises ....................................................... 201 Notes .......................................................... 204 8. Infinite Graphs ................................................. 209 8.1 Basic notions, facts and techniques* ............................ 210 8.2 Paths, trees, and ends(∗) ........................................ 219 8.3 Homogeneous and universal graphs* ............................ 228 8.4 Connectivity and matching ..................................... 231 8.5 Recursive structures ............................................ 242 8.6 Graphs with ends: the complete picture ......................... 245 8.7 The topological cycle space ..................................... 254 8.8 Infinite graphs as limits of finite ones ........................... 258 Exercises ....................................................... 261 Notes .......................................................... 273 9. Ramsey Theory for Graphs ................................... 283 9.1 Ramsey’s original theorems* .................................... 284 9.2 Ramsey numbers(∗) ............................................. 287 9.3 Induced Ramsey theorems ...................................... 290 9.4 Ramsey properties and connectivity(∗) ........................... 300 Exercises ....................................................... 303 Notes .......................................................... 304 10. Hamilton Cycles .............................................. 307 10.1 Sufficient conditions* ........................................... 307 10.2 Hamilton cycles and degree sequences ........................... 311 10.3 Hamilton cycles in the square of a graph ........................ 314 Exercises ....................................................... 319 Notes .......................................................... 320

xviliContents11. Random Graphs32311.1 The notion of a random gray.32411.2 The probabilistic method32933211.3 Properties of almost all graphs*33511.4 Threaoldfu.342ExerciseNotes34412. Graph Mir34712.1 Well34812.2The graph minor theorem for trees：34912.3Tree-cositions(*35112.4 Tree-width(*)... 35536012.5 Tar12.6Tre36912.7 The graph minor theorem(*)374Exercises382+++++*++..Notes388A. Infinite sets393B. SurfacesHints for all th407409IndeSymbol index427

xviii Contents 11. Random Graphs ............................................... 323 11.1 The notion of a random graph* ................................. 324 11.2 The probabilistic method* ...................................... 329 11.3 Properties of almost all graphs* ................................ 332 11.4 Threshold functions and second moments ....................... 335 Exercises ....................................................... 342 Notes .......................................................... 344 12. Graph Minors ................................................. 347 12.1 Well-quasi-ordering(∗) ........................................... 348 12.2 The graph minor theorem for trees ............................. 349 12.3 Tree-decompositions(∗) .......................................... 351 12.4 Tree-width(∗) ................................................... 355 12.5 Tangles ........................................................ 360 12.6 Tree-decompositions and forbidden minors ...................... 369 12.7 The graph minor theorem(∗) .................................... 374 Exercises ....................................................... 382 Notes .......................................................... 388 A. Infinite sets ..................................................... 393 B. Surfaces ......................................................... 399 Hints for all the exercises............................................... 407 Index .................................................................. 409 Symbol index .......................................................... 427

1The BasicsThis chapter gives a gentle yet concise introduction to most of the ter-minology used later in the book. Fortunately, much of standard graphtheoretic terminology is so intuitive that it is easy to remember; the fewterms better understood in their proper setting will be introduced later,when their time has coction 1.1 offers a brief but self-contained sumryof themostbasic definitions in graph theory, those centred round the notion of agraph. Most readers will have met these definitions before, or will havethem explained to them as they begin to read this book. For this reason,Section 1.1 does not dwell on these definitions more than clarity requires:its mainpurpose is to collect themost basicterms in one plaoloreasyreference later. For deviations for multigraphs see Section 1.10.From Section 12onwards.all newdefinitions will bebroughttolifealmostimnmediatelybyanumber ofsimplevetfundamental propositionsOften, these will relate the newly defined terms to one another: theof how the vaof oneriant influences that of anotheTOuunderlies much of graph theory, and it will be good to become familiarwith this line of thinking early.By N we denote the set of natural numbers, including zero. The setZ/nZ of integers modulo n is denoted by Zn; its elements are writenZ,asi:=i+nzWhen weregard Z,=0.i)as afield,wealso denoteit as F, - [0,1]. For a real mumber we denote by [] the greatest[] [a]integer .and by[r the least integer ≥ r.Logarithms written aslog' are taken at baoase2:thenatural logarithmwillbedenotedby"lnlog, InTan that a is being defined aand:E·,Ax) of disjoint subsets of a set A is a partisetA-fAorpartof Aif the union UAof all the sets A, e A is A and A; + O for every i.UAAnother partition [A', .., A] of A refines the partition A if each A, is[4]contained in some Aj. By [A]* we denote the set of all k-element subsetsof A. Sets with k elements will be called k-sets: subsets with k elementare k-subsets.k-set Reinhard Diestel 2017RTTexts1natics173GrapnTnDOI10.1007/978-3-662-53622-3_

1 The Basics This chapter gives a gentle yet concise introduction to most of the ter￾minology used later in the book. Fortunately, much of standard graph theoretic terminology is so intuitive that it is easy to remember; the few terms better understood in their proper setting will be introduced later, when their time has come. Section 1.1 offers a brief but self-contained summary of the most basic definitions in graph theory, those centred round the notion of a graph. Most readers will have met these definitions before, or will have them explained to them as they begin to read this book. For this reason, Section 1.1 does not dwell on these definitions more than clarity requires: its main purpose is to collect the most basic terms in one place, for easy reference later. For deviations for multigraphs see Section 1.10. From Section 1.2 onwards, all new definitions will be brought to life almost immediately by a number of simple yet fundamental propositions. Often, these will relate the newly defined terms to one another: the question of how the value of one invariant influences that of another underlies much of graph theory, and it will be good to become familiar with this line of thinking early. By N we denote the set of natural numbers, including zero. The set Z/nZ of integers modulo n is denoted by Zn; its elements are written Zn as i := i + nZ. When we regard Z2 = {0, 1} as a field, we also denote it as F2 = {0, 1}. For a real number x we denote by x the greatest integer x, and by x the least integer  x. Logarithms written as x, x ‘log’ are taken at base 2; the natural logarithm will be denoted by ‘ln’. log, ln The expressions x := y and y =: x mean that x is being defined as y. A set A = {A1,...,Ak} of disjoint subsets of a set A is a partition partition of A if the union A of all the sets Ai ∈ A is A and Ai = ∅ for every i. A Another partition {A 1,...,A } of A refines the partition A if each A i is contained in some Aj . By [A] k we denote the set of all k-element subsets [A] k of A. Sets with k elements will be called k-sets; subsets with k elements are k-subsets. k-set R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, DOI 10.1007/978-3-662-53622-3_1 © Reinhard Diestel 2017 1

21. The Basics1.1 GraphsA graph is a pair G=(V,E) of sets such that E C [V]?; thus, theelementsgraphof E are 2-element subsets of V. To avoid notational ambiguities, weshall always assume tacitly that VnE = 0. The elements of V are thevertices (or nodes, or points) of the graph G, the elements of E are itsvertexedgeedges (or lines). The usual way to picture a graph is by drawing a dot foreach vertex and joining two of these dots by a line if the correspondingtwo vertices form an edge. Just how these dots and lines are drawn isconsidered irrelevant: all that matters is the information of which pairsof vertices form an edge and which do not.Fig. 1.1.1. The graph on V = [1,--, 7) with edge setE = [(1,2], [1,5], [2,5], [3,4], [5, 7)]A graph with vertex set V is said to be a graph on V. The vertexonV(G),E(G) set of a graph G is referred to as V(G), its edge set as E(G). Theseconventions are independent of any actual names of these two sets: thevertex set W of a graph H = (W, F) is still referred to as V(H), not asW(H). We shall not always distinguish strictly between a graph and itsDr edge set. For example, we may speak of a vertex ue G (ratherortXthan u e V(G)), an edge e e G, and so olorderThe number of vertices of a graph G is its order, written as [Gl; itsJG, JIGInumber of edges is denoted by Gll. Graphs are finite, infinite, countableand so on according to their order. Except in Chapter 8, our graphs willbe finite unless otherwisestatedFor the empty graph (0, 0) we simply write 0. A graph of order 0 or 1trivialis called trivial. Someg.to start an induction,trivialgraphscantimegraphbe useful; at other times they form silly counterexamples and become aquisance.To avoid cluttering the text with non-triviality conditions.weshall mostly treat the trivial graphs, and particularly the empty graphwith generous disregardincident.A vertex v is incident with an edge e if u e e; then e is an edge at wendsThe two vertices incident with an edge are its enduertices or ends, andan edge joins its ends. An edge [z,y) is usually written as ry (or yr).If r e X and y e Y, then ry is an X-Y edge. The set of all X-Y edgesE(X,Y)in a set E is denoted by E(X,Y); instead of E((r),Y) and E(X, (y))we simply write E(r,Y) and E(X,y). The set of all the edges in E at aE(u)vertex u is denoted by E(v)

2 1. The Basics 1.1 Graphs A graph is a pair G = (V,E) of sets such that E ⊆ [V ] 2 graph ; thus, the elements of E are 2-element subsets of V . To avoid notational ambiguities, we shall always assume tacitly that V ∩ E = ∅. The elements of V are the vertex vertices (or nodes, or points) of the graph G, the elements of E are its edge edges (or lines). The usual way to picture a graph is by drawing a dot for each vertex and joining two of these dots by a line if the corresponding two vertices form an edge. Just how these dots and lines are drawn is considered irrelevant: all that matters is the information of which pairs of vertices form an edge and which do not. 1 2 3 4 5 6 7 Fig. 1.1.1. The graph on V = {1,..., 7} with edge set E = {{1, 2}, {1, 5}, {2, 5}, {3, 4}, {5, 7}} on A graph with vertex set V is said to be a graph on V . The vertex V (G), E(G) set of a graph G is referred to as V (G), its edge set as E(G). These conventions are independent of any actual names of these two sets: the vertex set W of a graph H = (W, F) is still referred to as V (H), not as W(H). We shall not always distinguish strictly between a graph and its vertex or edge set. For example, we may speak of a vertex v ∈ G (rather than v ∈ V (G)), an edge e ∈ G, and so on. order The number of vertices of a graph G is its order, written as |G|; its |G|, G number of edges is denoted by G. Graphs are finite, infinite, countable and so on according to their order. Except in Chapter 8, our graphs will be finite unless otherwise stated. ∅ For the empty graph (∅, ∅) we simply write ∅. A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can trivial graph be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly treat the trivial graphs, and particularly the empty graph ∅, with generous disregard. incident A vertex v is incident with an edge e if v ∈ e; then e is an edge at v. ends The two vertices incident with an edge are its endvertices or ends, and an edge joins its ends. An edge {x, y} is usually written as xy (or yx). If x ∈ X and y ∈ Y , then xy is an X–Y edge. The set of all X–Y edges E(X, Y ) in a set E is denoted by E(X, Y ); instead of E({x}, Y ) and E(X, {y}) we simply write E(x, Y ) and E(X, y). The set of all the edges in E at a E(v) vertex v is denoted by E(v)