<div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://files.passeidireto.com/569c7f44-7960-452b-bd43-a9ca6943a2c9/bg1.png"><div class="c x1 y1 w2 h2"><div class="t m0 x0 h3 y2 ff1 fs0 fc0 sc0 ls1 ws0">Reinhard Diestel</div><div class="t m0 x0 h4 y3 ff1 fs1 fc0 sc0 ls1 ws1">Graph Theory</div><div class="t m0 x0 h5 y4 ff1 fs2 fc0 sc0 ls1 ws2">Electronic Edition 2005</div><div class="t m0 x2 h6 y5 ff1 fs3 fc0 sc0 ls1">c</div><div class="t m0 x0 h6 y6 ff2 fs3 fc0 sc0 ls0">\ue001<span class="ff1 ls1 ws3">Springer-V<span class="_0 blank"></span>erlag Heidelb<span class="_1 blank"> </span>erg, New Y<span class="_0 blank"></span>ork 1997, 2000, 2005</span></div><div class="t m0 x0 h6 y7 ff1 fs3 fc0 sc0 ls1 ws4">This is an electronic v<span class="_2 blank"></span>ersion of the third (2005) edition of the ab<span class="_1 blank"> </span>ov<span class="_2 blank"></span>e</div><div class="t m0 x0 h6 y8 ff1 fs3 fc0 sc0 ls1 ws5">Springer<span class="_3 blank"> </span>b o ok,<span class="_3 blank"> </span>from<span class="_3 blank"> </span>their<span class="_3 blank"> </span>series<span class="_3 blank"> </span><span class="ff3 ws6">Gr<span class="_2 blank"></span>aduate<span class="_3 blank"> </span>T<span class="_0 blank"></span>exts<span class="_4 blank"> </span>in<span class="_4 blank"> </span>Mathematics <span class="ff1 ls2 ws7">,v<span class="_5 blank"></span><span class="ls1 ws8">ol. 173.</span></span></span></div><div class="t m0 x0 h6 y9 ff1 fs3 fc0 sc0 ls1 ws9">The cross-references in the text and in the margins are active links:<span class="_6 blank"> </span>clic<span class="_2 blank"></span>k</div><div class="t m0 x0 h6 ya ff1 fs3 fc0 sc0 ls1 wsa">on them to b<span class="_1 blank"> </span>e tak<span class="_2 blank"></span>en to the appropriate page.</div><div class="t m0 x0 h6 yb ff1 fs3 fc0 sc0 ls1 wsb">The<span class="_7 blank"> </span>prin<span class="_2 blank"></span>ted<span class="_7 blank"> </span>edition<span class="_7 blank"> </span>of<span class="_7 blank"> </span>this<span class="_7 blank"> </span>b o ok<span class="_7 blank"> </span>can<span class="_7 blank"> </span>b e<span class="_7 blank"> </span>ordered<span class="_7 blank"> </span>via</div><div class="t m0 x3 h7 yc ff4 fs4 fc0 sc0 ls1 wsc">h<span class="_2 blank"></span>ttp://www.math.uni-ham<span class="_2 blank"></span>burg.de/home/diestel/b o oks/graph.theory/</div></div><a class="l" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/"><div class="d m1" style="border-style:none;position:absolute;left:90.818890px;bottom:154.247223px;width:287.000000px;height:12.000000px;background-color:rgba(255,255,255,0.000001);"></div></a><a class="l" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/orders.html"><div class="d m1" style="border-style:none;position:absolute;left:128.704890px;bottom:104.137223px;width:24.096000px;height:12.048000px;background-color:rgba(255,255,255,0.000001);"></div></a></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-31.181110,-178.752777]}'></div></div> <div id="pf2" class="pf w3 h8" data-page-no="2"><div class="pc pc2 w3 h8"><img class="bi x4 yd w4 h1" alt="" src="https://files.passeidireto.com/569c7f44-7960-452b-bd43-a9ca6943a2c9/bg2.png"><div class="c x1 ye w5 h9"><div class="t m0 x4 ha yf ff5 fs5 fc0 sc0 ls1 wse">Preface</div><div class="t m0 x0 h6 y10 ff5 fs3 fc0 sc0 ls1 wsf">Almost<span class="_3 blank"> </span>tw<span class="_2 blank"></span>o<span class="_3 blank"> </span>decades<span class="_3 blank"> </span>ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e<span class="_3 blank"> </span>passed<span class="_3 blank"> </span>since<span class="_3 blank"> </span>the<span class="_3 blank"> </span>app earance<span class="_3 blank"> </span>of<span class="_3 blank"> </span>those<span class="_4 blank"> </span>graph<span class="_3 blank"> </span>the-</div><div class="t m0 x0 h6 y11 ff5 fs3 fc0 sc0 ls1 ws10">ory<span class="_7 blank"> </span>texts<span class="_8 blank"> </span>that<span class="_7 blank"> </span>still<span class="_8 blank"> </span>set<span class="_7 blank"> </span>the<span class="_8 blank"> </span>agenda<span class="_7 blank"> </span>for<span class="_8 blank"> </span>most<span class="_7 blank"> </span>introductory<span class="_8 blank"> </span>courses<span class="_7 blank"> </span>taught</div><div class="t m0 x0 h6 y12 ff5 fs3 fc0 sc0 ls1 ws11">to da<span class="_2 blank"></span>y<span class="_0 blank"></span>.<span class="_9 blank"> </span>The<span class="_6 blank"> </span>canon<span class="_6 blank"> </span>created<span class="_6 blank"> </span>by<span class="_6 blank"> </span>those<span class="_6 blank"> </span>b o oks<span class="_6 blank"> </span>has<span class="_6 blank"> </span>help ed<span class="_6 blank"> </span>to<span class="_a blank"> </span>iden<span class="_2 blank"></span>tify<span class="_6 blank"> </span>some</div><div class="t m0 x0 h6 y13 ff5 fs3 fc0 sc0 ls1 ws12">main \ufb01elds of study and research, and will doubtless con<span class="_2 blank"></span>tin<span class="_2 blank"></span>ue to in\ufb02uence</div><div class="t m0 x0 h6 y14 ff5 fs3 fc0 sc0 ls1 ws13">the dev<span class="_2 blank"></span>elopmen<span class="_2 blank"></span>t of the discipline for some time to come.</div><div class="t m0 x5 h6 y15 ff5 fs3 fc0 sc0 ls3 ws14">Ye <span class="ls4 ws15">tm<span class="_b blank"></span><span class="ls1 ws16">uc<span class="_2 blank"></span>h<span class="_8 blank"> </span>has<span class="_8 blank"> </span>happ ened<span class="_6 blank"> </span>in<span class="_8 blank"> </span>those<span class="_8 blank"> </span>20<span class="_6 blank"> </span>y<span class="_2 blank"></span>ears,<span class="_8 blank"> </span>in<span class="_6 blank"> </span>graph<span class="_8 blank"> </span>theory<span class="_8 blank"> </span>no<span class="_6 blank"> </span>less</span></span></div><div class="t m0 x0 h6 y16 ff5 fs3 fc0 sc0 ls1 ws17">than<span class="_3 blank"> </span>elsewhere:<span class="_8 blank"> </span>deep<span class="_3 blank"> </span>new<span class="_3 blank"> </span>theorems<span class="_c blank"> </span>ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e<span class="_c blank"> </span>b een<span class="_3 blank"> </span>found,<span class="_3 blank"> </span>seemingly<span class="_3 blank"> </span>disparate</div><div class="t m0 x0 h6 y17 ff5 fs3 fc0 sc0 ls1 ws18">metho ds<span class="_4 blank"> </span>and<span class="_4 blank"> </span>results<span class="_4 blank"> </span>ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e<span class="_4 blank"> </span>become<span class="_4 blank"> </span>interrelated,<span class="_4 blank"> </span>en<span class="_2 blank"></span>tire<span class="_4 blank"> </span>new<span class="_4 blank"> </span>branc<span class="_2 blank"></span>hes<span class="_4 blank"> </span>ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e</div><div class="t m0 x0 h6 y18 ff5 fs3 fc0 sc0 ls1 ws19">arisen.<span class="_9 blank"> </span>T<span class="_0 blank"></span>o name just a few such dev<span class="_2 blank"></span>elopmen<span class="_2 blank"></span>ts, one ma<span class="_2 blank"></span>y think of how</div><div class="t m0 x0 h6 y19 ff5 fs3 fc0 sc0 ls1 ws17">the<span class="_d blank"> </span>new<span class="_d blank"> </span>notion<span class="_d blank"> </span>of<span class="_d blank"> </span>list<span class="_d blank"> </span>colouring<span class="_d blank"> </span>has<span class="_d blank"> </span>bridged<span class="_d blank"> </span>the<span class="_d blank"> </span>gulf<span class="_d blank"> </span>b etw<span class="_2 blank"></span>een<span class="_d blank"> </span>in<span class="_2 blank"></span>v<span class="_0 blank"></span>ari-</div><div class="t m0 x0 h6 y1a ff5 fs3 fc0 sc0 ls1 ws1a">an<span class="_2 blank"></span>ts<span class="_a blank"> </span>such<span class="_a blank"> </span>as<span class="_a blank"> </span>av<span class="_2 blank"></span>erage<span class="_a blank"> </span>degree<span class="_d blank"> </span>and<span class="_a blank"> </span>c<span class="_2 blank"></span>hromatic<span class="_a blank"> </span>num<span class="_2 blank"></span>ber,<span class="_d blank"> </span>how<span class="_a blank"> </span>probabilistic</div><div class="t m0 x0 h6 y1b ff5 fs3 fc0 sc0 ls1 ws18">metho ds<span class="_4 blank"> </span>and<span class="_3 blank"> </span>the<span class="_4 blank"> </span>regularit<span class="_2 blank"></span>y<span class="_3 blank"> </span>lemma<span class="_4 blank"> </span>ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e<span class="_4 blank"> </span>perv<span class="_2 blank"></span>aded<span class="_3 blank"> </span>extremal<span class="_4 blank"> </span>graph<span class="_3 blank"> </span>t heory</div><div class="t m0 x0 h6 y1c ff5 fs3 fc0 sc0 ls1 ws1b">and Ramsey theory<span class="_0 blank"></span>, or how the en<span class="_2 blank"></span>tirely new \ufb01eld of graph minors and</div><div class="t m0 x0 h6 y1d ff5 fs3 fc0 sc0 ls1 ws1c">tree-decomp ositions<span class="_8 blank"> </span>has<span class="_8 blank"> </span>brought<span class="_8 blank"> </span>standard<span class="_8 blank"> </span>metho ds<span class="_8 blank"> </span>of<span class="_6 blank"> </span>surface<span class="_8 blank"> </span>top ology</div><div class="t m0 x0 h6 y1e ff5 fs3 fc0 sc0 ls1 ws1a">to<span class="_7 blank"> </span>b ear<span class="_7 blank"> </span>on<span class="_7 blank"> </span>long-standing<span class="_7 blank"> </span>algorithmic<span class="_7 blank"> </span>graph<span class="_7 blank"> </span>problems.</div><div class="t m0 x5 h6 y1f ff5 fs3 fc0 sc0 ls1 ws1d">Clearly<span class="_0 blank"></span>, then, the time has come for a reappraisal:<span class="_a blank"> </span><span class="ff6 ws1e">what<span class="_7 blank"> </span>are,<span class="_4 blank"> </span>to day<span class="_0 blank"></span>,</span></div><div class="t m0 x0 h6 y20 ff6 fs3 fc0 sc0 ls1 ws1c">the<span class="_8 blank"> </span>essen<span class="_2 blank"></span>tial<span class="_8 blank"> </span>areas,<span class="_8 blank"> </span>metho ds<span class="_8 blank"> </span>and<span class="_6 blank"> </span>results<span class="_8 blank"> </span>that<span class="_8 blank"> </span>should<span class="_8 blank"> </span>form<span class="_8 blank"> </span>the<span class="_8 blank"> </span>centre<span class="_7 blank"> </span>of</div><div class="t m0 x0 h6 y21 ff6 fs3 fc0 sc0 ls1 ws10">an<span class="_4 blank"> </span>in<span class="_2 blank"></span>troductory<span class="_4 blank"> </span>graph<span class="_4 blank"> </span>theory<span class="_4 blank"> </span>course<span class="_4 blank"> </span>aiming<span class="_3 blank"> </span>to<span class="_4 blank"> </span>equip<span class="_4 blank"> </span>its<span class="_4 blank"> </span>audience<span class="_4 blank"> </span>for<span class="_4 blank"> </span>th<span class="_2 blank"></span>e</div><div class="t m0 x0 h6 y22 ff6 fs3 fc0 sc0 ls1 ws1f">most lik<span class="_2 blank"></span>ely dev<span class="_2 blank"></span>elopmen<span class="_2 blank"></span>ts ahead?</div><div class="t m0 x5 h6 y23 ff5 fs3 fc0 sc0 ls5 ws20">Ih<span class="_e blank"></span><span class="ls6 ws21">ave <span class="ls1 ws22">tried in this b<span class="_1 blank"> </span>o<span class="_1 blank"> </span>ok to o\ufb00er material for suc<span class="_2 blank"></span>h a course.<span class="_f blank"> </span>In</span></span></div><div class="t m0 x0 h6 y24 ff5 fs3 fc0 sc0 ls1 ws23">view of the increasing complexit<span class="_2 blank"></span>y and maturit<span class="_2 blank"></span>y of the sub<span class="_10 blank"> </span>ject, I hav<span class="_2 blank"></span>e</div><div class="t m0 x0 h6 y25 ff5 fs3 fc0 sc0 ls1 ws1a">brok<span class="_2 blank"></span>en<span class="_4 blank"> </span>with<span class="_7 blank"> </span>the<span class="_7 blank"> </span>tradition<span class="_4 blank"> </span>of<span class="_7 blank"> </span>attempting<span class="_4 blank"> </span>to<span class="_7 blank"> </span>co<span class="_2 blank"></span>v<span class="_2 blank"></span>er<span class="_4 blank"> </span>b oth<span class="_7 blank"> </span>theory<span class="_4 blank"> </span>and<span class="_7 blank"> </span>appli-</div><div class="t m0 x0 h6 y26 ff5 fs3 fc0 sc0 ls1 ws10">cations:<span class="_a blank"> </span>this<span class="_7 blank"> </span>b o ok<span class="_4 blank"> </span>o\ufb00ers<span class="_7 blank"> </span>an<span class="_7 blank"> </span>in<span class="_2 blank"></span>troduction<span class="_7 blank"> </span>to<span class="_7 blank"> </span>the<span class="_4 blank"> </span>theory<span class="_7 blank"> </span>of<span class="_7 blank"> </span>graphs<span class="_4 blank"> </span>as<span class="_7 blank"> </span>part</div><div class="t m0 x0 h6 y27 ff5 fs3 fc0 sc0 ls1 ws24">of (pure) mathematics;<span class="_6 blank"> </span>it contains neither explicit algorithms nor \u2018real</div><div class="t m0 x0 h6 y28 ff5 fs3 fc0 sc0 ls1 ws17">w<span class="_2 blank"></span>orld\u2019<span class="_8 blank"> </span>applications.<span class="_11 blank"> </span>My<span class="_8 blank"> </span>hop e<span class="_8 blank"> </span>is<span class="_8 blank"> </span>that<span class="_8 blank"> </span>the<span class="_8 blank"> </span>p otential<span class="_7 blank"> </span>for<span class="_8 blank"> </span>depth<span class="_8 blank"> </span>gained<span class="_8 blank"> </span>by</div><div class="t m0 x0 h6 y29 ff5 fs3 fc0 sc0 ls1 ws25">this restriction in scop<span class="_1 blank"> </span>e will serv<span class="_2 blank"></span>e students of computer science as m<span class="_2 blank"></span>uc<span class="_2 blank"></span>h</div><div class="t m0 x0 h6 y2a ff5 fs3 fc0 sc0 ls1 ws1a">as<span class="_4 blank"> </span>their<span class="_4 blank"> </span>peers<span class="_4 blank"> </span>in<span class="_4 blank"> </span>mathematics:<span class="_a blank"> </span>assuming<span class="_4 blank"> </span>that<span class="_4 blank"> </span>they<span class="_4 blank"> </span>prefer<span class="_4 blank"> </span>algorithms<span class="_4 blank"> </span>but</div><div class="t m0 x0 h6 y2b ff5 fs3 fc0 sc0 ls1 ws1a">will<span class="_8 blank"> </span>b ene\ufb01t<span class="_8 blank"> </span>from<span class="_8 blank"> </span>an<span class="_6 blank"> </span>encoun<span class="_2 blank"></span>ter<span class="_8 blank"> </span>with<span class="_8 blank"> </span>pure<span class="_8 blank"> </span>mathematics<span class="_8 blank"> </span>of<span class="_8 blank"> </span><span class="ff6 ws26">some </span><span class="ws27">kind, it</span></div><div class="t m0 x0 h6 y2c ff5 fs3 fc0 sc0 ls1 ws28">seems<span class="_3 blank"> </span>an<span class="_4 blank"> </span>ideal<span class="_3 blank"> </span>opp ortunity<span class="_3 blank"> </span>to<span class="_4 blank"> </span>look<span class="_4 blank"> </span>for<span class="_3 blank"> </span>this<span class="_4 blank"> </span>close<span class="_3 blank"> </span>to<span class="_4 blank"> </span>w<span class="_2 blank"></span>here<span class="_12 blank"> </span>their<span class="_3 blank"> </span>heart<span class="_12 blank"> </span>lies!</div><div class="t m0 x5 h6 y2d ff5 fs3 fc0 sc0 ls1 ws29">In the selection and presen<span class="_2 blank"></span>tation of material,<span class="_d blank"> </span>I hav<span class="_2 blank"></span>e tried to ac-</div><div class="t m0 x0 h6 y2e ff5 fs3 fc0 sc0 ls1 ws2a">commo<span class="_1 blank"> </span>date t<span class="_2 blank"></span>w<span class="_2 blank"></span>o con\ufb02icting goals.<span class="_13 blank"> </span>On the one hand, I<span class="_a blank"> </span>b<span class="_1 blank"> </span>elieve that an</div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf3" class="pf w3 h8" data-page-no="3"><div class="pc pc3 w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff5 fs3 fc0 sc0 ls7 ws2b">viii <span class="ff7 fs6 ls1 ws2c">Preface</span></div><div class="t m0 x0 h6 y30 ff5 fs3 fc0 sc0 ls1 ws10">in<span class="_2 blank"></span>tro ductory<span class="_7 blank"> </span>text<span class="_7 blank"> </span>should<span class="_7 blank"> </span>be<span class="_7 blank"> </span>lean<span class="_7 blank"> </span>and<span class="_7 blank"> </span>concentrate<span class="_4 blank"> </span>on<span class="_7 blank"> </span>the<span class="_7 blank"> </span>essential,<span class="_4 blank"> </span>so<span class="_7 blank"> </span>as</div><div class="t m0 x0 h6 y31 ff5 fs3 fc0 sc0 ls1 ws2d">to o\ufb00er guidance to those new to the \ufb01eld.<span class="_a blank"> </span>As a graduate text, moreov<span class="_2 blank"></span>er,</div><div class="t m0 x0 h6 y32 ff5 fs3 fc0 sc0 ls1 ws2e">it should get to the heart of the matter quickly:<span class="_a blank"> </span>after all,<span class="_8 blank"> </span>the idea is to</div><div class="t m0 x0 h6 y33 ff5 fs3 fc0 sc0 ls1 ws2f">con<span class="_2 blank"></span>v<span class="_2 blank"></span>ey at least an impression of the depth and metho<span class="_1 blank"> </span>ds of the sub<span class="_1 blank"> </span>j<span class="_1 blank"> </span>ect.</div><div class="t m0 x0 h6 y34 ff5 fs3 fc0 sc0 ls1 ws1a">On<span class="_d blank"> </span>the<span class="_d blank"> </span>other<span class="_d blank"> </span>hand,<span class="_14 blank"> </span>it<span class="_d blank"> </span>has<span class="_d blank"> </span>b een<span class="_d blank"> </span>m<span class="_2 blank"></span>y<span class="_d blank"> </span>particular<span class="_d blank"> </span>concern<span class="_d blank"> </span>to<span class="_d blank"> </span>write<span class="_d blank"> </span>with</div><div class="t m0 x0 h6 y35 ff5 fs3 fc0 sc0 ls1 ws30">su\ufb03cien<span class="_2 blank"></span>t detail to mak<span class="_2 blank"></span>e the text enjoy<span class="_2 blank"></span>able and easy to read:<span class="_15 blank"> </span>guiding</div><div class="t m0 x0 h6 y36 ff5 fs3 fc0 sc0 ls1 ws31">questions and ideas will b<span class="_1 blank"> </span>e discussed explicitly<span class="_0 blank"></span>, and all pro<span class="_1 blank"> </span>ofs presen<span class="_2 blank"></span>ted</div><div class="t m0 x0 h6 y37 ff5 fs3 fc0 sc0 ls1 ws17">will<span class="_7 blank"> </span>b e<span class="_7 blank"> </span>rigorous<span class="_7 blank"> </span>and<span class="_7 blank"> </span>complete.</div><div class="t m0 x5 h6 y38 ff5 fs3 fc0 sc0 ls9 ws32">At<span class="_16 blank"></span><span class="ls1 ws33">ypical c<span class="_2 blank"></span>hapter, therefore, b<span class="_1 blank"> </span>egins with a brief discussion of what</span></div><div class="t m0 x0 h6 y39 ff5 fs3 fc0 sc0 ls1 ws34">are the guiding questions in the area it cov<span class="_2 blank"></span>ers, con<span class="_2 blank"></span>tin<span class="_2 blank"></span>ues with a succinct</div><div class="t m0 x0 h6 y3a ff5 fs3 fc0 sc0 ls1 ws35">accoun<span class="_2 blank"></span>t<span class="_d blank"> </span>of<span class="_14 blank"> </span>its<span class="_d blank"> </span>classic<span class="_d blank"> </span>results<span class="_14 blank"> </span>(often<span class="_d blank"> </span>with<span class="_d blank"> </span>simpli\ufb01ed<span class="_14 blank"> </span>pro ofs),<span class="_14 blank"> </span>and<span class="_14 blank"> </span>then</div><div class="t m0 x0 h6 y3b ff5 fs3 fc0 sc0 ls1 ws36">presen<span class="_2 blank"></span>ts<span class="_6 blank"> </span>one<span class="_6 blank"> </span>or<span class="_a blank"> </span>tw<span class="_2 blank"></span>o<span class="_8 blank"> </span>deep er<span class="_a blank"> </span>theorems<span class="_6 blank"> </span>that<span class="_6 blank"> </span>bring<span class="_a blank"> </span>out<span class="_6 blank"> </span>the<span class="_6 blank"> </span>ful l<span class="_6 blank"> </span>\ufb02av<span class="_2 blank"></span>our<span class="_8 blank"> </span>of</div><div class="t m0 x0 h6 y3c ff5 fs3 fc0 sc0 ls1 ws37">that<span class="_12 blank"> </span>area.<span class="_a blank"> </span>The<span class="_12 blank"> </span>pro ofs<span class="_12 blank"> </span>of<span class="_4 blank"> </span>these<span class="_12 blank"> </span>latter<span class="_12 blank"> </span>results<span class="_4 blank"> </span>are<span class="_12 blank"> </span>typically<span class="_3 blank"> </span>preceded<span class="_12 blank"> </span>by<span class="_3 blank"> </span>(or</div><div class="t m0 x0 h6 y3d ff5 fs3 fc0 sc0 ls1 ws38">in<span class="_2 blank"></span>tersp<span class="_1 blank"> </span>ersed with) an informal accoun<span class="_2 blank"></span>t of their main ideas, but are then</div><div class="t m0 x0 h6 y3e ff5 fs3 fc0 sc0 ls1 ws39">presen<span class="_2 blank"></span>ted formally at the same lev<span class="_2 blank"></span>el of detail as their simpler counter-</div><div class="t m0 x0 h6 y3f ff5 fs3 fc0 sc0 ls1 ws35">parts.<span class="_a blank"> </span>I<span class="_7 blank"> </span>so on<span class="_7 blank"> </span>noticed<span class="_7 blank"> </span>that,<span class="_7 blank"> </span>as<span class="_7 blank"> </span>a<span class="_4 blank"> </span>consequence,<span class="_7 blank"> </span>some<span class="_7 blank"> </span>of<span class="_7 blank"> </span>those<span class="_7 blank"> </span>proofs<span class="_7 blank"> </span>came</div><div class="t m0 x0 h6 y40 ff5 fs3 fc0 sc0 ls1 ws1a">out<span class="_d blank"> </span>rather<span class="_d blank"> </span>longer<span class="_d blank"> </span>in<span class="_a blank"> </span>print<span class="_d blank"> </span>than<span class="_d blank"> </span>seemed<span class="_a blank"> </span>fair<span class="_d blank"> </span>to<span class="_d blank"> </span>their<span class="_d blank"> </span>often<span class="_d blank"> </span>beautifully</div><div class="t m0 x0 h6 y41 ff5 fs3 fc0 sc0 ls1 ws3a">simple conception.<span class="_a blank"> </span>I would hope, how<span class="_2 blank"></span>ev<span class="_2 blank"></span>er, that ev<span class="_2 blank"></span>en for the professional</div><div class="t m0 x0 h6 y42 ff5 fs3 fc0 sc0 ls1 ws35">reader<span class="_6 blank"> </span>the<span class="_8 blank"> </span>relatively<span class="_8 blank"> </span>detailed<span class="_6 blank"> </span>account<span class="_8 blank"> </span>of<span class="_6 blank"> </span>those<span class="_6 blank"> </span>pro ofs<span class="_6 blank"> </span>will<span class="_6 blank"> </span>at<span class="_6 blank"> </span>least<span class="_6 blank"> </span>help</div><div class="t m0 x0 h6 y43 ff5 fs3 fc0 sc0 ls1 ws3b">to minimize reading time<span class="ff8 ls8 ws3c">...</span></div><div class="t m0 x5 h6 y44 ff5 fs3 fc0 sc0 ls1 ws1a">If<span class="_6 blank"> </span>desired,<span class="_a blank"> </span>this<span class="_6 blank"> </span>text<span class="_6 blank"> </span>can<span class="_6 blank"> </span>b e<span class="_6 blank"> </span>used<span class="_6 blank"> </span>for<span class="_a blank"> </span>a<span class="_6 blank"> </span>lecture<span class="_6 blank"> </span>course<span class="_6 blank"> </span>with<span class="_6 blank"> </span>little<span class="_6 blank"> </span>or</div><div class="t m0 x0 h6 y45 ff5 fs3 fc0 sc0 ls1 ws3d">no further preparation.<span class="_d blank"> </span>The simplest wa<span class="_2 blank"></span>y to do this w<span class="_2 blank"></span>ould be to follow</div><div class="t m0 x0 h6 y46 ff5 fs3 fc0 sc0 ls1 ws3e">the order of presen<span class="_2 blank"></span>tation,<span class="_d blank"> </span>c<span class="_2 blank"></span>hapter b<span class="_2 blank"></span>y c<span class="_2 blank"></span>hapter:<span class="_9 blank"> </span>apart from t<span class="_2 blank"></span>w<span class="_2 blank"></span>o clearly</div><div class="t m0 x0 h6 y47 ff5 fs3 fc0 sc0 ls1 ws35">mark<span class="_2 blank"></span>ed<span class="_4 blank"> </span>exceptions,<span class="_7 blank"> </span>an<span class="_2 blank"></span>y<span class="_4 blank"> </span>results<span class="_7 blank"> </span>used<span class="_4 blank"> </span>in<span class="_7 blank"> </span>the<span class="_4 blank"> </span>pro of<span class="_7 blank"> </span>of<span class="_4 blank"> </span>others<span class="_7 blank"> </span>precede<span class="_4 blank"> </span>them</div><div class="t m0 x0 h6 y48 ff5 fs3 fc0 sc0 ls1 ws3f">in the text.</div><div class="t m0 x5 h6 y49 ff5 fs3 fc0 sc0 ls1 ws40">Alternativ<span class="_2 blank"></span>ely<span class="_0 blank"></span>, a lecturer may wish to divide the material in<span class="_2 blank"></span>to an easy</div><div class="t m0 x0 h6 y4a ff5 fs3 fc0 sc0 ls1 ws41">basic course for one semester, and a more challenging follo<span class="_2 blank"></span>w-up course</div><div class="t m0 x0 h6 y4b ff5 fs3 fc0 sc0 ls1 ws42">for another.<span class="_a blank"> </span>T<span class="_0 blank"></span>o help with the preparation of courses deviating from the</div><div class="t m0 x0 h6 y4c ff5 fs3 fc0 sc0 ls1 ws43">order of presen<span class="_2 blank"></span>tation, I ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e listed in the margin next to eac<span class="_2 blank"></span>h pro<span class="_1 blank"> </span>of the</div><div class="t m0 x0 h6 y4d ff5 fs3 fc0 sc0 ls1 ws35">reference<span class="_6 blank"> </span>num<span class="_2 blank"></span>b ers<span class="_6 blank"> </span>of<span class="_a blank"> </span>those<span class="_a blank"> </span>results<span class="_a blank"> </span>that<span class="_a blank"> </span>are<span class="_a blank"> </span>used<span class="_a blank"> </span>in<span class="_a blank"> </span>that<span class="_6 blank"> </span>p ro of.<span class="_13 blank"> </span>These</div><div class="t m0 x0 h6 y4e ff5 fs3 fc0 sc0 ls1 ws44">references are giv<span class="_2 blank"></span>en in round brack<span class="_2 blank"></span>ets:<span class="_14 blank"> </span>for example, a reference (4.1.2)</div><div class="t m0 x0 h6 y4f ff5 fs3 fc0 sc0 ls1 ws45">in the margin next to the pro<span class="_1 blank"> </span>of of Theorem 4.3.2 indicates that Lemma</div><div class="t m0 x0 h6 y50 ff5 fs3 fc0 sc0 ls1 ws46">4.1.2 will b<span class="_1 blank"> </span>e used in this pro<span class="_1 blank"> </span>of.<span class="_d blank"> </span>Corresp<span class="_1 blank"> </span>ondingly<span class="_0 blank"></span>, in the margin next to</div><div class="t m0 x0 h6 y51 ff5 fs3 fc0 sc0 ls1 ws47">Lemma<span class="_8 blank"> </span>4.1.2<span class="_7 blank"> </span>there<span class="_8 blank"> </span>is<span class="_8 blank"> </span>a<span class="_8 blank"> </span>reference<span class="_7 blank"> </span>[ 4.3.2 ]<span class="_8 blank"> </span>(in<span class="_8 blank"> </span>square<span class="_8 blank"> </span>brack<span class="_2 blank"></span>ets)<span class="_7 blank"> </span>informing</div><div class="t m0 x0 h6 y52 ff5 fs3 fc0 sc0 ls1 ws35">the<span class="_8 blank"> </span>reader<span class="_8 blank"> </span>that<span class="_8 blank"> </span>this<span class="_8 blank"> </span>lemma<span class="_8 blank"> </span>will<span class="_8 blank"> </span>b e<span class="_8 blank"> </span>used<span class="_6 blank"> </span>in<span class="_8 blank"> </span>the<span class="_8 blank"> </span>pro of<span class="_8 blank"> </span>of<span class="_8 blank"> </span>Theorem<span class="_8 blank"> </span>4.3.2.</div><div class="t m0 x0 h6 y53 ff5 fs3 fc0 sc0 ls1 ws17">Note<span class="_3 blank"> </span>that<span class="_3 blank"> </span>this<span class="_3 blank"> </span>system<span class="_3 blank"> </span>applies<span class="_c blank"> </span>b etw<span class="_2 blank"></span>een<span class="_3 blank"> </span>di\ufb00eren<span class="_2 blank"></span>t<span class="_3 blank"> </span>sections<span class="_c blank"> </span>onl y<span class="_3 blank"> </span>(of<span class="_3 blank"> </span>the<span class="_3 blank"> </span>same</div><div class="t m0 x0 h6 y54 ff5 fs3 fc0 sc0 ls1 ws48">or of di\ufb00eren<span class="_2 blank"></span>t c<span class="_2 blank"></span>hapters):<span class="_6 blank"> </span>the sections themselves are written as units and</div><div class="t m0 x0 h6 y55 ff5 fs3 fc0 sc0 ls1 ws49">b est<span class="_7 blank"> </span>read<span class="_7 blank"> </span>in<span class="_7 blank"> </span>their<span class="_7 blank"> </span>order<span class="_7 blank"> </span>of<span class="_7 blank"> </span>presentation.</div><div class="t m0 x5 h6 y56 ff5 fs3 fc0 sc0 ls1 ws4a">The mathematical prerequisites for this b<span class="_1 blank"> </span>o<span class="_1 blank"> </span>ok,<span class="_d blank"> </span>as for most graph</div><div class="t m0 x0 h6 y57 ff5 fs3 fc0 sc0 ls1 ws4b">theory texts, are minimal:<span class="_a blank"> </span>a \ufb01rst grounding in linear algebra is assumed</div><div class="t m0 x0 h6 y58 ff5 fs3 fc0 sc0 ls1 ws4c">for Chapter 1.9 and once in Chapter 5.5,<span class="_d blank"> </span>some basic top<span class="_1 blank"> </span>ological con-</div><div class="t m0 x0 h6 y59 ff5 fs3 fc0 sc0 ls1 ws4d">cepts<span class="_4 blank"> </span>ab out<span class="_7 blank"> </span>the<span class="_4 blank"> </span>Euclidean<span class="_4 blank"> </span>plane<span class="_7 blank"> </span>and<span class="_4 blank"> </span>3-space<span class="_4 blank"> </span>are<span class="_7 blank"> </span>used<span class="_4 blank"> </span>in<span class="_4 blank"> </span>Chapter<span class="_7 blank"> </span>4,<span class="_4 blank"> </span>and</div><div class="t m0 x0 h6 y5a ff5 fs3 fc0 sc0 ls1 ws4e">a previous \ufb01rst encoun<span class="_2 blank"></span>ter with elemen<span class="_2 blank"></span>tary probabilit<span class="_2 blank"></span>y will help with</div><div class="t m0 x0 h6 y5b ff5 fs3 fc0 sc0 ls1 ws4f">Chapter 11.<span class="_17 blank"> </span>(Ev<span class="_2 blank"></span>en here, all that is assumed formally is the knowledge</div><div class="t m0 x0 h6 y5c ff5 fs3 fc0 sc0 ls1 ws1e">of<span class="_4 blank"> </span>basic<span class="_4 blank"> </span>de\ufb01nitions:<span class="_a blank"> </span>the<span class="_4 blank"> </span>few<span class="_4 blank"> </span>probabilistic<span class="_4 blank"> </span>to ols<span class="_4 blank"> </span>used<span class="_7 blank"> </span>are<span class="_12 blank"> </span>developed<span class="_4 blank"> </span>in<span class="_4 blank"> </span>the</div></div><a class="l" href="#pf60" data-dest-detail='[96,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:351.910100px;bottom:189.096497px;width:24.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a><a class="l" href="#pf6b" data-dest-detail='[107,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:256.910100px;bottom:177.096497px;width:24.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a><a class="l" href="#pf60" data-dest-detail='[96,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:64.910100px;bottom:165.096497px;width:24.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a><a class="l" href="#pf60" data-dest-detail='[96,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:99.910100px;bottom:153.096497px;width:25.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a><a class="l" href="#pf6b" data-dest-detail='[107,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:214.910100px;bottom:153.096497px;width:24.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a><a class="l" href="#pf6b" data-dest-detail='[107,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:352.910100px;bottom:141.096497px;width:24.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf4" class="pf w3 h8" data-page-no="4"><div class="pc pc4 w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff7 fs6 fc0 sc0 ls1 ws50">Preface <span class="ff5 fs3 ws51">ix</span></div><div class="t m0 x0 h6 y30 ff5 fs3 fc0 sc0 ls1 ws1a">text.)<span class="_17 blank"> </span>There<span class="_6 blank"> </span>are<span class="_8 blank"> </span>tw<span class="_2 blank"></span>o<span class="_8 blank"> </span>areas<span class="_6 blank"> </span>of<span class="_8 blank"> </span>graph<span class="_6 blank"> </span>theory<span class="_6 blank"> </span>whic<span class="_2 blank"></span>h<span class="_8 blank"> </span>I<span class="_6 blank"> </span>\ufb01nd<span class="_6 blank"> </span>b oth<span class="_8 blank"> </span>fascinat-</div><div class="t m0 x0 h6 y5d ff5 fs3 fc0 sc0 ls1 ws52">ing<span class="_7 blank"> </span>and<span class="_4 blank"> </span>imp ortant,<span class="_4 blank"> </span>esp ecially<span class="_7 blank"> </span>from<span class="_7 blank"> </span>the<span class="_4 blank"> </span>p ersp ective<span class="_4 blank"> </span>of<span class="_7 blank"> </span>pure<span class="_7 blank"> </span>mathematics</div><div class="t m0 x0 h6 y5e ff5 fs3 fc0 sc0 ls1 ws53">adopted here, but which are not co<span class="_2 blank"></span>v<span class="_2 blank"></span>ered in this bo<span class="_1 blank"> </span>ok:<span class="_a blank"> </span>these are algebraic</div><div class="t m0 x0 h6 y5f ff5 fs3 fc0 sc0 ls1 ws54">graph theory and in\ufb01nite graphs.</div><div class="t m0 x5 h6 y60 ff5 fs3 fc0 sc0 lsd ws55">At <span class="ls1 ws56">the end of eac<span class="_2 blank"></span>h c<span class="_2 blank"></span>hapter,<span class="_d blank"> </span>there is a section with exercises and</span></div><div class="t m0 x0 h6 y61 ff5 fs3 fc0 sc0 ls1 ws57">another with bibliographical and historical notes.<span class="_a blank"> </span>Many of the exercises</div><div class="t m0 x0 h6 y62 ff5 fs3 fc0 sc0 ls1 ws58">w<span class="_2 blank"></span>ere c<span class="_2 blank"></span>hosen to complemen<span class="_2 blank"></span>t the main narrative of the text:<span class="_11 blank"> </span>they illus-</div><div class="t m0 x0 h6 y63 ff5 fs3 fc0 sc0 ls1 ws59">trate new concepts,<span class="_d blank"> </span>sho<span class="_2 blank"></span>w ho<span class="_2 blank"></span>w a new in<span class="_2 blank"></span>v<span class="_0 blank"></span>ariant relates to earlier ones,</div><div class="t m0 x0 h6 y64 ff5 fs3 fc0 sc0 ls1 ws5a">or indicate w<span class="_2 blank"></span>a<span class="_2 blank"></span>ys in whic<span class="_2 blank"></span>h a result stated in the text is b<span class="_1 blank"> </span>est possible.</div><div class="t m0 x0 hb y65 ff5 fs3 fc0 sc0 ls1 ws5b">P<span class="_2 blank"></span>articularly<span class="_7 blank"> </span>easy<span class="_7 blank"> </span>exercises<span class="_7 blank"> </span>are<span class="_7 blank"> </span>identi\ufb01ed<span class="_4 blank"> </span>by<span class="_7 blank"> </span>the<span class="_7 blank"> </span>superscript<span class="_7 blank"> </span><span class="ff9 fs7 lsa v1">\u2212</span><span class="ws5c v0">, the more</span></div><div class="t m0 x0 hc y66 ff5 fs3 fc0 sc0 ls1 ws5d">c<span class="_2 blank"></span>hallenging ones carry a <span class="ffa fs7 lsb v1">+</span><span class="ws5e">.<span class="_14 blank"> </span>The notes are intended to guide the reader</span></div><div class="t m0 x0 h6 y67 ff5 fs3 fc0 sc0 ls1 ws5f">on to further reading, in particular to any monographs or surv<span class="_2 blank"></span>ey articles</div><div class="t m0 x0 h6 y68 ff5 fs3 fc0 sc0 ls1 ws60">on the theme of that c<span class="_2 blank"></span>hapter.<span class="_a blank"> </span>They also o\ufb00er some historical and other</div><div class="t m0 x0 h6 y69 ff5 fs3 fc0 sc0 ls1 ws3f">remarks on the material presen<span class="_2 blank"></span>ted in the text.</div><div class="t m0 x5 h6 y6a ff5 fs3 fc0 sc0 ls1 ws37">Ends<span class="_7 blank"> </span>of<span class="_7 blank"> </span>pro ofs<span class="_8 blank"> </span>are<span class="_7 blank"> </span>marked<span class="_7 blank"> </span>b<span class="_2 blank"></span>y<span class="_7 blank"> </span>the<span class="_7 blank"> </span>symbol<span class="_7 blank"> </span><span class="ffb ws61">\ue001</span><span class="ws17">.<span class="_d blank"> </span>Where<span class="_8 blank"> </span>this<span class="_7 blank"> </span>symbol<span class="_7 blank"> </span>is</span></div><div class="t m0 x0 h6 y6b ff5 fs3 fc0 sc0 ls1 ws35">found<span class="_7 blank"> </span>directly<span class="_8 blank"> </span>b elow<span class="_7 blank"> </span>a<span class="_7 blank"> </span>formal<span class="_8 blank"> </span>assertion,<span class="_7 blank"> </span>it<span class="_8 blank"> </span>means<span class="_7 blank"> </span>that<span class="_8 blank"> </span>the<span class="_7 blank"> </span>pro of<span class="_8 blank"> </span>should</div><div class="t m0 x0 h6 y6c ff5 fs3 fc0 sc0 lse ws62">be <span class="ls1 ws1a">clear<span class="_4 blank"> </span>after<span class="_7 blank"> </span>what<span class="_4 blank"> </span>has<span class="_7 blank"> </span>been<span class="_7 blank"> </span>said\u2014a<span class="_4 blank"> </span>claim<span class="_7 blank"> </span>w<span class="_2 blank"></span>aiting<span class="_4 blank"> </span>to<span class="_7 blank"> </span>be<span class="_7 blank"> </span>ve<span class="_2 blank"></span>ri\ufb01ed!<span class="_a blank"> </span>There</span></div><div class="t m0 x0 h6 y6d ff5 fs3 fc0 sc0 ls1 ws63">are also some deep<span class="_1 blank"> </span>er theorems whic<span class="_2 blank"></span>h are stated, without pro<span class="_1 blank"> </span>of, as back-</div><div class="t m0 x0 h6 y6e ff5 fs3 fc0 sc0 ls1 ws35">ground<span class="_12 blank"> </span>information:<span class="_a blank"> </span>these<span class="_12 blank"> </span>can<span class="_4 blank"> </span>b e<span class="_12 blank"> </span>identi\ufb01ed<span class="_12 blank"> </span>by<span class="_3 blank"> </span>the<span class="_4 blank"> </span>absence<span class="_12 blank"> </span>of<span class="_4 blank"> </span>b oth<span class="_12 blank"> </span>pro of</div><div class="t m0 x0 h6 y6f ff5 fs3 fc0 sc0 ls1 ws64">and <span class="ffb ws61">\ue001</span>.</div><div class="t m0 x5 h6 y70 ff5 fs3 fc0 sc0 ls1 ws17">Almost<span class="_8 blank"> </span>every<span class="_8 blank"> </span>b ook<span class="_6 blank"> </span>contains<span class="_8 blank"> </span>errors,<span class="_8 blank"> </span>and<span class="_6 blank"> </span>this<span class="_8 blank"> </span>one<span class="_6 blank"> </span>will<span class="_8 blank"> </span>hardly<span class="_6 blank"> </span>b e<span class="_8 blank"> </span>an</div><div class="t m0 x0 h6 y71 ff5 fs3 fc0 sc0 ls1 ws1a">exception.<span class="_11 blank"> </span>I<span class="_6 blank"> </span>shall<span class="_8 blank"> </span>try<span class="_6 blank"> </span>to<span class="_8 blank"> </span>p ost<span class="_8 blank"> </span>on<span class="_6 blank"> </span>the<span class="_8 blank"> </span>W<span class="_0 blank"></span>eb<span class="_8 blank"> </span>any<span class="_8 blank"> </span>corrections<span class="_8 blank"> </span>that<span class="_8 blank"> </span>b ecome</div><div class="t m0 x0 h6 y72 ff5 fs3 fc0 sc0 ls1 ws65">necessary<span class="_0 blank"></span>.<span class="_f blank"> </span>The relev<span class="_2 blank"></span>an<span class="_2 blank"></span>t site ma<span class="_2 blank"></span>y c<span class="_2 blank"></span>hange in time, but will alwa<span class="_2 blank"></span>ys be</div><div class="t m0 x0 h6 y73 ff5 fs3 fc0 sc0 ls1 ws3f">accessible via the follo<span class="_2 blank"></span>wing t<span class="_2 blank"></span>w<span class="_2 blank"></span>o addresses:</div><div class="t m0 x2 h7 y74 ffc fs4 fc0 sc0 ls1 ws66">h<span class="_2 blank"></span>ttp://www.springer-n<span class="_2 blank"></span>y<span class="_0 blank"></span>.com/supplements/diestel/</div><div class="t m0 x2 h7 y75 ffc fs4 fc0 sc0 ls1 ws66">h<span class="_2 blank"></span>ttp://www.springer.de/catalog/h<span class="_2 blank"></span>tml-\ufb01les/deutsch/math/3540609180.h<span class="_2 blank"></span>tml</div><div class="t m0 x0 h6 y76 ff5 fs3 fc0 sc0 ls1 ws17">Please<span class="_7 blank"> </span>let<span class="_7 blank"> </span>me<span class="_7 blank"> </span>kno<span class="_2 blank"></span>w<span class="_7 blank"> </span>ab out<span class="_7 blank"> </span>an<span class="_2 blank"></span>y<span class="_7 blank"> </span>errors<span class="_7 blank"> </span>you<span class="_4 blank"> </span>\ufb01nd.</div><div class="t m0 x5 h6 y77 ff5 fs3 fc0 sc0 ls1 ws28">Little<span class="_8 blank"> </span>in<span class="_7 blank"> </span>a<span class="_8 blank"> </span>textb o ok<span class="_8 blank"> </span>is<span class="_8 blank"> </span>truly<span class="_8 blank"> </span>original:<span class="_d blank"> </span>even<span class="_7 blank"> </span>the<span class="_8 blank"> </span>style<span class="_7 blank"> </span>of<span class="_8 blank"> </span>writing<span class="_8 blank"> </span>and</div><div class="t m0 x0 h6 y78 ff5 fs3 fc0 sc0 ls1 ws1a">of<span class="_12 blank"> </span>presentation<span class="_3 blank"> </span>will<span class="_12 blank"> </span>inv<span class="_0 blank"></span>ariably<span class="_12 blank"> </span>b e<span class="_12 blank"> </span>in\ufb02uenced<span class="_12 blank"> </span>by<span class="_3 blank"> </span>examples.<span class="_a blank"> </span>The<span class="_12 blank"> </span>b o ok<span class="_12 blank"> </span>that</div><div class="t m0 x0 h6 y79 ff5 fs3 fc0 sc0 ls1 ws67">no doubt in\ufb02uenced me most is the classic GTM graph theory text by</div><div class="t m0 x0 h6 y7a ff5 fs3 fc0 sc0 ls1 ws68">Bollob´<span class="_18 blank"></span>as:<span class="_a blank"> </span>it w<span class="_2 blank"></span>as in the course recorded b<span class="_2 blank"></span>y this text that I learn<span class="_2 blank"></span>t m<span class="_2 blank"></span>y \ufb01rst</div><div class="t m0 x0 h6 y7b ff5 fs3 fc0 sc0 ls1 ws69">graph theory as a student.<span class="_17 blank"> </span>An<span class="_2 blank"></span>y<span class="_2 blank"></span>one who knows this bo<span class="_1 blank"> </span>ok well will feel</div><div class="t m0 x0 h6 y7c ff5 fs3 fc0 sc0 ls1 ws3b">its in\ufb02uence here, despite all di\ufb00erences in conten<span class="_2 blank"></span>ts and presen<span class="_2 blank"></span>tation.</div><div class="t m0 x5 h6 y7d ff5 fs3 fc0 sc0 ls1 ws6a">I should lik<span class="_2 blank"></span>e to thank all who gav<span class="_2 blank"></span>e so generously of their time,</div><div class="t m0 x0 h6 y7e ff5 fs3 fc0 sc0 ls1 ws17">kno<span class="_2 blank"></span>wledge<span class="_a blank"> </span>and<span class="_a blank"> </span>ad vice<span class="_a blank"> </span>in<span class="_a blank"> </span>connection<span class="_d blank"> </span>with<span class="_6 blank"> </span>thi s<span class="_a blank"> </span>b o ok.<span class="_19 blank"> </span>I<span class="_a blank"> </span>hav<span class="_2 blank"></span>e<span class="_a blank"> </span>bene\ufb01ted</div><div class="t m0 x0 h6 y7f ff5 fs3 fc0 sc0 ls1 ws6b">particularly<span class="_4 blank"> </span>from<span class="_7 blank"> </span>the<span class="_4 blank"> </span>help<span class="_7 blank"> </span>of<span class="_4 blank"> </span>N. Alon,<span class="_4 blank"> </span>G<span class="_1 blank"> </span>. Brigh<span class="_2 blank"></span>tw<span class="_2 blank"></span>ell,<span class="_4 blank"> </span>R. Gillett,<span class="_7 blank"> </span>R. Halin,</div><div class="t m0 x0 h6 y80 ff5 fs3 fc0 sc0 ls1 ws6c">M. Hin<span class="_2 blank"></span>tz,<span class="_7 blank"> </span>A. Huck,<span class="_7 blank"> </span>I. Leader,<span class="_7 blank"> </span>T.<span class="_c blank"> </span>\ue003<span class="_5 blank"></span>Luczak,<span class="_7 blank"> </span>W. Mader,<span class="_7 blank"> </span>V. R¨<span class="_18 blank"></span>odl,<span class="_8 blank"> </span>A.D. Scott,</div><div class="t m0 x0 hd y81 ff5 fs3 fc0 sc0 ls1 ws6d">P<span class="_0 blank"></span>.D. Seymour,<span class="_a blank"> </span>G. Simonyi,<span class="_6 blank"> </span>M.<span class="_c blank"> </span><span class="v2">\u02c7</span></div><div class="t m0 x6 h6 y81 ff5 fs3 fc0 sc0 ls1 ws6b">Sk<span class="_2 blank"></span>oviera,<span class="_a blank"> </span>R. Thomas,<span class="_a blank"> </span>C. Thomassen<span class="_a blank"> </span>and</div><div class="t m0 x0 h6 y82 ff5 fs3 fc0 sc0 ls3 ws6e">P. V<span class="ls1 ws6f">altr.<span class="_a blank"> </span>I<span class="_3 blank"> </span>am<span class="_12 blank"> </span>particularly<span class="_3 blank"> </span>grateful<span class="_12 blank"> </span>also<span class="_12 blank"> </span>to<span class="_3 blank"> </span>T<span class="_0 blank"></span>ommy<span class="_3 blank"> </span>R. Jensen,<span class="_12 blank"> </span>who<span class="_3 blank"> </span>taught</span></div><div class="t m0 x0 h6 y83 ff5 fs3 fc0 sc0 ls1 ws1a">me<span class="_3 blank"> </span>muc<span class="_2 blank"></span>h<span class="_3 blank"> </span>ab out<span class="_3 blank"> </span>colouring<span class="_12 blank"> </span>and<span class="_12 blank"> </span>all<span class="_3 blank"> </span>I<span class="_12 blank"> </span>know<span class="_3 blank"> </span>ab out<span class="_3 blank"> </span><span class="ff8 lsc">k</span><span class="ws70">-\ufb02ows, and who in<span class="_2 blank"></span>v<span class="_2 blank"></span>ested</span></div><div class="t m0 x0 h6 y84 ff5 fs3 fc0 sc0 ls1 ws35">immense<span class="_4 blank"> </span>amounts<span class="_12 blank"> </span>of<span class="_4 blank"> </span>diligence<span class="_4 blank"> </span>and<span class="_4 blank"> </span>energy<span class="_7 blank"> </span>in<span class="_12 blank"> </span>his<span class="_7 blank"> </span>proofreading<span class="_4 blank"> </span>of<span class="_7 blank"> </span>the<span class="_12 blank"> </span>pre-</div><div class="t m0 x0 h6 y85 ff5 fs3 fc0 sc0 ls1 ws28">liminary<span class="_7 blank"> </span>German<span class="_7 blank"> </span>ve<span class="_2 blank"></span>rsion<span class="_7 blank"> </span>of<span class="_7 blank"> </span>this<span class="_7 blank"> </span>b o ok.</div><div class="t m0 x0 h6 y86 ff5 fs3 fc0 sc0 ls1 ws71">Marc<span class="_2 blank"></span>h 1997<span class="_1a blank"> </span><span class="ffd ws51">RD</span></div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf5" class="pf w3 h8" data-page-no="5"><div class="pc pc5 w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff5 fs3 fc0 sc0 lsf">x<span class="ff7 fs6 ls1 ws2c">Preface</span></div><div class="t m0 x0 he y30 ffe fs3 fc0 sc0 ls1 ws72">Ab out<span class="_8 blank"> </span>the<span class="_6 blank"> </span>second<span class="_6 blank"> </span>edition</div><div class="t m0 x0 h6 y87 ff5 fs3 fc0 sc0 ls1 ws73">Naturally<span class="_0 blank"></span>,<span class="_12 blank"> </span>I<span class="_4 blank"> </span>am<span class="_12 blank"> </span>delighted<span class="_3 blank"> </span>at<span class="_4 blank"> </span>ha<span class="_2 blank"></span>ving<span class="_12 blank"> </span>to<span class="_12 blank"> </span>write<span class="_4 blank"> </span>this<span class="_12 blank"> </span>addendum<span class="_12 blank"> </span>so<span class="_4 blank"> </span>so on<span class="_12 blank"> </span>after</div><div class="t m0 x0 h6 y88 ff5 fs3 fc0 sc0 ls1 ws28">this<span class="_7 blank"> </span>b o ok<span class="_8 blank"> </span>came<span class="_8 blank"> </span>out<span class="_7 blank"> </span>in<span class="_8 blank"> </span>the<span class="_8 blank"> </span>summer<span class="_7 blank"> </span>of<span class="_8 blank"> </span>1997.<span class="_14 blank"> </span>It<span class="_7 blank"> </span>is<span class="_8 blank"> </span>particularly<span class="_8 blank"> </span>gratifying</div><div class="t m0 x0 h6 y89 ff5 fs3 fc0 sc0 ls1 ws17">to<span class="_4 blank"> </span>hear<span class="_7 blank"> </span>that<span class="_4 blank"> </span>p eople<span class="_7 blank"> </span>are<span class="_4 blank"> </span>gradually<span class="_7 blank"> </span>adopting<span class="_4 blank"> </span>it<span class="_7 blank"> </span>not<span class="_4 blank"> </span>only<span class="_7 blank"> </span>for<span class="_4 blank"> </span>t heir<span class="_4 blank"> </span>p ersonal</div><div class="t m0 x0 h6 y8a ff5 fs3 fc0 sc0 ls1 ws74">use but more and more also as a course text; this, after all, was m<span class="_2 blank"></span>y aim</div><div class="t m0 x0 h6 y8b ff5 fs3 fc0 sc0 ls1 ws75">when I wrote it,<span class="_d blank"> </span>and m<span class="_2 blank"></span>y excuse for agonizing more o<span class="_2 blank"></span>v<span class="_2 blank"></span>er presen<span class="_2 blank"></span>tation</div><div class="t m0 x0 h6 y8c ff5 fs3 fc0 sc0 ls1 ws76">than I migh<span class="_2 blank"></span>t otherwise hav<span class="_2 blank"></span>e done.</div><div class="t m0 x5 h6 y8d ff5 fs3 fc0 sc0 ls1 ws77">There<span class="_a blank"> </span>are<span class="_a blank"> </span>tw<span class="_2 blank"></span>o<span class="_6 blank"> </span>ma jor<span class="_a blank"> </span>changes.<span class="_1b blank"> </span>The<span class="_a blank"> </span>last<span class="_a blank"> </span>chapter<span class="_6 blank"> </span>on<span class="_a blank"> </span>grap<span class="_1 blank"> </span>h<span class="_a blank"> </span>minors</div><div class="t m0 x0 h6 y8e ff5 fs3 fc0 sc0 ls1 ws78">no<span class="_2 blank"></span>w giv<span class="_2 blank"></span>es a complete pro<span class="_1 blank"> </span>of of one of the ma<span class="_10 blank"> </span>jor results of the Rob<span class="_1 blank"> </span>ertson-</div><div class="t m0 x0 h6 y8f ff5 fs3 fc0 sc0 ls1 ws79">Seymour theory<span class="_0 blank"></span>, their theorem that excluding a graph as a minor b<span class="_1 blank"> </span>ounds</div><div class="t m0 x0 h6 y90 ff5 fs3 fc0 sc0 ls1 ws35">the<span class="_8 blank"> </span>tree-width<span class="_7 blank"> </span>if<span class="_8 blank"> </span>and<span class="_8 blank"> </span>only<span class="_8 blank"> </span>if<span class="_8 blank"> </span>that<span class="_8 blank"> </span>graph<span class="_8 blank"> </span>is<span class="_8 blank"> </span>planar.<span class="_14 blank"> </span>This<span class="_8 blank"> </span>short<span class="_8 blank"> </span>pro of<span class="_8 blank"> </span>did</div><div class="t m0 x0 h6 y91 ff5 fs3 fc0 sc0 ls1 ws7a">not exist when I wrote the \ufb01rst edition, which is wh<span class="_2 blank"></span>y I then included a</div><div class="t m0 x0 h6 y92 ff5 fs3 fc0 sc0 ls1 ws7b">short pro<span class="_1 blank"> </span>of of the next b<span class="_1 blank"> </span>est thing, the analogous result for path-width.</div><div class="t m0 x0 h6 y93 ff5 fs3 fc0 sc0 ls1 ws7c">That<span class="_3 blank"> </span>theorem<span class="_12 blank"> </span>has<span class="_3 blank"> </span>now<span class="_3 blank"> </span>b een<span class="_3 blank"> </span>dropp ed<span class="_12 blank"> </span>from<span class="_3 blank"> </span>Chapter<span class="_12 blank"> </span>12.<span class="_a blank"> </span>Another<span class="_3 blank"> </span>addition</div><div class="t m0 x0 h6 y94 ff5 fs3 fc0 sc0 ls1 ws7d">in this c<span class="_2 blank"></span>hapter is that the tree-width duality theorem, Theorem 12.3.9,</div><div class="t m0 x0 h6 y95 ff5 fs3 fc0 sc0 ls1 ws7e">no<span class="_2 blank"></span>w<span class="_7 blank"> </span>comes<span class="_7 blank"> </span>with<span class="_7 blank"> </span>a<span class="_7 blank"> </span>(short)<span class="_7 blank"> </span>pro of<span class="_7 blank"> </span>to o.</div><div class="t m0 x5 h6 y96 ff5 fs3 fc0 sc0 ls1 ws7f">The second ma<span class="_10 blank"> </span>jor c<span class="_2 blank"></span>hange is the addition of a complete set of hin<span class="_2 blank"></span>ts</div><div class="t m0 x0 h6 y97 ff5 fs3 fc0 sc0 ls1 ws80">for the exercises.<span class="_1c blank"> </span>These are largely T<span class="_0 blank"></span>omm<span class="_2 blank"></span>y Jensen\u2019s w<span class="_2 blank"></span>ork,<span class="_d blank"> </span>and I am</div><div class="t m0 x0 h6 y98 ff5 fs3 fc0 sc0 ls1 ws81">grateful for the time he donated to this pro<span class="_10 blank"> </span>ject.<span class="_d blank"> </span>The aim of these hin<span class="_2 blank"></span>ts</div><div class="t m0 x0 h6 y99 ff5 fs3 fc0 sc0 ls1 ws82">is to help those who use the b<span class="_1 blank"> </span>o<span class="_1 blank"> </span>ok to study graph theory on their o<span class="_2 blank"></span>wn,</div><div class="t m0 x0 h6 y9a ff5 fs3 fc0 sc0 ls1 ws83">but <span class="ff6 ws84">not </span><span class="ws85">to<span class="_8 blank"> </span>sp oil<span class="_8 blank"> </span>the<span class="_8 blank"> </span>fun.<span class="_11 blank"> </span>The<span class="_8 blank"> </span>exercises,<span class="_8 blank"> </span>including<span class="_8 blank"> </span>hints,<span class="_7 blank"> </span>contin<span class="_2 blank"></span>ue<span class="_7 blank"> </span>to<span class="_8 blank"> </span>b e</span></div><div class="t m0 x0 h6 y9b ff5 fs3 fc0 sc0 ls1 ws86">in<span class="_2 blank"></span>tended<span class="_7 blank"> </span>for<span class="_7 blank"> </span>classro om<span class="_7 blank"> </span>use.</div><div class="t m0 x5 h6 y9c ff5 fs3 fc0 sc0 ls1 ws87">Apart from these t<span class="_2 blank"></span>w<span class="_2 blank"></span>o c<span class="_2 blank"></span>hanges, there are a few additions.<span class="_a blank"> </span>The most</div><div class="t m0 x0 h6 y9d ff5 fs3 fc0 sc0 ls1 ws88">noticable of these are the formal in<span class="_2 blank"></span>tro<span class="_1 blank"> </span>duction of depth-\ufb01rst searc<span class="_2 blank"></span>h trees</div><div class="t m0 x0 h6 y9e ff5 fs3 fc0 sc0 ls1 ws89">in Section 1.5 (whic<span class="_2 blank"></span>h has led to some simpli\ufb01cations in later pro<span class="_1 blank"> </span>ofs) and</div><div class="t m0 x0 h6 y9f ff5 fs3 fc0 sc0 ls1 ws37">an<span class="_7 blank"> </span>ingenious<span class="_4 blank"> </span>new<span class="_7 blank"> </span>pro of<span class="_7 blank"> </span>of<span class="_4 blank"> </span>Menger\u2019s<span class="_7 blank"> </span>theorem<span class="_4 blank"> </span>due<span class="_7 blank"> </span>to<span class="_7 blank"> </span>B¨<span class="_18 blank"></span>ohme,<span class="_4 blank"> </span>G¨<span class="_18 blank"></span>oring<span class="_7 blank"> </span>and</div><div class="t m0 x0 h6 ya0 ff5 fs3 fc0 sc0 ls1 ws17">Haran<span class="_2 blank"></span>t<span class="_7 blank"> </span>(whic<span class="_2 blank"></span>h<span class="_7 blank"> </span>has<span class="_7 blank"> </span>not<span class="_7 blank"> </span>otherwise<span class="_7 blank"> </span>b een<span class="_7 blank"> </span>published).</div><div class="t m0 x5 h6 ya1 ff5 fs3 fc0 sc0 ls1 ws8a">Finally<span class="_0 blank"></span>,<span class="_14 blank"> </span>there is a host of small simpli\ufb01cations and clari\ufb01cations</div><div class="t m0 x0 h6 ya2 ff5 fs3 fc0 sc0 ls1 ws8b">of argumen<span class="_2 blank"></span>ts that I noticed as I taught from the bo<span class="_1 blank"> </span>ok, or which w<span class="_2 blank"></span>ere</div><div class="t m0 x0 h6 ya3 ff5 fs3 fc0 sc0 ls1 ws8c">p<span class="_1 blank"> </span>oin<span class="_2 blank"></span>ted out to me b<span class="_2 blank"></span>y others.<span class="_a blank"> </span>T<span class="_0 blank"></span>o all these I o\ufb00er my special thanks.</div><div class="t m0 x5 h6 ya4 ff5 fs3 fc0 sc0 ls1 ws28">The<span class="_7 blank"> </span>W<span class="_0 blank"></span>eb<span class="_7 blank"> </span>site<span class="_7 blank"> </span>for<span class="_7 blank"> </span>the<span class="_7 blank"> </span>b o ok<span class="_7 blank"> </span>has<span class="_7 blank"> </span>follow<span class="_2 blank"></span>ed<span class="_4 blank"> </span>me<span class="_7 blank"> </span>to</div><div class="t m0 x7 h7 ya5 ffc fs4 fc0 sc0 ls1 ws8d">h<span class="_2 blank"></span>ttp://www.math.uni-ham<span class="_2 blank"></span>burg.de/home/diestel/b o oks/graph.theory/</div><div class="t m0 x0 h6 ya6 ff5 fs3 fc0 sc0 ls1 ws17">I<span class="_7 blank"> </span>exp ect<span class="_7 blank"> </span>this<span class="_7 blank"> </span>address<span class="_7 blank"> </span>to<span class="_7 blank"> </span>b e<span class="_7 blank"> </span>stable<span class="_7 blank"> </span>for<span class="_7 blank"> </span>some<span class="_7 blank"> </span>time.</div><div class="t m0 x5 h6 ya7 ff5 fs3 fc0 sc0 ls1 ws8e">Once more,<span class="_14 blank"> </span>m<span class="_2 blank"></span>y thanks go to all who con<span class="_2 blank"></span>tributed to this second</div><div class="t m0 x0 h6 ya8 ff5 fs3 fc0 sc0 ls1 ws8f">edition b<span class="_2 blank"></span>y commen<span class="_2 blank"></span>ting on the \ufb01rst\u2014and I lo<span class="_1 blank"> </span>ok forw<span class="_2 blank"></span>ard to further com-</div><div class="t m0 x0 h6 ya9 ff5 fs3 fc0 sc0 ls1 ws51">men<span class="_2 blank"></span>ts!</div><div class="t m0 x0 h6 yaa ff5 fs3 fc0 sc0 ls1 ws17">Decem<span class="_2 blank"></span>b er<span class="_7 blank"> </span>1999<span class="_1d blank"> </span><span class="ffd ws51">RD</span></div></div><a class="l" href="#pf14d" data-dest-detail='[333,"XYZ",null,null,null]'><div class="d m1" style="border-style:none;position:absolute;left:347.910100px;bottom:376.096497px;width:29.000000px;height:9.000000px;background-color:rgba(255,255,255,0.000001);"></div></a></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf6" class="pf w3 h8" data-page-no="6"><div class="pc pc6 w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff7 fs6 fc0 sc0 ls1 ws50">Preface <span class="ff5 fs3 ws51">xi</span></div><div class="t m0 x0 he y30 ffe fs3 fc0 sc0 ls1 ws72">Ab out<span class="_8 blank"> </span>the<span class="_6 blank"> </span>third<span class="_6 blank"> </span>edition</div><div class="t m0 x0 h6 yab ff5 fs3 fc0 sc0 ls1 ws28">There<span class="_6 blank"> </span>is<span class="_a blank"> </span>no<span class="_a blank"> </span>denying<span class="_6 blank"> </span>that<span class="_6 blank"> </span>this<span class="_a blank"> </span>b o ok<span class="_a blank"> </span>has<span class="_6 blank"> </span>grown.<span class="_13 blank"> </span>Is<span class="_6 blank"> </span>it<span class="_a blank"> </span>still<span class="_6 blank"> </span>as<span class="_a blank"> </span>\u2018lean<span class="_a blank"> </span>and</div><div class="t m0 x0 h6 yac ff5 fs3 fc0 sc0 ls1 ws90">concen<span class="_2 blank"></span>trating on the essen<span class="_2 blank"></span>tial\u2019 as I said it should b<span class="_1 blank"> </span>e when I wrote the</div><div class="t m0 x0 h6 yad ff5 fs3 fc0 sc0 ls1 ws3f">preface to the \ufb01rst edition, now almost eigh<span class="_2 blank"></span>t y<span class="_2 blank"></span>ears ago?</div><div class="t m0 x5 h6 yae ff5 fs3 fc0 sc0 ls11 ws91">Ib<span class="_1e blank"></span><span class="ls1 ws1a">eliev<span class="_2 blank"></span>e<span class="_3 blank"> </span>that<span class="_3 blank"> </span>it<span class="_12 blank"> </span>is,<span class="_12 blank"> </span>p erhaps<span class="_3 blank"> </span>now<span class="_3 blank"> </span>more<span class="_3 blank"> </span>than<span class="_12 blank"> </span>ev<span class="_2 blank"></span>er.<span class="_a blank"> </span>So<span class="_3 blank"> </span>why<span class="_3 blank"> </span>the<span class="_3 blank"> </span>increase</span></div><div class="t m0 x0 h6 yaf ff5 fs3 fc0 sc0 ls1 ws92">in v<span class="_2 blank"></span>olume?<span class="_9 blank"> </span>Part of the answ<span class="_2 blank"></span>er is that I ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e con<span class="_2 blank"></span>tin<span class="_2 blank"></span>ued to pursue the</div><div class="t m0 x0 h6 yb0 ff5 fs3 fc0 sc0 ls1 ws1a">original<span class="_d blank"> </span>dual<span class="_d blank"> </span>aim<span class="_a blank"> </span>of<span class="_d blank"> </span>o\ufb00ering<span class="_d blank"> </span>t<span class="_2 blank"></span>w<span class="_2 blank"></span>o<span class="_d blank"> </span>di\ufb00eren<span class="_2 blank"></span>t<span class="_a blank"> </span>things<span class="_d blank"> </span>b etw<span class="_2 blank"></span>ee<span class="_2 blank"></span>n<span class="_d blank"> </span>one<span class="_d blank"> </span>pair<span class="_a blank"> </span>of</div><div class="t m0 x0 h6 yb1 ff5 fs3 fc0 sc0 ls1 ws51">co<span class="_2 blank"></span>v<span class="_2 blank"></span>ers:</div><div class="t m0 x8 hf yb2 fff fs3 fc0 sc0 ls10">\u2022<span class="ff5 ls1 ws93">a<span class="_3 blank"> </span>reliable<span class="_3 blank"> </span>\ufb01rst<span class="_3 blank"> </span>introduction<span class="_3 blank"> </span>to<span class="_3 blank"> </span>graph<span class="_3 blank"> </span>theory<span class="_3 blank"> </span>that<span class="_3 blank"> </span>can<span class="_3 blank"> </span>b e<span class="_3 blank"> </span>used<span class="_3 blank"> </span>either</span></div><div class="t m0 x9 h6 yb3 ff5 fs3 fc0 sc0 ls1 ws1a">for<span class="_7 blank"> </span>p ersonal<span class="_7 blank"> </span>study<span class="_7 blank"> </span>or<span class="_7 blank"> </span>as<span class="_7 blank"> </span>a<span class="_7 blank"> </span>course<span class="_7 blank"> </span>text;</div><div class="t m0 x8 hf yb4 fff fs3 fc0 sc0 ls10">\u2022<span class="ff5 ls1 ws94">a graduate text that o\ufb00ers some depth in selected areas.</span></div><div class="t m0 x0 h6 yb5 ff5 fs3 fc0 sc0 ls3 ws95">Fo r<span class="_14 blank"> </span><span class="ls1 ws1a">each<span class="_a blank"> </span>of<span class="_d blank"> </span>these<span class="_a blank"> </span>aims,<span class="_d blank"> </span>some<span class="_d blank"> </span>material<span class="_a blank"> </span>has<span class="_a blank"> </span>b een<span class="_d blank"> </span>added.<span class="_19 blank"> </span>Some<span class="_d blank"> </span>of<span class="_a blank"> </span>this</span></div><div class="t m0 x0 h6 yb6 ff5 fs3 fc0 sc0 ls1 ws96">co<span class="_2 blank"></span>v<span class="_2 blank"></span>ers new topics,<span class="_14 blank"> </span>whic<span class="_2 blank"></span>h can be included or skipp<span class="_1 blank"> </span>ed as desired.<span class="_1f blank"> </span>An</div><div class="t m0 x0 h6 yb7 ff5 fs3 fc0 sc0 ls1 ws93">example<span class="_d blank"> </span>at<span class="_d blank"> </span>the<span class="_d blank"> </span>introductory<span class="_d blank"> </span>level<span class="_d blank"> </span>is<span class="_d blank"> </span>the<span class="_d blank"> </span>new<span class="_d blank"> </span>section<span class="_d blank"> </span>on<span class="_d blank"> </span>pac<span class="_2 blank"></span>king<span class="_d blank"> </span>and</div><div class="t m0 x0 h6 yb8 ff5 fs3 fc0 sc0 ls1 ws97">co<span class="_2 blank"></span>v<span class="_2 blank"></span>ering with the Erd\u02dd<span class="_18 blank"></span>os-P´<span class="_18 blank"></span>osa theorem,<span class="_14 blank"> </span>or the inclusion of the stable</div><div class="t m0 x0 h6 yb9 ff5 fs3 fc0 sc0 ls1 ws98">marriage theorem in the matc<span class="_2 blank"></span>hing c<span class="_2 blank"></span>hapter.<span class="_a blank"> </span>An example at the graduate</div><div class="t m0 x0 h6 yba ff5 fs3 fc0 sc0 ls1 ws99">lev<span class="_2 blank"></span>el<span class="_7 blank"> </span>is<span class="_8 blank"> </span>the<span class="_7 blank"> </span>Rob ertson-Seymour<span class="_8 blank"> </span>structure<span class="_8 blank"> </span>theorem<span class="_7 blank"> </span>for<span class="_8 blank"> </span>graphs<span class="_7 blank"> </span>without<span class="_8 blank"> </span>a</div><div class="t m0 x0 h6 ybb ff5 fs3 fc0 sc0 ls1 ws9a">giv<span class="_2 blank"></span>en minor:<span class="_a blank"> </span>a result that takes a few lines to state, but one whic<span class="_2 blank"></span>h is in-</div><div class="t m0 x0 h6 ybc ff5 fs3 fc0 sc0 ls1 ws9b">creasingly relied on in the literature, so that an easily accessible reference</div><div class="t m0 x0 h6 ybd ff5 fs3 fc0 sc0 ls1 ws9c">seems desirable.<span class="_a blank"> </span>Another addition, also in the chapter on graph minors,</div><div class="t m0 x0 h6 ybe ff5 fs3 fc0 sc0 ls1 ws9d">is a new pro<span class="_1 blank"> </span>of of the \u2018Kurato<span class="_2 blank"></span>wski theorem for higher surfaces\u2019\u2014a pro<span class="_1 blank"> </span>of</div><div class="t m0 x0 h6 ybf ff5 fs3 fc0 sc0 ls1 ws1a">whic<span class="_2 blank"></span>h<span class="_7 blank"> </span>illustrates<span class="_8 blank"> </span>the<span class="_8 blank"> </span>in<span class="_2 blank"></span>terpla<span class="_2 blank"></span>y<span class="_7 blank"> </span>b etw<span class="_2 blank"></span>een<span class="_7 blank"> </span>graph<span class="_8 blank"> </span>minor<span class="_8 blank"> </span>theory<span class="_7 blank"> </span>and<span class="_8 blank"> </span>surface</div><div class="t m0 x0 h6 yc0 ff5 fs3 fc0 sc0 ls1 ws1a">top ology<span class="_c blank"> </span>b etter<span class="_3 blank"> </span>than<span class="_3 blank"> </span>w<span class="_2 blank"></span>as<span class="_c blank"> </span>previously<span class="_3 blank"> </span>possible.<span class="_a blank"> </span>The<span class="_3 blank"> </span>proof<span class="_3 blank"> </span>is<span class="_3 blank"> </span>complemen<span class="_2 blank"></span>ted</div><div class="t m0 x0 h6 yc1 ff5 fs3 fc0 sc0 ls6 ws9e">by <span class="ls1 ws9f">an app<span class="_1 blank"> </span>endix on surfaces, which supplies the required bac<span class="_2 blank"></span>kground and</span></div><div class="t m0 x0 h6 yc2 ff5 fs3 fc0 sc0 ls1 wsa0">also sheds some more ligh<span class="_2 blank"></span>t on the pro<span class="_1 blank"> </span>of of the graph minor theorem.</div><div class="t m0 x5 h6 yc3 ff5 fs3 fc0 sc0 ls1 wsa1">Changes that a\ufb00ect previously existing material are rare, except for</div><div class="t m0 x0 h6 yc4 ff5 fs3 fc0 sc0 ls1 wsa2">coun<span class="_2 blank"></span>tless<span class="_8 blank"> </span>lo cal<span class="_8 blank"> </span>improv<span class="_2 blank"></span>eme<span class="_2 blank"></span>nts<span class="_7 blank"> </span>intended<span class="_7 blank"> </span>to<span class="_8 blank"> </span>consolidate<span class="_8 blank"> </span>and<span class="_8 blank"> </span>p olish<span class="_8 blank"> </span>rather</div><div class="t m0 x0 h6 yc5 ff5 fs3 fc0 sc0 ls1 ws28">than<span class="_8 blank"> </span>change.<span class="_17 blank"> </span>I<span class="_6 blank"> </span>am<span class="_6 blank"> </span>aw<span class="_2 blank"></span>are<span class="_8 blank"> </span>that,<span class="_6 blank"> </span>as<span class="_6 blank"> </span>this<span class="_6 blank"> </span>b o ok<span class="_8 blank"> </span>is<span class="_6 blank"> </span>increasingly<span class="_6 blank"> </span>adopted<span class="_6 blank"> </span>as</div><div class="t m0 x0 h6 yc6 ff5 fs3 fc0 sc0 ls1 wsa2">a<span class="_7 blank"> </span>course<span class="_8 blank"> </span>text,<span class="_7 blank"> </span>there<span class="_8 blank"> </span>is<span class="_7 blank"> </span>a<span class="_7 blank"> </span>certain<span class="_8 blank"> </span>desire<span class="_7 blank"> </span>for<span class="_8 blank"> </span>stabilit<span class="_2 blank"></span>y<span class="_0 blank"></span>.<span class="_d blank"> </span>Many<span class="_7 blank"> </span>of<span class="_7 blank"> </span>these<span class="_7 blank"> </span>lo cal</div><div class="t m0 x0 h6 yc7 ff5 fs3 fc0 sc0 ls1 wsa3">impro<span class="_2 blank"></span>v<span class="_2 blank"></span>emen<span class="_2 blank"></span>ts are the result of generous feedback I got from colleagues</div><div class="t m0 x0 h6 yc8 ff5 fs3 fc0 sc0 ls1 wsa4">using the b<span class="_1 blank"> </span>o<span class="_1 blank"> </span>ok in this w<span class="_2 blank"></span>a<span class="_2 blank"></span>y<span class="_0 blank"></span>, and I am very grateful for their help and</div><div class="t m0 x0 h6 yc9 ff5 fs3 fc0 sc0 ls1 ws51">advice.</div><div class="t m0 x5 h6 yca ff5 fs3 fc0 sc0 ls1 wsa5">There<span class="_7 blank"> </span>are<span class="_8 blank"> </span>also<span class="_8 blank"> </span>some<span class="_7 blank"> </span>lo cal<span class="_8 blank"> </span>additions.<span class="_14 blank"> </span>Most<span class="_8 blank"> </span>of<span class="_7 blank"> </span>these<span class="_8 blank"> </span>developed<span class="_8 blank"> </span>from</div><div class="t m0 x0 h6 ycb ff5 fs3 fc0 sc0 lsd wsa6">my<span class="_6 blank"> </span>ow n<span class="_6 blank"> </span><span class="ls1 wsa7">notes, p<span class="_1 blank"> </span>encilled in the margin as I prepared to teach from the</span></div><div class="t m0 x0 h6 ycc ff5 fs3 fc0 sc0 lse wsa8">bo<span class="ls1 wsa9">ok.<span class="_1f blank"> </span>They typically complemen<span class="_2 blank"></span>t an important but tec<span class="_2 blank"></span>hnical proof,</span></div><div class="t m0 x0 h6 ycd ff5 fs3 fc0 sc0 ls1 wsaa">when<span class="_a blank"> </span>I<span class="_6 blank"> </span>felt<span class="_a blank"> </span>that<span class="_a blank"> </span>its<span class="_a blank"> </span>essential<span class="_6 blank"> </span>ideas<span class="_a blank"> </span>might<span class="_6 blank"> </span>get<span class="_a blank"> </span>o<span class="_2 blank"></span>v<span class="_2 blank"></span>erlooked<span class="_6 blank"> </span>in<span class="_a blank"> </span>the<span class="_a blank"> </span>formal</div><div class="t m0 x0 h6 yce ff5 fs3 fc0 sc0 ls1 wsab">write-up.<span class="_15 blank"> </span>F<span class="_0 blank"></span>or example, the pro<span class="_1 blank"> </span>of of the Erd\u02dd<span class="_18 blank"></span>os-Stone theorem now has</div><div class="t m0 x0 h6 ycf ff5 fs3 fc0 sc0 ls1 wsa5">an<span class="_12 blank"> </span>informal<span class="_12 blank"> </span>p ost-mortem<span class="_12 blank"> </span>that<span class="_12 blank"> </span>lo oks<span class="_12 blank"> </span>at<span class="_12 blank"> </span>how<span class="_3 blank"> </span>exactly<span class="_4 blank"> </span>the<span class="_12 blank"> </span>regularity<span class="_3 blank"> </span>lemma</div><div class="t m0 x0 h6 yd0 ff5 fs3 fc0 sc0 ls1 wsac">comes to b<span class="_1 blank"> </span>e applied in it.<span class="_a blank"> </span>Unlike the formal pro<span class="_1 blank"> </span>of, the discussion starts</div><div class="t m0 x0 h6 yd1 ff5 fs3 fc0 sc0 ls1 ws1a">out<span class="_7 blank"> </span>from<span class="_4 blank"> </span>the<span class="_7 blank"> </span>main<span class="_7 blank"> </span>idea,<span class="_7 blank"> </span>and<span class="_7 blank"> </span>\ufb01nally<span class="_7 blank"> </span>arriv<span class="_2 blank"></span>es<span class="_4 blank"> </span>at<span class="_7 blank"> </span>how<span class="_4 blank"> </span>the<span class="_7 blank"> </span>parameters<span class="_7 blank"> </span>to<span class="_7 blank"> </span>be</div><div class="t m0 x0 h6 yd2 ff5 fs3 fc0 sc0 ls1 ws35">declared<span class="_6 blank"> </span>at<span class="_a blank"> </span>the<span class="_a blank"> </span>start<span class="_6 blank"> </span>of<span class="_a blank"> </span>the<span class="_6 blank"> </span>f ormal<span class="_6 blank"> </span>pro of<span class="_a blank"> </span>must<span class="_6 blank"> </span>b e<span class="_6 blank"> </span>sp eci\ufb01ed.<span class="_13 blank"> </span>Similarly<span class="_0 blank"></span>,</div><div class="t m0 x0 h6 yd3 ff5 fs3 fc0 sc0 ls1 wsad">there is no<span class="_2 blank"></span>w a discussion p<span class="_1 blank"> </span>oin<span class="_2 blank"></span>ting to some ideas in the pro<span class="_1 blank"> </span>of of the p<span class="_1 blank"> </span>erfect</div><div class="t m0 x0 h6 yd4 ff5 fs3 fc0 sc0 ls1 ws35">graph<span class="_7 blank"> </span>theorem.<span class="_d blank"> </span>Ho<span class="_2 blank"></span>w<span class="_2 blank"></span>ev<span class="_2 blank"></span>er,<span class="_7 blank"> </span>in<span class="_7 blank"> </span>all<span class="_7 blank"> </span>these<span class="_7 blank"> </span>cases<span class="_7 blank"> </span>the<span class="_7 blank"> </span>formal<span class="_7 blank"> </span>pro ofs<span class="_7 blank"> </span>hav<span class="_2 blank"></span>e<span class="_7 blank"> </span>been</div><div class="t m0 x0 h6 yd5 ff5 fs3 fc0 sc0 ls1 wsae">left essen<span class="_2 blank"></span>tially un<span class="_2 blank"></span>touc<span class="_2 blank"></span>hed.</div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf7" class="pf w3 h8" data-page-no="7"><div class="pc pc7 w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff5 fs3 fc0 sc0 ls7 wsaf">xii <span class="ff7 fs6 ls1 ws2c">Preface</span></div><div class="t m0 x5 h6 y30 ff5 fs3 fc0 sc0 ls1 wsb0">The only substan<span class="_2 blank"></span>tial change to existing material is that the old</div><div class="t m0 x0 hb yd6 ff5 fs3 fc0 sc0 ls1 wsb1">Theorem 8.1.1 (that <span class="ff8 wsb2">cr <span class="ffa fs7 ls12 v1">2</span><span class="ls13">n</span></span><span class="wsb3">edges force a <span class="ff8 ls15 wsb4">TK</span></span></div><div class="t m0 xa h10 yd7 ff10 fs7 fc0 sc0 ls14">r<span class="ff5 fs3 ls1 wsb5 v3">) seems to ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e lost its</span></div><div class="t m0 x0 h6 yd8 ff5 fs3 fc0 sc0 ls1 ws35">nice<span class="_6 blank"> </span>(and<span class="_a blank"> </span>long)<span class="_6 blank"> </span>pro of.<span class="_13 blank"> </span>Previously<span class="_0 blank"></span>,<span class="_6 blank"> </span>this<span class="_a blank"> </span>pro of<span class="_6 blank"> </span>had<span class="_a blank"> </span>serve<span class="_2 blank"></span>d<span class="_6 blank"> </span>as<span class="_a blank"> </span>a<span class="_6 blank"> </span>welcome</div><div class="t m0 x0 h6 yd9 ff5 fs3 fc0 sc0 ls1 ws1c">opp ortunit<span class="_2 blank"></span>y<span class="_8 blank"> </span>to<span class="_8 blank"> </span>explain<span class="_6 blank"> </span>some<span class="_8 blank"> </span>metho ds<span class="_6 blank"> </span>in<span class="_8 blank"> </span>sparse<span class="_8 blank"> </span>extremal<span class="_6 blank"> </span>graph<span class="_8 blank"> </span>theory<span class="_0 blank"></span>.</div><div class="t m0 x0 h6 yda ff5 fs3 fc0 sc0 ls1 wsb6">These metho<span class="_1 blank"> </span>ds ha<span class="_2 blank"></span>v<span class="_2 blank"></span>e migrated to the connectivit<span class="_2 blank"></span>y c<span class="_2 blank"></span>hapter, where they</div><div class="t m0 x0 h6 ydb ff5 fs3 fc0 sc0 ls1 wsb7">no<span class="_2 blank"></span>w liv<span class="_2 blank"></span>e under the ro<span class="_1 blank"> </span>of of the new pro<span class="_1 blank"> </span>of b<span class="_2 blank"></span>y Thomas and W<span class="_0 blank"></span>ollan that 8<span class="ff8 ls16 wsb8">kn</span></div><div class="t m0 x0 h6 ydc ff5 fs3 fc0 sc0 ls1 wsb9">edges mak<span class="_2 blank"></span>e a 2<span class="ff8 lsc">k</span><span class="wsba">-connected graph <span class="ff8 lsc">k</span><span class="wsbb">-linked.<span class="_6 blank"> </span>So they are still there, leaner</span></span></div><div class="t m0 x0 h6 ydd ff5 fs3 fc0 sc0 ls1 ws1a">than<span class="_7 blank"> </span>ever<span class="_4 blank"> </span>b efore,<span class="_8 blank"> </span>and<span class="_7 blank"> </span>just<span class="_7 blank"> </span>presenting<span class="_7 blank"> </span>themselv<span class="_2 blank"></span>es<span class="_7 blank"> </span>under<span class="_7 blank"> </span>a<span class="_7 blank"> </span>new<span class="_7 blank"> </span>guise.<span class="_d blank"> </span>As</div><div class="t m0 x0 h6 yde ff5 fs3 fc0 sc0 ls1 wsbc">a consequence of this c<span class="_2 blank"></span>hange,<span class="_14 blank"> </span>th<span class="_1 blank"> </span>e t<span class="_2 blank"></span>w<span class="_2 blank"></span>o earlier c<span class="_2 blank"></span>hapters on dense and</div><div class="t m0 x0 h6 ydf ff5 fs3 fc0 sc0 ls1 ws1a">sparse<span class="_7 blank"> </span>extremal<span class="_8 blank"> </span>graph<span class="_7 blank"> </span>theory<span class="_8 blank"> </span>could<span class="_7 blank"> </span>b e<span class="_8 blank"> </span>reunited,<span class="_8 blank"> </span>to<span class="_7 blank"> </span>form<span class="_8 blank"> </span>a<span class="_7 blank"> </span>new<span class="_8 blank"> </span>chapter</div><div class="t m0 x0 h6 ye0 ff5 fs3 fc0 sc0 ls1 wsbd">appropriately named as <span class="ffd wsbe">Extr<span class="_2 blank"></span>emal<span class="_7 blank"> </span>Gr<span class="_2 blank"></span>aph<span class="_7 blank"> </span>The<span class="_2 blank"></span>ory <span class="ff5">.</span></span></div><div class="t m0 x5 h6 ye1 ff5 fs3 fc0 sc0 ls1 wsbf">Finally<span class="_0 blank"></span>, there is an entirely new c<span class="_20 blank"></span>hapter, on in\ufb01nite graphs.<span class="_14 blank"> </span>When</div><div class="t m0 x0 h6 ye2 ff5 fs3 fc0 sc0 ls1 wsc0">graph theory \ufb01rst emerged as a mathematical discipline, \ufb01nite and in\ufb01-</div><div class="t m0 x0 h6 ye3 ff5 fs3 fc0 sc0 ls1 wsc1">nite graphs w<span class="_2 blank"></span>ere usually treated on a par.<span class="_15 blank"> </span>This has changed in recen<span class="_20 blank"></span>t</div><div class="t m0 x0 h6 ye4 ff5 fs3 fc0 sc0 ls1 wsc2">y<span class="_2 blank"></span>ears, which I see as a regrettable loss:<span class="_d blank"> </span>in\ufb01nite graphs con<span class="_20 blank"></span>tinue to pro-</div><div class="t m0 x0 h6 ye5 ff5 fs3 fc0 sc0 ls1 wsc3">vide a natural and frequently used bridge to other \ufb01elds of mathematics,</div><div class="t m0 x0 h6 ye6 ff5 fs3 fc0 sc0 ls1 wsc4">and they hold some sp<span class="_1 blank"> </span>ecial fascination of their o<span class="_20 blank"></span>wn.<span class="_d blank"> </span>One asp<span class="_1 blank"> </span>ect of this</div><div class="t m0 x0 h6 ye7 ff5 fs3 fc0 sc0 ls1 wsc5">is that pro<span class="_1 blank"> </span>ofs often hav<span class="_20 blank"></span>e to b<span class="_1 blank"> </span>e more constructiv<span class="_2 blank"></span>e and algorithmic in</div><div class="t m0 x0 h6 ye8 ff5 fs3 fc0 sc0 ls1 wsc6">nature than their \ufb01nite counterparts.<span class="_15 blank"> </span>The in\ufb01nite version of Menger\u2019s</div><div class="t m0 x0 h6 ye9 ff5 fs3 fc0 sc0 ls1 wsc7">theorem in Section 8.4 is a typical example:<span class="_6 blank"> </span>it o\ufb00ers algorithmic insights</div><div class="t m0 x0 h6 yea ff5 fs3 fc0 sc0 ls1 wsc8">in<span class="_2 blank"></span>to connectivit<span class="_2 blank"></span>y problems in netw<span class="_20 blank"></span>orks that are invisible to the s<span class="_2 blank"></span>lic<span class="_2 blank"></span>k</div><div class="t m0 x0 h6 yeb ff5 fs3 fc0 sc0 ls1 ws37">inductiv<span class="_2 blank"></span>e<span class="_7 blank"> </span>pro ofs<span class="_7 blank"> </span>of<span class="_7 blank"> </span>the<span class="_7 blank"> </span>\ufb01nite<span class="_7 blank"> </span>theorem<span class="_7 blank"> </span>given<span class="_4 blank"> </span>in<span class="_7 blank"> </span>Chapter<span class="_7 blank"> </span>3.3.</div><div class="t m0 x5 h6 yec ff5 fs3 fc0 sc0 ls1 wsc9">Once more, my thanks go to all the readers and colleagues whose</div><div class="t m0 x0 h6 yed ff5 fs3 fc0 sc0 ls1 ws28">commen<span class="_20 blank"></span>ts<span class="_12 blank"> </span>help ed<span class="_3 blank"> </span>to<span class="_3 blank"> </span>improv<span class="_20 blank"></span>e<span class="_3 blank"> </span>the<span class="_3 blank"> </span>b o ok.<span class="_a blank"> </span>I<span class="_3 blank"> </span>am<span class="_3 blank"> </span>particularly<span class="_3 blank"> </span>grateful<span class="_3 blank"> </span>to<span class="_3 blank"> </span>Imre</div><div class="t m0 x0 h6 yee ff5 fs3 fc0 sc0 ls1 wsca">Leader for his judicious commen<span class="_20 blank"></span>ts on the whole of the in\ufb01ni<span class="_1 blank"> </span>te c<span class="_20 blank"></span>hapter;<span class="_4 blank"> </span>to</div><div class="t m0 x0 h6 yef ff5 fs3 fc0 sc0 lsd wscb">my <span class="ls1 wscc">graph theory seminar, in particular to Lilian Matthiesen and Philipp</span></div><div class="t m0 x0 h6 yf0 ff5 fs3 fc0 sc0 ls1 wscd">Spr ¨<span class="_21 blank"></span>ussel,<span class="_6 blank"> </span>for<span class="_a blank"> </span>giving<span class="_6 blank"> </span>the<span class="_6 blank"> </span>chapter<span class="_6 blank"> </span>a<span class="_6 blank"> </span>test<span class="_6 blank"> </span>run<span class="_a blank"> </span>and<span class="_6 blank"> </span>solving<span class="_6 blank"> </span>all<span class="_6 blank"> </span>its<span class="_a blank"> </span>exercises</div><div class="t m0 x0 h6 yf1 ff5 fs3 fc0 sc0 ls1 wsce">(of<span class="_12 blank"> </span>which<span class="_12 blank"> </span>eight<span class="_20 blank"></span>y<span class="_4 blank"> </span>survived<span class="_12 blank"> </span>their<span class="_4 blank"> </span>scrutiny);<span class="_12 blank"> </span>to<span class="_4 blank"> </span>Angelos<span class="_4 blank"> </span>Georgakopoulos<span class="_4 blank"> </span>for</div><div class="t m0 x0 h6 yf2 ff5 fs3 fc0 sc0 lsd wscf">mu ch<span class="_4 blank"> </span><span class="ls1 ws37">pro ofreadi ng<span class="_12 blank"> </span>elsewhere;<span class="_7 blank"> </span>to<span class="_12 blank"> </span>Melanie<span class="_4 blank"> </span>Win<span class="_4 blank"> </span>Myint<span class="_12 blank"> </span>for<span class="_4 blank"> </span>recompiling<span class="_12 blank"> </span>the</span></div><div class="t m0 x0 h6 yf3 ff5 fs3 fc0 sc0 ls1 wsd0">index and extending it substan<span class="_2 blank"></span>tially; and to Tim Stelldinger for nu<span class="_2 blank"></span>rsing</div><div class="t m0 x0 h6 yf4 ff5 fs3 fc0 sc0 ls1 wsd1">the whale on page 366 until it w<span class="_20 blank"></span>as strong enough to carry its baby</div><div class="t m0 x0 h6 yf5 ff5 fs3 fc0 sc0 ls1 ws51">dinosaur.</div><div class="t m0 x0 h6 yf6 ff5 fs3 fc0 sc0 ls1 wsd2">Ma<span class="_2 blank"></span>y 2005<span class="_22 blank"> </span><span class="ffd ws51">RD</span></div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf8" class="pf w3 h8" data-page-no="8"><div class="pc pc8 w3 h8"><img fetchpriority="low" loading="lazy" class="bi x0 yf7 w6 h11" alt="" src="https://files.passeidireto.com/569c7f44-7960-452b-bd43-a9ca6943a2c9/bg8.png"><div class="c x1 ye w5 h9"><div class="t m0 xb ha yf8 ff5 fs5 fc0 sc0 ls1 wse">Con<span class="_0 blank"></span>ten<span class="_20 blank"></span>ts</div><div class="t m0 x0 h7 yf9 ffc fs4 fc0 sc0 ls1 wsd3">Preface <span class="ff11 ls17 wsd4">................................................................ </span><span class="ws66">vii</span></div><div class="t m0 x0 h12 yfa ff5 fs8 fc0 sc0 ls1 wsd5">1.<span class="_11 blank"> </span>The Basics<span class="_9 blank"> </span><span class="ff11 fs4 ls17 wsd6">...................................................... <span class="ffc ls1">1</span></span></div><div class="t m0 xc h7 yfb ffc fs4 fc0 sc0 ls1 wsd7">1.1<span class="_d blank"> </span>Graphs* <span class="ff11 ls17 wsd8">........................................................ </span>2</div><div class="t m0 xc h7 yfc ffc fs4 fc0 sc0 ls1 wsd9">1.2<span class="_d blank"> </span>The degree of a v<span class="_20 blank"></span>ertex*<span class="_6 blank"> </span><span class="ff11 ls17 wsda">......................................... </span>5</div><div class="t m0 xc h7 yfd ffc fs4 fc0 sc0 ls1 wsdb">1.3<span class="_d blank"> </span>P<span class="_20 blank"></span>aths and cycles*<span class="_11 blank"> </span><span class="ff11 ls17 wsdc">.............................................. </span>6</div><div class="t m0 xc h7 yfe ffc fs4 fc0 sc0 ls1 wsdd">1.4 Connectivit<span class="_2 blank"></span>y*<span class="_14 blank"> </span><span class="ff11 ls17 wsde">.................................................. </span><span class="ws66">10</span></div><div class="t m0 xc h7 yff ffc fs4 fc0 sc0 ls1 wsdf">1.5<span class="_d blank"> </span>T<span class="_0 blank"></span>rees and forests*<span class="_d blank"> </span><span class="ff11 ls17 wse0">.............................................. </span><span class="ws66">13</span></div><div class="t m0 xc h7 y100 ffc fs4 fc0 sc0 ls1 wse1">1.6<span class="_d blank"> </span>Bipartite graphs*<span class="_6 blank"> </span><span class="ff11 ls17 wse2">............................................... </span><span class="ws66">17</span></div><div class="t m0 xc h7 y101 ffc fs4 fc0 sc0 ls1 wse3">1.7<span class="_d blank"> </span>Con<span class="_20 blank"></span>traction and minors*<span class="_11 blank"> </span><span class="ff11 ls17 wse4">....................................... </span><span class="ws66">18</span></div><div class="t m0 xc h7 y102 ffc fs4 fc0 sc0 ls1 wse5">1.8<span class="_d blank"> </span>Euler tours*<span class="_6 blank"> </span><span class="ff11 ls17 wse6">.................................................... </span><span class="ws66">22</span></div><div class="t m0 xc h7 y103 ffc fs4 fc0 sc0 ls1 wse7">1.9<span class="_d blank"> </span>Some linear algebra<span class="_11 blank"> </span><span class="ff11 ls17 wse8">............................................ </span><span class="ws66">23</span></div><div class="t m0 xd h7 y104 ffc fs4 fc0 sc0 ls1 wse9">1.10<span class="_d blank"> </span>Other notions of graphs<span class="_11 blank"> </span><span class="ff11 ls17 wsea">........................................ </span><span class="ws66">28</span></div><div class="t m0 x9 h7 y105 ffc fs4 fc0 sc0 ls1 wseb">Exercises <span class="ff11 ls17 wsec">....................................................... </span><span class="ws66">30</span></div><div class="t m0 x9 h7 y106 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 wsee">.......................................................... </span><span class="ws66">32</span></div><div class="t m0 x0 h12 y107 ff5 fs8 fc0 sc0 ls1 wsef">2.<span class="_11 blank"> </span>Matc<span class="_2 blank"></span>hing, Co<span class="_2 blank"></span>v<span class="_20 blank"></span>ering and Pac<span class="_20 blank"></span>king<span class="_11 blank"> </span><span class="ff11 fs4 ls17 wsf0">............................. <span class="ffc ls1 ws66">33</span></span></div><div class="t m0 xc h7 y108 ffc fs4 fc0 sc0 ls1 wsf1">2.1<span class="_d blank"> </span>Matc<span class="_20 blank"></span>hing in bipartite graphs*<span class="_11 blank"> </span><span class="ff11 ls17 wsf2">.................................. </span><span class="ws66">34</span></div><div class="t m0 xc h13 y109 ffc fs4 fc0 sc0 ls1 wsf3">2.2<span class="_d blank"> </span>Matc<span class="_20 blank"></span>hing in general graphs<span class="ff12 fs9 ls18 v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls19">)</span></span><span class="ff11 ls17 wsf4 v0">................................... </span><span class="ws66 v0">39</span></div><div class="t m0 xc h7 y10a ffc fs4 fc0 sc0 ls1 wsf5">2.3<span class="_d blank"> </span>P<span class="_20 blank"></span>acking and co<span class="_20 blank"></span>vering<span class="_d blank"> </span><span class="ff11 ls17 wsf6">........................................... </span><span class="ws66">44</span></div><div class="t m0 xc h7 y10b ffc fs4 fc0 sc0 ls1 wsf7">2.4<span class="_d blank"> </span>T<span class="_0 blank"></span>ree-pac<span class="_20 blank"></span>king<span class="_7 blank"> </span>and<span class="_4 blank"> </span>arb oricity<span class="_8 blank"> </span><span class="ff11 ls17 wsf8">..................................... </span><span class="ws66">46</span></div><div class="t m0 xc h7 y10c ffc fs4 fc0 sc0 ls1 wsf9">2.5<span class="_d blank"> </span>P<span class="_20 blank"></span>ath cov<span class="_20 blank"></span>ers<span class="_17 blank"> </span><span class="ff11 ls17 wsfa">.................................................... </span><span class="ws66">49</span></div><div class="t m0 x9 h7 y10d ffc fs4 fc0 sc0 ls1 wsfb">Exercises <span class="ff11 ls17 wsfc">....................................................... </span><span class="ws66">51</span></div><div class="t m0 x9 h7 y10e ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 wsee">.......................................................... </span><span class="ws66">53</span></div><div class="t m0 xe h7 y10f ffc fs4 fc0 sc0 ls1a">*<span class="ff7 fs6 ls1 wsfd">Sections marke<span class="_2 blank"></span>d by an asterisk are recommended for a \ufb01rst course.</span></div><div class="t m0 x5 h14 y110 ff7 fs6 fc0 sc0 ls1 wsfe">Of sections mark<span class="_2 blank"></span>ed <span class="ff12 fs9 ls1b v4">(</span><span class="ff14 ls1c v4">\u2217<span class="ff12 fs9 ls1d">)</span></span><span class="wsff">,<span class="_12 blank"> </span>the<span class="_12 blank"> </span>b eginning<span class="_4 blank"> </span>is<span class="_12 blank"> </span>recommended<span class="_12 blank"> </span>for<span class="_12 blank"> </span>a<span class="_4 blank"> </span>\ufb01rst<span class="_12 blank"> </span>course.</span></div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pf9" class="pf w3 h8" data-page-no="9"><div class="pc pc9 w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff5 fs3 fc0 sc0 ls7 ws100">xiv <span class="ff7 fs6 ls1 ws2c">Conten<span class="_20 blank"></span>ts</span></div><div class="t m0 x0 h12 y30 ff5 fs8 fc0 sc0 ls1 ws101">3. Connectivit<span class="_20 blank"></span>y<span class="_15 blank"> </span><span class="ff11 fs4 ls17 ws102">.................................................... <span class="ffc ls1 ws66">55</span></span></div><div class="t m0 xc h7 y111 ffc fs4 fc0 sc0 ls1 wsdb">3.1<span class="_d blank"> </span>2-Connected graphs and subgraphs*<span class="_14 blank"> </span><span class="ff11 ls17 ws103">............................ </span><span class="ws66">55</span></div><div class="t m0 xc h15 y112 ffc fs4 fc0 sc0 ls1 wsd9">3.2<span class="_d blank"> </span>The structure of 3-connected graphs<span class="ff12 fs9 ls1e v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls1f">)</span></span><span class="ff11 ls17 ws104">.......................... </span><span class="ws66">57</span></div><div class="t m0 xc h7 y113 ffc fs4 fc0 sc0 ls1 ws105">3.3<span class="_d blank"> </span>Menger\u2019s theorem*<span class="_14 blank"> </span><span class="ff11 ls17 ws106">............................................. </span><span class="ws66">62</span></div><div class="t m0 xc h7 y114 ffc fs4 fc0 sc0 ls1 ws107">3.4<span class="_d blank"> </span>Mader\u2019s theorem<span class="_14 blank"> </span><span class="ff11 ls17 ws108">............................................... </span><span class="ws66">67</span></div><div class="t m0 xc h16 y115 ffc fs4 fc0 sc0 ls1 ws109">3.5<span class="_d blank"> </span>Linking pairs of v<span class="_20 blank"></span>ertices<span class="ff12 fs9 ls18 v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls20">)</span></span><span class="ff11 ls17 ws10a v0">...................................... </span><span class="ws66 v0">69</span></div><div class="t m0 x9 h7 y116 ffc fs4 fc0 sc0 ls1 wsfb">Exercises <span class="ff11 ls17 wsfc">....................................................... </span><span class="ws66">78</span></div><div class="t m0 x9 h7 y117 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 wsee">.......................................................... </span><span class="ws66">80</span></div><div class="t m0 x0 h12 y118 ff5 fs8 fc0 sc0 ls1 ws10b">4.<span class="_11 blank"> </span>Planar Graphs<span class="_11 blank"> </span><span class="ff11 fs4 ls17 ws10c">.................................................. <span class="ffc ls1 ws66">83</span></span></div><div class="t m0 xc h7 y119 ffc fs4 fc0 sc0 ls1 ws10d">4.1<span class="_d blank"> </span>T<span class="_0 blank"></span>opological<span class="_7 blank"> </span>prerequisites*<span class="_11 blank"> </span><span class="ff11 ls17 ws10e">...................................... </span><span class="ws66">84</span></div><div class="t m0 xc h7 y11a ffc fs4 fc0 sc0 ls1 ws10f">4.2<span class="_d blank"> </span>Plane graphs*<span class="_d blank"> </span><span class="ff11 ls17 ws110">.................................................. </span><span class="ws66">86</span></div><div class="t m0 xc h7 y11b ffc fs4 fc0 sc0 ls1 ws111">4.3<span class="_d blank"> </span>Dra<span class="_20 blank"></span>wings <span class="ff11 ls17 ws112">....................................................... </span><span class="ws66">92</span></div><div class="t m0 xc h7 y11c ffc fs4 fc0 sc0 ls1 ws107">4.4<span class="_d blank"> </span>Planar graphs:<span class="_6 blank"> </span>Kuratowski\u2019s theorem*<span class="_6 blank"> </span><span class="ff11 ls17 ws113">.......................... </span><span class="ws66">96</span></div><div class="t m0 xc h7 y11d ffc fs4 fc0 sc0 ls1 ws114">4.5<span class="_d blank"> </span>Algebraic planarit<span class="_20 blank"></span>y criteria<span class="_14 blank"> </span><span class="ff11 ls17 ws115">..................................... </span><span class="ws66">101</span></div><div class="t m0 xc h7 y11e ffc fs4 fc0 sc0 ls1 ws10f">4.6<span class="_d blank"> </span>Plane dualit<span class="_20 blank"></span>y<span class="_a blank"> </span><span class="ff11 ls17 ws116">................................................... </span><span class="ws66">103</span></div><div class="t m0 x9 h7 y11f ffc fs4 fc0 sc0 ls1 wseb">Exercises <span class="ff11 ls17 ws117">....................................................... </span><span class="ws66">106</span></div><div class="t m0 x9 h7 y120 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws118">.......................................................... </span><span class="ws66">109</span></div><div class="t m0 x0 h12 y121 ff5 fs8 fc0 sc0 ls1 ws119">5.<span class="_11 blank"> </span>Colouring <span class="ff11 fs4 ls17 ws11a">........................................................ <span class="ffc ls1 ws66">111</span></span></div><div class="t m0 xc h7 y122 ffc fs4 fc0 sc0 ls1 ws11b">5.1<span class="_d blank"> </span>Colouring maps and planar graphs*<span class="_8 blank"> </span><span class="ff11 ls17 ws11c">............................. </span><span class="ws66">112</span></div><div class="t m0 xc h7 y123 ffc fs4 fc0 sc0 ls1 ws11d">5.2<span class="_d blank"> </span>Colouring v<span class="_20 blank"></span>ertices*<span class="_d blank"> </span><span class="ff11 ls17 ws11e">............................................. </span><span class="ws66">114</span></div><div class="t m0 xc h7 y124 ffc fs4 fc0 sc0 ls1 ws11d">5.3<span class="_d blank"> </span>Colouring edges*<span class="_d blank"> </span><span class="ff11 ls17 ws11f">............................................... </span><span class="ws66">119</span></div><div class="t m0 xc h7 y125 ffc fs4 fc0 sc0 ls1 ws120">5.4<span class="_d blank"> </span>List colouring<span class="_11 blank"> </span><span class="ff11 ls17 ws121">.................................................. </span><span class="ws66">121</span></div><div class="t m0 xc h7 y126 ffc fs4 fc0 sc0 ls1 ws122">5.5<span class="_d blank"> </span>P<span class="_20 blank"></span>erfect graphs<span class="_a blank"> </span><span class="ff11 ls17 ws123">.................................................. </span><span class="ws66">126</span></div><div class="t m0 x9 h7 y127 ffc fs4 fc0 sc0 ls1 wsfb">Exercises <span class="ff11 ls17 ws124">....................................................... </span><span class="ws66">133</span></div><div class="t m0 x9 h7 y128 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws125">.......................................................... </span><span class="ws66">136</span></div><div class="t m0 x0 h12 y129 ff5 fs8 fc0 sc0 ls1 ws101">6. Flo<span class="_20 blank"></span>ws<span class="_9 blank"> </span><span class="ff11 fs4 ls17 ws126">............................................................ <span class="ffc ls1 ws66">139</span></span></div><div class="t m0 xc h17 y12a ffc fs4 fc0 sc0 ls1 wsdd">6.1 Circulations<span class="ff12 fs9 ls1b v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls21">)</span></span><span class="ff11 ls17 ws127 v0">.................................................. </span><span class="ws66 v0">140</span></div><div class="t m0 xc h7 y12b ffc fs4 fc0 sc0 ls1 ws128">6.2<span class="_d blank"> </span>Flo<span class="_20 blank"></span>ws in netw<span class="_20 blank"></span>orks*<span class="_d blank"> </span><span class="ff11 ls17 ws129">............................................. </span><span class="ws66">141</span></div><div class="t m0 xc h7 y12c ffc fs4 fc0 sc0 ls1 ws12a">6.3<span class="_d blank"> </span>Group-v<span class="_0 blank"></span>alued \ufb02ows<span class="_d blank"> </span><span class="ff11 ls17 ws12b">............................................. </span><span class="ws66">144</span></div><div class="t m0 xc h7 y12d ffc fs4 fc0 sc0 ls1 ws12c">6.4 <span class="ff11 ls22">k</span><span class="ws128">-Flo<span class="_2 blank"></span>ws for small <span class="ff11 ls23">k<span class="ls17 ws12d">............................................. </span></span><span class="ws66">149</span></span></div><div class="t m0 xc h7 y12e ffc fs4 fc0 sc0 ls1 ws12e">6.5<span class="_d blank"> </span>Flo<span class="_20 blank"></span>w-colouring duality<span class="_6 blank"> </span><span class="ff11 ls17 ws12f">.......................................... </span><span class="ws66">152</span></div><div class="t m0 xc h7 y12f ffc fs4 fc0 sc0 ls1 ws130">6.6<span class="_d blank"> </span>T<span class="_0 blank"></span>utte\u2019s \ufb02o<span class="_20 blank"></span>w conjectures<span class="_15 blank"> </span><span class="ff11 ls17 ws131">........................................ </span><span class="ws66">156</span></div><div class="t m0 x9 h7 y130 ffc fs4 fc0 sc0 ls1 wseb">Exercises <span class="ff11 ls17 ws124">....................................................... </span><span class="ws66">160</span></div><div class="t m0 x9 h7 y131 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws125">.......................................................... </span><span class="ws66">161</span></div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div> <div id="pfa" class="pf w3 h8" data-page-no="a"><div class="pc pca w3 h8"><div class="c x1 ye w5 h9"><div class="t m0 x0 h6 y2f ff7 fs6 fc0 sc0 ls1 ws132">Conten<span class="_20 blank"></span>ts <span class="ff5 fs3 ws51">xv</span></div><div class="t m0 x0 h12 y132 ff5 fs8 fc0 sc0 ls1 ws133">7.<span class="_11 blank"> </span>Extremal Graph Theory<span class="_d blank"> </span><span class="ff11 fs4 ls17 ws134">....................................... <span class="ffc ls1 ws66">163</span></span></div><div class="t m0 xc h7 y133 ffc fs4 fc0 sc0 ls1 wsdd">7.1 Subgraphs*<span class="_17 blank"> </span><span class="ff11 ls17 ws135">.................................................... </span><span class="ws66">164</span></div><div class="t m0 xc h18 y134 ffc fs4 fc0 sc0 ls1 wsdd">7.2 Minors<span class="ff12 fs9 ls18 v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls24">)</span></span><span class="ff11 ls17 ws136">....................................................... </span><span class="ws66">169</span></div><div class="t m0 xc h7 y135 ffc fs4 fc0 sc0 ls1 ws137">7.3<span class="_d blank"> </span>Hadwiger\u2019s conjecture*<span class="_d blank"> </span><span class="ff11 ls17 ws138">......................................... </span><span class="ws66">172</span></div><div class="t m0 xc h7 y136 ffc fs4 fc0 sc0 ls1 ws139">7.4<span class="_d blank"> </span>Szemer<span class="_20 blank"></span>´<span class="_b blank"></span>edi\u2019s regularit<span class="_20 blank"></span>y lemma<span class="_d blank"> </span><span class="ff11 ls17 ws13a">................................... </span><span class="ws66">175</span></div><div class="t m0 xc h7 y137 ffc fs4 fc0 sc0 ls1 ws13b">7.5<span class="_d blank"> </span>Applying the regularit<span class="_20 blank"></span>y lemma<span class="_17 blank"> </span><span class="ff11 ls17 ws13c">................................. </span><span class="ws66">183</span></div><div class="t m0 x9 h7 y138 ffc fs4 fc0 sc0 ls1 wsfb">Exercises <span class="ff11 ls17 ws124">....................................................... </span><span class="ws66">189</span></div><div class="t m0 x9 h7 y139 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws125">.......................................................... </span><span class="ws66">192</span></div><div class="t m0 x0 h12 y13a ff5 fs8 fc0 sc0 ls1 ws13d">8.<span class="_11 blank"> </span>In\ufb01nite Graphs<span class="_15 blank"> </span><span class="ff11 fs4 ls17 ws13e">................................................. <span class="ffc ls1 ws66">195</span></span></div><div class="t m0 xc h7 y13b ffc fs4 fc0 sc0 ls1 ws13f">8.1<span class="_d blank"> </span>Basic notions, facts and tec<span class="_20 blank"></span>hniques*<span class="_11 blank"> </span><span class="ff11 ls17 ws140">............................ </span><span class="ws66">196</span></div><div class="t m0 xc h13 y13c ffc fs4 fc0 sc0 ls1 ws141">8.2<span class="_d blank"> </span>P<span class="_20 blank"></span>aths, trees, and ends<span class="ff12 fs9 ls18 v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls25">)</span></span><span class="ff11 ls17 ws142">........................................ </span><span class="ws66">204</span></div><div class="t m0 xc h7 y13d ffc fs4 fc0 sc0 ls1 ws143">8.3<span class="_d blank"> </span>Homogeneous and univ<span class="_20 blank"></span>ersal graphs*<span class="_14 blank"> </span><span class="ff11 ls17 ws144">............................ </span><span class="ws66">212</span></div><div class="t m0 xc h7 y13e ffc fs4 fc0 sc0 ls1 ws114">8.4<span class="_d blank"> </span>Connectivit<span class="_20 blank"></span>y and matching<span class="_d blank"> </span><span class="ff11 ls17 ws145">..................................... </span><span class="ws66">216</span></div><div class="t m0 xc h7 y13f ffc fs4 fc0 sc0 ls1 ws146">8.5<span class="_d blank"> </span>The<span class="_4 blank"> </span>top ological<span class="_4 blank"> </span>end<span class="_7 blank"> </span>space<span class="_11 blank"> </span><span class="ff11 ls17 ws147">...................................... </span><span class="ws66">226</span></div><div class="t m0 x9 h7 y140 ffc fs4 fc0 sc0 ls1 wseb">Exercises <span class="ff11 ls17 ws117">....................................................... </span><span class="ws66">237</span></div><div class="t m0 x9 h7 y141 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws118">.......................................................... </span><span class="ws66">244</span></div><div class="t m0 x0 h12 y142 ff5 fs8 fc0 sc0 ls1 ws148">9.<span class="_11 blank"> </span>Ramsey Theory for Graphs<span class="_17 blank"> </span><span class="ff11 fs4 ls17 ws149">................................... <span class="ffc ls1 ws66">251</span></span></div><div class="t m0 xc h7 y143 ffc fs4 fc0 sc0 ls1 ws141">9.1<span class="_d blank"> </span>Ramsey\u2019s original theorems*<span class="_6 blank"> </span><span class="ff11 ls17 ws14a">.................................... </span><span class="ws66">252</span></div><div class="t m0 xc h18 y144 ffc fs4 fc0 sc0 ls1 ws10d">9.2<span class="_d blank"> </span>Ramsey<span class="_4 blank"> </span>num<span class="_20 blank"></span>b ers<span class="ff12 fs9 ls18 v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls26">)</span></span><span class="ff11 ls17 ws14b">............................................. </span><span class="ws66">255</span></div><div class="t m0 xc h7 y145 ffc fs4 fc0 sc0 ls1 ws14c">9.3<span class="_d blank"> </span>Induced Ramsey theorems<span class="_d blank"> </span><span class="ff11 ls17 ws14d">...................................... </span><span class="ws66">258</span></div><div class="t m0 xc h17 y146 ffc fs4 fc0 sc0 ls1 ws14e">9.4<span class="_d blank"> </span>Ramsey<span class="_4 blank"> </span>prop erties<span class="_4 blank"> </span>and<span class="_7 blank"> </span>connectivit<span class="_20 blank"></span>y <span class="ff12 fs9 ls27 v1">(</span><span class="ff13 ws66 v1">\u2217<span class="ff12 fs9 ls28">)</span></span><span class="ff11 ls17 ws14f v0">........................... </span><span class="ws66 v0">268</span></div><div class="t m0 x9 h7 y147 ffc fs4 fc0 sc0 ls1 wsfb">Exercises <span class="ff11 ls17 ws124">....................................................... </span><span class="ws66">271</span></div><div class="t m0 x9 h7 y148 ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws125">.......................................................... </span><span class="ws66">272</span></div><div class="t m0 x0 h12 y149 ff5 fs8 fc0 sc0 ls1 ws150">10.<span class="_11 blank"> </span>Hamilton Cycles<span class="_9 blank"> </span><span class="ff11 fs4 ls17 ws151">.............................................. <span class="ffc ls1 ws66">275</span></span></div><div class="t m0 xd h7 y14a ffc fs4 fc0 sc0 ls1 ws152">10.1<span class="_d blank"> </span>Simple su\ufb03cien<span class="_20 blank"></span>t conditions*<span class="_d blank"> </span><span class="ff11 ls17 ws153">.................................... </span><span class="ws66">275</span></div><div class="t m0 xd h7 y14b ffc fs4 fc0 sc0 ls1 ws154">10.2<span class="_d blank"> </span>Hamilton cycles and degree sequences*<span class="_17 blank"> </span><span class="ff11 ls17 ws155">......................... </span><span class="ws66">278</span></div><div class="t m0 xd h7 y14c ffc fs4 fc0 sc0 ls1 ws154">10.3<span class="_d blank"> </span>Hamilton cycles in the square of a graph<span class="_a blank"> </span><span class="ff11 ls17 ws156">........................ </span><span class="ws66">281</span></div><div class="t m0 x9 h7 y14d ffc fs4 fc0 sc0 ls1 wsfb">Exercises <span class="ff11 ls17 ws124">....................................................... </span><span class="ws66">289</span></div><div class="t m0 x9 h7 y14e ffc fs4 fc0 sc0 ls1 wsed">Notes <span class="ff11 ls17 ws125">.......................................................... </span><span class="ws66">290</span></div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,-32.089900,-159.903503]}'></div></div>
Compartilhar