GRAPH THEORY 'Y — INTRODUCTION AND BASIC. OF GRAPHS, PLANAR GRAPHS, WEIGHTED GRAPHS, ISOMORPHIC IS, CYCLES AND CONNECTIVITY Graph-A graph G consists of two parts — () AstV=V(G), whose elements are called vertices, points, or nodes. (i) Acollection E = E(G), whose elements are called edges (or lines isieathes) such that e, is identified with an unordered Pair (Vj, vj) or vertices Wewnite G (V, E) Frretampl, let V = {v,, vo, V3, v4} and E = (01, €, €3, ey, €,). e& 3, : 7 Fig. 3.27 be i . M) tyfes % eg fe. ‘3 Ma! 5 v3 “'Gnph with 4 Vertices Fig. 4.2 Another Graph with Same oS Rages ‘Number of Vertices and Edges are ges Iftwo edges start and end with the same pair of vertices, le gr''® be parallel edges, e.g, in fig. 4.1, edges e, and e, stat and Soe “ices vj and v5, hence they are said to be parallel eiges. peg" Man edge starts and ends on the same vertex, it is sad to be peg MB. 4.2, edge €, starts with vertex v) and end on vertex Vp * “Self loop (or simply a loop). es eticcn g Simple graph is one in which there is no more ®pair of nodes. In such a graph there is neither a self-loop192 Discrete Structure In drawing a graph, it is immaterial whether the line Np tis arcarve, long orsbor. The important thing i hat nt des nd vrs For example the thre eraphs dr 4 {0 ofthe varies and ees) are the same." fig ee ne, + mo so L. OG, % 4 - wo —— w © a ™ Fig. 43 Same Graphs Drawn Diferenty @) 6G; Subgraph ~ Let = (V, E)be a gph. gph O'=(V, En, Fig. 4.5 2 subgraph oF Gi Eis a subset of E and V'is asl ‘edges in E’ are incident only with the vertices in V. For example, fig. 44 (a), (b) and (c), hd @ mw Fig. 44 Subgraph of a Graph sinlary the intersection GG, of graphs G, and G, is a graph qe My Ei) somsisting only ofthese vertices and edges that are in both G, 1G, sch hat Vg V0V2 and E,=E,0E og Sum of Two Graph — The ring sum of two graphs G, and G, 4adsiG;@ G, is graph consisting ofthe vertex set V/V, and of edges ‘ate stern G, or G but not in both. Teuionoftwo graphs G, and G, the intersection ‘ito gaphs G; and Gs, and the ting sum of two are commutative, GG, = Gc, aed tbBph OG si to bev spanning sur G,nG, = GG, vertices Of G. The complement ofa subgraph G'=(V>E) 4 {the graph G is another subgraph G" = (V", E"), such tht E' 8 ee OH af ta, , EE’ and V" contains only the vertices with which thee" | agp #4 G, ae edge disjoint, then Gy Gp is @ incident, a if For example, fig. 4.4 (c) shows the complement of * er cris = UG, fig. 44.0). af vertex disjoint, then Gy Gi is empty. Union and Intersection of Two Graphs ~ hism of the G raphs — A graph G, = (V,, E,) is said to be esas O02 Ete isaone oncom eve then the Such @ way that if e, is an edge with end vertices u, Andy, in gg OTESPONKINg edge e, in Gy has its end points the Stspondenec? Ntich correspond tou, and v, respectively. Such @ called a graph isomorphism. Let G,= (VE) G,= (Vs, E) be two graphs. Union of these two graphs is G\= GG, such that V3 = ViLV2 ‘and a wos Bsr Seoe —w 194. iserete Structure Graph Theory 195 soon io ca ae G, are said to be homeomorphic if they can be of sued and ends atv. or isomorphic graphs by tis method ein om Gg Fe) al point of ean vith dination o Far example, the sph (2) and () in ae" fig. 4.7 i, bo they _ are not isomorphic, but they are spaipint Fe sor of U eee +4 4 err or univ nodeomins ifaw fenci 0 oa yj directed ede in a digraph G Then the following the graph (c) by adding appropriate vertices. @ wis adjacent Maldgraphs ~ A muligaph G - f 30 of Gin the pan oe een Facy 6) HE seed gph Gi emennnon of inthe plane. Tht abecemin oa fis wre 5 Hc mace cient multiple edges, i.c. edges connect ¢ same ups = (0) 5 NP ea iia) Seay coctaln Be oom Uwe Diet Graph ~ Ifthe edges andlor vertices of a directed Ioops, ie. an edge whose end points are the ee ec nan ee es Fron dened gph CV ibe te Oe lle a ng etter ois ws foie ii) E consists of the seven edges (¢), e sy ‘Theorem 1, (The Handshaking Theorem) Gcontain multiple edges, e, and e., which connect the same two ei} Let G= (V, B) be an undirected graph with e edges. ‘Aand C. Also G contains a loop e, whose end points are the une vetel) Thea, 20 = Yidea(v) Finite Multigraph — A multigraph G = G(\, E) is finite, if both V a fe) ve ‘Trivial Graph — The trivial graph is the graph with one vertexandsoe (oe that this applies even if multiple edges and loops are present). Empty or Null Graph - The empgy graph isthe graph wit» oe thatthe sum of the degree of the vertices of an undirected and no edges ‘Graph — ‘or mul Isolated Vertex - A verex Vis isolated, it des not bos ee koe Ponda eres vert of aepesoneiscata tO Stones fen eases [7 aye. geno] SabIS ph int vei Ky <| ‘Adjacency and Tncdence ~ Suppose, ¢= (uv) Bancie Mag) GaN with cong edges as inte. |” (a) () and vare end points ofe. Then the vertex wis sad te also be dawn with noncrossing ¥, and the edge ¢ is said to be incident on w and om ¥: nt TE 49 0, hence Ky is planar Degree of a Vertex ~ The degree of a vertex V HAT «it an important clas of planar Fig 49 deg(v), is equal to the number of edges which are inci at) Gyaygy ‘words, the number of edges which contain v as an end i‘ PT anand Bipartite Graph — They are many different types of said to be even or odd according as dee») is hs Compe a SOF the, complt regular ad bia gaphs Directed Graphs— A directed graph Gor E to tai a is called complete if every vertex in G is aka Ni) «0 Ti) Qa The fertex in G. Thus a complete graph must be : complete gr 200 | fe pe BRPh with 2 vere i denoted by Ky Fig 410 ‘A set E of ordered pairs (u,v) of Ve pein Kk, vertices are said be veto196 Discrete Structure Graph Theory 197 is called bipartite ifs veces V can be =A) io sisi Graph ‘and N such that each edge of G connects a Jae jlete bipartite graph, we mean that each it 9 Of By a comph k ae Mio to each x 2 oe is ere mi oe for sar Nem <0. Fig. 4.13 iS etopetsB: 3 Kosaka Ks ae a asim eds. ig. s i RY | en arp is ft alematvl sequence of vertices ina graph G Fig, 4.10 Fa ae val ending wth same or diferent vertices, such that no Regular Graphs—A graph G is regular of deqreskorkrpnieg | apanpexsmin ta one, however a vertex may be, Walk can also be eres degesk: noe words, a goph seguir ifevey oar | eat cn same degree. ‘oe Walk in a graph Gis") bia ‘ The connected regular graph of degrees 0,1, or 2 are easly deci dayasibeaph of graph G: ‘The connected O-regular graph isthe trivial graph with one vet ay} €) A-seoop may be a - ‘ges. The graph having two vertices and one edge connecting the sa | eto Be walk the connected L-egular graph, The connected 2-egular with nvetisit| Opn Walk ~ A walk in ¢ je 1 @ (b) graph which consists of a single n-cycle, isha and ends vertices are Gieen (diferent terminal . eae ee Fig. 414 ‘elle open walk. 5 (@) O-regular Cae Fig 414 (b) shows an open a isha it stars with «and 5 aheng. a Al] seats aur ‘iilsneteminal vertex), called @ @ (o) regular walk Fig. 4.15 (by, Fig. 4.15 Graph and its Closed Walk Fig. 4.11 . ~Avalk which is not closed is called an open walk. ‘The 3regular graphs must have an even numberof ee | PA An open wal in : ‘sum of the degrees of the vertices is an even numbet. Fig: a one CTX APPears more ‘connected 3-regular graphs with six salled a path, 1¢ vertices. In gener, regula paphs handa sete. ss can be quite complicated. For of eg ofthe path, example, there are nineteen 3- Pah ee ‘regular graphs with ten vertices. We ath, An @ ow ‘note thatthe complete graph with ee tng IOP is ig. 4.16 Graph and its Path from a tod ‘mvetiesK, isregularofdegree n— 1. Fig 4 (ae, bes c¢, d) of Length 3 ete ts198 Discrete Structure CCyele—A cyte isa closed path in which a yer p= Mg: A cycle of length kis called a k-eyce. 9 have length 3 or more. ate dig ny Connectivity, Connected Components — 4 agape tk 2 ‘there is a path between any two of its vertice mG i Gay Lg cs. The onnected, but the graph in fig. 4.17 (6) is not connected ean eli path between vertices D and E. ince a ‘Suppose Gisa graph. A connected subgraph Hof G scales, ua penden Yre component of G if His not contained in any larger connec G Forexample, the graph G in fig 4.17()hasthree connected components, the subgraphs induced by the verex sets (A. ,D), (EF) and (B). The verex Bin fg 4.17 (0) an isolated vertex. Thus, B itself forms a connected component of the graph. Gircnit— A closed walkin which no verex appears more than once, is called a circuit. It on-intrsecting walk, such ‘that every vertex is of degree ‘two. A self loop is also a circuit. A circuit is also referred as cowcular path tc] Rel soc ero te atx ven on page 195. (4 dein regular graph ns Rfe to the matter given on page 196. Boos rs Fe @ Og @ 0 0 Fig. 4.18 Three Different Cieis or ove hatin bom. ‘SLlfve consider the vertices with odd and even degrees separately, sfey an be expressed! as the sum of two sums each taken over Graph Theory 199 (RGPV, June 2012, 2013) (RGPY., May 2018) (RGPV, Nov. 2018) (RGPV, June 2013) (RGPW, Now. 2018) (RGPY, Dec. 201) Peete Po Prve that number of vertices of odd degree in a graph is always (RGBV, Nox. 2019) graph, there are an even number of vertices of odd (RGPV, Dec. 2014) 0) ‘a pv, sane 201,308 i lal amit on Sol foes and od degre respectively, as follows — 2003, Explain isomorphic graphs. (RGPV, Dee. a * Or May Lewy = Lawy+ Taw Explain isomorphic graph briefly. (GRY, Dee 27 . - sed $e ht. Or Vian side ofequation (i) is (RGP Ys Me ne equation (i) is even, and the first expression must isomorphic graphs with example. a i _— Q.2. When it can be said that 1wo i given on page 193- BU) = As eiecrintee200 Discrete Structure Prob, Show that the raph G, = 0B) ana ‘fig. 4.19 are isomorphic. 2" Kp @ ® Fig. 419 So The fiction £ ith £0) = 1) = 4) ag is @ one-to-one correspondence between V and W yf wl fh>y ‘correspondence preserves adjacency, note that adj ta acency vers 20 yy a0 vy Hy and Uy) vy and a) = gen ne Alu) = vo, and flu3) = v3 and f(u,) = vz are adjacent in H. i" ‘Prob3. Find the degre of each vertex in the multiraph inf ss ‘Prob.4. Draw a planar representations of a graph. a : F " e ca py., Dee Fig. 4.21 GP ot o ‘Sol. This is not the star graph K, This has a planar TEP Graph Theory 201 f > Fig. 422 aa nh. Is this graph planar ? pons ron Ks patie STP. Ty Dec. 2008) Graph , ing edges, 0 Ks. is SLE 423, tees many crossing edges, 50 Ks. poaese el he circu of the following graph — Fok Drow sa “ | S a ee 7" ‘ “ibe:9) — (b) (Be ce, de, 6) (©) (ae, ce; de, be, a) me Fig. 4.28 Inver Mt! Planar graph has at east ome verexof degree Mc (RGPY., Dec. 2014) =p si Sle depeecar it bOse al vertices ae of degree 6 or more, then all the ‘erties would be greater than or equal to Gv. the “Then na Stef the vertices ewe the numberof tials s20 vst iar Me Ai)202 Discrete Structure Graph Theory 209, AX Gee But, any planar graph have the property, ‘Also, from Euler's formula, we have 2ev-etr 4 Now, puting the vale of¥ and rom (and i BS oa wha ey @ () Wosapb atl! 429 Graphandts Hamiltonian Creat Since, the saement 2:0 is not tre, hence we coe ao fa eree sx len than 5, ~ ‘te circuit have exactly the number of edges as the srnian cut nalways in a connected graph, but every amos not havea Hamiltonian circuit vréremove an edge from Hansltonin cite, we ae lft with is paths Hamiltonian path Eulerian Path — We define an Eul ke Graphs, Disconnected Graphs and Components mag tgnttrrmnsrecokma| mma eno ee ah: sacs ‘Sreaitinapraph Go be an circuit that traverses om ‘cach edge exactly once and only once. ‘Euler Graph ~ If we are moving on a ‘saph by covering all the edges of the graph, ee ‘and returning to the initial vertex, such a walk ; is called an Euler line and graph is called an Euler graph. een = KOO =ph G contains all the edges ‘ofthe raph G then the walk is called an Euler afl line sod the graph is called an Euler graph. Fig. 4.27 Two Eat of Euler Graph — Euler graph is always connected. ‘id EEaler graph does not contain any isolated or pendet i) Al the vertices of an Euler graph are of even 0B ‘Hamiltonians Path and Circuits ~ soon Ifa closed walk contains every vertex ofthe wh fr itt degree of every vertex is 2, then the walk is called Ham ‘And if the walk is open then iis said to be Hamilionlan scarecoeni Bf np @ o Fig. 4.31 Disconnected Graph v vertices and s components can have Never Asin graph with (RGPY,, June 2010, 2012) gy204 Discrte Structure Gamnrnesy, 05 . : : = Du = nity spine Ly-aenie-9 noe CS Oe mn ter eft th. ‘ = LYoi-v pre 3 rian Pl | Squaring both : eben Eg a graph G there are three va ro SE of SE i sg (s0 "2 as an Eulerian path, thes ie 2D) = oF 2+ hs i cama rtm or "aad sno of od dere Ove of Fig. 432 xe et be the starting point ‘of an Eulerian path, and the other : : ee jit ‘vertex at one end of the untrav sed eds . iat ie te id grtex atone end ofthe untraversed ed xine a Hamiltonian path in a graph Gof m vertices, or each par of vertices in G is m1 oF larger. proved if we could show that the graph G is @ "Vi =1 0.00535 | — pred THE aes of te degre. Tro The theorem is ened gh. és Meni orem, suppose G i not connected tat is it has two (oF pens hiss, supose vi vertex in one component which rine, andy be he vertex with n vertices in another component ‘vend thatthe degree of v is almost n,~ 1 and that of vis almost ol Tins, dev) + deu(v,) =m, + my idishss tan 2 1. Pits: assumption. Hence the theorem is proved. Proved Toren 5. Gis a. charms Gb a comet graph and ever vere has een deere rove ta a yest rk Ge Ele rank and ot ne im Si tot te (RGBY., Nov. 2019) iE Rite here ae connected graphs where every vertex bas ‘Sti cei te Ec it Coote such a gph G wit be ge fan ome vat se, if there Ocoee there is clearly an Euler circuit. Letv be Soistororvie the must be cru that begins and ends a Stabe ad yer two and G is connected, there must be baad Y. ES and b, Since G is connected, there bY, “Seg Suppose that x: vu" ending at Beeiicr sean = = Sie ett ayey 3 3 - ae. Ubycqting , (RGBY, Dec. 208) | 8 ofpaths of length | from to ¥; serie Seppe that such paritioning exists. Consider two ais) n> Tard MP! (a4), ices and b of G such that acV, and beV, No path can exist ewes . M= (by) and. MP =(6) ‘esos sand b otherwise, there would be a last one edge bon one ‘ertex would bein V, and the other in V;. Hence i a partion exists, Gist connected, Conversely ' ‘wind : Jength a~1 from v0 ‘Let G be adsconnected graph, Consider a vertex equals othe number of paths of 1st V be the tof all vertices that ae joined by paths to See 8 jesuals the number of arcs from v, to vj, Hence, ay by; gives the Vs does nt include all vertices to G. The rennin vet of length fom v 10, where yi the next-to-last vertex Dill form a (non-empty) set V,, No vertex in V; is joined to any vertex > all paths of length n fom v; to v; can be obtained by surmming by anedge, Hence the parton. lk That sy isthe mimiver of paths of length nom ¥ 10 | Theorem The maximum number of edges in a simple sraphvi* theorem is proved Proved veri = GRY, Dec. 2008, June 2011, De mab connected map, with Vertes, Fees nd R “Proof, Wwe ke, = 1,203 venice, ten the theorem : V-E+R=2 — (RGPY, May/June 2006)208. Discrete Structure ei Fs Graph Theory 209 Proof. Suppose the connected may as shown in fig. 4.33. map M consists of 9 single a wed of Graph {G= (VE) is graph and |V] =n. Then the esr ph has elements defined by = 1 iff fv YEE No, aterie ae ald ace iT ‘Then Hence Otherwise M can be built up from constructions. pe fom» Single vertex by ue gy, i (@) Adda new vertex Q; and connect ittoan ‘edge which does not cross any existing edge as shown in ne’ 7m a 44 te ren) and A= AT. Ithen follows tht | a Ih | . then a picture of graph G is obtained by drawing a a a a @ is 08 el rine ajaceney Matrix A of a Graph G= @ Men ifthe graph has no sl oop, he ene long the of matrix A areal 0s Fig. 4.34 (ii) Connect two existing vertices Q, and Q, by an edge with eg eee «axistng edge as shown in figure adjacency matrix makes no provision for parallel iether operation changes the valve of V—E + R. Hence Mas ise cy mvas defined for graphs without value of V - E +R as the map, consisting of a single vertex, tht is, _ V-E+R=2 E i fe goph hs no paralel edges (and no sel-top) then the Hence, the theorem is proved. rex equals tothe numberof one’s (e's) inthe corresponding ‘Theorem Il. Let G be a connected planar graph with p verice sit reid of A. edges, where p 23. Then prove that (i) Pemustons of rows and of the corresponding column imply a eves ented Howth thro and columns Proof Let rb te number of repons ina planar recess? Ve Se en ant to te ieee Fate A i he conespoding clan mus fe eetwo graphs G, and G, with no parallel edges are isomorphic matics A(G,) and A(G;) ae related “TAG)R p-atr=2 [Now the sum ofthe degrees equals 2a by theorem I But each region has degree 3 or more; hence a tion of mates, Hence 15293 disconnected and isin wo components an its ‘Substituting this in Euler’s formula gives be partitioned as 2=p-att 2 4 2sp-at or2sP- 3ant 210. Diserete Structure Graph Theory where A(g) isthe adjacency matrix of the component g vy v2 V3 V4 YS rs St ang i the component gp: cre ea Ce This partoning implies tha there exists no edges ws Re liedebab PO subgraph g, to any vertex in subgraph g,, Min ag | 13 igor 2 (i) Gi 9 A= v3 cn tone ns nym.) g Sef af vi 01 8 | that Qis the adjacency matrix. Pn ee a} lt oT TO Incidence Matrix — ae si mn ~ Suppose M = (m, Epeesc ores Ss Defiton - Suppose M=(ny) she mn matin detney, | Bee piii0 aie nese. mf Pty 0.8 0, otherwise Bey 0 ‘Then M is said to be the incidence matrix. ar eae ee Properties of Incidence Matrix — ya® : ar (@. Since every edge is incident, on exact Sesh mix Mims acty ee 0 ree ~G(0, 1) ise snl det rah wim zl mas yath matrix or reachability matrix of G is the (i) The numberof one’s in an incident matrix of graph i ae thesumaf dogs ofall the verze oft pap aap) dei fs - (Gi) The total number of edges incident tothe coresponing we] 1, ifthere is path from v; to vj of that row is equal tothe summation of a row of the matrix. PE Jo, otherwise (ix) Its coresponding incidence matrix may have identical a ‘ evensatieiad (wocrmon amare hens pall Set eee ingen (¥) Ifa graph G js disconnected and consists of two comport}. ‘ae Pon 'B; and g» then the incidence matrix M(G) of graph G can be writen ina yea there must be a cycle from vj t© vj diagonal form as Sine G has m vertices, ‘such a simple path must have length m — 1 or 09a a eycle must have length m or less. This means that there is 2 Mig) ° ren the matrix MG)= ‘ By= A4A2+ AP act AM ° M(2). arix of G Accordingly the path matrix Pand By, where My) snd M(gp are he incidence maces of eomponesE # i ‘Here no edge in g,, is incident on vertices of gp and vice-vers® formally. ‘This also satisfies for a graph with any number of compones ‘Ais the adjacency matrix of a graph G with m vertices (i) We can reconstruc its corresponding - ‘aph easily, fora given incidence matrix. of BRE ASAPH ADS AM For example ~ We now consider the following «, matrix P and B,, have the same nonzero entries, i ee is the adjacency matrix of a graph G with m vertices, Suppose the edges matrix is B, the adjacency matrix is Aand incidence matrix is M, then B= A+AD+ AR A™ ‘Connected if and only if B, has nonzero entriesimber — raph with colors such that no two adjacent von u%8 a, alld the proper coloring or simply coloring wus have very vrox has been assigned a color accor ns hen ab ay Fig. 4.36 shows fa Bray ing apres Pro three differen Pe Fig. 4.36 Proper Colorings of a ‘The proper coloring is one that nue this proces till every vertex in T has been d (see fig 4.37). Now in T we find that all vertices stances fom have colo, while vand vertices distances from v have color 1. ow along any path in T the vertices are of ting | ese sae stween any two vertices in a tree, no two #3 4 the same color. Thus, T has Fig. 437 | with two colors. Coloring ofa T* ant Graph Theory 213 is colored with two colors, with no adjacent - iemeans that G is 2-chromatic, “odd length, we need at least thre colors “he theorem is proved. f Thus, Het We define a weighted graph as cither an ordered ordered triple (V,E,f), or an ordered triple (V,E, isthe set of edges, fis a function whose in is E. The function f is an ‘gis an assignment of 4.38 is a description of the behaviour of the machine nd to the amounts that have already been deposited 0, 5, 10 and 15c or more. At any moment, 2 things ~ deposit a nickel, deposit a dime and press her choice. Correspondingly, in the graph in fig ag edges from each vertex labelled 5, 10 and P. An ‘otal amount deposited in the machine when the kel, and an edge with weight 10 updates the total amount hen the customer puts in a dime, Clearly, when we nothing will happen when we press a button to select llrelease a candy bar only when vertex ds reached.Graph Theory 218, 214 Discrete Stuctre (RGRY, June 2011) ME trie ras 0, i andj although other intereetaton such ay ine ye highwas: or the number of accidents on the hig esti abel le ey Keemrwiaccpsn ttn hn eae faving ran: pene ‘lt we have to determine a shortest path from ve ia (RGRY, Dec. 2011) (RGPY, June 2013) es Oat LEX 10 (RGPY, June 2015) with example, (R.GRY, Dec. 2015) zt the mater given on page 202. a ‘and incidence matrix to represent graph. ao” (RGRY, June 2015) ‘coloring and chromatic number. (RGBV., June 2013) ge can be allowed to shrink into ay ie ; rink ito yen of a graph and chromatic number of a Anco et ct mars, Dee 205 ala Elen pts ed crea (RGRY, June 20,05 (RGRY, Dec. 2017, May 2019) m paths and circuits (i) Graph coloring. (RGPY, Dec. 2016) | Define Enler graph Paths and Circuits —Refer to the mater given on o the mater, A Refer othe fr given on page 202. a ~ Refer to the matter given on page 212. re rg sere: (RGR, Jame: a rs GRV, Dec. 2017, May (ii) Hamittonian path oe "8 (i?) Chromatic number. on page 202. (RGRY, Dec. 2019)216 Discrete Structure Ans. () Euler Path ~ Refer to the matter iven o lly, dd one edge at atime to the m vertices (i) Hamiltonian Path — Refer tothe nn ‘until m ~ 1 edges are added, Graph Theory 217 (iy Graph Cotoring- Rete 10 he man 0 i Formedges that were added. (0) Chromatic Number — Refer to ine i (RGRY, June 2013) given on Page cea om and homomorphism of graphs. Ans A spanning re ina graph G is a minima) oP ty eae abet the verices of G IF graph “G" is weighted graph, " the mater ziven 0” Po Spanning tee “obtained from a graph “Gj yeh la fora planar graph. Give an example of a the weights associated withthe branches in th he tg ler Sarind 5 regions and verify Euler's formula for wih 5 vertices (R.GR¥, Dec, 2015) ge 214. mula - A connected vetices and e edges has ie EN avs an example of a planar ee = 8 and v = 5, then the F i eee 8 52, Cleary, fi. 9 ° ons of minimum spanning tree areas fo freon results true. doet23) sean mag eerie ry et The minimum length of wire needea egg le and prove Eulers theorem. (R.GRY, June 2013) ‘supply can be provided, is a minim pa Sateen Let p and m be relatively prime. Then for any p, © pf) mod m = 1 Fran postive integer m, and hence e p= pl mod m Pot Inca and arty ine that is, ‘ 9m) = GED{q, m) = 1 to show that this assumption indicates that (pq) mod m is me to m. Suppose, to the contrary, that Dips) mod m, m} = d where d > 1 that d divides both (pq) mod m and m. In addition, d - indicates that either d divides p or d divides q, in which c = or GCD (q, m) = d, id a contradiction aris dicomes te Sorin suena, delete each edge which 0%] 9 Thivelyprineom. ~ Ledges remain. i» Nae the set of different elements which the remaining edges, m Then ae so ‘The input is a graph G with m vertices. sv (PXqqq) mod m), FG by increasing lengths Wvely rime tom, enumerates the elements Mt means that the set {x}, X34 su Xam) isGraph Theory 219 218 Disco Srtre e he four vertices has degree 3, thus by soup of ede fn) with expect © multiplication. fess sf odd degree. FOND Meet he ye ty has even ’ te gs even egress the ea proved THe invert oF an clement ca toute pt=ptm—1 ied i ‘but nota Hamiltonian circuit. alr cea bat net RY, Jane 2016) agan Euler circuit which is also a Hamiltonian h G as shown in fig. 4.46. Let EEG we maualy Soke ot RdGraph Theory 225 Show that a graph with n vertices yl. (R.GRV., June 2009, Dec. 2012) ‘Birkhoff given a way of tackling the four- chromatic aH — function P(M, 2), defined for all positive Se acerca ot en Pe etcetera e @ en P,(h) = 2 oF AQ, ~ 1), Hence o or? vertices then Py is ees 1G Oa pose that result is true forall trees having less - 21,2. We Pee. T with n vertices. Then T has at least vy be a pendant vertex of T. Consider T aie sty n — | vertices. Hence by induction hypothesis, VI lioness \ seo (a= 4. - DP. . in T. Now add v to T*. Suppose u Sot. First order the vertices accordin, " he vertex adjacent tov in T. eeessng dress fo obiain the soquence Ec “sr rane colours. Then V canbe coloured with any HA,D,F.B,CE,G ening b= 1 colous, ne Proceeding sequentially, we use the frst color the mmber of ways of colouring to paint the vertices H, B, and then G. (We cannot me 508) = AA — DF. - 1) =20.- D1 paint A, D, or F the first color since cach is connected 1, vee result follows by induction. Paint Cor the frst color sinee each s connected to citer or8} at] spose Gib graph on vertices whose chromatic polyoma is Sequetaly withthe unpainted vertices, we use the scondecirmesap P= AQ. = DP Netioes A and D. The remaining vertices F, Cand E canbe psineéwag]_ Melle by induction on n that Gis tree, If ~ 1 then P\(A) = {third color, Thus, the chtomatic number n cannot be greater tan Hs eens isolated and thus is a tree. If n = 2, then P3(2) = \(— 1). in any coloring, H, D and E must be painted iffeent ols sae ye esspoing graphs clearly an edge joining the two vertices which isa connected to each other. Hence n = 3. see forn= 1, 2, result is true. We assume thatthe result i tue for Prob22:Determine a minimum Hamil- ra sre it 1 tions snd chromate tonian circuit for the graph given below. . GRY, June 2005, 2009) al pe (GPK, June ><) 224 Discrete Structure Prob20. Find the minimum number n of map in fig. 4.58. olor’ req, Sol (n=4 Gi)n=3 (Gi) Only wo colors are needed, i, n = Prob2l. Use coloring procedure to pain tng wii cama of the graph. 4 ‘Sol. Hamiltonian circuit for the above Taal Sfseiteanbecooned na acs fm Basi ‘graph is given below — Fe GT Swi apap with n~ I vertices yhose chroneae Several Clearly it is Hamiltonian circuit because ination OD = HO — 192. (@_ Number of edges = Number of be pmhG yy chain pete eee vertices Mn TEXOFG— yp, We show that vg cannot be connected (i) Degree of each vertex is 2 fen G4, i Suppose if possible v is joined to two 7 ‘ois a tee with chromatic polynomial, and Itis @ connected graph.Graph Theory 227 panning tree of @ graph give the shortest ‘nodes ? Convert the given graph with Fig. 4.61 (RGR, June 2016) ibe G, since graph G has 9 vertices, hence any forming nyc) nl Ot following data ~ ei [Bie a20 Discrete Stuctre Nom, Ke) = min 4,142) 23 0 vertices ‘and 2s de Am222 Dacmte Sirctre =10 “1 spn riae tet then We hay “ ‘ fez} . =i 16 = ede), Te eta Fig 470 (RGPY, Dec. 2019) tom 6.113594 fz} then, we have ey ee Maha = {a} and T= {b, c,d. © f 7) 25H He minimum distance bee, war eT Oe . Be vest, Ke) Kf) = 29, Mz) = © dts js ‘minimum al is ew focus (note that we can ae eae ae Path isi ‘value, therefore ¢ is our ne es x Senet rh ft oe i rinirmum value 2 and then proceed further), ming Sraph betw ‘dotake that has the me! ‘Hence P= eehana T= (be £2) Now Ke) =min.3,2+3)= (mari Wee dhe wole Md) = 29 = {b,c d) ) = min(s, 2+ 6) 2's 1 Me) ~ ming, 2+ 2)=3 te Since imine 372) 5 vy Sports Hence l= iE, therefore bis our new: = td) focus, then we the 4+6)=5 Ka)=min, @, 2+2)=2 ‘Ke) = min. (co, 2 +4) = 6 Kf) = min. (0, 2+6)=8 a) = mi. (2,2 +0) = Sine is minimum value, therefore dis our new focus, then we tke fa, c,d} and T= {b, €, f 2) = min. @,2+2)=3 min. (6,2 +2) =6 rnin, (8,2+4)=6 a) = min. (2,2 +0) = 2 Since 3 is minimum vale, therefore is our new focus, then we tke P= {a, c,d, b} and (e, fz} Now Ke) = min. (6,3+4)=6 Kf) = min. (6, 3 + ©) a) min. (3 +2) =0 Since 6s inimum vale, heefre eis our new focus, then we take Pe (werd bye) and T= (62) Kf) = min. (6, 6 +0) = 6 Az) = min. (@, 6 + 2)= 8 Since 6s minimum value, therefore fi our new fous, then we tke P= (a,c 4, 6,1) and T= (2) Ka)~'min. (8,64 3)=8 ‘rence the length of the shortest path from a to is 8. The shortest path is Now) = min, (o,2 +6) = Sine 3 i ei 20,2 | nat pounimum value, Da 3+ =7 ie aida4 . 3+ 1 minimum vag, 7 minim ale, at Dae ming Br es 1K GA imum value 7 and then proceed arden ming, 7+) 2702) Proceed further) Now, iD) = Fig 472 (GRY, June 2004, 2011) Graph Theory 235 «1 inthe graph shown in J8- er Lagat d distance between a ah ane 1009, Dec. 2010) a Mee sae, Nowsec. 2007, June 2 i n aand z in the following ht ee [oi Nea (RGPY., June 2012) 17 08 a p= (a) and T eure VE Kb) = 22, Ke) Ke)= sate inimum value, then we take p= {eajand T= (0.0566 2) so we we A" 0 new foes. Load (by = minimum (22, 8 + ©) = 22 e)= minimum (16, 8+ 10) = 16 ‘ninimum (0, 8 +2) = tninimum (2, 8+ 6) = 14 tinimum (2,842) == 1Wistheminimum valu, ten we ake . PH (ea. TH (682) Sojve we ‘fa anew focus ee Xb) = minimums (22, 14° 7) =21 ie)= minimum (16, 1443) =16 ie) = minimum (18420) = 1G) = sim (=, 149) =23 16a the minimum vl, then we take Bo Ga ee ‘b)= minimum (21, 16 + 20)=21 Xe) nimi , 16-4) = 20 fe) ina 9, 16 +10) =23 P= (ord, f,0,e) and T= (b 2) 1) nin (21,20 +2) = 24 1a) sion (23, 20+ 4) = 23298 Disc Strive = KAO = min(4, 342) < 4 =min(o,3+3) 6 Aas = min, 3 +5) ming, 3-40). ea 44226 ts)-mata tsa HAS) = min(, 4 +2) may 16) = min(o, mts =) :rin. (6,2) =5 min. (8,8) = min, (©,4 +5) = min. (2,9)~9 therefore b is our new foes, then we tle 44,6) and T= fe, Ac) =min. (6,6 + 2)= min (8, s) 8 4y)= min. (9,6 + =) = min, 9, 2) Fe ea oe thereat sour new tone nase nt P= (WB, 0,4, f,b,c} and T Now 19)= min. (9, 8 + 2) = ‘Hence, the minimum distance between u and v i 9 ‘The shortest path is {u, gf, )