30CHAPTER1.INTRODUCTIONTOGRAPHSFigure 1.2 shows six graphs, namely G and the graphs H, for i = 1,2,...,5.All six of these graphs are proper subgraphs of G, except G itself and Hi. SinceG is a subgraph of itself, it is not a proper subgraph of G. The graph H, containsthe edge uz.which G does not and so H, is not even a subgraph of G.The graphH3 isa spanning subgraph of G since V(H3)=V(G).Since yEE(G)butry E(Ha), the subgraph H is not an induced subgraph of G. On the otherhand, the subgraphs H2 and H, are both induced subgraphs of G.Indeed, forSi = {u, , y,z] and S2 = [u, U,y, z], H2 = G[Si] and Hs = G[S2]. The subgraphH4 of G is edge-induced; in fact, H = G[X], where X =[uw,w, wy, z,yz].QuQUuHi :G :H2:1yeuoowuoHs :H3 :H:1792yo02y2Figure1.2:Graphsand subgraphsFor a vertex u and an edge e in a nonempty graph G - (V,E), the subgraphG - u, obtained by deleting u from G, is the induced subgraph G[V-[u]] of Gand the subgraph G - e, obtained by deleting e from G, is the spanning subgraphof G with edge set E-fe).More generally,for a proper subset U of V, the graphG - U is the induced subgraph GJV - Ul of G. For a subset X of E, the graphG-X is the spanning subgraph of G with edge set E-X. If u and u are distinctnonadjacent vertices of G, then G + uu is the graph with V(G + uu) = V(G) andE(G + uu) = E(G) U [uu). Thus G is a spanning subgraph of G + uu. For thegraph G of Figure1.3, the set U = {t,] of vertices, and the set X ={tw, ur, ur]of edges, the subgraphs G-u, G-wz, G-U, and G-X of G are also shown inthat figure, as is thegraph G+uv.1.2ConnectedGraphsThere are several types of sequences of vertices in a graph as well as subgraphs ofa graph that are used to describe ways in which one can move about within thegraph. For two (not necessarily distinct) vertices u and u in a graph G, a u-walkW in G is a sequence of vertices in G, beginning at u and ending at u such that
30 CHAPTER 1. INTRODUCTION TO GRAPHS Figure 1.2 shows six graphs, namely G and the graphs Hi for i = 1, 2, . . . , 5. All six of these graphs are proper subgraphs of G, except G itself and H1. Since G is a subgraph of itself, it is not a proper subgraph of G. The graph H1 contains the edge uz, which G does not and so H1 is not even a subgraph of G. The graph H3 is a spanning subgraph of G since V (H3) = V (G). Since xy ∈ E(G) but xy /∈ E(H4), the subgraph H4 is not an induced subgraph of G. On the other hand, the subgraphs H2 and H5 are both induced subgraphs of G. Indeed, for S1 = {v, x, y, z} and S2 = {u, v, y, z}, H2 = G[S1] and H5 = G[S2]. The subgraph H4 of G is edge-induced; in fact, H4 = G[X], where X = {uw, wx, wy, xz, yz}. z x u w y u v y w z x ................................................................... ........................................................................... v H5 : H2 : H4 : H1 : H3 : G : u u v z y z x y w z x v y w u z x y . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ........ ........ . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ........ ......... . ........ ........ . ......... ......... . ......... ......... . ......... ........ . ......... ......... . ......... . ......... ......... ......... . ........ ........ . ......... ......... ......................................................... . .......................................................................... ........................................................................ . ......... ......... . ......... ......... . ......... ......... . ........ ........ . ........ ......... . ......... ......... Figure 1.2: Graphs and subgraphs For a vertex v and an edge e in a nonempty graph G = (V, E), the subgraph G − v, obtained by deleting v from G, is the induced subgraph G[V − {v}] of G and the subgraph G − e, obtained by deleting e from G, is the spanning subgraph of G with edge set E − {e}. More generally, for a proper subset U of V , the graph G − U is the induced subgraph G[V − U] of G. For a subset X of E, the graph G − X is the spanning subgraph of G with edge set E − X. If u and v are distinct nonadjacent vertices of G, then G + uv is the graph with V (G + uv) = V (G) and E(G + uv) = E(G) ∪ {uv}. Thus G is a spanning subgraph of G + uv. For the graph G of Figure 1.3, the set U = {t, x} of vertices, and the set X = {tw, ux, vx} of edges, the subgraphs G − u, G − wx, G − U, and G − X of G are also shown in that figure, as is the graph G + uv. 1.2 Connected Graphs There are several types of sequences of vertices in a graph as well as subgraphs of a graph that are used to describe ways in which one can move about within the graph. For two (not necessarily distinct) vertices u and v in a graph G, a u−v walk W in G is a sequence of vertices in G, beginning at u and ending at v such that
311.2.CONNECTEDGRAPHSG:G.2T77472sO1OU97oG-U:G-X :G+uw:uuwuFigure 1.3: Deleting vertices and edges from and adding edges to a graphconsecutive vertices in W are adjacent in G. Such a walk W in G can be expressedasW= (u = vo, i,..., Uk = w),(1.1)where vivi+1 E E(G) for 0 ≤i≤ k -1. (The walk W is also commonly denotedby W : u = vo, Ui,.., vk = v.) Non-consecutive vertices in W need not be distinct.The walk W is said to contain each vertex u(O ≤ i≤ k) and each edge uiui+1(O≤i<k-1). The walk W can therefore be thought of as beginning at the vertexu = vo, proceeding along the edge vou to the vertex ui, then along the edge viu2 tothe vertex v2, and so forth, until finally arriving at the vertex w = Uk. The numberofedgesencounteredinW(includingmultiplicities)isthelengthof W.Hencethelength of the walk W in (1.1) is k. In the graph G of Figure 1.4,(1.2)Wi= (r,w,y,w,v,u,w)is an r-w walk of length 6.This walk encounters thevertex w three times andthe edge wy twice.A walk whose initial and terminal vertices are distinct is an open walk; other-wise, it is a closed walk.Thus the walk Wi in (1.2) in thegraph G of Figure1.4is an open walk.It is possible for a walk to consist of a single vertex, in which caseit is a trivial walk. A trivial walk is therefore a closed walk.A walk in a graph G in which no edge is repeated is a trail in G. For example,in the graph G of Figure 1.4, T = (u, v, y, w, u) is a u - u trail of length 4. Whileno edge of T is repeated, the vertex u is repeated, which is allowed. On the otherhand, a walk in a graph G in which no vertex is repeated is called a path. Everynontrivial path is necessarily an open walk. Thus P' = (u, u, w,y) is u -y path of
1.2. CONNECTED GRAPHS 31 ............................................................... ....................................................... u v v x z u x z z x y w . ......................................................... ...................................................... ..................................... .................................... ..................................................................... ...................................... ................................... . ........ . ................................................. t w y s t w y x G − U : w y u v w y t G : G − u : G − wx : t s s s t w y v s z v s u x v u z z G − X : G + uv : .......................................... . ........ ........ . .. ......... ......... . ........ ......... . ......... ......... . ......... ......... . ......... ......... . ........ ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ....... ........ . ........ ........ . ........ ........ . ........ ......... . ........ ........ . ......... ......... . ........ ......... . ........ ........ . ......... ......... . ......... ......... . ......... ......... . ........ ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ........ ........ . ......... ......... . ....... ........ . ......... ......... . ......... ......... . ......... ......... . ......... ......... . . .......................................................... .................................. ........................ . . ..................................................................... . .................................................... ................... . ......... ......... . ......... ......... . ........ ........ . ........ ......... . ......... ......... . ......... ......... ........................ ................................... . . ............................................................ ................................................... . .............................. Figure 1.3: Deleting vertices and edges from and adding edges to a graph consecutive vertices in W are adjacent in G. Such a walk W in G can be expressed as W = (u = v0, v1, . . . , vk = v), (1.1) where vivi+1 ∈ E(G) for 0 ≤ i ≤ k − 1. (The walk W is also commonly denoted by W : u = v0, v1, . . . , vk = v.) Non-consecutive vertices in W need not be distinct. The walk W is said to contain each vertex vi (0 ≤ i ≤ k) and each edge vivi+1 (0 ≤ i ≤ k −1). The walk W can therefore be thought of as beginning at the vertex u = v0, proceeding along the edge v0v1 to the vertex v1, then along the edge v1v2 to the vertex v2, and so forth, until finally arriving at the vertex v = vk. The number of edges encountered in W (including multiplicities) is the length of W. Hence the length of the walk W in (1.1) is k. In the graph G of Figure 1.4, W1 = (x, w, y, w, v, u, w) (1.2) is an x − w walk of length 6. This walk encounters the vertex w three times and the edge wy twice. A walk whose initial and terminal vertices are distinct is an open walk; otherwise, it is a closed walk. Thus the walk W1 in (1.2) in the graph G of Figure 1.4 is an open walk. It is possible for a walk to consist of a single vertex, in which case it is a trivial walk. A trivial walk is therefore a closed walk. A walk in a graph G in which no edge is repeated is a trail in G. For example, in the graph G of Figure 1.4, T = (u, v, y, w, v) is a u − v trail of length 4. While no edge of T is repeated, the vertex v is repeated, which is allowed. On the other hand, a walk in a graph G in which no vertex is repeated is called a path. Every nontrivial path is necessarily an open walk. Thus P ′ = (u, v, w, y) is u − y path of
32CHAPTER1.INTRODUCTIONTOGRAPHSu0QG :ayFigure1.4:Walks in agraphlength 3 in the graph G of Figure 1.4. Many proofs in graph theory make use ofu-u walks or u--v paths of minimum length (or of maximum length) for somepair u, u of vertices of a graph. The proof of the following theorem illustrates this.Theorem1.3If a graphG contains au-wwalk,then G contains au-upath.Proof.Amongallu-uwalks in G,letP= (u= uo,ui,...,uk=u)be a u-u walk of minimum length. Thus the length of P is k. We claim that P isa u -- path. Assume, to the contrary, that this is not the case. Then some vertexof Gmustberepeated inP,sayui=ujfor someiand jwith O≤i<j≤k.Ifwethen delete the vertices ui+, ui+2,...,u, from P, we arrive at the u - walk(u= uo, ui,*-, ui-1, ui = uj, uj+1,...,uk = v)whose length is less than k, which is impossible.DA nontrivial closed walk a graph G in which no edge is repeated is a circuit inG.For example,C= (u,w,t,y,w, v,u)is a u-u circuit in the graph G of Figure 1.4. In addition to the required repetitionof u in this circuit, w is repeated as well.This is acceptable provided no edge isrepeated. A circuitC=(u= Vo,U1,...,Uk=v),k ≥ 2, for which the vertices i, 0< i< k-1, are distinct is a cycle in G. Therefore.C" = (u,v,y,a,w,u)is a u-u cycle of length 5 in the graph G of Figure1.4.A cycle of lengthk≥3 iscalled a k-cycle. A 3-cycle is also referred to as a triangle. A cycle of even lengthis an even cycle, while a cycle of odd length is an odd cycle.There are also subgraphs of a graph referred to as paths and cycles. A subgraphP of a graph G is a path in G if the vertices of P can be labeled as i, U2, ..,ukso that its edges are Viu2, U2u3,**., Uk-1vk. A subgraph C of G is a cycle in G
32 CHAPTER 1. INTRODUCTION TO GRAPHS G : w x y u v .. .............................................................. ............................................................... ... ................................................................. ............................................................... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... Figure 1.4: Walks in a graph length 3 in the graph G of Figure 1.4. Many proofs in graph theory make use of u − v walks or u − v paths of minimum length (or of maximum length) for some pair u, v of vertices of a graph. The proof of the following theorem illustrates this. Theorem 1.3 If a graph G contains a u − v walk, then G contains a u − v path. Proof. Among all u − v walks in G, let P = (u = u0, u1, . . . , uk = v) be a u − v walk of minimum length. Thus the length of P is k. We claim that P is a u − v path. Assume, to the contrary, that this is not the case. Then some vertex of G must be repeated in P, say ui = uj for some i and j with 0 ≤ i < j ≤ k. If we then delete the vertices ui+1, ui+2, . . . , uj from P, we arrive at the u − v walk (u = u0, u1, . . . , ui−1, ui = uj, uj+1, . . . , uk = v) whose length is less than k, which is impossible. A nontrivial closed walk a graph G in which no edge is repeated is a circuit in G. For example, C = (u, w, x, y, w, v, u) is a u−u circuit in the graph G of Figure 1.4. In addition to the required repetition of u in this circuit, w is repeated as well. This is acceptable provided no edge is repeated. A circuit C = (v = v0, v1, . . . , vk = v), k ≥ 2, for which the vertices vi , 0 ≤ i ≤ k−1, are distinct is a cycle in G. Therefore, C ′ = (u, v, y, x, w, u) is a u − u cycle of length 5 in the graph G of Figure 1.4. A cycle of length k ≥ 3 is called a k-cycle. A 3-cycle is also referred to as a triangle. A cycle of even length is an even cycle, while a cycle of odd length is an odd cycle. There are also subgraphs of a graph referred to as paths and cycles. A subgraph P of a graph G is a path in G if the vertices of P can be labeled as v1, v2, · · · , vk so that its edges are v1v2, v2v3, · · · , vk−1vk. A subgraph C of G is a cycle in G
331.3.DISTANCEINGRAPHSif the vertices of P can be labeled as ui,2,..,vk (k ≥3) so that its edges areUiu2,u2u3,...,vk-1vk,vkui. Consequently, paths and cycles have two interpreta-tions in graphs -as sequences of vertices and as subgraphs.This is the case withtrails and circuits as well.The path P' and the cvcle C described earlier in thegraphGof Figure1.4 correspond tothe subgraphs shown in Figure1.5.uuUuUU-0OGwp0OayyayFigure 1.5: A path and cycle in a graphTwo vertices u and uin a graph G are connected if G contains a u-u path.The graph G itself is connected if every two vertices of G are connected. ByTheorem1.3,agraphGisconnectedifGcontainsau-uwalkforeverytwovertices u and u of G. A graph G that is not connected is a disconnected graph.The graph F of Figure 1.6 is connected since F contains a u-upath (and a u-walk) for every two vertices u and u in F. On the other hand, the graph H isdisconnected since, for example, H contains no y4 - ys path.31T192QQ33F:H :Cby4O15ZOO0y6y597T6Figure 1.6: A connected graph and disconnected graphA connected subgraph H of a graph G is a component of G if H is is not aproper subgraph of a connected subgraph of G.The number of components in agraph G is denoted by k(G).Thus G is connected if and only if k(G) = 1. Forthe sets Si = [y1,y2,y3,y4) and S2 = (y5,y6,y7] of vertices of the graph H ofFigure 1.6, the induced subgraphs H[Si] and H[S2] are (the only) components ofH. Therefore, k(H) = 2.1.3DistanceinGraphsIf u and are distinct vertices in a connected graph G, then there is a u-u pathin G. In fact, there may very well be several u -u paths in G, possibly of varying
1.3. DISTANCE IN GRAPHS 33 if the vertices of P can be labeled as v1, v2, · · · , vk (k ≥ 3) so that its edges are v1v2, v2v3, · · · , vk−1vk, vkv1. Consequently, paths and cycles have two interpretations in graphs – as sequences of vertices and as subgraphs. This is the case with trails and circuits as well. The path P ′ and the cycle C ′ described earlier in the graph G of Figure 1.4 correspond to the subgraphs shown in Figure 1.5. .................................. ..................................... u x G : w y u v y w v x y u v P ′ : C w ′ . : ................................... . ....... ........ . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ........ ......... . ......... ......... . ........ ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ........ ........ . ......... ........... . ............................... .................................. ..................... .. . ............................ ... .. .. .. .. .. . .. .. .. .. .. Figure 1.5: A path and cycle in a graph Two vertices u and v in a graph G are connected if G contains a u − v path. The graph G itself is connected if every two vertices of G are connected. By Theorem 1.3, a graph G is connected if G contains a u − v walk for every two vertices u and v of G. A graph G that is not connected is a disconnected graph. The graph F of Figure 1.6 is connected since F contains a u − v path (and a u − v walk) for every two vertices u and v in F. On the other hand, the graph H is disconnected since, for example, H contains no y4 − y5 path. ................... .. .. .. .. .. .. .. .. .. .. x2 x4 x6 x5 y5 y6 y7 x1 y1 y2 y3 x3 y4 F : H : . ......... ......... . ......... ........ . ......... ......... . ........ ......... . ......... ........ . ......... ........ . ........ ......... . ........ ......... . ......... ......... . ........ ......... . ......... ......... . ......... ......... . ......... ......... .................. .. .. .................... .......................... .. .... .... ..... Figure 1.6: A connected graph and disconnected graph A connected subgraph H of a graph G is a component of G if H is is not a proper subgraph of a connected subgraph of G. The number of components in a graph G is denoted by k(G). Thus G is connected if and only if k(G) = 1. For the sets S1 = {y1, y2, y3, y4} and S2 = {y5, y6, y7} of vertices of the graph H of Figure 1.6, the induced subgraphs H[S1] and H[S2] are (the only) components of H. Therefore, k(H) = 2. 1.3 Distance in Graphs If u and v are distinct vertices in a connected graph G, then there is a u − v path in G. In fact, there may very well be several u − v paths in G, possibly of varying
34CHAPTER1.INTRODUCTIONTOGRAPHSlengths.This information can be used to provide a measure of howclose uand uareto each otherorhowfarfrom each othertheyare.Themost common definitionof distance between two vertices in a connected graph is the following.The distance d(u,u) from a vertex u to a vertex y in a connected graph G istheminimum of thelengths ofthe u-upaths in G.A u-upath of length d(u,u)iscalled a u-ugeodesic.In the graph Gof Figure 1.7, thepath P= (i,U5,u6,uio)is a v1 - v1o geodesic and so d(i, u1o) = 3. Furthermore,d(ui, Vi) = 0, d(v1,2) =1, d(v1,ve) = 2, d(1,) = 3, and d(u1,vs)= 4U1U23V4G:U5UsU6U7Ug10Figure 1.7: Distances in a graphThe distance d defined above satisfies each of the following properties in a con-nectedgraphG(1) d(u, v) ≥ 0 for every two vertices u and u of G;(2) d(u,v) = 0 if and only if u = v;(3) d(u,v)=d(u,u) for all u,EV(G) (the symmetric property):(4) d(u,w)≤ d(u,) +d(u,w) for all u, v,w E V(G) (the triangle inequality)Since d satisfies the four properties (1)-(4), d is a metric on V(G) and (V(G), d) isametricspace.Sincedissymmetric,wecanspeakofthedistancebetweentwovertices u and u rather than the distance from u to v.The eccentricity e(u) of a vertex u in a connected graph G is the distancebetween u and a vertex farthest from in G.The diameter diam(G)of G isthe greatest eccentricity among the vertices of G, while the radius rad(G) is thesmallest eccentricityamong the vertices of G.The diameter of G is also the greatestdistance between any two vertices of G. A vertex u with e(u) = rad(G) is called au with e(v) = diam(G) is called a peripheralcentral vertex ofGandavertevertex of G.Two verticeand u of G with d(u,) = diam(G) are antipodalvertices of G.Necessarily.if u and yantipodal vertices in G,then each ofuand u is a peripheral vertex. For the graph G of Figure 1.7,e(v6) = 2, e(v2) = e(v3) = e(u4) = e(v5) = e(v7) = e(vg) = e(V10) = 3,e(ui) = e(vg) = 4
34 CHAPTER 1. INTRODUCTION TO GRAPHS lengths. This information can be used to provide a measure of how close u and v are to each other or how far from each other they are. The most common definition of distance between two vertices in a connected graph is the following. The distance d(u, v) from a vertex u to a vertex v in a connected graph G is the minimum of the lengths of the u−v paths in G. A u−v path of length d(u, v) is called a u−v geodesic. In the graph G of Figure 1.7, the path P = (v1, v5, v6, v10) is a v1 − v10 geodesic and so d(v1, v10) = 3. Furthermore, d(v1, v1) = 0, d(v1, v2) = 1, d(v1, v6) = 2, d(v1, v7) = 3, and d(v1, v8) = 4. .......................................... ............................................. ..................................... v1 v2 v3 v8 v6 v7 G : v5 v9 v10 v4 . ......... ......... . ........ ......... . ........ ........ . ......... ........ . ......... ........ . ........ ......... . ......... ......... . .. ........ ......... . ........ ......... . ........ ......... Figure 1.7: Distances in a graph The distance d defined above satisfies each of the following properties in a connected graph G: (1) d(u, v) ≥ 0 for every two vertices u and v of G; (2) d(u, v) = 0 if and only if u = v; (3) d(u, v) = d(v, u) for all u, v ∈ V (G) (the symmetric property); (4) d(u, w) ≤ d(u, v) + d(v, w) for all u, v, w ∈ V (G) (the triangle inequality). Since d satisfies the four properties (1)-(4), d is a metric on V (G) and (V (G), d) is a metric space. Since d is symmetric, we can speak of the distance between two vertices u and v rather than the distance from u to v. The eccentricity e(v) of a vertex v in a connected graph G is the distance between v and a vertex farthest from v in G. The diameter diam(G) of G is the greatest eccentricity among the vertices of G, while the radius rad(G) is the smallest eccentricity among the vertices of G. The diameter of G is also the greatest distance between any two vertices of G. A vertex v with e(v) = rad(G) is called a central vertex of G and a vertex v with e(v) = diam(G) is called a peripheral vertex of G. Two vertices u and v of G with d(u, v) = diam(G) are antipodal vertices of G. Necessarily, if u and v are antipodal vertices in G, then each of u and v is a peripheral vertex. For the graph G of Figure 1.7, e(v6) = 2, e(v2) = e(v3) = e(v4) = e(v5) = e(v7) = e(v9) = e(v10) = 3, e(v1) = e(v8) = 4