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 simplegraphs1.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