5.1 INTRODUCTION A graph is a mathematical object that captures the notion of connection In other Graph theory isa special branch ofthe mathematics which deals the problems, widgets of graphs. It has application in computer science, electronics engineering, methane’ engineering and other branches of sciences. A graph ean used to represent alnow a. physical situations involving diserete objects anda relationship amona them, Inhisches some basic concepts of graph theory have been introduced and some elementary rs have been obtained. Here we are explaining graph, path, circuit, tree and is application, Graph theory was bom in 1736 with Euler's paper in which he solved the Konigsbes bse problems. 5.2 THE KONIGSBERG BRIDGE PROBLEM (K.B.P.) ‘The Konigsberg Bridge Problem (K.B.P.) is the best known example in the field ofthe grant theory. The problem is as follows. The city of Konigsberg was located on the pragel rivers Prussia. The river divided the city into four separate land masses, including the island ct kneiphoff. These four regions were linked by seven bridges as shown in the diagan Residents of the city wondered if it were possible to leave home, cross each of the sev bridges exactly once, and return home. The Swiss mathematician Leon Hard Euler (1701- 1783) thought about this problem and the method he used to solye itis considered by ms to the birth of graph theory. 8 Inthe agraph — th vertices. Th answer to thSO1UtiON Was ssraction othe pee vere of he alka Reet Bor ing cach of the land pao : wn epresenting Cach bridge et & 9 “ging the Vertices Corres nytt < correspon, j masses, We now haves oat -s the net ssary information. aa ding a“clo, a sed walk sire. This is called Eulerian cineye phofthe KBP, is a Let uy wees to f UTILITIES PROBLEM - three houses Hy, Hy, Hy. Be ty Ha» Hy. Each to by and electricity (E), by © Connected to Ve ch connections Tia) Meas of cond, Rethoftethee w sie any crossovers oe ae THE BEDbem is sine eae s the conduingy ‘1 Petbeto p 1 (Three utilities problem) inthe adjoining figure, we have shown tat how thi problem can beserecie sph — the conduits are shown as edge while the houses and utility supply centres are verze, This graph cannot be drawn in te plane without 85 crossing ove. Ths ‘siner to this problem is no.ae 4 TEXTBOOK OF ENGINEERING 5.4 GRAPH. (RGPK June 2004, Deo, 2007, A graph G consists of two sets, Feb 2005, (0 AseE= (04, ¥9p.05} Whose elements are called Vertlee (op : Point (i) Aset B= (0, } whose elements are called Bayes oF Or tnes oF brant No 1 of g We denote ch a graph by G = ( In other words, A Guaph G = (K, £) consists two sets, one is set of vertices (E), such that each edge is associated with an unord For Examples Iz Let = fvy, vp, v5.94) and (V another lered pair of vertices, "Oey, £1, Cy 65, €4, 05) My Le ) Me 8; ig vq Prema he (Graph with four vertices and five edges) 2. Let V= (v4, 5,4, ¥4} and B= fe, &, e, e,, : Inthe a 1 ay My, a zh 2p gy C5; €G ey} sgaseit loop: CNS Note. 57 ORDE ‘The order 0: Examy (Graph with four vertices and seven edges) \ Note: The fotal number of vertices of a graph is called order of graph, 5.5 PARALLEL EDGES Iftwo edges start and end with the same pair of vertices, then they are said to be parallel edges i.c., In other words, if two or more edges start and end with the same pair of vertices, then they are said to be parallel edges. Example: Ng AG Inth e W=6, 2 58 size The size 9 v4 Pi Ye (Graph will parallel edges)pH THE” ye above graph WUBES ey -and 5 starts 894 re said t0 be parallel edges, And end on thy 5 wo © Vertices vy ahiFig Meine jue, The parallel edges are uv N 4g SELF LOOP edges start and ends on the same vertex, Example: salled mutipte edges, ia » Its said to, be “Selttoop” V2 a ci C 5 Lk V3 e% i (Graph with self loop) Inthe above graph edge e; starts with vertex vj and end on vertex v). Hence edge ey iseselfloop. ee Note. A self loop of graph G is simply called “loop” of the graph G. 5.7 ORDER OF THE GRAPH The order of the graph is the number of the vertices in a graph. It is denoted by P orn (v). Example: \ 4 fabove graph is 6 Le, p= ices. Hence the order of above io r ra above graph, there are 6 vertices. 58 ; in ia joted by Q orm (e)- Thesizs ofthe graph isthe number ofthe edges in the graph. teni vi ‘a Inte above paphihreae igs Hemet ote Bap ie, gu Maing 4 c 5.9, TYPES OF THE GRAPH — 1. Simple Graph IRGPY Dec. 2005, Feb, 2, rt A pach aha lor normale! cdg called s Mpegs pas srapn, eA which doesnot ave any self oop and parle ees sealed gee a Malt Example: ven 1 Mal Ys Me 3 v5 / \ ed: Po teiingaiias vy a va (Simple Graph) 2. Multi-Graph Thegreph costing mlple edges (parallel edges) is called mul graph v A multi graph G=(¥, E) consists ofa set V of vertices, a set E of Se {1 %) v2 EF, v, #93). The edges ey and e, are FOYE Le)893 Newyork Chicago Washington Los Angeles (Muti graph) 4, Pseudo Graph Apseudo graph G = (¥; E) consists of a set V of vertices, a set é fam Eto (0,92): ¥2€V).An edge eaters eee ASE Ofte tnd a fiction / FO = ,, Pseudo graph are the most gen: ‘oops and multiple edges, ¥2} = {v1} for some v, € feral type of undirected graphs since they may contain Notes, 1. Multi graph are undirected Sraph that may contain multiple edges but may not have loops. 2, An undirected graph G consists ofa set of veices, Vanda set of edges E: The edge st contins the unordered pair of vertices. F(v,, v2) € then we say and are connected by an edge where and vp are vertices in the set x By a graph, we always mean an undirected graph. Examples: e (Pseudo graph) 4. Null Graph =. A.praph in which edge set £ is empty (Le, E= 9), ee Faria wot be empty b=» res (thervise there is no graph) is called Null Graph. Example : Consider the graph G=GUy, BE) where * Fortormn ve vom) andé . (Null Graph)7 wscee ATEXTIOOK OF ENGINEERING hay ot THO $ d He 5 Sub-graph [RGPV June 2005, 200%, Feb, 2008, 2010;r49)0. psa A graph Gis said tobe sub-graph of graph G ifall the edges und vertices ype 2?) are in G, such that each edge of G, has the sanie end vertices asin G.In other «®t raph ofa graph G~ (¥, 6) is graph G, = (Vy £) inwhich Fy Pande, nv ane Of G, has the same end ver Fang, ach eg in G, as in graph G. Properties of Subgraph |. Byery graph isa sub-geaph of itself 2 Asingle vertex of a graph G is.a sub-graph of G. 3. Assingle edge (with its end vertices) of a graph G is.a sub-graph of g, 4. Asub-graph of subgraph of G isa sub-graph of G, Examples 1: Vs Vs | pirected u i Iti adirected mu sanction ro vs Ve sa : \ M2 Vs @ * (i) (Graph ()) and its subgraph (i) ‘ % 8, Complete My Vy A simple graph ifthere is an ed graph. Forexan Ve Ve . 0) si Vs ae Complete (Graph (i) and its subgraph (i) os i Properties 6. ‘Directed Graph — (Digraph) 7 AA directed graph G = G (¥, E) consists of a set of vertices Vand a set of edges £10" aie ordered pair of elements of V. = : 2 Ins Itis noted thatthe edges of directea graph are ordered pairs. Loops, ordre Po" veri of the same element, are allowed, but multiple edges in the same direction betvee" " 8. Triviat ¢ vertices are not allowed. * Staph, fonegaat THEORY Example: (Directed graph) 7, Directed Multi Graph Adirected multi graph G = finctionfttom E to {(¥4,v,): Example: San Francisco (KE) consists of a Set V of vertices, a set & of edges, and a NW25 1). The edges e and ey are mulipleedgesit/(e)-/te), Chicago, Denver Los Angeles 8. Complete Graph Asimple graph in which there exists an edge between every pair of vertices or we.can say if fee isa case from every vertex to rest of vertices, then the graph is called complete ‘raph, Forexamples : be Gs Se (Directed multi graph) ° o——— > s G2 ‘Complete graph with one, two, three and four vertices. P h "0perties of complete grap n(n=1) 1. The total number of edges in a complete graph is alweys — au IK hh the degree of every vertex is one less than the number of In a complete grap! vertices, 8. Tiviat Graph Of one vertex and no edge ie., a single point is called the trivial graph.896 A TEXTBOOK OF ENGIKEERING et Mari rHe0! For example: Suppose the graph G = G(¥; £) eat. ror example Where Vm (v) and &=@ Then the graph G is called the trivial graph. My ; 5.10 INCIDENCE =. iva gra ? trend vetce apes ft 894 ten and ae the end verica ny m 2, Thedewree of ‘amend vertex of an edge ¢,,then vertex v, and ed 6 € are said to by rita nk s eaealelb a incident withegey Ht vs tee 13 jgOLATED V 3S pr sox with degree 2 u a : Aves vertex having soe’ example? e ee Ms oF Ve Clearly ¢;, ¢, are incident on vertexy,, and es are incident on vertex v3, incident on vertex vs. edges e, and e, are incident OT Verte edges es, e;, and eg are incident on dogs VETIER edge 5.11 ADJACENCY ‘Two vertices V1, % Which are joined by anedge eina ‘graph are called adjacent Yertices, = For example: Inthe above graph, te adjacent vertices ar) 41) na Clearly d (ve) (a y)and(v, v3). 5.14 PENDANT VI 5.12 DEGREE OF A VERTEX IRGPY Feb. 2008, June 2004, 2008, Avertex of degree one i 2009, Dec. 2003, 2005, 2006, Sept. 209) Forexample: The number of edges incident on a vertex ¥ (with self loop counted twice) is called ie degree of the vertex V, It is denoted by d[ 11, es Example: es “5 Ya | ey ley } : ee | Clearly d(u,)=1, | 345 Parity (EVE & SoG te degree of the following vertices are, rity ofa vert Joe, dO), depen Mio ee teeny —s ae E Then the vertex v, Note. 1. The total degree ofall the vertises of a graph is twice the number of edges ote. 1. eei “ son nner” | porexamplte: | garda) +acay 897 yegen ede 2 ah 4 Tedesiee ofa verter inatgg ot ee Called valency 519 ISOLATED VERTEX avertex with dopree zero (no ed, vertex having no Ike incident on iy Wide? {8 said to be Hentedge catego be isolated vere, In other fed vertex Clearly dv) = d(vs) = 0. Therefore vg and vs are called isolated vertex: ") 5.14 PENDANT VERTEX [RGPY Dec. 2005) | Avettex of degree one is called a pendant vertex. Forexample+ Ml es Ms e e e4 és &5 Vg Va (v4) = 1, and d(v_) = 1. Therefore vertex v4 and ys are called pendant vertex. Clearly a i x 5.5 PARITY (EVEN OR ODD) OF A ere Vertex is said to be even or odd according to its degre ‘called parity ofavertex. Reece Inthe above graph, 3, dw=3 d@) =4 or xd parity of a vertex Then the vertex v4,¥2.and V3 Fe id, Then the vertex898 A TEXTBOOK OF ENGINEERING nary 5.16 SOME OTHER IMPORTANT GRAPH REGULAR GRAPH (RGPY Dew, 2995, Tits Sep, rach: ts Forexample: ve / _\ a vt c ve OM e ve a 2) (3) * In the above praphs (1) and (2), the degree of each vertex is 2. Therefore these are called regular graph. Similarly the graph (3), the degree of each vertex is Thee } graph (3) is regular graph, r = + Sv en Wed vj a i / M2 vs i % Intheabove graphs the degree of each vertex.is3, therefore they are called regular rh isomorphic Graphs [RGPV Dec, 2006, June 2006, 05, 2009, Feb. 2066) ‘Two graphs G, and G, are called isomorphic (or equivalent) to each other, ifthey have ne: to-one correspondence between their edges and their vertices such that the inciderc: relationship must be preserved. Thus two graphs are isomorphic to each other if, IL. they have same number of edges. 2 they have same number of vertices. 3, the one-to-one correspondence between vertex and edges i. relationship between vertex and edges must be preserved. (The degret ¢ corresponding vertices are equal). Forexamples: 4 ey wy vy, V4, Ve e% ‘6 pt THEORY rere we see that Both the gra Both the gra on as Clearly both ar Homeomorphic Two graph G, and G, Hor isomorphic) by ‘Two graphs Gj bya sequence of sub ofdegree two in any Esamplel: Na v4 The graph G, degree 2 on the e¢ phic.7 THEORY ere we see that J. Both the Erephs have 6 ed, 199 2 Bott the aeaphs have same yy tho A deg) —de8 0 =1 epat sty deg (vs) = deg (nj) = 3 og (v3) ~ dex (ns) = 3 deg (¥,) = deg (vj) = 2 deg (v5) = deg (vg) = 3. ‘then by the definition above APH have same eee © HUNDEF OF edyon, both graphs are © isomorphic we Ve ‘A Ne ee Clearly both are isomorphic graphs, Homeomorphic Graphs yoeph@, and G, are called homeomorphieif they can be obtained from thesame granh ‘Hor somorphic) by dividing an edge of H (ot ot isomorphic graph) with addtional vertices OR are called homeomorphic graphs FG can be obtained from G) In oer words, we can introxtuce vetiess ‘Twographs G, and G yasequence ofsubdivisions of the edges of ofdegree two in any edge of Graph G; ‘Example 1: Ct “ @ ™ by adding vertices vy and v4 of Hence the two graphs are vo btained from the graph Jz 4) respectively: OS) ‘The graph G; can be ol degree 2 on the edges (v1, V3) and (V2 ™ fomeomorphic. ve ‘ Example2: 2 6 Gi)900 A TEXTBOOK OF ENGINEERING MATHEMATICS ‘The graph G, ania ae en C39 man SETS OuFee 2 00 edges (oy, 4) and (0, v) respectively. Hence the ‘graphs are homeomorphic Bipartite Graph [RGPY Feb, 2008) A graph G=(h, ‘ps blpaie fine venexset/can be paritioned into two subsets (Aisjojny) caer ye such that every edge in & connects averteX iT ¥1 and a yeitex vs (Such thatno ee rea eee elder two vertices in v or swo vertions in ¥2) (7 ¥2) is called a bipartition of G_ Obviously, a bipartite graph can have no loop: Example I: ¥ Ve Clearly, ¢ isbipartite graph, because its vertex set can be partitioned into the twoses {oq 5 15} and Vs = fs, ¥q vp} and every edge ofc, connects a vertex in Vanda verex y x (Gipartie graph) Complete Bipartite Graph ae ens srph on mand vertices, denoted by kg, isthe graph, vos an edge between each pair eas . one jcesand V5 with m vertices in which there i complete bipartite graphs fo, fo, 4 y, a Va. Whiere yy is in Vj; and v5 is in VT (ka a)encom Gt TPES OF SUBGRap), (p98 Dislolnt Subgroph, 01 nd Gs AF to subgraph Gi if ifthey °f graph g, inet ParaP ey on Do pie: iRGpy, ®ph G ¥ June 203 and 108 (Then G2 Bre catieg (hey may never ee TH are ) Clearly the graph G has, ey, andibesub-graph G has Yj ~{v,,v,, v5} and é, = (Hye Pge Yar V5 ¥e} and E, ~ {es, €3, 6, 7} We see that E, Gand G; edge disjoint sub-graph of G. (i) Vertex Disjoint Subgraphs [RGPY June2003} Tietyosubersphs G; and G, of graphs G are called veriex disjoint sub-graphs, ifthe do jot liave any vertex in common and they do not have any edge in common, Examples: a ee ‘i Ve es vy ee % = L & le, fy 3 eee | @ (Gi) 6) eg ener) R ents - yt) and E= (0 a has P= eta een 1 Dip Vea 30 7 = ' fe, €5, &}- nE=% Tee es $e cxasoit subgraph ‘Therefore G, and Gare callene ht HEC ' prerng0K OF ENGINEERING MATHEMATICS. ark 902 z [RGPV June 2002, Dec. 200) qnen (i) Spanning semen cae ning subgraph ofthe mraph ICM CH= Vic) ih bs called «a Conner the graph © /“ 3 Exam] a ¥ vs Then the spanning subgraphs are, vt p qi eH 2 | @ ey 85 v3 Vi % es Ve yy Property of Spanning sub-graph |. Spanning sib-graph fs defined only for @ connected graph. k 2. A spanning sub-graph of a graph with n vertices always consists m — 1 number of ate oss edges. is why 3. There may be more than one spanning sub-graph of a graph G. : P 5.18 SOME IMPORTANT THEOREMS Proof ‘Theorem 1; (The Handshaking theorem), The total di fall the vertices of: “ graph istwicethe number of edges. : ao | with » : OR | 1fG~ (8) bean undirecied graph with e edges and n vertices, then dq) = oe 2 Dams [ROP June, 20071 ae a Yip i aed be the n vertices, ofgraphG. Since the degree ofa vert" number of times an edge is icles vines Sine cea, Mie Seztee counts the ba Vertex. Sin eae wi ‘two vertices, each edge gets counted twice, once wee ae ig1 pee Dides) = dee (v1) + don(v,) +d00(0,)+degt = 143444343 4 x7 ice the number of edges. )+deg(v,) Nile) This theorem applies even if multiple edges and loops are presen. The abovethecen Ieilhisrulpthat ifseveral people shake hands, the toll number of hands stake muse vent vty the heorem is called handshaking theorem. em2: The number of vertices of odd degree ina graph isalwayseven, iV Feb 2005, 06, 07, 2010 June 2006, 2008, Dec. 2002, 06,07, March 2010) Proof: Let G=G (V, E) be a graph such that Y= (vp, %,Vonrvy) and (eye om to) With Vertices and m edges and we know that by handshaking theorert, . Dae) = 2e=2m. Weean write the above equation such as Yaw) = Yaere 200? i isan 5 Law ds dao) yaw = fa jeeENGINEERING MATHEMATIC where : ways ever her fay raph isalwayseeven. Proved ger ina simple graph with, ‘wo even num tices of 0 ‘maxim [The subtraction of Hence the number of v= ber of edi ‘Theorem 3: Show that the im number Feb, 2008, Dec. 2008, April 2009 xGe=D) [wepY June 2005, et ls ae Gurpbensimpleannivter peril nor self loop) suck, roof: iat @= GU. } with n vertices and », ee y= foyevpons vo NDE (68 elges and we know that by handstiaking theorems Yaw 26 tt +d(w,)* 2 L Free ico know tit the maximum degres ofany vertex ina simple graph with x vertex is n=l Then from equation (1), we get (i= 1) (n= 1) + snc times=2e = miei) =2e => € a ‘Proved. s ] 5i19 WALK [RGPV Dec. 2000, June 2002 ‘Walk in a graph G isa finite altemating sequence of vertices and edges, beginnin; ending with same or different vertices, such that no edge can appear more than once howevera yertex may appear more than once. Walkcan alsobe referred as edge chain For examples: “ i (i)THEORY. S jes of Walk j. BYeHY WAIK OFA praph e % Aselfloop may bean, 1 Agraph has more i, 7 tS su, Pan or ihe eh of is AH One Waly qpere are TWO Types of Wai, (y OPEN WALK soll whieh start and end veri, pute Insite Words an open wary in Miedgesstich that starting and coy hay oe Tioes are i Stemating son C!S open Forexamples : HO edge cha ane RecA nbpear more + Walk . Clearly y, e v3 e) Ys &9 ¥3 €9¥ €5 vy 18 (i) CLOSED WALK Avalkin which start and end vert other words, a walk which is not op: % Forexamples : are same (sire terminal vertex) called closed wal en is called closed walk (Graph) ‘ avai 2"! Hy ve 13 €5 5 #6 867"?i OF ENGINEERING MATHEATICs a rexTB00! 192, 06, 04 2008, Dec. 2004, 2003, 1, 906 gev June 20 ee called & path, fteannot inv 8.20 PATH nore an ane ber of edges in Path i aiey cv no vette mi Anajen wakin wich no veeh Te ah, ee, ie a et 19? ot po ef 007 8 path of length Ine engi of path: An & vs y For examples? e Me eres Cy le va 4 Vs (Path) +4) isan open walk of length 3. ve “The path vy 0-v4 (21 9242 ¥5 4 Properties of Path 1. Inapath terminal vertices are of degree one. 2) Rest of the intermediate vertices are of degree two only. 3. Length of the path isnumber of edges which contribute to form a rath, 4. Length of a path is always one less than the number of vertices in that path. 5. Every open walk has more than once path. 5.21 CIRCUIT OR CYCLE {RGPV June 2004, 2003, 2008, Sept. 2009) A circuit (or cycle) is # closed walk in which all vertices are distinct ex it os cept the termina je (ie, Se and final vertex). In othet words, a closed ok awh appears more thanonee,is called a circuit or cycle. It is non-intersecti . a 0 u intersecting walk, sul that every vertex is of degree two, A self loop is also a circuit, A circuit is ibook Accycle of length Kis called a K- For examples: aie . oon cea the closed walk vo, 1B Bee MFO is a ciroun Hue 1, r sPeuitverent cycles are given” “VME Is Hoe iy, 8 Cini, 907 6.22 EULER GRAPHS [RGPV June 2005, March 2010, aes moving on a graph, by covering all the edges of the graph and return ‘Setalsertex, such a walk is called Euler line and graphis called Euler graph Tiotherwords, we can say that if some closed walk ina ofthe graph ¢ iph Gcontains all the \h is called an Eulergraph908 “a vl @) ey 0 ie Example ae if we starting from vy and covering al the edges such that Clearly, this is a sulergraph 4° unicur 5.25 TRAIL 1fina walk ali ch trail, So in tra ‘Examp'es: Properties of Euler Graph : 1. Buler graph is always connected. 7 , , 2 Euler graph does not contain any isolated or s cs y/ 3. Alllthe vertices of an Euler graph 4, Buler graph can be decomposed into | 5.23 HAMILTONIANS PATHS AND. Ifa closed walk contain every vertex of the graph G,. 2, then the walk is called Hamiltonian circuit, and ‘Hamiltonian path, Examples: Properties of Hamiltonian Paths and Circuits 1, Hamiltonian circuit have exsctly the > 2. Hamiltonian circuit is sleet one ke. doesnot have a Hamiltonian cirouit, oa. 3. If we remove an edge from Hamiltonian ciren onthis Hamiltonian path. mo aeIRGPY June 2092, 63 2006, Sept, 200 2003, 05, 06 Feb, connected graph having no circuit is called a tree. From the definition, it is obvious that a tree is a simple graph tha selfloop nor parallel edges because both of them are from a circuit, Wee aaly finite graphs, having at least one vertex, therefore a tree is fin e a yeriex, A tree consisting of a single vertex with no edges is called degenerat: tollection of disjoint trees is said to be a forest. In other words, a forest G is a cra gjeles, therefore the connected components of G are trees. A leaf (or terminal nod isayertex of degree one. A vertex of degree more than oneis called a Bran Examples : = 9 @T GT & a], ; ra ’ (Tree) =MaTHENAICS Fer every pa ab vetioes. wy baw every pale of vertices then \ iin graph : frag ta tee cigs 150 170. a ‘¢ snnected graph elit: se vertices and 1 eeges fs 9 tres \ 0 S Agraph tea tree fan only jrritis iniewally connected | yoo H Haxingishe some Properties of Trees asa 8 Theorem 1s Ageaphisacreeirana vitae soneanonly ane pathiney ec soto pairofvertices. Bide 2001, 02) oie por Proof: Them wary condition Fuppose 7 fa tree ton ve shall ave to prove tat there exists ony One al tetwcen every parorvertices iT sal is es nerefreTHconmecte graph anthas ere He possible, fat there be wo NETS ana yin Tsuch tat there ars ovo ormore io cine att pas between ual vs UT TE these pals Will give Us a circuit crete not possible ina tree Tad #0 Tanne, Sie atree, whieh és contradiction to our apposition, Hence there ison and only one path between every pair of vertices in r The sufficient onion Let G bea graph in which there is one and only oie path between every pair of 32 DE y pair of ti nfo show ta se, Sie te AS 8D between every pair rerces oF G, therefore Gis connected. Lettre be ace in G, then itimplies that there } tar Teast one pair of vertices x, pin G such that there exists two distinct paths between i ‘Thesorti i vee which eoniradets the given condition. Hence 6 has no SeaicaeGisates, to any sy" Hence Proved. called de ae Agraphisa tree ifand only ifitisminimally connected. Fo ‘rook: The necessary condition the flow: ae graph bea tree, Since there is one and only one path between every pair of decision ice, therefore it we remove any edge between 8 pair of vertices th : graph wll be dseotnected, and we know that aconnected graph ¢ iy cxnneces if deletion of any one ed ais raph G is minimally connected ‘edge from G disconnects the y eck eo connects the graph G, Hence the tree is minimally Te tthe graph be a minimally conn . 8 ected If the graph has circuits or parallel edges, mane Then ye have to prove that G s.r Fel doe lino dsoounet gap The a oi plga from tay circuit tas neither circuit nor parallel edges, Hence the Boa einai) coanecie’ 5.33 | Hence Proved. we minimally connected graph js a tree ‘Theorem3: A coni A e ynected graph with a: ‘bina vert : ices and (n~ 1) edges is atree. either 1 [AGP Dec. 2005, 21 ! = Prot eee deny mv 2009, Feb, 07, June 2007, June 200” ected therefore there is at least one path tran (n= 1) edges. Since it pair of vertices and (7 cages, Are just suicient to co s nected all the m vertices and the circuit and hence G with n vertices Tee cess ia efore there cannot be a ges isa tree. 5.30 DIRECTED TREE [RGPY Feb. 2006| A directed graph is said to be di cdges are ignored rected tree if it becomes. tree when the di ¢ directions ofsjrsonig of the mail according to uni 2 to unique pin o SN cre cr roman siden tree. ‘ example: Let you have two altem the low chart of the problem is shown in t oe decision tree, : IK 3 BINARY TREE [RGPY Dee, 2004, Fel in which the root is of er== ga special type of tree, 3 or 1. Every binary tree's ® rooted tree: DanNGINEERING MATHEMATICS - | 916 A TEXTBOOK OF EI Properties of @ Binary Tree always 0 ves are Of | vertices in stiges in whieh one of the degree 2 ad number of Ve! degree | or 3: A binary tree is always one less than the 1. Binary tree consists and rest of the vertic 2 The number of internal umber of pendent vertices: ’ 4. The total number of pendent vertex in 8 pinary tree is [( total number of vertices in a binary tee: ry tee 7. Then (#-p—1) isthe 4. Letp be the number of pendent vertices in a bina’ number of vertices of degree 3. nt 1)/2]. Where 17 is the 5.34 SPANNING TREE |RGPY Dee. 2004, June 2005, Spanning tree Sof'a graph Gis an another special type of tree wh of graph G (graph G is obviously connected). Spanning tree S Thus for $10 be spanning tree, we have three following requirements: () Sthas the same set ¥ of vertices as does in G. (i) Sisatree and (ii) Sis a subgraph of G. Note that the spanning trees in in G, therefore a spanningtree is a maximal 06, Feb 2005, 08, 2010, March 2010) jich consists all the vertices isa subgraph of graph G. G, sothey are the largest trees among all the trees treeor itis a maximal tree subgraph of G. Ma es ‘7 Properties of a Spanning Tree L Sy i ii K peu see) i ales only for a connected graph, graph with m vertices al : 3, There may be more than one spannit tea a i ig trees in a graph G. For a disconnected graph, each e : become a collecti ach component haye i ‘. ‘ lection of spanning tree, and this Bigs cuicraie er OM it will est. Branch and Chord of a Grnanminn TL.