1 GRAPHS a graphical repre- Pg many problems dealing with discrete objects and binary relations, jent form of repre- ay Phects and the binary relations on them is : i ofthe tds us naturally toa study ofthe theory Coon i ic TERMINOLOGY th ‘he graphs consist of points or nodes called vertices which are connected to each other sajtines called edges. These lines may be directed or undirected. 4g.DIRECT! EDGRAPH (P.T.U., M.C.A. May 2003 ; P.T.U., B.Tech. Dec. 2006, May 2005) ‘directed graph is defined as an ordered pair (V, E) where V is a set and E is a binary gation 07 V.A directed graph can be represented geometrically as a set of marked points V east of arrows E between pairs of points. Also ‘The elements in V are called vertices. ‘The ordered pairs in E are called edges. Foreg., consider the Fig. 11.1 given below. It is a directed graph, ea Directed graph Fig. 11.1 Fig. 11.2 Here, the vertices are a, b, d and the edges are (a, b), (b, a), (b, d), (d, a). An edge is said to be ineident with the vertices it joins. For example, the edge (a, b) is b) is incident from vertex a , uit with the vertices a and b. Also, we say that the edge (a ieident into vertex b. 423~ Dis 424 CTE ? ‘The vertex a is called the vertex and the vertex b is called the term: Res edge (a, b). 7 Ly, ao ‘An edge that is incident from and into the same vertex is called al : (Fig. 11.2). OOP oF sete ie Degree of a self-loop is two as it is twice incident on a vertex. “Toy, Corresponding to an edge (a, b), the vertex a is said to be adja. cent to the vertex b and the vertex 6 is said to be adjacent from the A vertex a. ‘ 4 A vertex is said to be an isolated vertex if there is no edge inci. : dent with it. : : j i For example, consider the following graph (Fig. 11.3) ‘The vertex ‘a’ has aself-loop. :. dega=4 The vertex ‘b’ is a Pendent vertex since only one edge is inci- dent on it. a ‘The vertex isan isolated vertex as it has no edge incident oni, Alsy gn, a =0. 11.4, (a) UNDIRECTED GRAPHS (PU. MCA Naya An undirected graph G consists of a set of vertices, V and a set of edges The... contains the unordered pair of vertices. If(u, v) ¢ B then we say w and v are eon edge where u and v are vertices in the set V. ected by an For example, let V = (1, 2, 3, 4) and E = (1, 2), (1, 4), (3, 4), (2, 3)). Draw the PU, MCA Me The graph can be drawn in several ways. May 2g ‘Two of which are as follows (Fig. 11.4 and Fig. 11.5). These are directed graphs Q 2) 1) @ ® ) © © Fig. 11.4 Fig. 11.5 ‘ Consider the graph shown in'Fig. 11.6 Determine the edge set and the vertex set of this undirected graph. 1 2 Fig. 11.6425 E= ((1, 2), (1, 4), (2, 3 ), (2, 4), (3, 4) V=(1,2,8, 4), : Hl py MIXED Cee : ; nG= IV, E] in which some ed; n '8es are directed and some : set is called a mixed graph. The graph shown in Fig. 11.7 ah. 6% graph ie i "FINITE GRAPH ial fH ,aph = [V, E] is said to be finite if V and B are finite seta Ag 4 (LINEAR GRAPH ie Fig. 11.7 aph G = (V, E) is said to be a linear graph ifits ed, se o—2 0 0 is linear graph, oresampres 4 DISCRETE OR NULL GRAPH a iges joining vertices lie along aline. ‘Agraph. containing only vertices and no edge is called a diserete or null graph. The ofedges in a graph G = [V, B] is empty in a discrete graph. Also each vertex in a discrete ‘ js an isolated vertex. 15. SIMPLE GRAPH (P.T-.U., B.Tech. Dec. 2006, May 2005 ; M.C.A. May 2007, Dec. 2005) Asimple graph is one for which there is no more one ed; ige directed from any one vertex pany other vertex. All other graphs are called multigraphs. (see Figs. 11.8, 11.9) Ae D A D : e ou , e es ——— 8 % c 8 a c ‘Simple graph Fig. 118 Fig. 119 nig. 11.9, the edges e, and e, are called multi edges. "COMPLEMENT GRAPH ‘The com "etces i ich has the same number of plement of a graph is defined to be a graph whicl “Sin graph G and has two vertices connected iff they are not connected in the graph G.oo DISCRETE g TH 426 PUcTys 11.7. (a) DEGREE (PTI, B.Tech. Dec, 2006, y, ty 204 i. The degree of v, denoted by « v be a vertex of an undirected graph. Y dv), ig of cage that connect v to the other vertices in the graph. The degree of many : rang negative. a 11.7. (b) INDEGREE AND OUTDEGREE (PLU. B.Tech, e If v is a vertex of a directed graph, then the outdegree of vy, denoted by outless (v), is the number of edges of the graph that initiate v. The indegree of v, denoted by indeg(v), is the number of edges that terminate at v. For e.g., consider the graph shown in Fig. 11.10. The degrees of A, B, C, D are 3, 3, 5, and 3 respectively. Mutigraph 41.8. SOURCE AND SINK Fig. 11.19 Uy A vertex with indegree 0 is called a source and a vertex with y outdegree 0 is called a sink. For example, consider the graph shown in Fig. 11.11. Here u, is a sink. 4) | For example, consider the graph shown below (Fig. 11.12) Fig. 111 The graph shown in Fig. 11.12 has 7 edges. a Indegree of ‘a’ = 3, Indegree of b’ = 2; } Indegree of ‘’ = 1, Indegree of ‘d’ = 1 Also, outdegree of ‘a’= 1, _outdegree of ‘6’ = 3 outdegree of ‘c’ : cisasink. outdegree of ‘d’ = 3. d c 11.9. EVEN AND ODD VERTEX Fig. 11.12 A vertex is said to be even vertex if its degree is an even number. A D A vertex is said to be an odd vertex if its degree is an odd number. en For example, consider the graph, as shown in Fig. 11.13. The vertices A and D are even vertices since deg(A)=2, _e, j deg(D) = 2 The vertices B and C are odd vertices since deg(B) = 3, deg(C) = 3 A vertex of degree zero is called isolated vertex. B & G Avvertex with degree one is called a pendent vertex. The 25s RG only edge which is incident with a pendent vertex is called the Fig. 11.13 pendent edge.2 anne le rtices are called adjacent if they 0 vk say that vertex e, is adjacent to n 427 ENT VERTICES i! are connected by vertex e, and vey Jf 7 gheorem J, Show that ed sum of degree of all the Uertices in a graph G, is even. f, Bach edge contribute two degrees in a graph, Also, ach of the vertices on which it is incident. tom if there are N edges in G, then we have 2N = d(vy) + dv.) +... dvy) thus, 2N is always even. other statement. The sum of the de, umber of edges in G. co 'y an edge. If there is an edge ie Ttex e, is adjacent to vertex ey. each edge contributes one fences Erees of the vertices of a graph G is equal to qheorem Il. Prove that in any graph, there are an even number of vertices of odd de- (P.T.U., M.C.A. Dec. 2005) odd. Now, make two groups Yay U, and other with odd degree of vertices © proof. Consider a graph having vertices of degree even and «ives. One with even degree of vertices v,, erties. : yy ge ‘Suppose, Ved) +dW,) +... +dlv,) Usd(u,) + dus) +... +du,). Now, we know that sum of degree of all the vertices is even (Theorem 1). So, V + U is 1a : % Since, V is the sum of K even numbers. Hence, it is even, But U is the sum of n odd unter, So o be U an even number, n must be even, Hence proved, ILLUSTRATIVE EXAMPLES Example 1. Verify that the sum of the degree of all the vertices is even for the graph soon in Fig, 11.14. vy Ve 4 Fig. 11.14428 Sol. The sum of degree of all the vertices is =d(v,) + d(v,) + dv,) + dv,)+ dv,) + di M6) + dov,) +g =243434343444242 = 09 whi Kw chiseven, ®) Pxample 2. Verify that there are an even number of Vertices of odd degres As shown in Fig. 11.15. he rap Fig. 11.15 Sol. The number of vertices of degree odd are 8 and each have degree three in the ab, graph. Hence, we have even number of vertices of odd degree. Above 11.11. PATH IN A GRAPH A path of length n is a sequence of n + 1 vertices of a graph in which ach pair of vere, is an edge of the graph. 1. A Simple Path (P.TU,, B.Tech, Dee 2003) The path is called simple one if no edge is repeated in the path ie” ali the vertices are distinct except that first vertex equal co last vertex. 2. An Elementary Path. Th the path i.e, all the vertices are dis 3. Cireuit or Closed Path (P.T.U., B.Tech. May 2002) The circuit or closed Path is a path which starts and ends at th. e same vertexive, v=, 4 Simple Circuit Path. The simple circuit is a simple path which is « circuit, path is called elementary one if no Vertex is repeated in tinct. Theorem III (a). Suppose a raph G contains two distinct paths from a vertex u tog vertex v. Show that G has a cycle, (P.T.U,, B.Tech, May 2002) Proof. Consider two distinct (eye, Paths from u tov be P, = 0,5 05s wseny €,). Now delete from the paths P, and P, all the initial edges which are identical ie, of we Me en 83a es'tymess \ ot ey bute, #6’, |. We will delete all the first k edges of both the paths P, and'P,, fter deleting the k edges both the Paths end atv. Now, to first meet any gy ony @,) and Py =(e/, Start from the same vertex, (let u,) and construct a cycle, start from Vertex w, and follow the left over path of P, until we Vertex of the left over path of P,. Iethis vertex is u,, . th then the remaining cycle ig computed by following the left over pat of Pz which starts from tus and ends at v. a _—_£m WH 0). Ifa graph has n em I vertices 429 peor path from v tow of length no more ae vertex v ig connected i882 Ge prove this theorem by mathe on 10 vertex w, then y and the shortest path from v tow pa ot*Adiction, Let yg now that, a vertex list for a path ofengsh » Tet m, where m ig ume that v is Pve ted a8 Uo» Uy» U2 ~~ Up» Where vy = y ang v, will have m + 1 vertices The =a tse there are only n distinct ., tert *-This path ean ore ince n ertices and m vers Now east be same duplicated vertices in the lane are listed in the path ere circuit in the path. Thus our assumption j ™ ver reduced, which is a contradiction f Rot after v,, tTue and the minimus’ ple 3. Consider the graph shown ya simple path from V, to V,. Y An elementary path from V, to V,. ay simple path which is not elementary from V, to V, UM apath which is not simple and starting from iyo (i asimple circuit starting from V,, : (Acireuit which is not simple and start gobi) Asimple path from V, to V, is Vy Vos Var Va Ves Vo. (i) An elementary path from V, to V, is Vy, Vay Var Vg Vp Vo. ii) Asimple path which is not elementary from V, to V,is : a V5 V51 Van Vy, Vo. {v) Apath which is not simple and starting from V, is Vor Vay Var Von Var Ves Ve d (v) Asimple circuit starting from V, is Pigs ; Vy Von Vip Ves Ven Vas Vy. (oi/Acireuit which is not simple and starting from V, is ‘an Var Vi» Vo» Vip Vy» Vor Example 4. Consider the graph shown in Fig. 11.17. Give an example of the following : in Fi i 18. 11.16. Give an example of the following ing from V,, (i) An elementary path (ii) A simple path (iii) A path which is not simple (iv) A simple path which is not elementary (v)A simple circuit (vi) A circuit which is not simple. a b © ZC Fig. 11.17430 Sol. There are many solutions to the above problems, but we will take only on (i) An elementary path is a, 6, fed. © for, cag (ii) A simple path is a, heb da. (ii) A path which is not simple is a, 6, €, & bd. ath which is not elementary is a, 6, e, f, ¢, 6, d. (iv) A simple pi (v) A simple circuit is a, 6, ¢ f (vi) A cirouit which is not simple is a, b, €,f ¢ b, dy a Example 5. Consider the graph as shown in y, : Fig. 11.18. H y Determine the following : (i) Pendent vertices (ii) Pendent edges (iii) Odd vertices * fe, (iv) Even vertices (v) Incident edges (vi) Adjacent vertices. % ol. (i) The vertex V, is the pendent vertex. vy *% < (ii) The edge (V,, V,) or e, is the pendent edge. . ‘ (iii) The vertices V, and V, are odd vertices. ig. 11.18 (iv) The vertices V,, V, and V, are even vertices. (v) The edge e, is incident on V, and V,. The edge e, is incident on V, and y, ‘The edge e, is incident on V, and V3. ‘The odge e, is incident on V, andy" hs ‘The edge e, is incident on V, and V,. (vi) The vertex V, is adjacent to V, and V,.__‘The vertex V, is adjacent to V, and¥, ‘The vertex V, is adjacent to V, and V,. The vertex V, is adjacent to V, and ‘The vertex V, is adjacent to V,. , Example 6. Consider the graph G shown in Fig. 11.19. Find the complement of ti graph. ie Va | ‘ Fig. 11.19 Sol. The complement of above is i i p graph is shown in Fig. 11.20. Here, we consider °° plete graph of 4 vertices and then delete the edges that are in G from the complete gr=0 remaining graph is the complemented graph.Va V3 Fig. 11.20 Complement of Graph G. wit yNDIRECTED COMPLETE GRAPH (P.T.U., M.C.A. Dec. 2004) i undirected complete graph G = (V, E) of n vertices is a graph in which each vertex is ied to every other vertex i.e., and edge exists between every pair of distinct vertices. It “rated by K,. A complete graph with n vertices will have n(n — 1/2 edges. iat ‘The complete graph k, for n = 1, 2, 3, 4, 5, 6 are shown below: —: ky ke AS Example 7. Draw undirected complete graphs K, and K,. Sol. The undirected complete graph of K, is shown in Fig. 11.21 and that of K, is shown iaFig. 11.22. vy Ve vy Ve vo} Vo Fig. 11.21. K, Fig. 11.22. K,~ 432 iscrere STRUG, Example 8. Draw the undirected graphs K, arid K, Ue Sol. Undirected graphs K, and K, are shown in Figs. 11.28 and 11.94 as Vs Vo! Vy Vo V5 4 . Fig. 11.23. Ky, Fig. 11.24. K, 11.13. CONNECTED GRAPH PU, B.Tech De C, 2 A graph is called connected if there is a path from any vertex u to v oF vice, ss) 'ersa, 11.14. DISCONNECTED GRAPH A graph is called disconnected if there is no path between any two ofits vertices 11.15. CONNECTED COMPONENT A subgraph of graph G is called the connected component of G, if it is not con any bigger subgraph of G, which is connected. It is defined by listing its vertices"! Example 9. Consider the graph shown in Fig. 11.26. Determine its connected componny Fig. 11.25 Sol. The connected components of this graph is {a, b, c}, {d, e, fl, {g, A, i) and {j). 7 Example 10. Consider the graphs shown in Figs. 11.26, 11.27 and 11.28, Determint whether the graphs are (a) Connected graphs or (b) Disconnected graphs. Also write their connected components.433 Fig, 1.26 i Fig 1 Mig. 11.27 Fig, 11.28 gol (The graph shown in Fig. 11.26 is a disconnected graph and its connected compo- sare eats (Wy Var Vn Vals (V5, Ve Vz, Vg) and (Vy, V, «iyThe graph shown in Fig. 11.27'%8 a diseonnected grad gents are (Vy, Va), (V5, Vals (Vg» Vols (Vis Vals (Vo, Vag) and (V,,, Vip) i The graph shown in Fig. 11.28 is a connected graph —. ‘theorem IV. Let G be a connected graph with at least two vertices. If the number of sjgsin Gis less than the number of vertices, then prove that G has a vertex of degree 1 Proof. Let G be a connected graph with n 22 vertices. Because graph G is connected, G tos no isolated vertices. Suppose G has no vertex of degree I. Then the degree of each vertex atleast 2. This implies that the sum of the degrees of vertices of G is at least 2n. Hence, it filiws that the number of edges is at least n (the sum of the degrees of vertices in any gh is twice the number of edges), which is a contradiction. This implies that G contains at {ast one vertex of degree 1. 1146. SUBGRAPH (P.T.U., B.Tech. Dec. 2006) Asubgraph of a graph G = (V, E) is a graph G’ = (V’, B’) in which Vc V and E’ CE and cath edge of G’ has the same end vertices in G’ as in graph G. a Note. A single vertex is a subgraph. Example 11. Consider the graph G shown in Fig. 11.29. Show the different subgraphs ofthis graph. 8 E Fig. 11.29bove graph (shown in Fi, Sol. The following are all subgraphs of the abo ne m Fis. 13, i, 11.32, 11.33). There may be another subgraphs o B % c ‘ D A c Fig. 11.30 Fig. 11.31 B B ae ic A c Fe 1D D = E Fig.11.52 Fig. 11.33 Example 12. Consider the directed graph as shown in Fig. 11.34. Show the four diff. ent subgraphs of this graph having at least four vertices. vy 4 Vs v, Fig. 11.34 Sol. The four subgraphs of the directed graph are shown in Figs. 11.35, 11.38, 1137 and 11.38, There may be another subgraphs ofthis graph.435 vs Ve Vo Ms vs \ Vy ve Fig. 11.35 Fig. 11.36 vy ve vy ve Ms V5 Ve Vs Fig. 11.37 Fig. 11.38 Je 13. Consider the multigraph shown in Fig. 11.39. Show two different subgraphs camp! eo h which are itself multigraphs. i mltigr a Fig. 11.39 Sol. The two different subgraphs of this multigraph which are itself multigraphs are shown in Figs. 11.40 and 11.41. There may be another subgraphs of this multigraph. Fig. 11.41436 DISCRETE stray s 11.17. (a) SPANNING SUBGRAPH PT.U,, B. Tech, Dec. » A graph G, = (V,, E,) is called a spanning subgraph of G = (V, E) if G, conten vertices of G and E+ E,. all thy For example : The Fig. 11.42is the spanning subgraph of the graph shown in ne B 129, —E Fig. 11.42. Spanning Subgraph. 11.17. (b) COMPLEMENT OF A GRAPH Let G = (V, E) be a given graph. A graph G =(V, E) is said to be com- plement of G = (V, E) If ¥ = V and E does not contain edges of E. i.e., edges in E are join of those pairs of vertices which are not joined in G. Consider the graph shown in Fig. 11.43 ‘The complement graph is shown in Fig. 11.44. Fig. 1143 Note that a graph and its complement graph have same vertices. Ifa graph G has n vertices and K, is a complete graph with n vertices, then G=K,-G Fig. 1.44 Consider K,. Then Consider K,. Then o * °a e COMPLEMENT OF A SUBGRAPH a 1. wi yet the F) be a graph and § be ae, f 4 subgraph of a japh so obtained is complement of rabgrepe sie a mieneees ee 3. -s the graph and its Consider A subgraph ghee ‘Then the complement of ot 8 S= Note that in a complement of a subgraph, the number of vertices donot change. 1118. (a) CUT - Consider a connected graph G = (V, E). A cut set for G is a smallest set of edges such removal of the set, disconnects the graph whereas the remaval of any proper subset of ‘st left a connected subgraph. pisses For example, consider the graph shown in Fig. 11.45. We determine the cut set for this poh Fig. 11.45 For this graph, the edge set ((V,, V,), (Vz, Vs)} is a cut set. After the removal of this set, have left with a disconnected subgraph. While after the removal of any of its proper subset, wehave left with a connected subgraph. 1148. (b) CUT POINTS OR CUT VERTICES Consider a graph G = (V, E). A cut point for a graph G, is a vertex v such that G-v has ‘ore connected components than G or disconnected. tga t® SUberaph G-v is obtained by deleting the vertex v from the graph G and also delet- I the edges incident on v. a438 DISCRETE g7, 11.19. EDGE CONNECTIVITY Let G = {V, E} be a connected graph, then cardinality of cut set of G is ¢ connectivity of graph G. ‘The edge connectivity of a connected graph cannot be more than the small ‘m vertex in the graph. It is denoted as A(G) Vertex connectivity Let G be a connected graph. Vertex connectivity of a graph is the least nu ces whose removal disconnects the graph. It is written as K(G) and is give by K(G)=n-1 for a complete graph with n vertices For example, we find edge and vertex connectivity of following graphs (Figs. 11.4611, alled 4 lest degree ber of ye Fig. 11.46 Fig. 11.47 In Fig. 11.47, removal of vertices 1, 2,6 disconnects the graph while removal of any t vertices does not. vertex connectivity is 3. It is a 3-regular graph. Only all edges incident on a vertex will disconnect it, edge connectivity is also 3. In Fig. 11.48, edge and vertex connectivity is 4. Theorem V. Prove that a simple graph with k-components and n vertices can have the most of BoB EsD edges. (P.TU., M.C.A. Dee. 200 Proof. Let the number of vertices in each of the k-components of a simple graph Gt yy gy ensey My Then k > %=2, where n, 21 1 We know that maximum number of edge in the i component of G = 2 n(n; -) ke Maximum number of edges in a graph less G = )) "7% i nS ]-3[ 0ins, No# Yn? sn? —(k- V2n-k) iat since £ Y @,- D =n~k, squaring both sides 2 i=) es (m,-1)+(n,-D+...... + - DP =n -kP : (nny — DP + (Mg VP + oeree + (My = VP + Diy — Wing = 1) + arn + (ity D) = (2 hP & yb +g + eee # My? — BM + My + one +n) + k + Non-negative terms = (n — hk)? ‘ “ 2 Yn? - 2) n, +b + Non-negative terms = (n —k)? a is 2 Ss 24 Be Is -2n + k + Non-negative terms =n? +k? — 2nk e ? + Non-negative terms = n? + k? - 2kn + 2n-k =n? — 2n(k — 1)2n -k) -n] ‘ = Yn? sn2?-@-DEQn-» a «From (1), we have Maximum number of edges in the graph G. [n? — (k - 1)(2n -k)-n) [n? - Qnk +k? +n—k) role win Rie 0 ( -kP + -k) = Fin — ink +) Hence the theorem. Example 14. Give an example of a graph with six vertices that has exactly two cut Sol. The graph with exactly two cut points is shown in Fig. 11.48.DISCRETE StRUcry 440 Fig. 11.48 this graph are c and d. The other vertices are not cut poin, 2 eae ‘The two cut points in thi ts sin, hh into more than one connected compo; al of them does not divide the graph it re one co1 meee removal of them doe: ith six vertices that has no cut pointy e sle of a graph wit le 15. Give an exampl J ari ee Bias -aph with no cut points is shown - eee eae Aah eee ‘any vertex and the edge: any cut poin more than one connected components. Not conta vide it in Fig. 11.49 Example 16. Consider the graph shown in Fig. 11.50. Determine the subgraphs @G-v, (ii) G-0, (iii) G- 0, Vs Vv, Fig. 11.50 jown in Fig. 11.51. is as shown in Fig. 11.52, 5 is as shown in Fig. 11.53. Sol. (i) The subgraph G-», is sh (ii) The subgraph Gy (tii) The subgraph G-v, CCVs Ve ve Vs Ve vig, 11.51 Fig. 11.52 Fig. 11.53 gxample 17. Consider the graph G shown in Fig. 11.54. Determine all the cut points of G. a b ¢ 9 fs e ' Fig. 11.54 gol. (a)'The vertex b is cut point for G. Since, G-b has more than one connected compo- vats as shown in Fig. 11.55. (b) The vertex is also a cut vents as shown in Fig. 11.56. point for G. Since G-e has more than one connected compo- : ° a b ¢ . 3 4 £ ‘ a of Fig. 11.55, Fig. 11.56 11 '120, BRIDGE (Cut Edges) th that G-e has more Reena a graph G = (V, E). A bridge for a graph G, is an edge ¢ suc components than G or disconnected.442 Example 18. Consider the graph sh (WG-e, (ii) G-e wn in Fig. 11.57. Determine the subgrapy, (ii) G-e, " Fig. 11.57 Sol. (i) The subgraph G-e, is shown in Fig. 11.58. (ii) The Subgraph G-e, is shown in Fig. 11.59. V, vy ° y, p Vs & ey Vs Ve vs Fig. 11.58 (iii) The subgraph G-e, is shown in Fig. 11.60. e 1 Ve e . vs sa vs Fig. 11.60 Fig. 11.59re 19. Consider the graph G shown in Fig. 11.61. Determine all the bridges of G. ple Fig. 11.61 ig) The edge ¢; is a bridge for G. Since G-e, has more than one connected compo- 2, wen in Fig. 11.6 ‘ er edge e, is a bridge for G. Since G-e, has more than one connected components as a Me ps Ve. oh * = Vy Ws al e ee e| ee ° Ve w yin ee ve vn A Fig. 11.62 Fig. 11.63, Example 20. Give an example of a graph with six vertices for the following : (a) that has exactly two bridges. (6) that has no bridges. S0l.(a) The graph that has exactly two bridges is shown in Fig. 11.64. The two bridges are e, and ey. q e ee ft a e t oom, Fig. 11.64 Fig. 11.65 te since renee =e bridges is shown in Fig. 11.65. This graph does not contain any e ‘dge does not divide it into more than one connected components.1. Draw a graph whose every edge is a bridge. wn in Fig. 11. the graph h, we got Example 2! Sol. The graph sho any edge is removed from ‘66 is a graph whose every edge is a bridge by, two components or a disconnected gr. . , y Ne Vs 11.21. ISOMORPHIC GRAPHS ‘two graphs G, and G, are called ence between their vertices and between their edges i.¢., tution except that the vertices may have different labels. Let G, = [Vj By) and G, = [Vp, Bp} are two graphs. These graphs are said to be isom, phic if there exists « function f: G, ~ G, such that o (j) fis one-one and onto ii) f preserves adjancies i.e., (iii) f preserves non-adjancies ‘The function fis called isomon ‘Theorem VI. If fis an isomorphism of graphs G, and Gt the degrees of v and flv) are equal. Proof, Let dog(v) = m : we can find exaetly m vertices ¥,, Ug, U, adjacent tov, Since fis an isomorphism, fv,), Av,), ~- Av.) are adjacent to fv) ‘Also as there is no other vertex adjacent to the vertex v in G,, there is no other ve adjacent to flu) in G,.: deg flv) = m. Hence the Theorem. For example, consider the following graphs shown in Fig. 11.67 and Fig. 11.68. They isomorphic graphs.(use above theorem) Ife, y) € By, Then (fix), fy) € By ie, If (x,y) é E,, Then (fx), fy) € E, phism between G, and G,. then, for any vertex v in G! vy ve Fig. 11.67445 pple 2 Show that the graphs shown in Fig. 11.69 and Fig. 11.70 are isomorphic i p a i, Fig. 11.69 Fig. 11.70 the degrees of vertices of two graphs and find the vertices from both the = degrees and make the pairs of the vertices in decreasing order of degree shoving Ss contain vertices having same degree, then they are isomorphic otherwise {fhe 00 rties in decreasing order of degree are as follows {pea ig) er d(vy), dd) © dlv,), d(b) © d(v,), dle) © dv), dic) © dvs). rh the graphs contain vertices having same degrees, hence they are isomorphic are sl. COMP! $e ng same since, bot seme 25- Show that the graphs shown in Fig, 11.71 and Fig, 11.72are not isomorphic a D N k m a n Fig. 11.72 Fig. 11.71 ecause the vertices of the graph shown in Fig. 11.72 gol. The graphs are not isomorphic b Fig, 11.71 contains two vertices having degree less ving degree 3 but the graph shown in isa three. /2.0RDER AND SIZE OF GRAPH a let G be a graph. The number of vertices in a graph G is called 0G. The number of edges in a graph G is called size of G. for example, Consider the graph G shown in Fig. 11.70 Here order of G = 3 size of G = 4 number of edges in G = 4.) > ¢446 DISCRETE StrUcry Re 11.23. HOMEOMORPHIC GRAPHS are called homeomorphic graphs if G, can be obtained fr, ‘Two graphs G, and G, ea 7 f the edges of G,. In other words, we can introdu, a sequence of subdivisions of the degree two in any edge of graph G,. For ¢.g-, : Consider the graph shown in Fig. 11.74 and Fig. 11.75, They are homeomorphic g, 'aphg| Ce verticgs Fig. 11.74. G). Fig. 11.75. G,. Example 24. Show that the graphs shown in Figs. 11.76 and 11.77 are homeomorphy ic Fig. 11.76. G,. Fig. 11.77. G,. Sol. The two graphs are homeomorphic because G, can be obtained from G, by int ducing vertices of degree 2 on edges (V,, V,) and (V,, V,). Example 25. Consider the directed graph G = (V, E) as shown in Fig. 11.78. Determi the vertex set and edge set of graph G. Fig. 11.78447 tex and edge set of graph , Bis sre vor Ge UL, 2 3), (1, 2), ( oe 402, ), 10 26. Let G = Ila, b, 6, I (Ca, b),(b, 6), (, 6), (a j oe raph of @ = (V, E) is shown in Fig. 12.79, 1. 30 &, (d, a))). Draw the graph G. Fig. 11.79 mple 27. Consider the directed graph shown in Fig. 11.80. Determine the indegree Bxame (seach of vertices of the graph. ot utdearee i Fig. 11.80 Sol. The indegree of digraph is indeg (1) = 2, indeg (2) = 1, indeg (8) = 3 ‘The outdegree of digraph is outdeg (1) = 3, outdeg (2) = 2, outdeg (3) = 1. 11.4, WEAKLY CONNECTED (P.T.U., B.Tech. Dec. 2005) Adirected graph is called weakly connected if its undirected graph is connected i.e., the suph obtained after neglecting the direction. 11.25, UNILATERALLY CONNECTED DIGRAPH A directed graph is called unilaterally connected if there is a directed path from any ‘wiew to v or vice-versa, for any pair of nodes of the graph. 1128. STRONGLY CONNECTED DIGRAPH ov qh iteeted graph is called strongly connected if there is a directed path from any node w sulvice-versa, for any pair of nodes of the graph.— 448 DISCRETE STRuG Ty 11.27, DISCONNECTED DIGRAPH A directed graph is called disconnected if its undirected graph is disconne, Example 28. Consider the graphs shown in Figs. 11.81, 11.82 and 11,g3 graphs are (i) Unilaterally connected digraph (ii) Weakly connected digraph (iii) Strongly connected digraph (iv) Disconnected digraph (also find its connected components). ced, Which oF vy Ve a b * V9 Vs 4 e t fh Fig. 11.81 Fig. 11.82 Fig. 11.83 Sol. The graph shown in Fig. 11.81 is strongly connected because there is a every vertex u to v and also there is a path from v to w. It is also weakly and unilater connected because a strongly connected digraph is both weakly and unilaterally connecte ‘The graph shown in Fig. 11.82 is weakly connected but not unilaterally connected) cause there is no directed path from vertex a to b or a to ¢ ete. but its undirected graph connected Path fro ‘The graph shown in Fig. 11.83 is a disconnected graph. The components ofthis gra are {g, a, c, f, h, b} and (e, d}. 11.28. DIRECTED COMPLETE GRAPH A directed complete graph G = (V, E) on n vertices is a graph in which each verter connected to every other vertex by an arrow. It is denoted by K,,. Example 29. Draw directed complete graphs K, and K,- Sol. Place the number of vertices at appropriate place and then draw an arrow fr each vertex to every other vertex as shown in Figs. 11.84 and 11.85. My Y Vo Va! Ve Vp Vs Vs Fig. 11.84. K,, Fig. 11.85. K,,449 TEST YOUR KNOWLEDGE "1 J 42.3:45 and B= ((1, 2), (2, 3), (3,3), 9 a Se size of the graph G shown j 0 the in the figure below ; oi afi : (3, 4), (4, 5) »'4, 5)). Find thy © number of e, ‘dges and size sao (ii) ¥ @ d the difference between directed and undirected graph. (P.T.U, BT “U., B.Tech. Dec. 2003) is What tiate between paths and circuits. (P.T.U,, B. Tech. May 2007) fore "i pnileeG has 16 edges and all vertices of G are of degree 2, Find the numbe umber of vertices. wae 91 edges, 3 vertices of di n G has 21 edges, of degree 4 and other vertices a eer of vertices in Gi er vertices are of degree 3. Find the has 5 vertices, 2 of degree 3 and 3 of degree 2. Find the number of e of edges. ar nodes (vertices) are required to construct a graph with at ode is of degree 2. ph with exactly 6 edges in which there does not exist a graph with 5 vertices with degrees 1, 3, 4, 2, 3 respectivel , 3,4, 2, 3 respectively. iy show that 5 : Q be a graph with 8 vertices and 29 edges? Py can there be @ 8 ip ow 2 er there is a graph with 10 edges if each vertex has degree 2? Ea tate exunt 8 eva th. tp versceg cach af legen Ur Game 3) Draw a simple graph with 3 vertices Draw a simple graph with 4 vertices jpcive an example for 6)simple eraph Gi) non-simple graph (iii) Multigraph, with suitable diagrams - sv that the maximum number of edges in a graph with n vertices and no multiple edges are in-D) a « hve Hondshaking theorem which states that the sum of degree of the vertices of a graph is equal to twice the number of edges. « i Determine whether it is possible to construct a graph with 12 ‘edges such that 2 of t have degree 3 and the remaining vertices have degree 4. ‘Give an example of each of multigraph, weighted graph, simple graph, non-simple graph, __ directed graph with suitable diagrams. (PT, B.Tech. May 2005) \ (a Which of the graphs in the given, figure the vertices .s are isomorphic ? @i)450 OVSORETE stay (iv) (wi) (viii) Qo (b) Show that the following graphs are not isomorphic. Fig. 1 Fig. II451 Fig. I : 8. Fig. IL a (a) Draw the graph G (complement of G) of the 8raph shown below. Also show that Gand G eancitse, a lat Gand G are (P.T.U., B.Tech. Dec. 2002) c e oy (y A — a b Fig. 1 Fig. II (6) Draw the complement of the graph shown in the fig. IT 10, Draw (a) a graph in which no edge is a cut edge. (6) a graph in which every edge is a cut edge. (c) only one cut vertex. Il. Find, if a &-regular graph with 8 vertices has 12 edges. Also draw h-regular graph. 12. Consider the graph G shown below: (a) Is G simple? (>) What is order and size of incidence matrix for G. (© Find minimum and maximum degree for G. Se ee ee ee} 15. Suppose a directed graph has m vertices. Show that if there is a ina si th n vertices, each vertex has maximum Prove that maximum degree of edges in a graph G with n vertices nfn-) degree (p, 4 no mutiny, : path from y, there is a path p’ of length m — 1 or less from u to v. eer ty Answers (a) Number of edges = 4, Size of graph =5 (6) (i) Order = 4, Size = 6, (i) Orgg, (a6 (6) 13 . 4, Sine . (6 (No (a0. oS @ We or a 4 | al aX : . b c (a) Not possible (a) (i) and (vi) are isomorphic (ii) and (éx) are isomorphic (iii) and (vii) are isomorphic (iv) and (v) are isomorphic (viii) and (ix) are isomorphic (c) Not isomorphic (@ Isomorphie 8 hy= WAN. 12. (a) Yes (6) 6,9(c)5,2