GRAPH THEORY Art-1, Introduction Graph theory was bor in 1736 with Euler’s paper in which he solved the Konigsberg bridge problem. In 1947. G.R. Kirchoff developed the theory of trees for their application in electrical network. A Caylay also discovered trees while he was trying to enumerate the isomers of saturated hydrocarbon C,, Hy +2. They also lay down four color conjective, which states that four colour are sufficient for colouring any atlas such that the countries with comrign boundaries have different colour. Now a day Graph Theory is employed in many areas, such as Communications, Engineering, Physical Sciences, Social Sciences etc. On account of diversity of its application, it is useful to develop and study the subject in abstract form and then import its results. In general areas of computer science such as switching theory and logical design artificial intelligence, formal languages, computer graphics, operating system, graph theory is very useful. In this chapter, we shall define the various components of the graph theory along with suitable examples. An attempt has been made to show that graphs can be usefill to represent any problem involving discrete arrangements of objects, where concem is not with the internal properties of these objects but with the relationships along them. Art-2.Terminology (P.T.U. B.C.A.-I, 2006) A graph (or undirected graph) is a diagram consisting of a collection of vertices together with edges joining certain pair of these vertices. Mathematically, we can write A graph G = [VG). EG)} where V(G) and E (G) are sets defined as V(G) = Vertex set (points set or nodes set) of the graph G, E(G) c V(G) x V (G), a relation on V(G), called edge set of G Each element e of E(G) is assigned on unordered pair of vertices (a, b) called the end vertices of ¢. Scanned with CamScannera v SPECTRUM DISCRETE STRUCTURES ‘A directed graph is a graph in which each element ¢ of E (G) is assigned.an ordered pair of vertices (a, 6) along with arrow starting from a to bj'where a is called the initial vertex and b is called the terminal vertex of the edge e. (P.T.U. B.C.A-I, 2006) ‘The graphs directed and undirected are shown in the following figures : (DIRECTED GRAPH) (UNDIRECTED GRAPH) (OA graph is represented by means of a diagram in which the vertices are denoted by points and edges are represented by line segments joining its,end vertices. (ii) It does not matter whether the joining of the two vertices in a graph is a straight line or a curve, longer or shorter. Two vertices « and v of a graph G = (V, E) are said to be adjacent if there is an edge e = (u, v) connecting u and v. Also the edge e is said to be incident on each of its end points u and v. For example :- In the above diagram a and b are adjacent vertices. Since there is an edge e1 = (a, b) joining a and b. Also the vertices a and d are not adjacent, as there is no edge joining the vertices a and d. Loop (or self loop) An edge that is incident from * self loop or sting. For Example :- In the above diay the is it ™ re ample zln gram the edge e7 is a loop. Since the edge e7 = (b, b) _ Isolated Vertex A vertex of a graph G = (V, E ich i woe . . cilled an isolated venex, 1» WHieh snot joined to any vertex by an edge in Gs For example :- In the above dia; igtam the vertex x is an isolated vertex. | Tf two (or more) edges of . called parallel age 'Bes ofa graph G have the same end vertices, For example : edges. and into itself starts and ends at same vertex is called then these edges are h ; n the above diagram the edges ey = (c, 4.) and eg = (6, d’) are parallel Scanned with CamScannerGRAPH THEORY Incidence ‘An edge e of a graph G = (V, E) is said to be incident with the vertex v if v is an end vertex of e (or w incident with e) Two non-parallel edges of the graph are called adjacent if they have one common vertex. For example :- In the above diagram the edges ¢; = (a, b) and e, = (a, c) are adjacent vertices, as they have a common end vertex a. “Art-3. Types of Graphs (@ Simple graph : A graph which has neither loop nor parallel edge is called simple graph. a a d es es e es & 7 b & f 5 e c The above graphs are simple graphs. (General graphi(or Multi graph) (P.TU. Bwc.A-I, 2004) A graph which have either loop or parallel edge or both, is called a general graph or (P.T.U. B.C.A.-I, 2004) a multi graph. Parallel The above graphs are general graphs. ‘A simple graph in which there exists an edge between s is called a complete graph. It is also known as universal graph. every pair of v Scanned with CamScannerL For example : Following graphs are complete graph. —/\ A\~A Note I: A complete graph with 1 vertices is usually denoted by K,, II: A complete graph has C (n, 2) edges. : Let G = (V, E) be any graph and @ : E > R bea function from edge set Eto set real numbers R. Then the graph G = (V, E, w) in which each edge is assigned a number called the weight of the edge, is known as weighted graph. 3.2 The above graph is a weighted graph, as each edge is assigned with a number. (®) Finite graph): A graph G = (V, E) is called a finite graph if the vertex set V isa finite set. + A graph G = (V, E) is called an infinite graph if the vertex set V is an infinite set. &s d q & ey 2 b © c (Finite graph) (Infinite graph) V@jlis ea order of (vi). Tri The trivial graph is the graph Let G be a graph then the no. of vertices denoted by | mpty graph with one vertex and no edges, The empty graph is the graph with No vertices and no edges, ( When is two . comnion and this vertex is of edges in a ‘graph have exactly one vertex in “BEE two, then two edges are said to be in series. Scanned with CamScannerGari THEORY, a Example. a\ eer €2are in series whereas ey, ¢) are not in series. ‘An Acyclic is a simple graph which does not have any cycles. ic. No Joop exists in such graphs. Example : / / “Arte, Degree in a Graph In-degree In a directed graph G, the in-degree of a vertex “a” is defined as the number of edges which have “a” as the terminal vertex. The in degree of the vertex a is denoted by deg G" (a) or d” (a). Out-degree In a directed graph G, the out-degree of a vertex “a” is defined as the number of. edges which have “a” as the initial vertex. The out-degree of the vertex a is denoted by deg G (a) or d (a) Remark. (i) A vertex in a directed graph with in-degree zero is called a souree and out-degree zero is called a Sink . (ii) The direction of a loop in a directed graph has no significance. a d es & & e c In the above figure degG(a)=2, deg G* (a) =0 degG(d)=0, deg G* ()=3 degG"(c)=2, deg G*(c)=2 In above graph, vertex “a” is called a source and the vertex “d” is called a Sink. Scanned with CamScanner* SPECTRUM DISCRETE STRUCTURES The vertex V is said to be even or odd according as deg,(V) is even or odd. * in a directed or undirected graph is defined as the total ‘a vertex “a’ ne orate ne of a vertex a is denoted by deg G (a) or number of edges incident with a. The degr da). Thus in a direct graph deg G (a) = deg G" (a) + deg G (a). For calculating degree of a a vertex in a general graph, a loop is counted twice. For example : In the following graph directed or undirected we have _ & (Directed (Undirected In directed graph In undirected graph deg GQ) = deg G'(x) + deg G(x) * degG(a)=2+2=4 deg G(a) = 4 deg G (b) +2=3 deg G(b) =3 degG(c) =2+3=5 deg G(c) = 5 degG(d) =3+1=4 deg G(a) = 4 _abdeinatag Po’ vex x : ertex whose degree in a graph is one is called pendent vertex. For example :- In the following graph . a : 6 ¢ The vertices a and c are pendent vertices, since deg G (a) = | and deg G(c)=1 Scanned with CamScannerGRAPH THEORY 7 ph : A graph in which all the vertices are of same degree is called a regular graph. TREE Regaien Oa A graph in which all the vertices have the same degree equal to &, is called a k-Regular graph. For example : 4 f ey ¢ a a a ) q | | | Bk) b b G a (1-Regular graph) (2-Regular graph) —_(3-Regular graph) (4-Regular graph) Next, we have a very important, but simple result on graph theory known as the first theorem on graph theory. irst Theorem on Graph Theory (Handshaking Theorem) The sum of the degrees of all the vertices in a graph G is equal to twice the number of edges in G. (Pbi.U., B.C.A., 2006; P.T.U. B.C.A.-I, 2004, 2007) Proof : Let e be any edge in graph between two vertices V, and V2. Now, when we count degree of all vertices e is counted twice, once in degree of V; and again in degree of V2. Also, if V; and V2 are identical, again e will be counted twice. (eis self-loop) Hence every edge is counted twice. So total degree is twice number of edges. or D degev,) =2€ im ‘Theorem 2; Prove that in a graph the number of vertices of odd degree is even. (PT.U. B.C.A-l, 2007) Proof.Let U1, Va. Ux be n-vertices and e}, 25 «um ee be e-edges in the graph G. Then by first theorem on graph theory n Xa W)=2€ wD) i=l Now, divide the sum on the L.H.S of (1) in two parts (@ One part contains the sum of degrec of vertices which have even degree. (ii) Second part contains the sum of the vertices which have odd degree. Scanned with CamScannerThen equation (1) can be written as Yaw+ Yd wn =2e even oad iso. Sod (v) is als (2) is an even number. even Since the R.H.S of even. implies that Dod (vs) is odd ‘ie. the sum of the degree of vertices having odd degr The number of vertices having odd degree must be even. mum degree of any vertex in a simple graph having , is even Prove that the maxi ve Proof. Since. in a simple graph, there are vertex can be connected to the remaining n— ‘ices is no parallel edges and no loops. Therefore z t vertices at the most by (”—1) edges. Hence, the maximum degree of any vertex in a simple graph having 7 vertices is n-, (ileorem4y show that the maximum number of edges ina simple graph with n venice, ) 2° 2 Front Let 0}, Uoj.ces Up be n-vertices and €}, €2, ....-4 €e be e-edges in a simple graphG. By First theorem on graph theory n Yd @)=2¢e Al) Also, we know that Ina simple graph, the maximum degree of any vertex with n vertices is n—1 ices is n— “+ Sum of maximum degrees of n vertices =(n— 1) + (n —1) ¢ ~ 1+. tems . =n(n-1 *. from (1), we have J 2e=n(n-1) Scanned with CamScannerpap THEORY 9 gol Since every vertex in a complete graph is joined with every other vertex through ne edge The degree of every vertex in a complete graph of n vertices is n-1. “. If e be the total number of edges in G. Then by first theorem on graph theory, we have n Ya w) =26 i= n(n-l) =2e [2d @) = 2-1 for 1s isn] n(n 1) > eee 2 1 . Total number of edges in G = ma) ILLUSTRATIVE EXAMPLES Example 1. If V= {a, b, c,d} and E= { (a, 6), (a, d), (b, ©), (b, d), (c, €)} be the vertex set and edge set of a graph G. Draw the directed graph G = (V, E). Is it a simple graph? Sol. The directed graph G = (V, E) is as shown below :~ a b Since it contain a loop. Therefore it is not a simple graph. Example 2. Find the degree of each vertices of the following graph. & pine Wena oe v2 & Us Also verify first theorem on graph theory. Sol. Here d (v1) = 3, d (v2) =3, d (vs)=3, d(vs)=4,d (v3) = | By first theorem of graph theory 1 Da @)=20 ‘ i=l Scanned with CamScannerSPECTRUM DISCRETE STRUCTURE 10 —... GR where ¢ is the number of edges and mis the number of vertices in the graph. Here » =5 and e=7 Also d(v:)+d (v2) +d (03) Thus first theorem on graph theory is verified. ‘A graph G has 21 edges, 3 vertices of degree 4 and all other vertices are gy ytd atd (us) =343+3 444 1=14=2(1)=2e Example 3. degree 3. Find the number of vertices in G. ae Sol. Let n be the number of vertices in G. So. Gi According of first theorem on graph theory. n Yd (v)=2¢, where ¢ is the no. of edges. Un be the remainin Let v}, U2, U3 be the vertices of degree 4 and U4, Us, « vertices of degree 3 3 n : Law)+ Yd w=220 i=l k=4 3x4 + (n-3)x3_ = 42 12+3n-9 =42 3n =39 n =13 Number of vertices in G be 13. Example 4. Prove that there does not exist a graph with 5 vertices with degree equal to! 3,4, 2, 3 respectively. Sol. Here n= 5, Let e be the number of edges in the graph By first Theorem on graph theory 4 , ' Yaw)=2e 1 = 143444243 =2e = 13 =2e 7 F 13 + Which is not possible Hence there does not exist a graph with 5S vertices of given degrees. Example 5. Is there a simple graph G with six vertices of degree 1, 1,3, 4,6,72 Sol. Here number of vertices in the graph, n= 6 Scanned with CamScannerURES =~ u pari THEORY We know that Maximum degree of any vertices in a simple graph = -1 = 6-1 = 5 e But G has a vertices of degree 7, which is not possible in a simple graph. Hence there is no simple graph G of six vertices having the given degrees. e of ind k, if'a k-regular graph with 8 vertices has 12 edges. Also draw k-regular we know that a graph G will be a k-regular graph if the degree of all the vertices in G are same and equal to k. ‘Also, number of vertices, = 8 number of edges, e = 12 «: By the first theorem on graph theory, we have n ning Ya w=2e i=l 8 De =202) i=l = 8k=24 > k= 3 so graph is 3-regular graph and the 3-regular graph is a h g f ol, b d e ¢ (3-Regular graph) Let G =(V, E) and G’ = (V', E’) be two graphs. Then G is isomorphic to G’ written as GG’ if there exists a bijection f, from V onto V’ suclf that (0; vj) GE, if and only if (f(v),f (vj) EE’. In other words, two graphs are isomo1 pnic if there exists a one-one correspondence between their vertices and edges such that incidence relationship is preserved. Remark. (a) Two graphs which are isomorphic will have (i same number of vertices (ii) same number of edges (iii) an equal number vertices with given degrees (b) The converse of (a) need not be true. j Scanned with CamScanner22 = & or tae i ic to each other (a) The following two graphs are isomorphic oh a % 3G) 1 * va 7 v) Suber ey 23 ee , ; 6) ~) % ee veD: ( wae vs Nhe! Because J a mapping wi _f_, vj fori=1,2,3,45 o and ¢, Le ifor i= 1, 2.3.45 phic even though they have the s: hs may be non-isomor (b) The two grap! y given degrees. umber of vertices and edges and an equal number of vertices of (G) v (i) Gi), If the graph G are the to be isomorphic to graph G’, then the vertex u1 m corresponds to v), because there is no other vertex of degree 3 in G’. Also in G' ther only one pendent vertex v2 adjacent to v; , while in G there are two pendent vertice: and 1 adjacent to 1. Hence G#G’. __ Given any graph G, obtain a new graph by dividing an edge of G with additi vertices. ‘ & eg. @ @® (© co1 e - J] 2 de © (a) and (6) Homeomorphic obtained from (c). Scanned with CamScanner13 ‘Gear Tugony Sub-Graphs =e (P.T.U. B.C.A--I, 2005) Let G and H be two graphs with vertex sets V(H), V(G) and edge sets E(H) and —E(G) respectively such that V(H) c V(G) and E (H) ¢ E(G), then we call H as a Subgraph of G (or G as a supergraph of H). If V(H) c V(G) and E(H) E(G), then H is a Proper subgraph of G and if V(H) = V(G) and E (H) c (G) then we say that H is a spanning subgraph of G. In other words, a graph H is said to be a subgraph of G if all the vertices and all the edges of H are in G, and each edge of H has the same end vertices in H as in G. For example. In the following examples, H is a subgraph of G. @ ® (9) Fall ubgraphy a Suppose H(V’, E') be a subgraph of G(V, E). H is called full subgraph of G if E contains all the edges of E whose end points lie in V’. It is called subgraph of G generated by V’. ae G-V is a subgraph of G obtained by deleting the vertex V from vertex set V(G) and deleting all the edges in E(G) which are incident on V. Cuverts A vertex V is called a cut vertex for G if G-V is disconnected. Scanned with CamScannerSPECTRUM DISCRETE STRUCTY, 14 Example. Let G be'the graph find G-A, G-B, G-C GRA A B S D E F Sol. (a) (b) (c) —e: eis an edge in G. G-eis the graph obtained by simply deleting ¢ from edge set of G. Example. Let G be graph. catchy A e Find (a) G- {A,B} (8).G - {B, C} (c)G~ {B,D} (d) G- {C, D} “A “IT Wa “7 cb c D c dp. Oc D G-{A,B) G- {B,C} G- {B,D} G-{CD} ° | Remarks (i) Every graph is its own subgraph (ii) The null graph obtained from G by deleting all the edges of G is a subgraph of ( Example 7. Which of the following pair of graphs are isomorphic ? Scanned with CamScannerGrarH THEORY. 15 (a) (b) 7X LAW i || ) a () +. (h) Sol. The graphs (a) and (e) ; (b) and (hi) ; and (g) and (d) are isomorphic. Since there a one-one correspondence between the vertex and the edge set preserving, incidence relation. | @U of two graphs : Let G, = (V(Gi), E(G,)) and. 12 = (V(G2), (G2)) be two graphs. Then their union is denoted by G; UGz, is a graph Gy U Gp = (V(Gi, U G2), E(Gi, UG2)) such that V(G;, UG,) = V(Gi) U V(G2) and E(GiU Gz) = E(G,) U E (G2) In other words, union of two graphs is a graph whose vertex set is the union of the vertex sets of the two graphs and edge set is the union of the edge sets of the two graphs. For example. GCG) (G.) (G,UG.) w Scanned with CamScannerSPECTRUM DISCRETE STRUCTUR, 1s Let Gi= (W(G,), E(G2)) and Gr = (ViG, is YY h E(G2)) te two graphs. Then their intersection is denoted by G NG», is a grap! 2) GyNG» = (VGING:), E(GiNG:)) such that. V(GiNG2) = V(Gi) N V(G2) E(G, M Gx) = E (Gi) NE (Go) i i vhs is a graph whose vertex set is 1 ther words, intersection of two grapl ; ; ec of the vertex sets of the two graphs and edge set is the intersection of edge sets of the two graphs. For example. vy V5 , ey 4. Ge e (SG, 5 — (GiNG2) a Ys vs %y ph : The compliment of a graph G is denoted by ( and is defined as the simple graph with the vertex set same as the vertex set of G togethi with the edge set satisfying the property that there is an edge between two vertices in G when there is no edge between these vertices in G. For example Ne 7 = © ~ © 3 v. Vy [Note ir the degree of a vertex v in a simple graph G having n vertices is k. The legree of v in G is n-K-l. What is total number of edges in k,, Justify your answer ? the complete graph on n vertices Sol. We know number of vertices in k, =n also in complete graph there is an edge between every two vertices. So we have to make pairs of n vertices for this number of ways = ¢(n, 2) a n(n-1) (n—2)12! 2 number of edges in complete graph = “(= 1) Scanned with CamScanner Ble ctGraru THEORY 1” (Example 9! Can a graph with seven vertices be isomorphic to its complement ? Justify. (B.C.A. I Sept. 2005) Sol. Let G be the given graph and G is complement of G. We know, if an edge e € G thene ¢ G. So total number of edges in G and G = Maximum number of possible edges in complete graph. Here we have number of vertices = 7 10- Using 7 vertices max. number of edge = om =21 So number of edges in G and G =21 which means number of edges in G # number of edges in G [+ 21 is odd] So G and G cannot be isomorphic. Example 10. Is there a graph with 8 vertices of degree 2, 2, 3, 6 5, 7, 8.4 justify your answ (B.C.A--II, April 2007) Sol. Total degree of all the vertices =2+2+3+6+5+7+8+4=37 We know total degree = 2 | E| where | E |= number of edges 37=2\E] = w= which is not possible. Hence given graph does not exists. EXERCISE 1 (a) 1. Draw all simple graphs of one, two and three vertices. 2, Draw graphs representing problems of (a) Two houses and three utilities (8) Three houses and three utilities (6) Four houses and four utilities, say water, gas, electricity, and telephone. 3. Draw graphs of the following chemical compounds (a) CHs (6) C2 He (€) Co He 4. Differentiate between directed graph and undirected graphs. 5. How many nodes are necessary to construct a 2-regular graph with exactly 6 edges? 6. Is it possible to construct a graph with 12 edges such that two of its vertices have degree 3 and remaining vertices have degree 4 ? Scanned with CamScanner18 SPECTRUM DISCRETE STRUCTURES 7. Find the degree of each vertices in the following graph : 8. Does there exist a graph with 6 vertices with degree equal to 3, 2,4, 1, 3,2 respectively. 9, Find k, if a k-regular graph with 7 vertices has 14 edges. Also draw the k-regular graph. 10. Find n, ifa complete graph having n vertices has 15 edges. 11. Draw 3-regular graph with eight vertices. 12. Draw 3-regular graphs with nine vertices. 13. Which of the following pair of graphs are isomorphic ? 14. Find the union and intersection of the following graphs. v SS ¥, Vs Scanned with CamScannerGRAPH THEORY, 16. 17. qi) . Va y, vy and . ve Ns vy v Find the compliment of the following graphs. @ (6) vs Vv, () Va Vs Let G be a complete graph of n vertices. Find the compliment of G. (ii) Let G = (V, E) be a loop free undirected graph, where V = U1, U2y Viren» Uo}. If deg (v1) = 2, deg (v2) = 3, deg (vs) = 3, deg (04) = 5, deg (vs) = 1, deg (v6) = 2, deg (v2) = 5, deg (Xs) = 2, deg (vs) = 3, deg (v10) = 2. Determine the deg (¥) in the compliment G, for all 1G'st S(a)= uy, fQ) = ty, f(C) = 3, f(a) = Uy, Fe) = Us The adjacency matrix for G for a, b, c, d,e and adjacency matrix for G’ for the ordering a> Wy, b> uy, Crus, d> uy,e>Us is o-r es conroe ono Horoco o-oo] G and G' are isomorphic. Example 9, Draw the Diagraph with given matrix as adjacency matrix. 0 0 1 | ool 1 0 oto 1 1 0 Sol. Let vertices are a, b, c, d then diagraph is shown below ra b Scanned with CamScanner ISGRAPH THEORY 35 EXERCISE 1 (b) 1. For the graph find how many paths are from b tof 2. Let G=(V, E) be undirected graph. a b e I e d g h Find how many paths are there in G from a to h ? How many of these have length 5? 3. Let G=(V, E) be undirected graph, Define a relation R on V by a R 6 If there is a path in G from a to b. Prove that R is an equivalence relation. 4, Find the number of connected graphs with four vertices and draw them, 5. (i) Which of the following multigraphs are connected ? (if) Which are cycle free ? (it) Which are simple graphs ? D @ Op ©) 6. A graph has adjacency matrix 00 1 0 _jo 0 0 1 M=Jo 1 0 0 oo1 1 Is the graph connected ? Scanned with CamScanner36 SPECTRUM DISCRETE STRUCTURES 7. Write adjacency matrix of multigraph ‘ Xx ANSWERS UBS VIS 5. The graph (c) is connected, N; No Graph is cycle free. (c)is simple graphs. a 6. No 0 13 2 1 1. o414 See eee Ore 21 1 °0 eee (P.T.U. B.C.A.-I 2007) Let G be any graph. If vertex set V can be Partitioned into two disjoint subsets A and B such that every edge in G joins a vertex in A with a vertex in B, then graph is said to be Bipartite graph. Example: a 6 c ] e Fig. Show bipartite graph of 5 vertices, Scanned with CamScannerGrarH THEORY 37 Bipartite graph is said to be complete if every vertex in A is joined to every vertex in B. If is denote by k,,,,- Where m, » are number of vertices insets A and B respectively. Example : Draw 3 5 ka A Planar graph is a graph drawn in the plane in such a way that no two edges intersect (cross) each other. A Planar graph is a graph which is isomorphic to a plane graph i-e., it can be redrawn as a plane graph. A graph which is not a planar graph is called non-planar graph. (i) The complete graph with four vertices K, is usually drawn with crossing edges see fig (a). But it can also be drawn with non-crossing edges see fig (b) ~~ Fig. (a) Oe Hence Ky, is a planar graph. (ii) A complete graph of five vertices is non-planar i.e., Ks is non-planar. fH @ Fig (a) Fig (6) Scanned with CamScanner38 SPECTRUM DISCRETE STRUCTURES plane without 1g ed gey Since the graph shown in fig. (a) cannot be «! see fig. (b). Hence Ks is non-planar graph. _Resiow: A plane graph partitions the plane into sev eral led faces. Each region is depicted by the set of edges. = The boundary of the region R of graph G is cycle if the boundary of R contains no eut edges of G. Ze., contain no edge such that on removing any edge in Rit will not be a closed circuit. : If G be graph boundary of g with cut edges counting twice is defined as the degree ¢ wal results na disconnected regions. These regions are calle and g be its face, then the number of edges in the of face g. +: Cut edge in a graph is an edge whose re graph. For example. Consider the following plane graph Various regions are shown by R,, Ro, Rs, Ra, Rs Here deg (Ri) = 3, deg (Ro) = 3, deg (Rs) = 5, deg (Ry) = 4, deg (Rs) = 3 Let G = (V, E) be a connected planar graph and let R be the nui i i imber of re; defined by any planar depiction of G. Then oe R=|El-|V|+2 Proof. We prove the result by induction let k be the number of regions determined by G We first show that the result is true for k= 1 . A tree determine the above region for example tree No. of vertices = 4, No. of edges = 3. Also from the formula, we have I=|E{-|V[+2>|El=|V|-1 ie., No. of edges = No. of vertices ~1, which is always true for a tree. Scanned with CamScanner(GRAPH THEORY. 39 (GRAPH THEORY The result is true for k Let us assume that the result is true for all k > 1. Let G be a connected plane graph determining (+1) regions, Remove an edge which is common to the boundary of two regions. We obtain a graph G’ having k-regions. Let |V', |E'|, R’ denote respectively the number of vertices number of edges and regions of G’, then R'=|E}-|V'1+2 sl) Also, we have |V']=IVL IET=IE|-1,R IE|-[Mi+2 =IE'|+1-[V'1+2 = ((E'|~|V'}+2) +1 =R'+1 =R result is true for +1 + of (1)] result follows by induction for all connected graphs. ILLUSTRATIVE EXAMPLES Example 1. Verify Euler's formula for the following graphs. a b 2 ane ase (ii) Sol, (i) In fig. () [V|=6, |E]= 10, R=6 By Euler’s formula, R=|E|-[V| +2 i.e, 6= 10—6 + 2, which is true (ii) In fig. (i) [V[=6, |E|=8, R=4 By Euler’s formula, R = |E|~ |V| +2 ie, 5=9-6 + 2, which is true Example 2, Determine the number of regions defined by a connected planar graph with 4 Nodes and 8 edges, Draw such a graph. Sol, Here [V|=4,|E|=8 Scanned with CamScannerSPECTRUM DISCRETE STRUCTUR», Gre By Euler’s formula. nat R=[E|-[Vi+2 = 8-442 “6 a ‘ «The given connected graph has 6 regions. The required graph is RMR, Rs NR Theorem 2. Let G = (V, E) be a simple, connected Planar graph with more than one edge, then the following inequalities holds. (i) JE | 2 3R (i) [E| $ 3 |V|-6 (iii) There is a vertex v of G such that deg (v) < 5. Proof. (i) Since G has more then one edge «. | E|>1 IfG defines only one region, then R= 1 [E|>122|E|>2>3>2|E|>3R_ holds. So, let R > 1, then each region is bounded by atleast 3-edges. But each edge ina planar graph touches almost 3 region, Thus we have 2 |E| > 3R (ii) By part (), we have ] 2|E/23R 2 oO RSSIEL Adding | V | both sides 2 IVI+RSIVI+ > 1E| .l) By Euler's formula R=|E|-|V|+2 IV|+R=|B]+2 =) From (1) and (2) we have 2 IE+2SIVI+ 218) > 3|E|+6<3|v|+2)5| > E|<3|V|-6 (it) Let each vertex of G of degree > 6. Scanned with CamScannerGrapH THEORY at 2aae_—— tH ‘Also by first theorem on graph theory Ydeg@)=2/E] vev = 6|VI<2/E| (+ LH.S 2 6 |V| and R.H.S =2/E!] | 1 5 MESS .@) Beane) Also, By part (i) R$ 5 |E| (4) ‘Adding (3) and (4) went 1 2 V[+RS=|E|+=|E|=|E IVI Pv eabirvcl ied ba es IVI+RS/E| (5) But by Euler's formula, we have - IMI+R =|E| +2 -(6) :. from (5) and (6) we have IE|+2<|E| > 20, not possible Our supposition is wrong Each vertex of G cannot have a degree > 6 Hence, there exist a vertex of G with degree < 5. = Example 3. Prove that the graph Ks is not planar, Sol. Number of vertices in Ks=5 g Number of edges in Ks=|E|=10 for planar graph |E|<3|V|-6 e a = 1053x5-6 > 10<9, which is contradiction. Ks is not planar graph. ? (P.T.U. B.C.A.-1 2007) Suppose G be a simple graph with n vertices, we are to paint all its vertices such ‘hat no two adjacent vertices have the same colour. Chromatic Number : The minimum number of colours needed to paint all the vertices of the graph Such that no two adjacent vertices have the same colour is called chromatic number of Gand denoted by C(G). 2 Scanned with CamScanner -SPECTRUM DISCRETE STRUCTU, 42 ile. For example. ea UZ i The above graphs are 3-chromatic, 2-chromic and 3-chromatic receptively. (Remark! complete graph of n vertices is n - chromatic, as all its vertices are: adjacen Example, Find the chromatic number for the following graphs. (a) (b) (c) Sol. Chromatic number of graph G is the minimum number of colour required to p all the vertices of the graph so that no two adjacent vertices have the same colour The chromatic colour for the graph (a) is 3 as shown below Blue DP Yellow The chromatic number for the graph (b) is 3 as shown below . a Green Green 7 Blue Green i, The chromatic number for the graph (¢) is 2 as shown below Blue ed Blue | f “ Green Blue » Green Blu Scanned with CamScannerGrapn THEORY ‘Proper Colouring 7 A colouring is proper if any two adjacent vertices w and v have different colours otherwise itis called improper colouring. Example, The chromatic number of complete bipartite graph k,, , mand n are +ve —., integers is two. Sol. The number of colour needed does not depend upon m and n. Only two colours are needed colour the set of m vertices with one colour and the set of n vertices with a second colour. Edges connect only a'vertex from the set of m vertices and a vertex from the set of'n vertices, no two adjacent vertices have the same colour. Prove that following statements are equivalent for a graph G. (@) Gis 2-cblorable. (b) Gis bipartite (c) Gis contains no odd cycle, Proof: a >. If G be 2-colorable then graph G has two sets of vertices V; and V2 with different colours say red and blue. Asno vertices of V, and V2 are adjacent {Vi, V2} is partition of G. Gis bipartite. bec Let G be bipartite and {V,, V2} be partition of vertices of G. Leta vertex x € V; and cycle begins at x. Let ined to vertex y-€ V2 and then to a vertex in V, and so on. When cycle gets completed.e. It returns to x in V; then it will be of even length (+ Gis bipartite) G has no odd eycle. eta Let each eycle in G be even let some vertex be coloured while then its adjacent vertex will have different colour black and its adjacent vertex will have colour white because every cycle has even length. sequence of vertices of even cycle is WBW ; WBWBW so on. Only two colours are used to colour the graph. “Gis 2 colourable. Four Colour Theoreni?1fG is any planar graph then C(G) <4. Scanned with CamScanner44 SPECTRUM DISCRETE STRUCTU, If is planar graph then GR Ex get (Clea So! ‘. oth Induction : Let us assume that all planar graphs with # ~ I vertices have.) chromatic number of 5 or less. Let G be a planar graph with n vertices. Blue C(G) <5. Proof : Basis : A graph with one vertex has chromatic number of one. Ex So! cor Red a vertex V with degree (V) < 5. * Let G-V be the planar obtained by deleting V and all edges that connect V to at ¢ vertices in G. Now by the Induction Hypothesis G-V has a 5-colouring. Let us assume that wer the colours red, white, blue, green and yellow. (i) Ifdeg(V) <5 then we can produce a 5 colouring of G by selecting a colour not used in colouring the vertices that are connected to V with an edge in G. (i) If deg(V) = 5, then we apply same technique if the five vertices that SE adjacent to V are not coloured differently. Now we have possible condition is that Vj, V2, V3, Vs, Vs are all connected to V! dis an edge and they are all coloured differently. Let us assume that they are red colout Me white, blue, yellow, and green. IfV, and V3 are not connected to one another using only blue and red vertices in! V. If we take all paths that begin at V; and go through only blue and red vertices. TH alr. we can not reach V3. When we exchange the colours of the vertices in these p#' rep including Vi, we still have a $ colouring of G-V. As V; is now red, we can colout! ue. : Now we assume that V, is connected to V; employing only blue and red vertices Then a path from V; to V3 by employing Blue and red vertices followed by! ver edges (Vs, V) and (V,V,) complete a circuit that either encloses V3 or encloses Vand! No path from V, to V, exist employing only green and white vertices, We’ “ then repeat the same process as in the previous paragraph with V> and Vs, which ! allow us to colour V-green. Hence G is 5 colourable, Scanned with CamScanner