Graph Theory OBJECTIVES Introduction Graph: Directed, Undirected, Simple Properties of Graph Adjacency & Incidence matrix of a Graph Operations on Graphs Cycle & Wheel Graph Bipartite @ Complete Bipartite Graph Weighted Graph Shortest Path in Weighted Graph Complete Graphs Isomorphic Graphs Path, Cycles @ Circuits Eulerian & Hamiltonian Graphs Matching & Coverings102 Discrete Mathematical Structures 10.1 Introduction ie é s. Its basic ideas were introduced in the Graph theory is an old subject with many modem applications. its WS OT eo solve the famous cighteenth century by the great Swiss mathematician Leonhard Kénigsberg bridge problem, which we will discuss in this chapter. = ; Graphs are used to solve problems in many fields. For example, graphs can be pote ar eaapai wee a circuit can be implemented on a planar board. We can distinguish between two chemnice! Cobponls wit the same molecular formula but different structures using graphs. We can determine whetet TV Computer are connected by a communications link graph models of computer networks. Graphs wit — ts oasis to their edges can be used to solve problems such as finding the shortest path between fre CHS in transportation network. We can also use graphs to schedule exams and assign channels to television stations ‘There was an old Persian town Kénigsberg formed by two Islands 1 and I situated in a Pregel ‘The city was divided into four parts and were connected by seven bridges. as exhibit in the fig. 1. om th banks A and B, one bridge connecting the two Islands. The main problem was to take-up a journey startin from any paint of either bank or island and returning back to the same starting paint after walking over al the bridges only once. Fig. 1 The inhabitants made several attempts to it but none could be successful. At last, in 1736, this problen was referred to the Irish Mathematician L, Euler (1707-1783) for its probable solution. For solution, Eule made use of graphs and as such laid down the foundation of graph theory. He represented the problen by the following graph.Tce ABI I are called the vertices of | gg de Blands |; and I, respectively, The as oF lines denoted by 6.0, 0, @ F eae On Oe se, and @ 5 peidges. The degree *ertex means the 1 7 are called edges of the graph denoting seven _ wor cach of degree 3 and I, was of depress OF eas incident on it. Therefore the vertices A, B. I, bridge be trave not be possible to have conclusion that, it is not possible up tne oy nly once and thus the problem was settled down with 4 : 2 path as i ; zit is als0 worth while to mention two needed i-e., Euler Circuit. so fee Of Trees with their applications in Electrical Networks. A. . 2 trying to enumerate the Isomers of saturated Hydrocarbons _G Hoes At that time two important conjectures were made. The fis s the four color conjecture which ‘or any planar geographical map (atlas) in which the countries with famous unsolved problem in graph theory, though it has Simulated an enormous amount of research in this field. | Problem of Necessary and Sufficient Conditions for a Hamiltonian Circuit __ Apuzzle game was invented in 1859 by the lish mathematician Sir WR. Hamilton (1805-1865). It consisted of 2 wooden dodecahedron having 12 faces and 20 comers, Each face was a regular pentagon with three fess meeting at each comer. ‘The comers were marked with the names of 20 important cities like London, Paris, Delhi, New York,Discrete Mathematical Stry and wavel along the edges of the dodecahedron, vg turn back to the starting city. Although the puzzle stence of such a circuit (called Hamilton, ent context the purpose is to ana The object of the puzzle was to start from any © each of the remaining 19 cities exactly once and ret E easily solved but the necessary and sufficient condition for the exi circuit) in an arbitrary graph is still the area for research. In the pres basic terminology and make familiar with some elementary sults on graphs. (as a rep a Sew A graph, written as G = (V, E) consists ‘of two components : 1. The set of vertices V, also called points or nodes, and es or arcs, connecting pair of vertices. 2. The set of edges E, also called lin xy an edge, is called the end points or en id vertices. Each pair of vertices, connected bs (aos Directed! Graph G A directed graph (V, E) consists of a set of vertices V of V. Example 1. @ G,= (yy, v3}, fe}) anda set of edges E that are ordered pairs of element ae cic e ¥y Gi) Gy= (€1, 2,3}, {61 eo e0)) 1 e 2 = e 7 (ii) Gy = (11, 2, 3, 4, fer &as es €4}) 4 2 3 e i 1 ey 2 Remark 1. A graph in which each edge is directed is called a directed h. grap!pndtboted Graph ph G= (VE), in which ev © is 2 A get mph. ery edge is associated with an unordered pair of vertices is called an gxample 2. () Gi = (rn Yah €e}) # ——______, 1 e % Ged 2,3}, {e1, eas &5}) 1 % 4 2 ~ 3 * Ina graph G = (V, E), if some edges are directed and some are undirected, then it is called a mixed graph. Example 3. G = ({1, 2, 3}, {e1, es, €3}) (mixed graph) ‘Avvertex v which is not connected with any vertex of a graph G, by an edge, is called an isolated vertex. Example 4. “If all the vertices of a graph are isolated [i.e., set.E = 4], the graph is called 2 null graph (or a totally Aisconnected graph). Example 8. G = ({,, ¥p Ys ©a Discrete Mathematical Struct, ”% Joop. Therefore, a loop is an edge ‘An edge having the same vertex as both its end vertices is called a self of the form (a, a). Example 6. Let V = (a, b,c, d) be a set of vertices, and E = ((a, @), (4, 6), (a, d), (b, €)} set of edges, Then G = (V, E) is drawn as follows b d Fig. 4 The edge (a, a) is represented by a closed curve drawn at a and is called a self loop. Let G = (V, B) be a graph and let e € E be a directed edge associated with the ordered pair of vertices (or nodes) (u, v). Then the edge e is said to be initially or originating in the vertex w and terminating of ending in the vertex v. The vertices w and v are called the initial and terminal vertices respectively of the edge e. An edge ¢ € E which joins the vertex u and v is said to be incident on the vertices 1 and v. Here parallel edges are a, b; 2,3 and 4, 5; 1, 2 and 3, 4‘A graph having neither self toop nor : allel edge i in the following two graphs, G, ig ae Saeed asi i imple graph otherwise called a multigraph. 118 @ simple graph while G, is si 4 mnultigraph, 4a /X yy b, e b G, G 2. Finite and Infinite Graph mae Ina graph G = (V, E), if the set V ah SetV and E are both finite then it is called a finite graph otherwise an infinite Example 7. Let G = (V, B) are infinite graphs. (WB) be a graph, where V= fv, v5, ¥5, wn} and E fe}, ep) ».}, then the following The number of vertices in a graph is called its order. ‘The number of edges in a graph is called its size. Remark 2, In calculating the size of a graph, a loop is treated to be of size 2. Example 8. Find the number of vertices, edges, loops, isolated vertex, parallel edges in the following graphs. Graph G:0% 0% oo e Graph G : % & vy C) 1 ¥s ve Ye M%Discrete: Mathematical Strty ey Vy My «donated a disconnected graph Sotation: The graph Gy has only four vertices ae ey at be Mae Nae Me The graph i. (i) Seven vertices, (ii) nine edges, GiiJone sett Loop es (iv) one isolated vertex Ys (9) 8 pair of paratiel edges ¢) and ey Example 8. Find whether the graph Gy following diagram is a simple graph or not wwith end vertices yy and Mx. «fei Os ve £4 651) FESR by Mae Me Ms Fig. 8 Solution: The graph G is a simple graph, because it does not contains any loop or parallel edge. “Adjacent Edges and Adjacent Vertices Two non-parallel edges are said to be adjacent if both are incident on a common vertex. . es and &y, ey, &s are adjacent edges. For instance : In fig. 8, e, and e, Two vertices connected by an edge are called adjacent vertices. For instance, in fig. 8 v4, vss Yi Mas U5i My Ye are adjacent vertices. Although a pictorial representation of a graph is very convenient for a visual study, other representations are better for computer processing. A matrix is a convenient and useful way of representing a graph (03 computer. A graph can be represented by @ matrix in the following two ways, namely : (a) Adjacency matrix; (b) Incidence matrix. 1, Adjacency Matrix Let G = (V, E) be graph with # vertices, then the adjacency matrix of 5), is a syrumtetr matix ACG) = foes where uljaceney matrix of G, denoted by AG), is a sy ay =k, if there are & edges between ¥, and v).ample 10 Let G be a simple oe % Braph whose diagram is Y G Va : Fig. 9 then the adjacency matrix A(G) of G is displayed as follows MVD Vy YS ¥% yfol1o10 wll 01110 w}1 10100 A= vO 1 1011 vs}1 10101 ylo 0011 0 Remark 3. The adjacency matrix of a simple graph is always 2 boolean matrix. Remark 4. Each entry of the principal diagonal of A(G) is zet, if there is no self loop in G. Remark 5. If the graph is a simple graph (ic. without loops and parallel edges) then’ the degree of any vertex is equal to the sum of the non-zero entry of corresponding row of A(G) of corresponding column of A(G). Let G be a graph with m vertices, ¢ edges, 1@) = @)q~@ 18 an Xe matrix, where f if edge e; is incident on vertex vj,and 0, otherwise and no self loops. Then the incidence matrix of G, denoted by incidence Mat ay= Example 11. If following is a graph G 7 yy a ethen 4 5% 0 % %| ¥%5 %4 ¥s ¥6! UG)= Hees repatetat ey 0 0 e--eceo 7% 00 00 1 00 10 o1 Ste teers e--oo scoo-ee -so-s Sooo es Remark 6. Since every edge is incident on exactly two vertices, each column of 1(G) has exactly two js, Remark 7. The number of 1's in each row equals the degree of the corresponding vertex. Remark 8. A veretx whose corresponding row has all 0’s, represents an isolated vertex. Remark 9. Parallel edges in a graph produce identical columns in its incidence matrix. Remark 10. The I(G) contains only two elements, 0 and 1, such a matrix is called a binary matrix oa boolean matrix or a (0, 1) matrix. Example 12. Find the adjacency matrix A = [ay] of the following graph Y A Fig. 11 Solution: The given graph is a multigraph with 5 vertices so its adjacency matrix is as follows : ‘The number of edges incident on a vertex v of a graph is called the degree of the vertex v and is dem as deg(v).endant Vertay) A vertex of degree one is known as the Pendant vertex, Example 13. Find the degree of ean ; on pendant vertex ? ‘ach Vertex in the following Braph, Also find is there any isolated vertex Solution: In the given graph deg (,)=4 deg (v,)=3 deg (v,)=0 deg (v,)=3 deg (¥5)=7 and deg (v,) = 1 ey Fig. 12 Here, v3 is an isolated vertex since deg (v3) = 0 and vg is a pendant vertex since deg (vs) = 1. Remark 11. The point of intersection is not treated as a vertex because it can be represented in a different manner. In example 8, the edges e; and es are shown intersecting but they may be denoted in a different way, so that may not look intersecting, Remark 12. Degree of a vertex is a non-negative integer. [i020 “Even ‘and Odd Vertices ” Ina graph, if the degree of a vertex is an even integer then the vertex is called the even vertex, and if the degree of g-xfitex is an odd integer the vertex is known as the odd vertex. Theorem. The Handshaking Theorem. The sum of the degrees of all the vertices in a graph is equal to twice the number of edges in the graph. IRTU 2009, 2011] Proof. Let G = (V, E) be a graph with n-vertices i, |V| = and the number of edges are |E| = e (say). Since each edge is incident with two vertices (u, ¥), say, $0 each edge contributes a count of 1 to each of ‘deg (u) and deg (v). Therefore, e edges will contribute 2e degrees (one for each end vertices of an edge), for all vertices. $ Deg(v,)=2e= 2. Fe .m 1 shows that the sum of the degrees of all the ph G is always even, IRTU 2009] Thus we vertices in a graph is always even. _ Remark 13, The theore! Theorem 2. The number of vertices ‘of odd degrees in a gray OR has an even number of vertices of odd degree. feven degree and the set of vert An undirected graph - Proof. Let V, and V; be the set of vertices 0} © in'an undirected graph G = (V, &). Then of odd degree, respectively,Discroto Mathomatical Structuro, 2o= Lewy) = ¥ dev) Y deg) je=lel wr wh wey Since deg(v) is even for v © Vj, the first term in the right hand side of the equality is even, Furthermore, the sum of the two terms on the right hand side of the equality is even, since this sum is 2e, Hence, the second term in the sum is also even, Since all the terms in this sum are odd, there must be an even number of such terms, Thus, there are an even number of vertices of odd degree. “1027 Degreé ofa Vertex in a Directed’ Graph eg Since the edges in graphs with directed edges are ordered paits, the definition of the degree of a vertex ean be refined to reflect the number of edges with this vertex as the initial vertex and as the terminal vertex, Ina graph with directed edges the in-degree of a vertex v, denoted by deg-(v), With v as their terminal vertex, The out-degree of v, denoted by deg’(v), their initial vertex, is the number of edges is the number of edges with v as Remark 14. A loop at a vertex contributes 1 to both the in-degree and out-degree of that vertex, Example 14. Find the in-degree and out-degree of each vertex in the graph G with directed edges displayed in the following figure. Solution: The in-degrees in G are : deg(a)=3, deg-(b) = deg(c)= deg(d) deg(e) ‘The out degrees are : deg*(a)=3, deg’(b)=1, deg*(c)= deg"(d) deg'(e)=3. Remark 15. Let G = (V, E) be a graph with directed edges. Then 2 deg™(v)= E deg*(»)=1e1 vey vey Remark 16, In a graph G, the sum of the out-de of the vertex v i.e., deg'(v) + deg(v) = deg(v). Remark 17, The out-degree and in-degree of an isolated vertex is always zero. Remark 18, The sum of out-degree and in-degree of a pendant vertex is unity Brees and in-degrees of a vertex v is equal to the degree deg'(v) + deg(») = 2 4if we find the degree of each y d rent fag Ee ree com Of © graph and write them in an ascending order, the sequence #0 Sequence of the graph, id the dew Agree sequence of the fatlowing graph G. Example 15. Solution : In this graph G deg(yy, . deg(',) = 3, deg(v,) = 0, deg(v',)= 3, deg(v.) = 7 and deg(v) = 1 . The degree sequence is (0, 1, 3, 3, 4, 7). Example 16, Construct two graphs having same degree sequence. m %, Solution : Let G= vy V2 Fig. 15 degree sequence is (2, 2, 2, 2) and : E D B ic Fig. 16 degree sequence is (2, 2, 2.2, 2 2)- : : Example 17. Prove that the degree of a vertex in a simple graph G with n vertices cannot be greater than @-1,Discrete Mathematical Structan, : parallel edges. Thus any vertex y Solution: Given that the graph is simple so it has no loops snd n0 ee be adjacent to at the most (mt — 1) vertices. Hence 0 < deg) Discrete Mathematical Struc, 5 ible? Example 24, Find whether a 3-regular graph on 17 vertices is feast Solution. Given that s = 17, n= 3 Now by size formula, ef ‘The value of 1 is not an integral value, so such a graph is not feasible. Example 25. Show that a 3-regular graph G on 14 vertices is feasible. Solution. Given that s = 14, » = 3 ‘A graph / is said to be a subgraph of graph H if all the vertices and all the edges of / are in H, and eae! edge of / has the same end vertices in h as in H. OR Let H(¥, E) be a graph, then the graph h(V,, E,) is said to be a subgraph of the graph H if 6 4 V, CV and 6 #E, CE Example 26. b ob b ; a d a hy h, H Fig. 19 In this figure 19 hy, hy are subgraphs of the graph H. The vertices a and b are isolated in the subgraph ?(epanning subgraph) Fig. 19 Remark 19. The following observations can be made immediately: (@) Every graph is its own subgraph (b) A subgraph of a subgraph of G is a subgraph of G. (0) Asingle vertex in a graph G is a subgraph of G. (@ Assingle edge in G, together with its end vertices, is also a subgraph of G. Let G(V, E) be a graph and S\(V,, E)), S:(Vo, E,) be two subgraphs of G. ‘Then subgraphs are known as vertex disjoint if VS) 9 VS)=9 and are called edge disjoint if E(S)) 0 E(S2)=9 ‘The vertex disjoint subgraphs are always edge disjoint. Suppose that G = (V, B) be an undirected graph, Let v © Y, the subgraph of G represented by G ~ v has the vertex set V, = V-— {v} and the edge set E, cE, where E, involves all the edges in E except for those which are incident to the vertex v. We conclude that the subgraph G ~ vis induced by set V,. G ~ v can Suppose that G = (V, E) be an undirected graph, letting ¢ = (a, 2) € E, we find a subgraph, denoted by G, from G by deleting the edge e without removing the vertices.- 5 Diserote Mathematical Structure, Example 28, Fig. 20 G, is also represented by G— e. 10.30 Connected Graphs and ‘Disconnected Graphs A graph G is said to be connected if there is at least one path between every pair of vertices in G, otherwise it is said to be disconnected, A disconnected graph consists of two or more connected subgraphs. Each of these subgraphs is called component. Example 29. The following is a connected graph. 1 5 g a °G i 34 q| if “ 7 = 2 6 Fig. 21(a) : Connected Fig. 21(b) : Disconnected Theorem 3. A graph G is disconnected if and only if its vertex set V disjoint subsets V, and V2 such that there exists no edge in G whos the other in subset V,. Proof. Let such a partitioning exists. Consider two arbit 5 & Vp. No path can exists between vertices a and b; ‘one end vertex would be in V, and the other in V. can be partitioned into two non-void, ¢ one end vertex is in subset V, and trary vertices a and b of G, such that a V, and otherwise, there would be at least one edge whos? Hence, if a partition exists, G is not connected. sraph. Consider a vertex a in G. Let V, be the set of all S disconnected, V, does not include all vertices of G Tb? No vertex in V, is joined to any in V, by any edge. Hence Conversely, suppose that G be a disconnected vertices that are joined by paths to a, Since G i vertices form a (non-void) set V,. the partition, Theorem 4, If graph (connected or disconnected) has exact two vertices of odd degree then there th joining these two vertices,which are odd. From theorem 1, "Y component of a disconnected graph, no graph can have ices. Thus, i es. Thus, in graph G, vy and vy must belong to same component, and therefore ‘must have a path between them Theorem 5. A simple graph (i.e, a > @ graph with components can have at moat 2 ee secre edges or self loops) with m vertices and & IRTU 2011, 2009, 2007] graph G be my rs, My ie, ZTn=n (1) where n;>1, i Consider, S-95 55, 1k a a isl squaring both the sides, we get [Ee -»| = (nk? =r? +h? -2nk ist & or, ¥ (4? 2m, +1) + non-negative cross terms = n? + @ — Ink iat (} = 2nj +1) 3, consist of 1 vertices vy, v5, . Wy Vads oocy Mats Yabs and (py V1} Remark 21. In a cycle C, (# > 3), each vertex is of degree 2, so each cycle is a 2-regular graph. Example 34. Sketch the cycles C,, 3 <1" <6. Solution: The cycles C3, C4, Cs and C, are displayed in the following EO Fig. 2510.34 Wheels We obtain the wheel W,, when we add an additional vertex new vertex to each of the m vertices in Cy) by new edges. ae Remark 22. The wheel is a simple graph having (n + 1) vertices and 2n edges. Remark 23. In wheel, the additional vertex is of degree and in the remaining (n— 1) vertices, each (ete is of degree 3, Example 35. Sketch the Wheel W,, 3 sn<6. a Solution: The wheels W3, W,, Ws and W, are displayed in the following to the cycle Cyp for 2 3, and connecs 4, IRTU 2010 Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets such th each edge connects a vertex in one of these subsets to a vertex in the other subset. OR, A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint nonvoi sets V, and V, such that every edge in the graph connects a vertex in V, and a vertex in V,(so that n¢ edge in G connects either two vertices in V, or two vertices in V,). Example 36. Show that C; is bipartite. Solution: Since its vertex set can be partitioned into the two sets V, = {M4. V5. Vs} and Vz = {¥, Ma Ye and every edge of Cs connects a vertex in V, and a vertex in V,,jeanple 37, Blow that ig 118-101 bipang intuitions 1 We divide panite, © VEN, ph Whe graph Set Of Kin erties 10H As Hiparting 1019 tn disig yortos 18 COMKELIE to eyeny lige (ae 10 vemos uneig en 2S: Ont Of Hanmple Mh, Ave the * HY an eAye, ‘Ty, MADE Cl end Ht displayed ax fol fallen us Ky connot be bipartite. rs bipartite ? a b i : i c fd Pig, 28 Soluttons Ciruph Gi is bipartite, since its i : i} cach edge connects verter 42 CT tis the union of two distnet sets, fa, by d) and (6, e,f a i¢ of these subsets to a vertex in the other subset (Note that f 0 be bipartite it is not necessary that eve i eae Oe eee eee a}. Vor instance, b and gate not adjacenyy 2 “ME% I fs bs dh be adjacent to every vertex in fe, ef Gruph HE is ic bipanite since its vertex set cannot be panitioned into two subsets so that edges do not connect WO vertices from the same subset (The reader should verify this by considering the vertices a, b and f). ‘The complete bipartite graph K,,, , is the graph that has its vertex set partitioned into two subsets of m and vertices, respectively, such that there is an edge between two vertices if and only if one vertex is in the fir subset and the other vertex is in the second subset. Example 39, Display the complete bipartite graphs Ky, Ky3, Kyg, and Ky, Solution: : (i) S (ii) x (iti) Gv) ‘ Kay Ky Fig, 29Diserete Mathematical Structin, Example 40. Prove that if G = (V, E) is a bipartite graph with 1 vertices, then the total number of aja. in G cannot exceeds 7— 4 2: Solution : We know that there are p + q vertices and pq edges in a complete bipartite graph K, If yy, ni it numbers are equal, then their product is maximum. On taking p=9=" in the bipartite graph, the maxim, number of edges will be A graph G = (V, E) is called a weighted graph, when each edge is assigned a positive real number, Example 41. The following graph is a weighted graph. Fig. 30 edge (a, 6) = 1 edge (b, c) = 2 edge (c, a) = 3 edge (c, d) = 5 edge (d, e) = 6 edge (e, = 7 edge (f, g)= 8 edge (g,e)=9 ete. Remark 24. Many problems can be modeled using graphs with weights assigned to their edges. As a illustration, consider how an airline system can be modeled. We set up the basic graph model by represent cities by vertices and flights by edges. Let G = (V, E) be a weighted graph. To find the shortest path distance between the two specific vertices G is known as the shortest path problem.‘(HAO Details of Dik ~gyample 42. What is the length of following graph. solution. The shortest path can ea : easily found by inspection, we come across certain ideas useful in understanding Dijkstra’s algorithm. Our aim is to eo path from a to successive vertices, Ive this problem by finding the length of the shortest until z is reached. ‘The only path beginning at is ‘Sinning at a that contain no vertex other than a (until the terminal vertex is reached) are a, b, and a, d. As the lengths oe igths of a, b and a, d are 4 and 2, respectively, it follows that d is the closest vertex We can find rae closest vertex by looking at all paths that go through only a and d(until the terminal vertex is reached), The shortest such path to bis still , b, with length 4, and the shortest such path to € is a, d, ¢, with length 5, Consequently, the next closest vertex to a is b. To find the third closest vertex a, we want to examine only paths that go through only a, d, and b (until the terminal vertex is reached). There is a path of length 7 to c, viz., a, b, ¢ and a path of length 6 to z, viz., a, d, e, z. Consequently, z is the next closest vertex to a, and the length of the shortest path to z is 6. Ne In this algorithm, following a weighted graph the intial vertex is temporarily labeled (marked) with 0 and the other vertices with a permanent label «. In the first step, the other vertex, under the following rules, is labeled by V. (i) Every vertex v; which is in of Vp initial label of v; + wir ength) of the edge (vi, ¥j)- In case there is no edge i) Now we find the minimum value of all the vertex labeled by =, itis labeled by the corresponding FT el IF there is a tie between, for the miniaum value of any, two vetioes, then no vertex can be selected. The iteration takes place till we reach the d Example 43, What is the length of the shortest path between the vertices p and u, in the following weighted ‘graph, Solution, In the given weighted ‘own enclosed in a square (). labeled, is labeled by the symbol having the value minimum {initial label ‘))}s where; in the fist step is labeled by w and w(v,v) is the weight between y; and v; then we have w(vj, vj) = 2. jestination vertex. raph the table of temporary label and permanent level is as follows. The temy label will be sh and the most recently assigned permanent label porary label wil in the vector is indicated by a tick YDinorete Mathomationt Mructayy The length of the shortest path between the PIroqosotou vertices pand w= 13, and the shortest path iy ‘xampple 44, What is the length of the shortest path between the vertices panel v in the following diet weighted graph: Solution. The table of temporary and permanent labels, in the given directed weighted graph, is as follow fee 4 r 5 i u v oy | = ° e [es « ° ol 7 I ° ~ co oo oO 7 My = ~ ° oO 4 in] * 5 4 co oO 4 oO 4 5 @ fou oO @ a 14 5 @ I o|a@|o 12 5 a u 0] @ a 2 | oy | 7 o @ Oo 12 8 @ 7 o a oO 12 a @ Ty ‘The shortest path is pF > v. The length of the shortest path between the vertices p and vis 7~The union of two simple a Sraphs Gs Veand B= Fro Ea and is donotey py Ge 2D 8M Gs = (vy, yy Example 45. Find G, Ug, ee i ae = (Vx Ed) = (rn vy, v5, Vs, % Yas Vs U5), em ey) {e125 €3, ey €5, e6}) and Gy e e 3 % . : G, Fig. 32(a) a - 32(b) Solution: We have . GU G = (VB) oe ae G02 Wintersection of TwolGrapns! The intersection of two graphs G, = (Vj), E,) and G, = (V>, E,) is a graph G = (V, B) such that, V = V, OV; and E = E, 0 E,, It is denoted by G = G, 0 G;. Example 46. For the graphs G, and G, as given in example 32, find Gy 9 Gy. Solution: G, 7 G, = (V, E), where V = {v5 V2 Ys Ys} and E = fe, ey, 5}Discrete Mathematical Structures — The ring sum of two graphs G, = (V,, E,) and G, = (V2, E,), denoted by G, © G,, is a graph G = E), where V = V, U V, and E is the set of edges cither G, or G, but not to both. Example 47. The ring-sum of two graphs G, and G, as given in example 32, is G = (V, E), where V Vy UV2= {Mp Va, Vay Ves M55 Vo} and E = {€4, €4, 5) €7y Cs or Cros 11}- The diagram of G, © G, is as follows : yg 7 & ( wh ee & G, ®G, ve e Vs Fig. 33 Remark 25. Obviously, by the definition of Union, Intersection and Ring-sum, @ G, UG, =G UG, (&) G, 0G) =G,9G, (© GUG=G=GnNG @ G, ®G,=G, 0G, (©) G@G = 6 (Null graph) Remark 26. If no edge is common in the graph G, and G,, then G, ® G,=G, UG,lementary graph & of ‘ The comp! a 4 simple graph g consisting oF alm vetices of gs all edge i Remark 27. Obviously, by go inition, Remark 28. 1 vertices, is the subgraph of the complete graph K,, Ne not in G, but are in K, 7 JS the degree of any vertex vi, then in the ‘he same vertex y, isn—py, Remark 29. The complemeniary gary k, of K, exist, but no edge ig Present, Remark 30, The complementary graph Kun Of complete bipantte graph K, , disjoint graphs K,, and K. Example 48. Let G = cy, n(n of complete graph K,, is @ graph in which all the n vertices is a graph of union of two E) be a simple graph of " Vertices and e edges then the number of edges in G vs Seen by G, x Gy, is a graph with set of (V»-Ey) and G2 = V2» Es es ty = 0, and the edge between The product of two graphs Gy = a (uy) and (Wy ¥2) are adj two ve pte Vertices V, x V, and anyDiscrete Mathematical Structuryy uy and vy belongs to E>, or uy = vy and the edge between u; and vy belongs to Ey. Example 49. The product G, » G, of G, and Gp can be shown as follows : (ity) (uy 2) (14, 2) ym) On) Oy) G,*G, The difference of two graphs G, and G,, written as G, ~ Gz, is a graph having all those edges which ar in G, but not in G,. G, — G, is also said to be the complement of G, in Gy. Example 50. If G, and G, are graphs as given below vr G then their difference is given ascues - e oe Graph’ nraph G is said t0 be decomposed into two subj : GU G,= Gand G, 4G, graphs G, and G, if =a null graph, gxample 51. The graph G a a b % Fe q e i: Ms © Vs Fig. 38 can be decomposed as identified i i laced ‘ i are sad to be fused (merged oF identified if the two vertices are rep See ee every edge that was incident on either w or v or on both is incident on the es =a te io of two vertices does not alter the number of edges, but it reduces the number new vertex. . of vertices by one.Digerote Mathematical Structur, Example 82. Fusion of Vertices aandb y vy @ (i) Fig. 41 | exists @ ‘Two graphs G, = (Vj), Ey) and G, = (V3, E3) are said to be Isomorphic to each other if there exist bijection mapping f from V, to V ie J: Vy > Vp such that for each of the vertices vy vj of Vy, (ey) € E, = (hv), Ay) © Ey The function fis called an Isomorphism from G, to G).(a) The same number of vertices ‘0 isomorphic graphs must (p) The same number of edges ¢) An equal number of vertices with a gi © ces with a given degree ive, same de However, these conditions are by no means suffic ‘Bee sequence, ne : sient. For insta all three conditions, yet they are not isomorphic, ee, the 0 Eas (given below) sty " w << —l_ y @) i ® Fig. 42 : Two graphs that are not isomorphic That the graphs in fig. 42(a) and (b) are not isomorphic can be shown as follows : If the graph (a) were to be isomorphic to the one in (b), vertex x must correspond to y, because there are no other vertices of degree three. Now in (b) there is only one pendant vertex, w, adjacent to y, while in (a) there are two pendant vertices, w and v, adjacent to x. ‘Thus the adjacency relationship is not preserved. Hence 42(a) and 42(b) are not isomorphic. Finding a simple and efficient criterion for detection of isomorphism is still actively pursued and is an important unsolved problem in graph theory. Example 54. The following graphs G = (V, E) and G' = (V', E’) are isomorphic since f: V— V', fy) = (i= is i ic Vf (E= 1, 2, 3 4, 5) is isomorphi a 4 G Fig. 43 is ‘hic to each other. Example 55. Prove that the graphs G1 and G, are isomorphic b ey a 1 3 e e, 1% & e; yi 4 4 G, 2 G, fe 441034 - mumber of vertices: af Cy ~ umber of ventions of @ ee une ces of Gy = re ‘ fay we define mapping + We observe the follow = number of edges in Gy af) = bf) = 6. 4D) d “© WG) Solution edges of Gy 2G; 3 Gy by MI) and (1, 2) =e, € EGG) (AV), A) = lane ‘Also, (4 3) = €3 © E(Gz) =# 02) /3)) = (bh, 0) = © HAG) 3,4) =e) € E(G)) =9 (3). JA) © (ce, d= 4 © UG) Further, (1, 4) € E(G,)) => (f1), (4) = (a, d) & i) (2,4) # E(G,) = (f2), 4) = 1 # EG) (1, 3) @ EG) = (0), fB)) = (a) & Gy) Therefore fis one-one, onto, and preserves adjacency as well as non adjacency of vertices Hence G, and Gy are isomorphic to each other Remark 32, Two graphs are said to be isomorphic if there is a one-to-on : ; phi eco i Rema aes and between ther edges such that incidence of vertices are preserved. Nesmalin ce Z ally, we do a aie entiates between isomorphic graphs even though their display may look different. (See . (See example 4 Example 56. @ vy (i) Exampl = ple 57. Prove that the following graphs are isomorphic ic. ‘ 5 vy Ve | » - 5 vy . G=(%E) “ GSWEy "3 Fig. 47BY on8-one ony wh ere fly) = yn Now, we have only to ch graph G, v) and v3: vy and y, © Mapping wisics ey ‘ G . Fig. 48 Solution: In the figure 48, we see that the vertices v,, v2, vs, Vs, Vs and vg of G correspond to the vertices Vp Vy V'a, Way Vs V6 Of G’. Similarly the edges €,, €2, ¢3, C4, &s and es of G correspond to the edges ey e's, €'s, €g, €’s and e's of G’. Also the degree of vertices in G and G’ are the same. Thus G and G? are isomorphic. Example 59 (i). Prove that the graphs G,, G; and G,, G; are non-isomorphic. Al L. | vy 5 ud 2 a 4¢ Gs G Fig. 49 ‘ are not isomorphic. [RTU 2010) (iProve that these graphs G, and GoDiscrete Mathematical Structures == 6 Wig. 80 Solution (Dz Number of edges in Gy = 3 Number of exlges in Gy = 3 Number of ealges in Gy = i i ‘unter of edges in Gy = 4 5 sc nornorpiie, set of gi n As the sizes of Gy, Gy and Gy, Gy are not same, so these set of graphs are Eonar isomorphic, the degree sequence of its vertices will be sar cidont of the vertex = its edges), the degree of vertices Solution GD: UC pWo graphs ane Gis Me dease of vetoes (Number of ele ar lot + The degree sequence of Gy is 1 U For Gy: The degtoe of each vertex is 2, So the degree sequence is Since the degree sequences of both the graphs are not same, therefore, G, and G» are not isomorphic. Example 60, Prove that the following nvo rregular graphs G, and Gy are not isomorphic. vy RY? Vy AX ] % G, Fig. 51 ine , 2, 2, 2, 2. Solution, We have the following in the graphs G, and G. Wil =6= Ny IE\L= 9 = [El G, > G) by sin) = Let us define a mappi The mapping is one-one and onto, Further the vertices in both the graphs are each of degree 3 therefore, the degree sequences of vertices of the two graphs are also the same, but where as vertices 1 and 2 are adjacent in Gy, vy and vy are not adjacent in G,. Here the condition of adjacency does not hold between the two graphs. Hence they are not isomorphic. A simple graph G = (VE are isomorphic.Theo ample 61. The following gra pe & Eph G is a self complementa a of G. y graph and G is the complementary graph 7 i) Ma % Z ee e 7 % G Fig. 82 Let us define a mapping set of vertices of G —> set of vertices of G. where M4) = ¥25 £2) = vgs f0v5) = v, and fry the edges ¢,, 2 and e, of G are in corresponder isomorphic. Hence G is a self complementary g: Example 62. ¥5, then obviously fis one-one onto mapping under which ance with the edges e’y, e’, and e’; of G. So G and G are raph, Determine whether the following pair of graphs are isomorphic ¥ vi : ; BX " ¥ v. % Gres. ‘ G Fig. 53 Solution. Let a mapping be defined as f : set of vertices of G, —> set of vertices of G,, where (v4) = v'y, Mi) = V's, fs) = V'p flv) = v's and flv) = v's. Obviously, fis one-one onto mapping under which the edges {¥4, Va}, {¥2 Vals (v3 Mal» (sy V5} and {¥s, %} of G; correspond to the edges {v"), v's}, {0"4, v'2), (¥'p, v's}, (5) V's} and (v"s, v"s}. Thus G, and G, are isomorphic. Example 63. Show that the following graphs are isomorphic Me ZY. hs bx y, % 5 G Fig. 54 Solution : There are 10 vertices and 15 edges in both the graphs G, and G,, degree of each vertex in Gy andDiscrete Mathematical Structures Gy are also same i.e, three. ‘The vertices My. Yas Yar Vor Ye My vo and Yio OF Gy ate also corresponding With the vertices. Wy. V%y. Wye gs Whos Hae Moe Pp Hy and" OF Gye ‘Vhus Gy and G, are isomorphie. Example 64, Show that the following graphs are not isomorphic. Fig. 55 Solution : The number of vertices and edges in G, and G, are the same even then Gy, and G, are not isomorphic because the degree of the vertex vy is 4 while there is no vertex of degree 4 in G,, ‘Thus G, and Gy are not isomorphic. that G = (V, B) be @ graph, then the subgraph g(V, E,) of G is called the component of G provided that g is connected and there does not exist a super subgraph g, of G containing g. Therefore g is not Proper subgraph of any connected subgraph of G. Therefore gC G is a component of G if for x, y € V\(g) = x and y are connected [implies that there is a path from x to »]. The number of component of G is denoted by K(G). Theorem 6, Prove that there exist a simple path between every pair of distinct vertices of a connected undirected graph. 4 Proof. Suppose that u and v be two distinet vertices of the connected undirected graph G = (V, E). Since G is connected, there is at least one path between w and v. Let xq, X15 X>y suns Xyy Where Xp = u and x, = be the vertex sequence of a path of leat length, This path of least length is simple. Suppose that it sno simple. Then x;= x for some i and j with O < i But the sets {e,, e3}s (ee &5 &) to be cut sets.Divcrolo Mathomatien! Steucty 10.54 Bridge : that edge is called a bridge for the If a entset for a connected graph consists of exnetly one edge, ten raph OR a graph G is known ay the bridge if KG ~ ¢) > K( An edge Example 67. In the following graph Fig. 58 {ei}, {ez} and {ey} are eutsets and ¢}, ey and ey are the bridges. 10.55" Edge Connectivity ~ mallest cut-set) is defined as the edge connectivity of G. The edge connectivity of a connected graph is also said to be the minimum number of edges whose deletion increases the number of components of the graph by 1. The minimum number of vertices whose deletion from the graph G = (V, E) leaves the remaining graph G, = (V;, E,) disconnected, is called the vertex connectivity of G. Vertex connectivity is sometimes also called simply connectivity. Example 68. In the following graphs, g es a d (a) (b)determine the edge connectivity ‘The edge conne, Solutlo tivity in the The verte connectivity in the gmphs (a) Ren al Remark 37. According to th three oF more vertices gnd a i (c) are one, two, and two, respectively, : (6) and (6) are rk 36 The edge co ? and (e) are one, two, and one, neetivity respectively. sonnected graph, the edge ‘re considered for connected graph. For tivity are considered as zero, © vertex connectiyi ie Not complete, onnectivity is ily’s defi ‘on, it makes sense only for graphs that have Remark 38, If the vertex: ¢¢ K, then the graph is termed _Separabie Graph) A connected graph is said to called non-separable, as K-conneetivity, be separable if its vertex o inectivity is one. All other connected graphs are OR A connected graph G is said to be separable if there exists of g in G) and g have only one vertex in common, a subgraph g in G such that g (the complement {na separable graph a vertex whose removal disconnects the graph is called a cut-vertex, a cut-node, or an articulation paint, OR, In a graph G, a vertex v is said be cut-vertex if KG — v) > K(G). Example 69. Find the cut vertex in the following graph 2 ad ) a (i) i Fig. 60 : a Solution : In the graph (i), 6 is cut-vertex. In the graph (ii) c is cut-vertex. a: In } Rem: mi le graph, A ed graph is the same as separab) T sed a a ae graph G cannot exceed the degree of vertex with the smallest degree tivity gra heorem 7. The edge connec! ° et dv) be the degree of v, Vertex v, can ae ith the smalest degree in G, Let d(y) fe the Hegrte of i PenoF Let vertex vy be the vores We gy) edges incident one verte J the edge connestvity of G S el ‘ing ever exceed the edge i. Tene! See © connect eames i ee ae a cut-set g in G with & Theorem 8. The vertex ora edge connectivity of G. Therefore, there ex the edg Proof. Suppose that 2 denoteDiscrete Mathematical Structures Az 3 oving at most 7. vertices from v, edges. Let g partition the vertices of G into subsets Vand By reine g (together with all other edzes (Or, om svtich the edges in g are incident, we ean effect the removal (or V3) on W > edges in gare incident, incident on these vertices) fom G. Hence the theorem: eee “40, Hvery eul-set in a non-separable graph with more oa n-vertices and e edges (¢ 2" ~ 1) is the ices contains at least two Rema edg ‘Theorem 9, The maximum vertex cont nectivity of a graph G of iimegral part of the number 22; that is | =* ei (2e degrees) is divided among n vertices, tal Proof, Every edge in G contributes two degrees. The 10 : is equal to or less than the number 2 te n f the theorems 7 and 8. Hence the theorem, follows ‘Therefore, there must be at least one vertex in G whose degree vertex connectivity of G cannot exceed this number, Remark 41. By virtue of the Theorems 7, 8 and 9, in view of the summarized results are as F : 2 (i) Vertex connectivity < edge connectivity $ = ” a 2e (ii) Maximum vertex connectivity possible = ||: Example 70. Determine the maximum vertex connectivity and the edge connectivity for the graph displayed: Fig. 61 Solution. Total number of edges in this graph = 16 = e. Total number of vertices = 8 = n. Thus the maximum edge connectivity and hence vertex connectivity Let G = (V, B) be a graph. A finite alternating sequence of verti ginni S07 0 0 tea ertices and edges, denoted by W, beginning W= ve 1 & ¥ Yat Cn Yip (2 = 0) such that each edge is incident with the vertices preceding and following it is known as the walk. ‘A walk is also referred to as an edge train or a chain, ‘A walk starting from vertex vp and end i tar ‘» and ending with the vertex v,, = called origin and terminal vertex. ae walk. vp and y, respectively It is not necessary that in a walk W, the origin vertex and the terminal vertex be different.For V9 # Ye the walk Wey 6, vy ey Vid Gy Yy is called an open walk, gomi0611 Closed Walk j Awalk that begun and end at the same vertex is called the closed walk. For vo = Yar the walk W = v9 @) Vy .. ¢y Vp i8 a closed walk, psn Length of Walk The number of edges (not all different necessarily) in a walk is called its length. Walk of length zero is called the trivial walk. Remark 42. Walk may repeats both vertices and edges. Example 71. Find the length of the walk W = vp e v; &2 v2 &3 V4 es Yo 5 V3 having the following graph. Solution. Y 2 a & A v4 v0 3% % Fig. 62 WE= vp &1 Vi 5 V4 Yo Yo es ¥5 oe The length of walk is 5. Since the adjacent vertices in any graph represents edges, so we may omit to write edges. As such the given walk W can also be written as W =v ¥1 ¥2 Ys Yo Yar Example 72. In the following graph ; vy & ey (ew & Va Fig. 63 closed walk Wy = vy 04 v4 ey V5 eo Ya C411 18Discrete Mathematical Structiny ‘An open walk in which no edge is repeated, is called a trail fs a tal i ven in fig. 63. Example 73. W, = v, €; Vs &y Vs €10 Ys @7 Ys @5 ¥2 is a trail in the graph given in fig. 10.64 Path x © g ‘An open walk in which no vertex appears more than once is ealled a path. Example 74, In example 70, W = vy €5 v5 &5 V2 @5 Ys es %4 is @ path. .1 Length of Path ‘The number of edges in a path is called the length of the path. Remark 43. Obviously, by the definition of path, every path is a trail but its converse is not necessarily true. Example 75. In example 70, w 1&4 Vy 5 Vs C19 Vs €7 V3 es ¥2 is a trail but not a path. 1065 Circuit A closed walk in which no edge appears more than once is called a circuit. Example 76. The following are the graph of three — "10.66 Cycles A closed path is called a cycle. In a closed path the end vertices are same. Remark 44. In electric engineering a circuit is sometimes referred to as a loop-not to be confused with self loop. Every self loop is a circuit, but not every circuit is a self loop Example 77. In the following graph 6 ¥ 2 i vy a es % > Ms apeony. W=¥1 6 95 7% 6 "2 € M1 8a cycle of length 4 while Wi = ¥1 21% €6 V5 e4 v, 5 vy : e7 Vs es vy, Oay in this closed walk one intermediate very) sor 's Vertex vs is repeated. gxample 78. Draw the graph Tepresenting walks, Paths, solution : The graph of walks, paths, and cireuit as sup 1Y and cireuits as subgraph, bbgraphs in G as follows : Any collection of edges in G. A non-edge retracing sequence } of edges of G Anon-intersecting Z Anon-intersecting open walk in G closed walk in G Fig. 66 Example 79. Determine in the following graph : (i A walk from b to d that is not a trail. (i) Ab —d trail that is not a path. (iii)A path from b to d. (iv)A close walk from b to b that is not a circuit. (¥) A circuit from b to b which is not a cycle (vi) A cycle from b to b Fig. 67 V5 V9 0 is a circuit 's 2 ¥3 Ys v4) is a circuit but not a cycle,Discrete Mathematical Structure, Solution: | ‘ ; of vertex and edge) is b (A walk from b to d which is mot a tail (separately APPEASE end is b-e-f- Gi) Ab = d trail which is not a path (with repeated vertex) iso i if Gi) path from 6 to d in which neither vertex mor edge IS FEREATET TS (iv) A closed walk from b to bis be — fg eo} which is not a circuit since edge (8, ¢) is repeated, : (vy) A cirenit from to be which is not a eyele is b= € in which vertex ¢ is repeated, is not a cycle, (Wi) cycle from 4 to 6 be in which neither edg Example 80. Explain by considering the following grap! nor vertex is repeated is b-c ~ a}. Jy, of which are open walk, close walk, tril ete, @ Wane ewer (i) Wo = 5 es EES Gi) Ws = vp 1 ¥y €2 V3 ee MES Gv) Wa = 4 65 Vs €5 MS Er Mees YS ELM () Ws = 95 (We = ve (vii) W, = vy 1 V2 €9 Ye eg (WiiDWs = Hy e199 Ye €9 ¥ Solution @ Wr = 1 er 2&9 Ys & 5 W, is simply walk ig i i i a epee) or th Bh es Vs a eg nea le I) Wa = V2 €s M6 7 Mp &s Hy . Wy is an open walk from vs t0 repeated, it is not a path, GD Ws = er rn es 93 6 Ye SHS Ws is an open walk from vy to repeated so it is a path. 6M EM EM is Tength is 3. It is also a trail as no edge is repeated since the vere length 4. As no edge is repeated, i is also a ta, As verex # COW = 04 63 05 66 ¥6 7 Mees HS ey Myhed. oe wy, sa closed walk of length 5, It is also a e also repeated twic Tosed trail by vp ts also reper ce. So it is a circuit ‘not a closed path as apart from the end vertices, oy Wem DEMS ME eg My Weis a closed walk of length 4. It is bo : Neaed and no Vertex is repeated. So ing co ODWe mer 8 ee and also a closed path as in the walk no edge is WW, is not a walk as it does not ends in a vertex (vi We m1 En 2 0 Me W, is not a walk as the intervening edge v, is not the edge joining vy and (vill) We = 1 12 8 oY | Wg is not a walk as there is no edge between the vertices vy and 1, s vy and vg. Ina graph G, a closed trail (circuit) consisting of all the edges of G is called Euler line, If there be isolated vertices in G, then they will not include in a trail as they are not connected by edges with other vertices of G. Hence an Euler line passes through all the edges of G but not through all the vertices of G in case some of the vertices of G be isolated. nH Aa ES Sener (710.68 Euler Graph ~ {ET(RTU)-2008] An Eulerian graph is a closed Eulerian line. Therefore, it is a closed trail with no edge traversed more than once and in which the starting point and end point are common. It is also a closed trail where length is equal to the number of edges in the graph. Example 81, The following is an Eulerian graph Fig. 69Discrete Mathematical Structures 4-5-6-7-8-9-10-11-2-4-6-8-3-9-H-1 =4-5-6-7-8-9-10-11= 12-24-68 "1012 — raph is always connected, except for any isolated vertices the graph may have an Euler Graph) A given connected degree (or none of the vertex is of [CE(RTU)-2007, Raj. 2005) (@) We 1-2-3 (bh) We 1-2 Remark 45, An Euler gi ‘Theorem 10, (Necessary and Sufficient Conditions for a Graph to be graph G is an Euler graph if and only if all vertices of G are of even odd degree). Proof. Necessary Condition Let G be an Euler graph. So G contains an Euler line (which is a closed walk). We find that in tracing this walk, every time this walk meets a vertex » going through two new edges incident on v — with one Wwe entered v and with the other exited. This is true not only for all intermediate vertices of the walk but also for the terminal vertex, because we exited and entered the same vertex at the beginning and end of the walk, respectively. Hence, if G is an Euler graph, the degree of every vertex is even. Sufficient Condition : Let all the vertices of G are of even degree. Now we construct a walk beginning ‘at an arbitrary vertex v and moving through the edges of G in such a way that no edge is traversed more than once. Continue traversing as far as possible, As every vertex is of even degree, we can exit from every vertex we enter; the tracing cannot stop at any vertex but v. Since v is also of even degree, we shall eventually reach v when the tracing comes to an end. If this closed walk h we just formed including all the edges of G, then G is an Euler graph. On the other hand, if not, we remove from G all the edges in / and obtain a subgraph h’ of G constituted by the remaining edges. As both G and h having all their vertices of even degree, the degrees of the vertices of h are also even, Moreover, h” must coincide h at least at one vertex a, as G is connected. Beginning from a, we can again form a new walk in graph A’. As all the vertices of h are of even degree, this walk in h* must terminate at vertex a; however, this walk in A’ can be combined with h to construct a new walk, which starts and ends at vertex v and has more edges than h. Repeat this process till a closed walk that traverses all the edges of G is obtained, Hence G is an Euler graph. Theorem 11, A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree. Proof. First, Assuming that a connected multigraph does have an Euler path from v, to vp, but not an Euler circuit. The first edge of the path contributes 1 to the degree of v,. A contribution of 2 to the degree of » is made every time the path passes through v;. The last edge in the path contributes 1 to the degree of vy. Every time the path goes through v, there is a contribution of 2 to its degree. Consequently, both v, and vp have odd degree. Every other vertex has even degree, since the path contributes 2 to the degree of a vertex when ever it passes through it. Converse : Let a graph has exactly two vertices of odd degree, say v; and v>. Taking into account that the larger graph made up of the original graph with the addition of a edge {v,, v2}. Every vertex of this larger graph has even degree, so that there is an Euler circuit, The removal of the new edge produces an Euler path in the original graph. Example 83. Which of the graphs in the following diagram have an Euler circuit ? Of those that do not, which have an Buler path?F a bY b a b é @ ne, | G, ¢ | ; _ @ Fig. 71 : solution: The graph G, has an Euler Gj has an Euler circuit. However Gy Circuit, for instance a, obs has an Euler path, name & & d, €, b, a. Neither of the graphs G, or Ys a, 0, d, €, b, dy a, b. Gy does not have an Example 84. Which of the directed graphs j ea do not, which have an Euler path 7 o> following diagram have an Euler circuit? Of those that Hy Hy Fig. 72 Solution : The graph Hy has an Euler circuit, for instance, a, g, c, b, g €, d, fa. Neither Hy or Hy has an Euler circuit. H has an Euler path, namely, ¢, a, b, c, d, 6, but H, does not. = Unicursal-Line/ AAs open Euler line is G when it exists is known as a unicursal line, ‘A (connected) graph that has @ unicursal line will be called a Unicursal graph. I'we add an edge between the initial and final vertices of a unicursal line we obtain an Euler line. Thus connected graph is unicursal iff it has exactly two odd vertices. Example 85. The following is the unicursal graph.Discrete Mathematical Structures } , there exist n edge di "heorem 12, Ina connected gph G with exactly 2n odd vertices such that they together contain all edges of G and that each is a unicursal graph Proof, Let v.19, Wy man ty be the odd vertices, in any arbitrary order, of the given graph g, Addn edges to G between the vertex pits (Hy, Wi)s (a, Was on (Wn Wn) £0 onstTUEE BREW graph H, Since every vertex of H is of even degree, H consists of an Buler line G. Now if we remove from ¢ the n-edges we just added (no two of these edges are incident on the same vertex), © will be split into y walks, euch of which is a unicursal line. The first removal will leave a single unicursal line; the secong removal will split that into two unicursal lines; and each successive removal will split a unicursal line jntg two unicursal lines, until there are » of them. Hence the theorem. 10.70 LIE In a graph G, a path (a walk in which no vertex is repeated and no edge is traversed more than once) ig said 10 be Hamilton path if it passes through all the vertices of G (it may or may not include all the edges of G). OR, A path tip. 11, sum y-1» Uy in the graph G = (V, B) is called a a Hamilton path 4 4 IV = (toy ty oy ty py Ug} and u # u, for OS 7 < fs. Example 86. The following is the diagram of ‘2 5 Hamiltonian path. S > é Let W = v; €; v2 €2 V3 €3 V4 4 Vy, in this walk W all the vertices of G are involved with no repetition of vertex as well as edge. So it is % a closed Fig. 74 Hamiltonian path. If there exists a Hamilton path between every pair of vertices vi, vj € G, then such a graph is known as Hamilton graph. : In a connected graph, a closed walk that traversed every vertex of G exactly once, except of course the starting vertex, at which the walk also terminates. ‘ OR, A circuit Woy ty hp, ony ty — 15 Myo Mo (With m > 1) in a graph G = (V, E) is called a Hamiltonian circuit if to, tyy suey My ~ 1 My iS & Hamilton path, Hamilton circuit can also be termed as Hamilton cycle. Example 87. Sketch Hamiltonian graph, Soloh gear. 6 ‘he graph G as shown is Hamiltonian ge are traversed exactly once, So. it i Kxumple 88. The following is the h Let W= ae, 4 closed Hamiltonian p, diagram of Hi 1b oy d ey 0 6 m path, Hence the arap jamilton Cycle i in this walk all the vertices Hence the graph G is a Hamiltonian graph. G Fig. 76 Cycle shown by heavy lines in G is Hamilton Cycle. Example 89. ‘The following is a Hamiltonian circuit. hamilton circuit in the graph G is shown by heavy lines. = = G Fig. 77 (=D) a eee vertices there are “= edge disjoint Hamiltonian cireuit, i Theorem 13, In a complete graph with {IT(RTU)-2008] is an odd number > 3. ise an F ete graph with n-vertices, and a Hamiltonian circuit in G consists ple a : Proof. There are “2=) edges in a com «That there are ea : Of n-edges, So, the samber of edge-disjoint Hamiltonian circuits in G cannot excee iges. So, the nut n=l when n is odd, it can be shown as follows : “T° edge disjoint Hamiltonian circuits, “ of vertices) inthe diagram iven below isa Hamiltonian circuit, Keeping the Subgraph (ofa complete graph ofDiscrete Mathematical Structure : 360 2.360 3.360 n=3 360 9 vertices fixed on a circle, rotate the polygonal pattern clockwise by acl a-1 ay SOBes. nl 2 n 13 Fig. 78 : Hamiltonian circuit, n is odd Notice that each rotation produces a Hamiltonian circuit that has no edges in common with any of the Previous ones. Therefore we have 3 new Hamiltonian circuits, all edge disjoint from the figure and also disjoint among themselves. Thus the theorem. Theorem 14. Let G be a simple graph with mvertices and let w and v are any two non-adjacent vertices in G which are such that deg(u) + devo) > n IfG + e be the super graph of G obtained by joining u and v by an edge e. Then G is Hamiltonian if and. only if G + e is Hamiltonian. Proof. Suppose that 2 graph G is Hamiltonian, then G + e is also Hamiltonian. Conversely, let G + e is Hamiltonian but G is not Hamiltonian, then deg(u) + deg) 2, and if deg(p) + deg(g) > n- 1 VB one vertex. Specially, both edges. 10.73, Certain Results of Importance |" Sas 1, Suppose that G = (V, E) be a loop free graph with |V| a € Vp #4, then G has a Hamilton path,oe pose that G = (V, E) be a | G has Hamilton path, * 19° Fee graph wien ne 2) vertices, and if deg(x) Z e and if deg(x) > suppose that K,® be a complete di or (7 1) is in, (called toumameny Ge ie Ky? bas n vert gue 1), always conan ces exactly one of the edges (u,v) ‘Suppose tha (V, E) be a loop free undi (directed) Hamilton path. vy non-adjacent p, 7 © V, then G has a Ha hat G = (V, B) by 5, Suppose = (V, E) be a loop F i ¥, then G contains a’ Hamilton eyele “™t"eeted graph with |v] 6, Suppose that G = (V, E) be a | [E12 "Ca + 2, then G contains a Hamilton a inverted graph with (VJ — n > 3, and if 2. Complete graphs having 3 of mote vertices cnusr = m2 3, and if deg) = 5 Vxe S constitute a class of graph having Hamilton cycle. 8, Ina complete graph with n vertices there are 1 +3. edge-disjoint Hamilton cycle, if n is an odd number cient (but by a 9, A suffi (but by no means necessary) condition for a simple graph G to have a Hamiltonian circuit is that the degree of every vertex in G be at least - where 1 is the number of vertices in G. p@@i.74 Complete Digraph ~ ‘There are two types of complete directed graph 1, Complete Symmetric Digraph : It is a simple digraph in which there is exactly one edge directed from every vertex to every other vertex. Thus, there are exactly two edges between every pair of vertices. For example, ¥, G Fig. 79 2. Complete Asymmetric Digraph : It is a simple digraph in which there is exactly one edge between every pair of vertices. For example, 7 Fig. 80Dincrole Mathomatical Structurgg W number of edge ‘Theorem 18. Show hat he complete «igeaph wih ween foe maxim numbe ie “A dr = 1) edgen, Axwuming there are ma loop i Proof, here me (wo typou of complete digraph Le., complete mre ea soils met i wore eden 0 ¢ asymmetrie digraph, Out of these two a complete aymmettie digraph Haw mors way et ae a hi 2% "Cy eden Lx I Proved Also a complete symmeteie digraph with 1 vertices Hence, maximum number of edges in a complete figraph in nt VWUUSTRATIVE EXAMPLES Jerian nor Hamiltonian, [RaJ. 2002, 2003, 2007, MNIT 2001, 2003] Example 90, Draw grph whieh in neither 1 Solution: Fig. BL This graph G cannot have any closed walk without repeating the vertices and edges. Thus neither any closed Eulerian circuit nor a closed Hamiltonian circuit is possible, Thus G is neither Eulerian nor Hamiltonian, Example 91, Sketch graph which is Hamilton but not Ei [Raj. 2003, 2007, MNIT 2003] Solution: : : « % q 7 &% es x Fig. 82 Let W= pe 4 er es 5 ey p be a closed walk. In this walk all the vertices are traversed exactly once so HE honed Hamiionian path, Therefore, the graph is Hamilton. In the above walk the edge e, is missing $0 it is not a closed Euler line. Also no such closed walk can be taken in whit not | Fepeated. So the graph is not Euler. eeee ued xample 92. Display a graph which is Euler but not Hamilton, [Raj. 2002, 2003, 2007, RTU 2010]Fly. 83 LAW=P SAS Osler erg e é be a close involved only once so that graph ig Puleran Closed walk. In this closed walk W all the edges of G are since in every closed walk involving all the yer Sees 8 Hamilionian path, 1 all the vertices the vertex r will occur more than once. There does Example 93. Draw graph which is Eulerian as well as Hamiltont nian, Solution: {Raj. 2002, 2003, 2007, RTU 2010] & es r G Fig. 84 Let W=p ey g ey Fc 8 Gq p be a closed walk, In this walk W each edge is traversed only once. Therefore it is an Eulerian graph. ‘The walk W contains all the vertices of G and no vertex and no edge is repeated in W. So it is a closed ‘Hamiltonian path. Thus the graph is both Eulerian and Hamiltonian, ample 94. 17 students have lunch together each day at a circular table. They are trying to know one Sr bette, so they make an effort to sit next to two different colleagues each afternoon. For how many [Raj. 2002] oon can they do this. elution: Suppose that the complete graph Kyy where 0 = 17(an odd number, as every student can shake nd with every other student). Assuming the 17 students as the corresponding vertex. K, be the Hamilton cycle corresponding to the seating arrangement. ‘Each of these cycles has n edges. We have, there are yele the edges are different. Thus 8 days are $ distinct Hamilton cycles and in every © uired for meeting each colleague by 0 : ie ample 95. Consider the problem of assigning Wek Te vento the same Chokidar are not scheduled on Fon /s, prove that it is always possible to schedule the duties. 11 Chokidars in seven days so that two duties days, If no Chokidar serves more than foureels 6 seven duties, The ede between different Chokidars. The degree of each vertex ig 41.6 which is greater than or equal to 7 ~ | = able schedule for the seven duties, Suppone that Gi be a yraph with se funy hyo vertiven eorrexpondy to the duties given by least 3, therefore the sum of deyuee of the vertices is at 6.Thuy the graph containy a Hamilion path, corresponding (0 a suit can we find a Hamilton path Example 96, In the following, multigmaph Gy Fig, 85 Hamilton path isa path which contains each vertex. In order to find a path let us take the given graph with the set of labels x, y, which are labeled in the following manner. First we label vertex a with x. Then the adjacent vertices of atic. b, ¢, d) are then labeled with y. Then we. of b, ¢, d with x, so the label on e, g and / are x. Finally we label the unlabeled g label the adjacent vert vertices adjacent to ¢, g and i with y, So all the vertices of G are labeled. nce |V| = 10, if G is to have a Hamilton path there must be an alternating sequence of five x's . Only four vertices are labeled with x, So this is impossible. Hence G has no Hamilton path or Now and five y cycle (since there Example 97, Show that isomorphism of simple graphs is an equivalence relation. Solution: Reflexive : Let G be any simple graph then G is isomorphic to itself by the identity function x [Raj. 2005) :. Isomorphism is reflexive, Symmetric : Let G is isomorphic to another simple graph H. Then there exists a one-to-one correspondence f from G to H that preserves adjacency J, y and non-adjacency. It follows that fis a one-to-one correspondence from H to G that preserves adjacency as well as non adjacency. x Hence isomorphism is symmetric, ‘Transitive : Let G is isomorphic to H and H is isomorphic to K, then there exist bijections f and g from G to H and from H to K that preserve adjacency and non adjacency. It follows that gof is a bijection from G to K that preserves adjacency and non adjacency. 52 x Hence isomorphism is transitive, Fig, ‘Thus, isomorphism is an equivalence relation, ; 2 Example 98, A simple connected (p, 4) graph G is Hamiltonian if g>(2-—32 +9) [RTU 2009] a Solution. Let 1 and v be (wo nonadjacent vertices of G. Let H be the subgraph of G, obtained by removing wand v, and all the edges incident on w and v, Clearly, then E(H) = g ~ Deg(u) - Deg(»). §raph Theory ‘The maximum edges in H can be (7-2)¢, _(P? ~Sp46) e+) Deg(u) + Deg(v) 2 q ~ P'S, 2q- P+6. p?-3 2 P=5P+6, p?-3p46 pi_sp QR PO PSP +6 | = G is Hamiltonian, ; 2 Example 99. How many edges are there in a graph with 10 verti Solution : Since the si a tum of the degrees of the vertices is 6 - 10 = 60, it fol ‘ = 60, it follows that 2e = 60. Therefore, ices each of degree 67 Example 100. Find the in degree and out degree of each v edges. ‘ertex in the following graph G with directed Solution : The indegrees in G are : deg-'(a) = 2, deg(b) = 2, deg (c) = 3, deg-(d) = 2, deg'(e) = 3, and deg-(f) = 0. *(a) = 4, deg’(b) = 1, deg'(c) = 2, deg'(d) = 2, deg'(e) = 3, and deg’(f) = 0. graphs G, and G, of which graph is given below The out degrees are : deg Example 101. Find the union of the b a - : ; : G: : d e : Fig. 88Discrote Mathematical Y atical Struct Solution : b ¢ a G UG: Fig. 89 The vertex set of the union G, U Gy is the union of the two vertex sets, namely, fa, b, c, d, ef). The ‘edge set of the union is the union of the two edge sets, The union is displayed in figure. Example 102. Use an adjacency matrix to represent the following graph G a b Fig. 90 Solution: We order the vertices as a, b, c, d. The matrix representing this graph is abed ao 11d AG)= 4/1 0 1 0 cll 100 dil 000 Example 103. Sketch the graph with adjacency matrix -oe- 1 0 oo1 0 1 1 0. > o-- eo with respect to the ordering of vertices a, b, c, d.| ggaph ery Solution: A graph with the Biven adjacency matrix is a Fig. 92 Solution: The incidence matrix is er & &4 &5 6% wfl 10000 wfoo 1104 I=yJo 00011 y|1 0 1000 v[0 101 1 0 Remark 46, Incidence matrices can also be used to represent multiple edges and loops. Multiple edges are represented in the incidence matrix using columns with identical entries, since these edyes are incident with the same pair of vertices. Loops are represented using a column with exactly one entry equal to 1, _ corresponding to the vertex that is incident with the loop. Example 105. Represent the pseudograph as shown below using an incidence matrix.E Diserete Mathematical s Struct i Solution: The incidence matrix for this graph is ey ee Oe Ow yff tt ooon0 yfot tr roto Ieyfo oor 1 ooo yfo 0000017 xfo ooo 1100 Example 106, Prove that the following graphs G and H are not isomorphic. b » | Q d 2 t : G “ " Fig. 04 Solution: Both G and 11 have five vertices and six edges. However, H has a vertex of degree 1, name , whereas G has no vertex of degree 1. It follows that Gand Hare not isomorphic. morphic. Example 107, Determine whether the graph displayed below are is [LT] | 1 | a fe © oY a u Fig. 95 Solution; The yraphs G and H both have eight vertices and 10 edges. They are both have four vertices degrees 2 and four of degree 3. Since these invariants all agree, it is still conceivable that these graphs isomorphic However, G and 1 are not isomorp! 0 see this, note that since deg(a) = 2 in G, a must correst to either 4, u, x, oF y in H, since each of these four vertices in His adjacent to another vertex of ds in H, which is not tue for a in G. Another way 00 see dat G and Hare not isomorphic is to note that the subgraph of Gand EE ats of vertices of degree 3 und the edges connected them must be isomorphic if these two graphs are Bemiph ‘Theory However these subgraph, 88 displaye Win fig, Seapeomarseae sal 96-10 NOL isomorphic, 7 Up. 96 th -vertox ot af - aire to show that n ; he vertex set of w grnph Gi to the vertex net Of a graph Hin eserves edges, One helpful way to do this iv lo use adjacency ik of H, whe eee we can show that the adjacency matrix G is the same aint are the labels of these rows and cola cate this is done in the fot Example 108. Apply a figure are isomorphic matrices. Specially, to as the adjacency matri the vertices in G that explained how lowing example, idjaceney i Taceney matries to determine whether the graph Gand Ht displayed inthe following, =a re 4, ’, G My "s 7 % Fig, 97 Solution: Both G and H have six vertices and seven edges. Both have four vertices of degree 2 and two vertices of degree 3. It is also easy to see that the subgraphs of G and H consisting of all vertices of degree 2 and the edges connecting them are isomorphic, Since G and H agree with respect to these invariants, it is reasonable to try to find an isomorphism /. Now we define a function / and determine whether it is an isomorphism. As deg(u,) = 2 and as 1%, is not adjacent to any other vertices of degree two, The image of u, must be either vy OF vy) the only vertices of degree 2 in H not adjacent to a vertex of degree 2, We arbitrarily set fl) ve. (I we have that this choice did not lead to isomorphism, we could then try flu) = vy). AS ty is adjacent es of uy are vy and vy. We arbitrarily set flu) = vy, Continuing in this way, d degrees as a guide, we set flu) = vy iy) = v5, fl) = Vy and fo-one correspondence between the vertex set of Gand the vertex set of {fis) = V4y Ais) © V9p Aus) = Vy Aug) = V2. To know whether f preserves urix of G, to m, the possible imag using adjacency of vertices an Als) = vp, We now have a one~t H, namely : flay) = Yoo Sls) = Ys ‘edges, we examine the adjacency maDiscrete Mathematical Structur ty ys ty ts M6 ufo 10100 ft 0 1 A(G)= 43] 0 0 0 ug} 1 1 0 1 1 0 0 1 0 and the adjacency matrix of H with the rows and columns labeled by the images of the correspondi vertices in G. % M3 Yas MMe vf0 1 0 1 0 0 wf1 01001 JO 10 10 0 AM=yJ1 01010 yfo 00101 wo 1001 0 As A(G) = A@D, it follows that f preserves edges. We conclude that f is an isomorphism, so that G and I are isomorphic. Note that if f turned out not to be an isomorphism, we would not have established that ( and H are not isomorphic, since another correspondence of the vertices in G and H may be an isomorphism Example 109. How many path of length 4 are there from a to d in the simple graph G as displayed beloy @ b d G c Fig. 98 Solution: The adjacency matrix of G (ordering the vertices as a, b, c, d) is Hence the number of paths of length 4 from a to d is the (1, 4)" entry of A‘. Sincea poor, 10.63 e008 OR BO 08 RO R008 co there are exactly eight paths of pda, by a 0, di a, sg nu : leg 4 from a to d. By inspection of the graph, we find that a, b, a TMS toed Be td ta et Sera) example 110. Which graphs as di Examp! hich graphs as displayed in the following graph have an Euler path ? A | | | | a < WY 6 G 7 4 ao ; a Gy Fig. 99 Solution: G, contains exactly two vertices of odd degree, namely, b and c. Hence, it has an Euler path that must have b and d as its end points. One such Euler path is d, a, bs ¢> 4, b. Similarly, G, has exactly two vertices of odd degree, namely b and d. So it has Euler path that must have b and d as end points. One such Euler path is b, 2, 8 f, & ds & 8 By & fd. Gs has no Euler path since it has six vertices of odd degree. Example 111. Find the following : @ K, Gi) Kuan Gi, WM Solution: (i) The compliment of Ky is the graph with n vertices and no edges. Gi) The complement of Ky is the disjoint union of K,, and K,, (ii) The complement of C, is the graph with vertices [Vy y,} with an edge between v; and v, unlessDiserote Mathematical Structure, ESF Lmao are represented by bit strings of Tength n wity ay fer in more than one bit. QW) The complement of Q, is the graph whose verti calge between OWo vertices if the associated bit strings def r G are isomorphic. Baanmple 112, What is called the graph i Gand G are isomorpl somorphic then the simple graph G is known as self complementary. Solutions U the graphs Gand G are each aris ; i a path. If it does not, gi Example 12, Does the following graph haye a Hamilton path ? If so, find such a ps siven aut argument to show why: no such path exists b é a 4 iF P A h e PE | ts Fig. 100 Solution: No Hamilton path exists. There are eight vertices of degree 2, and only two of them can be end Jettiees of a path. For each of the other six, their two incident edges must be in the path. It is not hard to find that if there is to be a Hamilton path, exactly one of the inside comer vertices must be an end. and that this is not possible, Example 114, Does the following graph have a Hamilton path 2 oS Solution: Yes, and the Hamilton path is a, b, ¢, fi, A, gd, e, 5 Example 115. For which value of m and n does the Solution: For m = Example 116, complete bipartite graph K,,,, have a Hamilton circuit? 2 2, Kyy, have a Hamilton circuit, Use adjacency list to describe the simple graph as displayed below.e da Fig. 102 : A simple graph Solution: The following tab ig "e ig these vertices adjacent to each of the vertices of the graph. ‘able : An Edge list for a simple Graph ; Ve ertex Adjacent Vertices a boe b vai c ade d e e acd Example 117. Represent the directed a graph as displayed below by listing al i re rt vertices of edges starting at each vertex of the graph. ern eee Fig. 103 : A Directed Graph Solution: The following table represents the directed graph as given in the above graph. + An Edge list for a Directed Graph juitial Vertex ‘Terminal Vertices bode10.66 Dincrote Mathematical Structure Example 118. How many ways are there to seat 1H persons around stable such that the neighbours agg never the same ? Ia}. 20044 Solution: Consider a graph with 11 vertices corresponds to 11 persons, Two pernons are said 0 be ncighhyy if there exists an edge between the two vertices correnpond to these two persons, Since, in each weatiny aly the Il persons be seated so the seating can be considered aw a Hamilton circuit, As, exch thine & Petron has 2 different neighbours so a person must have all the remaining 10 persons as its neighbour, ‘Thus, thig graph is a complete graph with I vertices, Hence, the required number of ways of seating = number of edge-disjoint Hamilton = Me Circuits possible in the graph 7 Example 119. If a graph has exactly 2 vertices of odd degree there must be a path joining these two yer. tices. Prove it, IRaJ. 2003) Solution: Let G be a graph with exactly two odd vertices, say, w and v. 1f G is a connected graph then there must exists a path joining w and v. Suppose G is disconnected then G consists of two oF more connected components. If possible, let us assume that these two odd vertices u and v lie in different compo J If vertex uw lies in some component C, then C, contains one odd vertex and rest of the vertices in C, are even. Then the sum of the degrees of all the vertices in C, is odd, which contradicts the fact that the sum of the degrees in any graph is always even, ‘Thus, our assumption that 1 and » lic in different components, was wrong. Hence, w and v must lie in same component and then there must be a path joining these two vertices. Example 120. Suppose that G and Hf are isomorphic simple graphs. Show that their complementary graphs G and H are also isomorphic. [Raj. 2005] Solution: Let f be an isomorphism from G onto H. Then f is a one-to-one correspondence from G onto H and f also preserves adjacency as well as non adjacency of vertic« s Let © be a mapping from G to 77, Further the adjacent vertices in G are not adjacent in G also the non adjacent vertices in G are adjacent in G, similar statement holds for the graph HY. y As G and H are simple so G and 7/ must be simple graph. Thus 6 is a one-to-one correspondence from G onto Hf and @ also preserves the adjacency as well as non-adjacency of vertices. Hence @ is an isomosphism from G onto 7. Therefore, and 77 ate isomorphic to each other. Example 121, If a connected graph G has exactly two vertices of odd degree then show that there is Fuler path in G which must start at one vertex of odd degree and end at the other, [Raj. 2003], Solution: Suppose G is the finite connected graph with exactly two odd vertices, say wand v, Add another edge ¢ from u to v to the graph G to form the new graph G' = GU {e}. Then all the vertices of the gph G' are even, Then there is must exists a closed Euler line o of G', Since a is closed, we can assume without loss of generality, that o begins with e. Let Bi be the path & without its first ed taversable wail of G beginning at v and ending, at u, as required,Q6 Q7 EXERCISE 10.1 Prove that a simple graph with m vertices is connected it it has more than @2—2"=2) edges. Prove that a connected simple [Raj. 2005] Braph with n vertices and more than (n — 1) edges, has at least one circuit Prove that the complete graph K,, has &n=2)! different Hamiltonian cycles. Let G be a K-regular graph with 2K — 1 : Define the following terms : (i Subgraph (iv) lsomorphic graph Define the followin; ~ 1 vertices. Prove that G is a Hamiltonian graph. (ii) Spanning subgraph (iii) Complete graph (¥) Regular graph (Raj. 2002] () Eulerian Chains Gi) Hamiltonian cycle )Digraph (iv) Walk, Path and Circuit = (Vj, E,) and G, = (V;, E,) be two loop free undirected connected graphs given in the following G, G Fig. 104 (Determine |V4l, [Val [Esl IEal (ii) Find the degree of each vertex in V; (iii) Are the graphs G, and G, isomorphic ? [Ans. (1) [Vy] = [Val = 8 1B = FEal = 14 (iii) No} Define Euler path and Euler circuit. Define the following operations on graphs. Give an example for each operation : tersection and ring sum of two graphs; and V2. IMREC 2001] [Raj. 2005] @_ Union, int Gi) Decomposition of graphs (iii)Deletion and fusion of vertices. {Raj. 2003, 2007)ee 10.68 Discrete Mathematical Structures 10.75 Planar Graph A graph is called planar if it can be drawn in the plane such that no two of its edges intersect each other except at vertex. Remark 48. A graph may be planar even if it is usually drawn with crossings, since it may be possible tg draw it in a different way without crossings. Example 122. The following are the graph of Ky and Ky with no crossings. KM (N K, (with no crossing) Fig. 105 K, is a planar graph because it can be drawn without crossings. Remark 49. A crossing of edges is the intersection of the lines or arcs representing them at a paint other than their common ené id paint [OR, meeting of edges at a vertex is not considered as an intersection} Example 123. Is Q,, shown in the following figure, planar ? Lt fy The graph Q, A Planar Graph for Q Fig. 106 Solution: Qs is a planar, because it can be drawn without any edges crossing, 7 i a cera rem 2 1076" Non-Planar Graph” A graph G = (V, ee ih divides the plane into regions (also called windows, A planar representation of a gra including an unbounded region. Example 124, Observe the graph in fig. 107. faces, or meshes), There are six regions in this graph,6, in the above graph is unbounded, 6. A planar graph has exactly one infinite region 7. By changing the embedding of a given planar graph, the infinite region ean be changed. Let R be a region in a planar embedding of a graph or a multigraph, the degree of the region R, denoted by deg(R), is the number of edges traversed in a shortest closed walk about the boundary of R. Example 125, Find the regions and degree of regions in the following graphs. Fig. 108Dineroto Mathonnaticn! Struetun, Solution: In the graph Gy, : ‘There are four regions. deg(R,) = 5 deg(R,) deg(Rs) = 3 deg(Ry) = 7 Since the closed walk regarding the boundary Ry is a~h~g—N~@~f-d~a 4 Also, Edew(A))=18 int For the graph Gz, we observe the following : There are four regions deg(Rs) deg(R,) = 3 deg(R;) = 5 deg(Ry) = 6 8 j ¥ deg(R))=18 ] and Jes we notice here that 4 8 DL deg(R,) = pana 2lel: i = ae Theorem 16. The sum of degrees of the region of a planar embedded graph is equal to twice the number" of edges in it. 4 In the example 89, the sum of degrees of regions is 18 which is equal to the twice the number of edges. Remark 50. When a graph is displayed, it may look differently by different representation. But the question is that whether the number of regions obtained from each embedding is the same or not ?” The explanation pertaining to this is contained in Euler’s formula, ‘Theorem 17. Let G be a connected planar simple graph with e edges and v vertices. If r be the number of regions in a planar graph representation of G, then reenv+2, 1) Proof. The proof proceeds by induction on the number of edges. As the basis of induction, we notice that for the two graphs with a single edge displayed fig. (A), equation (1) is satisfied. As the induction step, We suppose that (1) is satisfied in all graphs with n ~ 1 edges. Let G be a connected graph with n edges. If G has a vertex of degree unity, the removal of this vertex together with the edge incident with it will yield a connected graph G’, as shown in fig. (B).(A) ® © . n Fig. 109 since (1) is stisfied in Gis also satisfied in G G will increase the count of vertices by enity ond’ because putting the removal edge and vertex back into the boundary of a finite region will NY unity and the count of edges by unity, the removal of any edge in inG’, itis also satisfied in G. Hii @ connected graph G’, as shown in fig.109(c). Since (1) is satisfied Be hy oneal Be Goat re tig the sowed ge bck eo G will inerease the count Corollary 1. Fo of regions by unity, but will not change the count of vertices. + For a connected planar simple graph with y, : of the graph respectively, prove that ple graph with v, e (> 2), and r as the vertices, edges and regions (2) 3r 520 ()e<3v-6 arpat elg eo a connected simple graph, the boundary of each region contains at least three edges (ase : 2 has atleast degree 3. but there are r regions. therefore sum dearces regions graph will be greater than or equal to 3r. according theorem degrees all is 2e. so it follows that ‘thus 2c> 3r. Hence the result. (b) Appealing to Euler’s formula, we have ree-v+2 = 2e>He-v+2) [from part (a)] = es3v-6 Hence the result. Remark 51. The corollary is the necessary condition for a planar graph but not sufficient “That is if the graph is planar than the conditions (2) nd (b) of the corollary are satisfied, however the conditions (a) and (b) of corollary are satisfied, the graph may be non-planar. Corottary 2. If G be a simple graph then there isa vertex v in G such that deals) <5. Proof, If G be a simple planar graph then it will hve only one vertex, with degree 2ero. However, there degree of each vertex at most will be unity. are only two vertices in G, then the So we assume that G contains at least three vertices. Ifthe degree of each vertex in G is at least six, then E deg(r)2 6m | where n is the number of edges ve But L deg(v)$2e where ¢ is the number of edges in G. ‘¢ > 3n, which is impossible, because in a simple planar graph, we have Thus 2e > 6n => e e = 45 If the graph can be partitioned into r regions, then according to the Euler’s formula n-e+r=2=330-454+7=2 =r=17 ‘The graph can be partitioned into 17 regions. e-vt2 12, * Number of edges Example 128. Show that the complete graph K; is a nonplanar. Solution: The complete graph Ks has the following, Vertices = 5 Edges = 10 Ifthe graph Ks is a planar graph, then appealing to the result e < 3v— 6, we have €S3v-6 or 10<3x5-6=9 of 10 <9, which is impossible. Hence K, is a non-planar graph. Example 129. Show that the complete bipartite graph K,, is a non-planar graph. Solution: The complete bipartite graph Khas the following Vertices = 6 Edges = 9 By Buler’s formula e-v +2, we have r=9-6+2=5 So there are 5 regions. Since the bipartite graph K;3 cannot have a cycle of odd length, so that each cycle has length 2 4. Thus, degree of each region must be > 4, So the sum of degrees of r regions must be > But the sum of the degrees of all regions = 2e,Graph Theory. y : | Fig. 110 sn ars 20 woe) But r= 5, and e=9 The equation (1) = 20 < 18, which is impossible. Hence the graph K is non-planar. It is to be noted that K;, , satisfies the conditions (i) 2e > 3r and (ii) e < 3v- 6. Example 130, Find whether the following graph is planar or non-planar. b ce f e Fig. 111 ‘The given graph is non-planar as the necessary condition for planarity ie. ¢ < 3v ~ 6 is not Solution: satisfied by it. Here e = 15, v = 6 so 3v-6= 12 =e £ 3-6. Thus the graph is non-planar. “A081 Homes if one graph can be obtained from the other by the creation of edges in series (ie., bY Ss of degree two) o by the merger of edges in series, The three for instance graphs in the following, @ LA (i) Ly») L») j \ | Fig. 12 to be homeomorphic insertion of vertices figure are homeomorphic to each other, ‘Two graphs are saidDiserete Mathematical Structures Three graphs are homeomorphie to each other r is homeomorphic to G is planar. Remark 82. A graph G is planar i€ and only iF every graph that is homeomorphie to G is pl 10.82 Kuratowski’s Two Graphs A coniplete graph Ky ee Ea d Fig. 113 and a regular bipartite graph K3, 5 @ > ¢ g d PBX <—~ a é a f Fig. 114 are non-planar graph, These are known as Kuratowski’s first and second graph respectively. These two kuratowski’s graphs Ks and Ky, 5 are very important graphs, because these are used to find whether a given graph is planar or not, by using the property that if the two graphs are homeomorphic then they are simul- taneously planar (or non planar). ‘Theorem 18. Kuratowski’s Theorem IRTU 2010] A graph is non-planar if and only if it contains a subgraph that is homeomorphie to either Ky ot Ky, 3 OR A graph is planar if and only if it does not contain a subgraph homeomorphic to Ky or Ky. Example 131. Show that the Peterson graph given in the following figure is nonplanar,Graph THEO Peterson Graph us Solution: The graph given by the foll ji lowing fi ne ae eee ae eee a subgraph of Peterson graph. Since it involves all Fig. 116 ‘This graph is obtained from Ks, 5 by four sub-division as displayed i in the following figure. i d i q © b b (2) One subdivision (1) Ky Fig. 117 Fig. 118z Dincroto Mathomatical Structure, d ; b £ (3) Two subdivision (4) Three subdivision Fig. 119 Fig. 112 d g (5) Four subdivision Fig. 121 Thus the graph (5) is homomorphic to Ks, ; and (5) is a subgraph of Peterson graph. Therefore, Peterson graph is homeomorphic to K,, 5 Hence by the theorem of Kuratowski’s, Peterson graph is non-planar, 10.83 Chromatic Number Painting all the vertices of a graph with colors in such a way that the two adjacent vertices are colored With different colors is called the proper coloring or vertex coloring of graph. A graph in which every vertex has been assigned a color with regards to a proper coloring is said to be a Properly colored graph. The following graph shows three different proper coloring of a graph, V5 Yellow Tye Yellow 'sverti : ted raph, there ae scent to each other, will require n— coloring of nik ‘0 oF more components so, the 5 ect 0 other : two verices Ean be rapes need Banh ony dmpPonent. Therefore, it would be sufficient it © Component. Fi disregarded. Thus for colori ige without aff creutther, all parallel edges betws ing probl. affecting adja: : iges between Definition Problem we need to consider only simple commas ere * raphs. asa mgm mumber of colors required for proper colorin Utena is denoted by ir rf 1 displayed below. © © SCS) IE CCG) = x, the graph is ented rechtomate pont Guomati ae graph is Red Green Green Red It is an algorithm developed by Welch and Powell for finding minimum colors needed to paint a graph The steps of the algorithm are as follows : 1. Arrange vertices in a sequence according to their degrees in descending order. 2. Assign color C, to the first vertex of the sequence and then assign C, in the sequential order to each vertex which is not adjacent to previous vertex that assigned with color C. 3. Assign next color C, to the next unpainted vertex in the sequence and repeat the process of painting for previously unpainted vertices. 4. Repeat the procedure until all vertices have been painted. : Example 132. Use Welch-Powell algorithm to paint the following graph with minimum number of eotors yy 2 Vo G u Fig. 124