《图论》课程教学资源（书籍文献）Graph Theory I（1-9，J.A. Bondy，U.S.R. Murty）

ContentsGraphsSubgraphs3Connected GraphsTreesNonseparableGra17Tree-Search AlgorithmFlowsinNetwo157Complexity of Algori73Connectivity20510PlanarGrapl4:1l TheFour-Colour Problem12 Stable Sets and Cliqu9113TheProbabilisticMetho2514VertexColourin015Cole16Matching17 Edge Colouri

Contents 1 Graphs ........................................................ 1 2 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Connected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 Nonseparable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Tree-Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7 Flows in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 9 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 10 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 11 The Four-Colour Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 12 Stable Sets and Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 13 The Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 14 Vertex Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 15 Colourings of Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 16 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 17 Edge Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

XIIContents18HamiltonCye19Covering1 DaclnDirerted Grar20 Electrical Netwo21IntegerUnsolvedProblenReferenceGraOperatioPFamiliesof Grap!sfDtHeNotatioIndex637

XII Contents 18 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 19 Coverings and Packings in Directed Graphs . . . . . . . . . . . . . . . . . . . 503 20 Electrical Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527 21 Integer Flows and Coverings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 Unsolved Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 General Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Graph Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 Operations and Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 Families of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 Other Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637

1GraphsContents1.1 Graphs and TheRepresentation.................ANDEXAMPLES42DEBAE4SPECIALFAMILIESOFGRAPHS67INCIDENCEANDADJACENCYMATRICESVERTEX DEGREES1828PROOFTWOWAYS1.215and Automorphisms......oorons....EODTSAUTOMORPHISNABELLEDGRAPHS1.3GraphingfromOtherStructures....POLY+..INCIDENCE GRAPIINTERSECTIONGRAPHS1.4Constructing Graphs from Other Graphs .JNIONANDSCTION:RSA11.5Directed Graphs1.611Related Reading.SHISTORY OF GRAPH THEORY.1.1 Graphs and Their RepresentationDEFINITIONS AND EXAMPLESMany real-world situations can conveniently be described by means of a diagranconsistingof asetof pointstogetherwithlines joiningcertainpairs ofthesepoints

1 Graphs Contents 1.1 Graphs and Their Representation . ................. 1 Definitions and Examples ............................ 1 Drawings of Graphs ................................. 2 Special Families of Graphs .......................... 4 Incidence and Adjacency Matrices .................. 6 Vertex Degrees ..................................... 7 Proof Technique: Counting in Two Ways ............ 8 1.2 Isomorphisms and Automorphisms . . . . . . . . . . . . . . . . . 12 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Testing for Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Labelled Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Graphs Arising from Other Structures . . . . . . . . . . . . . 20 Polyhedral Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Set Systems and Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 21 Incidence Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Intersection Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4 Constructing Graphs from Other Graphs . . . . . . . . . . . 29 Union and Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.5 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.6 Infinite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.7 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 History of Graph Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.1 Graphs and Their Representation Definitions and Examples Many real-world situations can conveniently be described by means of a diagram consisting of a set of points together with lines joining certain pairs of these points

21 GraphsFor example, the points could represent people, with lines joining pairs of friends; orcation centres.with lines repiepointsmightbecolcatiorglinks. Notice that in such diagrams one is mainly interested in whether two givenpoints are joined by a line; the manner in which they are joined is immaterial. Amathematical abstraction of situations of this type gives rise to the concept of agraph.A graph G is an ordered pair (V(G),E(G) consisting of a set V(G) of verticesand a set E(G), disjoint from V(G),of edges, together with an incidence functionWc that asciates with each edge of G anunordered pair of (not.necessarilydistinct) vertices of G. If e is an edge and u and are vertices such that bc(e) -[u.ul.the is said to joinuand w,and the vertices u and y are called the endsof e. We denote the numbers of vertices and edges in G by v(G) and e(G); thesetwobasicparametersarecalledtheorderand szeofGrespectivelyTwo examples of graphs should serve to clarify the definition. For notationalsimplicity, we write uu for the unordered pair [u,].Erample 1.G = (V(G),E(G)whereV(G)= fu,u,w,r,y)E(G) = (a,b,c,d,e, f,g,h)and wc is defined byve(a) = c(b) =uu c(c) =ww we(d)= wadc(e) = va c(f) = wr wc(g) =ur c(h) = ryErample 2.H =(V(H),E(H)whereV(H) = [o, 1, 2, U3, 4,05]E(H)- (e1e2,e,e,e,e,,es,e,and wh is defined bybh(ei)=uiu2 bh(e2) = u2us wr(es) =vau wh(es) = vaus bh(es)= Usuih(e6)= ouh(e7)=ou2 h(es)=Voua (eo)=Vou h(e10)=PovsDRAWINGS OF GRAPHSGraphs are so named because they can be represented graphically, and it is thisgraphical representation which helps us understand many of their properties. Eachvertex is indicated by a point, and each edge by a line joining the points representing its ends. Diagrams of G and H are shown in Figure 1.1. (For clarity, verticesare represented by small circles.)

2 1 Graphs For example, the points could represent people, with lines joining pairs of friends; or the points might be communication centres, with lines representing communication links. Notice that in such diagrams one is mainly interested in whether two given points are joined by a line; the manner in which they are joined is immaterial. A mathematical abstraction of situations of this type gives rise to the concept of a graph. A graph G is an ordered pair (V (G),E(G)) consisting of a set V (G) of vertices and a set E(G), disjoint from V (G), of edges, together with an incidence function ψG that associates with each edge of G an unordered pair of (not necessarily distinct) vertices of G. If e is an edge and u and v are vertices such that ψG(e) = {u,v}, then e is said to join u and v, and the vertices u and v are called the ends of e. We denote the numbers of vertices and edges in G by v(G) and e(G); these two basic parameters are called the order and size of G, respectively. Two examples of graphs should serve to clarify the definition. For notational simplicity, we write uv for the unordered pair {u,v}. Example 1. G = (V (G),E(G)) where V (G) = {u,v,w,x,y} E(G) = {a,b,c,d,e,f,g,h} and ψG is defined by ψG(a) = uv ψG(b) = uu ψG(c) = vw ψG(d) = wx ψG(e) = vx ψG(f) = wx ψG(g) = ux ψG(h) = xy Example 2. H = (V (H),E(H)) where V (H) = {v0,v1,v2,v3,v4,v5} E(H) = {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10} and ψH is defined by ψH(e1) = v1v2 ψH(e2) = v2v3 ψH(e3) = v3v4 ψH(e4) = v4v5 ψH(e5) = v5v1 ψH(e6) = v0v1 ψH(e7) = v0v2 ψH(e8) = v0v3 ψH(e9) = v0v4 ψH(e10) = v0v5 Drawings of Graphs Graphs are so named because they can be represented graphically, and it is this graphical representation which helps us understand many of their properties. Each vertex is indicated by a point, and each edge by a line joining the points represent￾ing its ends. Diagrams of G and H are shown in Figure 1.1. (For clarity, vertices are represented by small circles.)

1.1 Graphs and Their RepresentatiorFig, 1.1. Diagrams of the graphs G and HThere is no single correct way to draw a graph: the relative positions of pointsrepresenting vertices and the shapes of lines representing edges usually have nosignificance. In Figure 1.l, the edges of G are depicted by curves, and those ofH by straight-lirle segments. A diagram of a graph merely depicts the incidencerelation holding between its vertices and edges. However, we often draw a diagramof a graph and refer to it as the graph itself; in the same spirit, we call its points'vertices' and its lines 'edges'.Most of the definitions and concepts in graph theory are suggested by thisgraphical representation. The ends of an edge are said to be incident with theedge, and vice versa. Two vertices which are incident with a common edge areadjacent, as are two edges which are incident with a common vertex, and twodistincadjacentverticneighbours. The set of neighbours of a vertex v in agraph G is denoted by Nc(o)An edgewithidentical erds is called a loop, and an edge with distendslink.Twoormorelinks withthesamepairofends aresaid tobe parllel edges.Inthe graph G of Figure 1.l, the edge b is a loop, and all other edges are links; theedges d and f are parallel edgesThroughout the book, the letter G denotes a graph. Moreover, when there isno scope for ambiguity,we omittheletterGfromgraph-theoreticsymbols andwrite, for example, V and E instead of V(G) and E(G). In such instances, wedenotethenumbers ofvertices and edgesof G by n andm,respectivelyA graph is finite if both its vertex set and edge set are finite. In this book, wmainle graphs, and the ternmgraph'always meanss 'finite graph'. TheICVgraph with no vertices (and hence no edges) is the null graph. Any graph with justone vertex is referred to as trivial. All other graphs are nontrivial. We admit thenull graph solely for mathematical convenience. Thus, unless otherwise specified,all graphs under discussion should be taken to be nonnullA graph is simple if it has no loops or parallel edges. The graph H in Example 2is simple, whereas the graph G in Example 1 is not. Much of graph theory isconcerned with thestudy of simplegraphs

1.1 Graphs and Their Representation 3 v0 v1 v2 v4 v3 v5 e1 e2 e3 e4 e5 e6 e7 e9 e8 e10 G u v x w y a b c d e f g h H Fig. 1.1. Diagrams of the graphs G and H There is no single correct way to draw a graph; the relative positions of points representing vertices and the shapes of lines representing edges usually have no significance. In Figure 1.1, the edges of G are depicted by curves, and those of H by straight-line segments. A diagram of a graph merely depicts the incidence relation holding between its vertices and edges. However, we often draw a diagram of a graph and refer to it as the graph itself; in the same spirit, we call its points ‘vertices’ and its lines ‘edges’. Most of the definitions and concepts in graph theory are suggested by this graphical representation. The ends of an edge are said to be incident with the edge, and vice versa. Two vertices which are incident with a common edge are adjacent, as are two edges which are incident with a common vertex, and two distinct adjacent vertices are neighbours. The set of neighbours of a vertex v in a graph G is denoted by NG(v). An edge with identical ends is called a loop, and an edge with distinct ends a link. Two or more links with the same pair of ends are said to be parallel edges. In the graph G of Figure 1.1, the edge b is a loop, and all other edges are links; the edges d and f are parallel edges. Throughout the book, the letter G denotes a graph. Moreover, when there is no scope for ambiguity, we omit the letter G from graph-theoretic symbols and write, for example, V and E instead of V (G) and E(G). In such instances, we denote the numbers of vertices and edges of G by n and m, respectively. A graph is finite if both its vertex set and edge set are finite. In this book, we mainly study finite graphs, and the term ‘graph’ always means ‘finite graph’. The graph with no vertices (and hence no edges) is the null graph. Any graph with just one vertex is referred to as trivial. All other graphs are nontrivial. We admit the null graph solely for mathematical convenience. Thus, unless otherwise specified, all graphs under discussion should be taken to be nonnull. A graph is simple if it has no loops or parallel edges. The graph H in Example 2 is simple, whereas the graph G in Example 1 is not. Much of graph theory is concerned with the study of simple graphs