Graph Theory and Combinatorics PDF

Graph Theory and Combinatorics Programs Offered n e...

Graph Theory and Combinatorics Programs Offered n e i Post Graduate Programmes (PG) l Master of Business Administration Graph Theory Master of Computer Applications n Master of Commerce (Financial Management / Financial Technology) O Master of Arts (Journalism and Mass Communication) Master of Arts (Economics) Master of Arts (Public Policy and Governance) and Combinatorics Master of Social Work Master of Arts (English) Master of Science (Information Technology) (ODL) Master of Science (Environmental Science) (ODL) i ty Diploma Programmes Post Graduate Diploma (Management) r s e Post Graduate Diploma (Logistics) Post Graduate Diploma (Machine Learning and Artificial Intelligence) Post Graduate Diploma (Data Science) i v Undergraduate Programmes (UG) Bachelor of Business Administration Bachelor of Computer Applications Bachelor of Commerce Bachelor of Arts (Journalism and Mass Communication) U n English / Sociology) Bachelor of Social Work y Bachelor of Arts (General / Political Science / Economics / it Bachelor of Science (Information Technology) (ODL) A m c )DIRECTORATE OF Product code ( DISTANCE & ONLINE EDUCATION Amity Helpline: 1800-102-3434 (Toll-free), 0120-4614200 AMITY For Distance Learning Programmes: [email protected] | www.amity.edu/addoe DIRECTORATE OF For Online Learning programmes: [email protected] | www.amityonline.com DISTANCE & ONLINE EDUCATION  e in nl O ty Graph Theory and Combinatorics r si ve ni U ity m )A (c  e in © Amity University Press All Rights Reserved nl No parts of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise without the prior permission of the publisher. O SLM & Learning Resources Committee ty Chairman : Prof. Abhinash Kumar Members : Dr. Divya Bansal si Dr. Coral J Barboza Dr. Apurva Chauhan Dr. Monica Rose r ve Dr. Winnie Sharma Member Secretary : Ms. Rita Naskar ni U ity m )A (c Published by Amity University Press for exclusive use of Amity Directorate of Distance and Online Education, Amity University, Noida-201313  Contents e Page No. Unit- I: Introduction to Graph Theory 01 in Unit- II: Operations on Graph 21 nl Unit- III 45 O Unit- IV 62 ty Unit- V: Directed graphs 87 Unit-VI: Planar and Dual Graphs si r 104 ve Unit- VII 121 ni Unit- VIII 139 U ity m )A (c (c )A m ity U ni ve r si ty O nl in e  Graph theory and Combinatorics 1 Module - I Notes e Unit- I: Introduction to Graph Theory in Introduction: nl In the field of mathematics, graph theory plays a vital role in engineering and computer science. It deals with the study of graphs that concerns with the relationship among vertices and edges. It is an important subject having many more applications in computer science, information technology, biomathematics, etc. It is also used O an extensively in the circuit connections. Also, it is used to facilitate the study of algorithms like Kruskal’s algorithm, Prim’s algorithm, Dijkstra’s algorithm etc. There is a main relationship between topology and graph theory, it is applied in the different ity types of topologies like star, bridge, series, parallel and network topologies etc. The interconnected computers in the network follows from the relationship among the principles of graph theory. The characterizations of graphs are depending on their structures. Definition of a Graph: 1.1 rs A Graph is said to be a pair of vertices and edges which consisting a set of objects (V, E) where V={v1 , v2, v3,…., vn} are called vertices and E={e1, e2, e3,….,en }are ve called edges. The vertex v1 is called the initial vertex and the vertex vn is called the terminal vertex. Each edge is associated with an unordered pair of vertices. Let us see an example of the graph in the figure (1.1) ni v1 e1 v2 U e2 e1 ity v3 e3 v4 Fig (1.1) m In the above figure (1.1), there are four vertices and four edges namely V={v1, v2, v3, v4} and E={ e1, e2, e3, e4} )A Definition: 1.2 A graph having without self loop and parallel edges is said to be a simple graph. [Equivalently a graph having neither self loop nor parallel edges is said to be a simple graph]. Let us see an example of simple graph (c Amity Directorate of Distance & Online Education  2 Graph theory and Combinatorics Notes e in nl O Fig (1.2) The above Fig (1.2) shows the graph is a simple graph which has no self loop and paral- lel edges. ity Definition: 1.3 rs Any two edges having the same initial vertex and the same end vertex is said to be Parallel edges. An edge having the same vertex as an initial vertex and end vertex then it is said be a Self loop. The below example having the graph with self loop and parallel edges. ve e2 v1 e1 v2 v3 e3 e2 ni e4 e3 v4 v3 v2 U e4 e1 Fig (1.3) ity In the Fig (1.3) the graph consists of five vertices and 7 edges. v4 1. In this graph V= {v1, v2, v3, v4, v5} and E= {e1, e2, e3, e4, e5, e6, e7}. Here the two edges 3 and 4 are parallel edges , the edges 3 and 4 having the same initial vertex ‘c’ and end vertex ‘d’. m 2. An edge 7 having same initial and end vertex namely ‘e’ and it is said be a self loop. )A Definition: 1.4 A graph with finite number of vertices is called finite graph otherwise is called infinite graph. (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 3 Notes e in nl Fig (1.4a) Fig (1.4b) O The above figure 1.4a is an example of finite graph which has three vertices and three edges and the figure 1.4b is an example of infinite graph which has an infinite number of vertices and infinite number of vertices. ity Definition: 1.5 Let the two vertices are said to be adjacent if they are connecting by an edge. If a vertex is incident to an edge then the vertex is one of the two vertices that connects rs the edges.In the above figure (1.1) the vertex ‘a’ is adjacent to the vertex ‘b’ and also is adjacent to ‘d’. ve Definition: 1.6 The degree of the vertex is said to be number of edges connecting in it. Let us see the below example e2 ni v1 e1 v2 v3 e2 U e3 e4 e3 v4 v3 ity e4 d(v1) = 2 d(v2) = 2 m d(v3) = 4 d(v4) = 3 )A d(v5) = 3 Note: In the self loop the degree of the edges must be counted twice. (c The number of edges in the graph must be twice the sum of the degree of the vertices. Amity Directorate of Distance & Online Education  4 Graph theory and Combinatorics Theorem: 1.8 (Handshaking Lemma) Notes e In any graph G(V,E) the sum of degrees of vertex is twice the number of edges. (i.e.) in n ∑ d (V ) = 2e i =1 i nl Proof: O Let us consider the graph G with ‘V’ vertices and ‘E’ edges. Now we can prove this theorem with a clear example. For that we consider the above graph Fig (1.3) The number of vertices in the graph is 5 and the number of edges in the graph is 7 ity d(v1) = 2, d(v2) = 2, d(v3) = 4, d(v4) = 3, d(v5) = 3 d(v1) + d(v2) + d(v3) +4, d(v4) +d(v5) = 2+2+4+3+3 =14 = twice the number of edges rs n Therefore ∑ d (V ) = 2e i =1 i ve Definition: 1.9 1. A vertex with degree one is called pendent vertex. ni 2. A vertex with degree zero is called isolated vertex. 3. A graph without any edges is called null graph U a b a b Fig (1.5a) Fig (1.5b) ity m Fig (1.5c) )A Fig (1.5a) represents the pendent vertex with degree one. Fig (1.5b) represents the isolated vertex with degree zero. (c Fig (1.5c) represents the null graph without any edges. Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 5 Theorem: 1.10 Notes e Prove that the number of vertices of odd degree in a graph is always even. in Proof: Let G be graph with ‘n’ vertices and ‘e’ edges. nl Let us split the vertices into two of odd degree and an even degree of vertices Let ‘k’ be the odd degree vertices and ‘j’ be the even degree vertices O n n n ∑ d (Vi ) =∑ d (Vk ) + ∑ d (V j ) →(1) =i 1 =k 1 =j 1 We know that by theorem (1.8) the sum of number of all the edges is twice the sum of ity degree of all the vertices. n That is ∑ d (V ) = 2e i =1 i rs n n 2e = ∑ d (Vk ) + ∑ d (V j ) →(2) =k 1 =j 1 ve Therefore the R.H.S of (2) is an even number Each d(vj)is even (since the sum of an even numbers is an even number ) ni Therefore eqn (2) is an even number The total number of terms in the sum must be even U Hence the number of vertices of odd degree in a graph is always even. Definition: 1.11 ity 1. In a graph a walk is an alternating sequence of vertices and edges and the element which are incident, that starts and ends with a same vertex 1 e a m 5 2 )A d b 4 c 3 (c Fig (1.6) Amity Directorate of Distance & Online Education  6 Graph theory and Combinatorics In the above fig (1.6) 1a2b3c4d5e1 is a walk. Notes e 2. A trail is a walk without repeating any edges. in 3. A path is a walk without repeating any vertices. In the above Fig (1.6) 1a2b3c4d4e is a path. nl Definition: 1.12 1. A walk is said to be open if the initial and terminal vertices are different. O 2. A walk is said to be closed if the initial and terminal vertices are same. 1 ity 5 2 4 rs 3 ve Fig (1.7) In the above figure (1.7) 1 → 2 → 3 → 4 → 1 → 5 is an open walk. ni In the above figure (1.6) 1a2b3c4d5e1 is a closed walk Definition: 1.13 U In a graph a path is said to be a finite or infinite sequence of edges which joins a sequence of vertices and the vertices are all distinct. a b ity c m )A e d Fig (1.8) (c The above figure (1.8) shows that a,b,c,d,e is a path Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 7 Notes e Definition: 1.14 in A graph is said to be a circuit such that no one edge is repeated and it is also closed 2 nl 1 4 O 3 ity 6 5 Fig (1.9) Remark: rs In the above figure (1.9) 1 → 2 → 4 → 3 → 6 → 5 → 3 → 1 is a circuit. ve In a circuit vertex can be repeated and edge not repeated. In a cycle the vertex and edge are not repeated. ni Definition: 1.15 U A graph is said to be connected if every pair of vertices in the graph is connected. [Equivalently, there is a path between every pair of vertex and should be some path traverse. It is also called the connectivity of a graph]. Otherwise it is said to be disconnected. ity 2 a b 1 4 7 3 e m 6 5 )A d c Fig (1.10a) Fig (1.10b) In the above figure (1.10a) represents the graph is connected. (c In the above figure (1.10b) represents the graph is disconnected. Amity Directorate of Distance & Online Education  8 Graph theory and Combinatorics Definition: 1.16 Notes e A directed graph is a graph which has a set of vertices connected by the edges and the edges have a direction with them. The below figure represents the directed graph in nl O Fig (1.11) ity Definition: 1.17 A graph ‘g’ is said to be a subgraph of a graph ‘G’, if all the vertices and all the edges of ‘g’ are in ‘G’ and each edge of ‘g’ has the same end vertices in ‘g’ as in ‘G’. a rs a 1 2 6 8 d 6 ve b 5 e 5 8 d e 7 7 4 3 3 c ni c G g U Fig (1.12) In the above figure ‘G’ is a graph and ‘g’ is a subgraph of a graph ‘G’ where ‘g’ contains all the edges in the graph ‘G’ ity Note: 1. Every graph has its own subgraph 2. A subgraph of a graph ‘G’ is a subgraph of ‘G’ m 3. A single vertex in a graph ‘G’ is also a subgraph of ‘G’ 4. A single edge in ‘G’ together which its end vertices is also a subgraph of ‘G’ )A Definition: 1.18 If two or more subgraphs ‘g1’ and ‘g2’ of G are said to be edge disjoint of ‘G’, if both ‘g1’ and ‘g2’ do not have any edges in common. (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 9 Notes e in nl O Fig (1.13a) [G] Fig (1.13b) [g1] ity rs ve Fig (1.13c) [g2] ni The above figure represents the edge disjoint subgraphs Remark: U 1. Edge disjoint graphs do not have any edge in common, but they may have vertices in common 2. Subgraphs that do not have vertices in common is said to be vertex disjoint subgraphs. ity The below figure (1.14) represents the vertex disjoint subgraphs where H1 and H2 do not have any vertices in common. m )A G H1 H2 (c Fig (1.14) Amity Directorate of Distance & Online Education  10 Graph theory and Combinatorics Theorem: 1.18 Notes e Prove that a graph G is disconnected if and only if its vertes set can be partitioned into two non-empty disjoint subsets,v1, and v2 such that there exist no edge in G whose in one end vertex is in subset v1 and the other in subset v2. Proof: nl Let G be a disconnected graph and its vertex set can be partitioned into two non- empty subsets v1, and v2. Suppose that such a partition exist, To prove that G is disconnected, Consider two arbitrary vertices ‘a’ and ‘b’of ‘G’ O such that ‘a’ in v1 and ‘b’ in v2 , no path can exist between vertices ‘a’ and ‘b’, otherwise their would be at least one edge whose one end vertex would be in v1 and the other in v2. Hence if partition exist ’G’ is connected. ity Conversely, Let G be a disconnected graph. Consider a vertex ‘a’ in G. Let v1 be the set of all vertices that are joined by path vertices will form a set v2. rs to ‘a’.Since G is disconnected ‘v’ does not include all vertices of G. Then the remaining Therefore no vertices in v1 is joined to only in v2 by an edge. ve Theorem: 1.19 Prove that a graph G is (connected or disconnected) has exactly two vertices of ni odd degree, there must be a path joining two vertices. Proof: U Case (i) Let G be a connected graph with exactly two vertices of odd degree say v1 and v2. There is at least one path joining v1 and v2 because G is connected. ity Case (ii) Let G be a disconnected graph with exactly two vertices of odd degree say v1 and v2. Since G is disconnected, their must be at least two components, each of which is a m connected subgraph. If v1 and v2 are in two different components say g1 and g2 respectively Therefore the number of odd degree vertices in g1 is one and also in g2, but g1 is )A a graph which is connected. We know that, in a graph the number of odd degree is always even, which is a contradiction (c Therefore v1 and v2 must be the same component. Hence there is a path between v1 and v2. Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 11 Remark: Notes e The maximum number of edges in a simple graph with ‘n’ vertices is n(n-1)/2 in Theorem: 1.20 Prove that a simple graph that is a graph without parallel edges or self loop with ‘n’ vertices and ‘k’ components can have atmost ( n − k )( n − k + 1) edges. nl 2 Proof: O Let G be a graph with ‘n’ vertices and ‘k’ components To Prove: G has atmost (n − k )(n − k + 1) edges ity 2 Let n1, n2, n3, ……nk be the number of vertices in 1st , 2nd,…..kth components respectively. n1 +n2 +n3, +……+nk = n rs k ⇒ ∑ ni − n, ni ≥ 1 i =1 n (n − 1) i i ve The maximum number of edges in the ith component of G is 2 Therefore the maximum number of possible edges in a graph G is k ni (ni − 1) ⇒∑ ni i =1 2 → (1) (ni2 − 1)k ⇒∑ U i =1 2 k k ⇒ ∑ n −∑ (ni2 − ni ) 2 i ity =i 1 =i 1 k k Now consider i =i 1 =i 1 ∑= n n,∑ ni2= −k n (n1 +n2 +n3, +……+nk ) – (1+1+1+……+1) = n-k m (n1 -1) +(n2 -1)+(n3-1)+……+(nk -1) = n-k k ∑n )A i =(ni − 1) = n − k i =1 k ∑n i =(ni − 1) 2 =(n − k ) 2 (c i =1 Amity Directorate of Distance & Online Education  12 Graph theory and Combinatorics (n1 -1)2 +(n2 -1)2+(n3-1)2+……+(nk -1)2 + some cross terms = (n-k)2 Notes e n12 -2n1 + n22 -2n2 +1+…… +nk2 -2nk +1+ some cross terms = (n-k)2 in Then (n12 +n22 +….+ nk2) - 2(n1+n2 +…… +nk )+(1+1+1+….+1) + some cross terms = (n-k)2 nl Therefore (n12 +n22 +….+ nk2) - 2(n1+n2 +…… +nk )+k + some cross terms = (n-k)2 O k k ⇒ ∑ n − 2∑ (ni + k ) ≤ (n − k ) 2 2 i =i 1 =j 1 ity k ⇒ ∑ ni2 − 2n + k ≤ (n − k ) 2 i =1 k ⇒ ∑ ni2 ≤ (n − k ) 2 + 2n − k rs i =1 ⇒ n 2 + k 2 ( k − 2n) − ( k − 2n) ve k ⇒ ∑ ni2 ≤ n 2 + (k − 2n)(k − 1) i =1 k ⇒ ∑ ni2 = n 2 − (−2n − k )(k − 1) ni i =1 k ni (ni − 1) Eqn (1) ⇒∑ U i =1 2 1 ≤ [n 2 − (2n − k )(k − 1) − n] 2 ity 1 2 [n − 2nk + 2n + k 2 − k − n] 2 1 2 m [ n − 2n − k + k 2 + 2n − k − n] 2 k ni (ni − 1) 1 ⇒∑ )A ≤ [(n − k ) 2 + (n − k )] i =1 2 2 1 ⇒ (n − k )(n − k + 1) 2 (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 13 Notes e 1 Therefore the maximum number of edges is ⇒ (n − k )(n − k + 1) 2 in Remark: 1. A path is also called simple path or an elementary path nl 2. A path does not intersect itself. 3. A self loop can be include in a walk but not in a path. O 4. The number of edges in a path is called the length of the path Definition: 1.21 ity A disconnected graph consists of two or more subgroups. Each of the connected subgraph is called a component. Definition: 1.22 rs If some closed walk in a graph contains all the edges of the graph then the walk is called an Euler line and this is called as Euler graph ve ni U ity m )A The above diagram represents the Euler graph Definition: 1.23 (c An open walk that includes or traces or covers all the edges of a graph without retracting any edge is called an unicursal line it is also said to be an open euler line. A connected graph that has a unicursal line is called unicursal graph Amity Directorate of Distance & Online Education  14 Graph theory and Combinatorics Notes a 4 b e 6 in 1 3 5 e 7 nl c 2 d Definition: 1.24 O If two graphs G and G’ are said to be isomorphic to each other, if there is a one-to-one correspondence between the vertices and between their edges such that the incidence relationship is preserved. ity v5 a e1 v4 e3 v3 e 5 2 rs 4 e4 1 e2 c 6 3 ve b d v1 e5 v2 ni The above two graphs are isomorphic. In the above graph the vertices a,b,c,d and e correspond to v1, v2,v3,v4, and v5 respectively. The edges 1,2,3,4,5 and 6 correspond to e1, e2,e3,e4,e5 and e6 U respectively. Therefore G And G’ are isomorphism Note: Without the labels of their vertices and edges the isomorphic graphs are the same ity graph that perhaps drawn differently m )A (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 15 Remark: Notes e 1. The isomorphic graphs must have the same number of vertices and the same number of edges. in 2. An equal number of vertices with a given degree nl O ity rs ve ni U Isomorphic Graphs ity m Non-Isomorphic graphs )A Relationship among subgraphs, walks, paths, and circuits: (c Amity Directorate of Distance & Online Education  16 Graph theory and Combinatorics Notes e Any collection of Subgraphs of G edges in G in nl A non edge Walk in G retracting O sequence of edges of G ity Path in G Circuit in G Non-intersecting rs Non-intersecting ve open walk in G closed walk in G Theorem: 1.25 ni A given connected graph G is an euler graph if and only if all vertices of a graph G are of even degree U ity m Proof: Necessary condition: )A Suppose that G is an euler graph To Prove: All vertices in G are of even degree (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 17 G is an euler graph. It contains an euler line (which is a closed walk) Notes e In tracing this closed walk, we know that every time the walk meets a vertex ‘v’ it goes through two new incident on v which one we entered and with the other existed in Thus is true not only of all intermediate vertices of the walk but also of the terminal vertex because we existed and entered to the same vertex at the beginning and nl end of the walk respectively. Thus G is an euler graph, the degree of every vertex is even. O Sufficient condition: Suppose that all vertices of a graph G are of even degree. Now we construct a walk starting at an arbitrary vertex ‘v’ and passing through the edges ity of G such that non edges is repeated or more than once. We continue tracing as far as possible. Since every vertex is of even degree, we can exit from every vertex , we enter , the tracing cannot stop at any vertex ‘v’ rs Since ‘v’ is also of even degree we shall eventually reach ‘v’ when the tracing come to an end Case: (i) ve If this closed wallk ‘h’ , we just traced includes all the edges of G is an euler graph. ni Case: (ii) If ‘h does not contains all the edges ‘G’ , we remove from G all the edges in ‘h’ and obtain a subgraph ‘h’ of G formed by the remaining edges U Since both G and ‘h’ have all their vertices of even degree, the degrees of the vertices of ‘h’ are also even. ity Moreover ‘h’ must touch ‘h’ atleast at one vertex ‘a’ because G is connected. Starting from ‘a’ we can again construct a new walk in ‘h’. Since all the vertices of ‘h’ are all even degree. This walk in ‘h’ must terminate at vertex ‘a’. But this walk in ‘h’ can be combained with ‘h’ to form a new walk, which starts and ends at vertex ‘v’ and m has more edges than ‘h’. This process can be repeated until we obtain a closed walk that traverses all the edges of G. Thus G is an euler graph. )A Theorem: 1.26 In a connected graph ‘G with exactly 2k odd vertices, there exists ‘k’ edge disjoint subgraph such that they together contain all edges of ‘G’ and that each is unicursal graph (c Amity Directorate of Distance & Online Education  18 Graph theory and Combinatorics Proof: Notes e Let the odd vertices of the given graph G be named v1,v2,……vk ; w1,w2,…..wk. in In any arbitrary order, Add ‘k’ edges to G between the vertex pairs (v1,w1), (v2,w2), (v3,w3),….. (vk,wk) to form a new graph G’ Since every vertex of G’ is of even degree g” consists of all and the euler line. nl Now if we remove from the euler line the ‘k’-edges, we just added, the euler line and will be split into ‘k’ walks, each of which is a unicursal line. O The first removal will live a single unicursal line. The second removal will split that into the unicursal lines and each successive removal will split a unicursal line into two unicursal lines until there are ‘k’ edges of them. ity Definition: 1.27 A graph is said to be reach ability, if a directed graph is the pair of objects G=(V,E) where each node v in V represents a reachable marking and each edge e in E represents a tran- rs sition markings. The set of reachable markings can be infinite, even for a finite petri net. Questions: ve 1. A graph which has no self loop and no parallel edge graph is__________ a) simple b) finite ni c) infinite d) none 2. A graph is __________both its vertex set and the edge set are finite U a) simple b) finite ity c) infinite d) none 3. A digraph that has no parallel edges is________ graph a) simple m b) finite c) infinite )A d) none 4. A digraph that has atmost one directed edge between a pair of vertices is ______. a) asymmetric b) symmetric (c c) a or b Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 19 d) a and b Notes e 5. A digraph which is both simple and symmetric is___________ a) simple symmetric graph in b) simple asymmetric graph c) a or b nl d) a and b 6. A digraph which is both simple and asymmetric is____________ O a) simple symmetric graph b) simple asymmetric graph c) a or b ity d) a and b 7. A digraph is simple antisymmetric if and only if its underlying undirected graph is___________. rs a) simple b) finite c) infinite ve d) none 8. Two vertices u and v in V(G) are said to be__________ if there is an edges e in E(G) such that (e) = (u; v). ni a) adjacent b) not a adjacent c) vertex U d) number 9. Let v be a vertex in a graph G. The degree dV of the vertex v in G is the ___________of G that are incident with v. ity a) number of vertex b) number of edges c) a or b m d) a and b 10. Let G be a graph. Then (G) = min{d(v)/v V (G)} is __________ )A a) minimum degree b) maximum degree c) in degree d) out degree (c Amity Directorate of Distance & Online Education  20 Graph theory and Combinatorics Answer: Notes e 1. a 2. b in 3. a 4. b nl 5. a 6. b O 7. a 8. a 9. b ity 10. a Exercises: 1. Define Graph and give an example 2. 3. rs Explain finite and infinite graphs with a suitable example Draw a graph of your own and find the degree of that graph ve 4. Explain incidence and degree of a graph. 5. Prove that, the number of vertices of odd degree in a graph is always even. 6. Prove that, if a graph has exactly two of odd degree there must be a path joining these two vertices. ni 7. Define Isolated vertex, Pendant vertex and Null graph. 8. Draw all simple graphs of one, two, three and four vertices. U 9. Define Isomorphism and explain it by comparing two graphs. 10. Define Edge-Disjoint Subgraphs and Vertex - Disjoint Subgraphs. 11. Define Connected graphs, Disconnected graphs and Components ity Sample Questions with Answers: 1. Prove that the sum of the degrees of the vertices of any finite graph is even. m Proof: Each edge ends at two vertices. If we begin with just the vertices and no edges, every vertex has degree zero, so the sum of those degrees is zero, an even number. )A Now add edges one at a time, each of which connects one vertex to another, or connects a vertex to itself (if you allow that). Either the degree of two vertices is increased by one (for a total of two) or one vertex’s degree is increased by two. In either case, the sum of the degrees is increased by two, so the sum remains even. (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 21 2. Show that every simple fifinite graph has two vertices of the same degree. Notes e Proof: in This can be shown using the pigeon hole principle. Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2,... , n-1 other vertices. If any of the vertices is connected to n-1 vertices, then it is connected to all the others, nl so there cannot be a vertex connected to 0 others. Thus it is impossible to have a graph with n vertices where one is vertex has degree 0 and another has degree n-1. Thus the vertices can have at most n-1 different degrees, but since there are n O vertices, at least two must have the same degree. 3. Prove that a complete graph with n vertices contains n(n-1)/2 edges. Proof: ity This is easy to prove by induction. If n = 1, zero edges are required, and 1(1-1-0)/2 = 0. Assume that a complete graph with k vertices has k(k -1)/2. When we add the (k + 1)st vertex, we need to connect it to the k original vertices, requiring k additional edges. We will then have k(k -1)/2 + k = (k + 1)((k + 1) ) 1)/2 vertices, rs ve ni U ity m )A (c Amity Directorate of Distance & Online Education  22 Graph theory and Combinatorics Module - II Notes e Unit- II: Operations on Graph in Definition: 2.1 nl The union of two graphs G1=(v1, e1) and G2=(v2, e2) is another graph G3 written as G3 = G1  G2 whose vertex set V3 = V1  V2 and the edges are E3 = E1  E 2 O Definition: 2.2 The intersection of graphs G1 and G2 is a graph G4 consisting only of those vertices and edges that are in both G1 and G2 ity The ring sum of two graphs G1 and G2 (written as G1 ⊕ G 2 is a graph) consisting of the verex set v1 union v2 and edges that are either in G1 or G2 but not in both Definition: 2.3 rs If G1 and G2 are said to be commutative then G1  G2 = G2  G1 G1  G2 = G2  G1 ve G1 ⊕ G2 = G2 ⊕ G1 If G1 and G2 are edge disjoint then G1 intersection G2 is a null graph G1 ⊕ G2 = G1  G2 ni If G1 and G2 are vertex disjoint then G1 intersection G2 is empty ⇒ G1  G2 = φ U For any graph , GG = GG = G G ⊕ G = null graph ity G ⊕ g = G − g whenever g ⊆ G Definition: 2.4 m A graph G is said to have been decomposed into two subgraphs, if g1  g 2 = G g1  g 2 = a null graph )A The below diagram shows the union, intersection, and ring sum of the graphs (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 23 Notes e in nl O ity rs ve ni U ity m Theorem: 2.5 )A Prove that a connected graph G is an euler graph if and only if it can be decomposed into circuits. (c Amity Directorate of Distance & Online Education  24 Graph theory and Combinatorics Notes e in nl Proof: O Suppose graph G can be decomposed into circuits (i.e.) G is a union of edge disjoint circuits Since the degree of every vertex in a circuit is two, the degree of every vertex in G ity is even Hence G is an euler graph. Conversely, rs Coinsider a vertex v1,. There are atleast two edges incident at v1 Let one of these edges between v1 and v2 ve Since vertex v2 is also of even degree, it must have atleast another edge say between v2 and v3 Proceeding in this way, we eventually arrive at a vertex that has previously been traversed thus forming a circuit. Let us remove the circuit form G. All the vertices in ni the remaining graph must also be of even degree. From the remaining graph remove another circuit in exactly the same way as be removed the circuit from G. Continuing this process until no edges are left. U Hence a connected graph G is an euler graph if and only if it can be decomposed into circuits. ity Definition: 2.6 In an euler graph , it is an euler line is obtained when follows any closed walk from a vertex V such that one arrives at a vertex can select any edges which has not be previous traversed. Such a graph is called an arbitrarily traceable graph from the m vertex )A (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 25 Notes e in nl O Definition: 2.7 ity Hamiltonian circuit in a connected graph is defined as a closed walk that traverses every vertex of G exactly once, except starting and final vertex A circuit in a connected graph G is said to be Hamiltonian it includes every vertex of G. Hence a Hamiltonian circuit in a graph of n vertices of exactly n edges rs ve ni U Hamiltonian circuit Graph of decahedron with Hamiltonian circuits ity m Graph without Hamiltonian circuits )A Definition: 2.8 If we remove any one edge from a Hamiltonian circuit, we are left with a path. This path is called a Hamiltonian path. (c Amity Directorate of Distance & Online Education  26 Graph theory and Combinatorics Definition: 2.9 Notes e A simple graph in which there exist an edge between every pair of vertices is called a complete graph in nl O ity rs ve Theorem: 2.10 In a complete graph with ‘n’ vertices there are n-1/2 edges disjoint Hamiltonian circuits if ‘n’ is an odd number greater than or equal to 3 ni Proof: A complete graph G of ‘n’ vertices has n(n-1)/2 edges, and a Hamiltonian circuit in G consist of ‘n’ edges U Therefore the number of edge disjoint Hamiltonian circuit, when n is odd it can be shown as follows. ity The subgraph (of complete graph of ‘n’ vertices) in figure is a Hamiltonian circuit Keeping the vertices on a circle rotate the polygonal pattern clockwise by 360 360 360 n − 3 360 ,2. ,3. ,...... , degrees n −1 n −1 n −1 2 n −1 m Observe that each rotation produces a Hamiltonian circuit that has no edges in common with any of the previous one. )A Thus n-3/2 new Hamiltonian circuits, all edge disjoint from the one in figure and also edge disjoint among themselves. Hence there are n-1/2 edge disjoint Hamiltonian circuit. (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 27 Notes e in nl O ity Problem: 1 Find the 4 edge disjoint Hamiltonian cycles in K9. Solution: rs ve ni U (i) (ii) ity m )A (iii) (iv) Edge disjoint hamiltonian cycles in K9 (c Amity Directorate of Distance & Online Education  28 Graph theory and Combinatorics Dirac’s Theorem: Notes e A vertex in G be at least sufficient (but by no means necessary condition) for a simple graph G to have a Hamiltonian circuit is that the degrees of every n/2, where ‘n’ in is the number of vertices in G Proof: nl Assume that G is non-hamiltonian circuit Let G be the maximal non-hamiltonian with n≥3 n O d (v i ) ≥ , i=1 to n 2 We know that, Any complete graph is Hamiltonian. ity Therefore G cannot be complete. There exist a pair of vertices u and v in G, which are not adjacent Consider G’=G+uv by choice of G. G’ becomes Hamiltonian rs As G is non-hamiltonian. this mean that every hamiltonian cycle of G must contain the edge uv (i.e.) Removal of an edge uv from any Hamiltonian cycle of G, results in a(u–v) Hamiltonian path in G ve Let p=v1,v2,v3,…….,vn with v1 = u as original and vn =v as terminous By definition, =A {v i / uv i ∈ E (G )} ni =B {v i / v i u ∈ E (G )} Now, uv ∉ E (G ) U v ∉ A u ∉ B and v ∉ B , v ∉ A  B and | A  B |< n ⇒ vk ∈ A  B ity v1,v2,v3,…….,vk, vn,vk-1, v1 is a Hamiltonian cycle of G Which is a contradiction to the fact that G is non-hamiltonian Therefore A  B = φ m (i.e.) | A  B |= 0 Now the definition of A and B, )A |A|=dG(u) and |B|=dG(V) Therefore dG(u) +dG(V)=|A| + |B| ≤ | A  B | + | A  B | < n+0 (c dG(u) +dG(V) < n Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 29 By the hypothesis, Notes e n ⇒ dg (u ) ≥ 2 n in ⇒ dg (v) ≥ 2 ⇒ dG(u) +dG(V) ≥ n + n 2 2 nl ⇒ dG(u) +dG(V) ≥ n Which is a contradiction O Therefore our assumption is wrong Therefore G must be Hamiltonian. ity Shortest Path Problem: Let us given a weighted network (V,E,C) with vertex set V, edge set E, and the weight set C specifying weight scij for the edges (i,j) ∈E. Weare also given a starting nodes ∈V. The one-to-all shortest path problem is the problem of determining the shortest path from rs nodes to all the other nodes in the network. ve ni U Algorithms Solving the Problem ity Dijkstra’s algorithm: Solves only the problems with non-negative costs, i.e., m cij≥ 0 for all (i,j)∈E Properties of Dijkstra’s algorithm )A Many more problems than you might at first think can be cast as shortest path problems, making Dijkstra’s algorithm a powerful and general tool. For example: Dijkstra’s algorithm is applied to automatically find directions between physical (c locations, such as driving directions on websites like Map quest or Google Maps. Amity Directorate of Distance & Online Education  30 Graph theory and Combinatorics In a networking or telecommunication applications, Dijkstra’s algorithm has Notes e been used for solving the min-delay path problem (which is the shortest path problem). in It is also used for solving a variety of shortest path problems arising in plant and facility layout, robotics and transportation. Dijkstra’s algorithm solves such a problem and finds the shortest path from a nl given nodes to all other nodes in the network where node s is called a starting node or an initial node Dijkstra’s algorithm starts by assigning some initial values for the distances O from nodes and to every other node in the network. It operates in steps, where a teach step the algorithm improves the distance values. ity A teach step, the shortest distance from nodes to another node is determined. Characterizations: The algorithm characterizes each node by its state. The state of a node consists of two features (i) (ii) Distance value Status label rs ve Distance value of a node is a scalar representing an estimate of its distance from nodes. Status label is an attribute specifying whether the distance value of a node is equal to the shortest distance to node s or not. ni The status label of a node is Permanent if its distance value is equal to the shortest distance from nodes. Otherwise, the status label of a node is Temporary. U The algorithm maintains and step-by-step updates the states of the nodes. At each step one node is designated as current Algorithm Steps ity Step 1. Initial Stage As sign the zero distance value to nodes, and label it as Permanent. [The state of node s is (0,p).] m Assign to every node a distance value of ∞ and Label them as Temporary. [The state of every other node is (∞,t).]. Designate the nodes as the current node )A Step 2. Distance Value Update and Current Node Designation Update Let i be the index of the current node. (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 31 Find the set J of nodes with temporary labels that can be reached from the Notes e current node i by a link (i, j). Update the distance values of these nodes. For each j∈J, the distance valuedj of node j is updated as follows new in dj=min{dj,di+cij} where cijis the cost of link (i,j), as given in the network problem. Determine a node j that has the smallest distance valuedj among all nodes nl j ∈ J,find j such that mindj=dj∗j∈J. Change the label of node j permanent and designate this node as the current node. O Step 3. Terminal Stage If all nodes that can be reached from nodes have been permanently labeled, then stop - we are done. ity If we cannot reach any temporary labeled node from the current node, then all the temporary labels become permanent Otherwise, go to Step 2. rs Problem: 3 To find the shortest path from node 1 to all other nodes using Dijkstra’s algorithm. ve ni U Step1: Initial Stage Node 1 is designated as the current state. ity The state of node 1 is (0,p). Every other node has state (∞,t) Step: 2 m )A (c Amity Directorate of Distance & Online Education  32 Graph theory and Combinatorics Nodes 2,3, and 6 can be reached from the current node 1. Notes e Update distance values for these nodes d2= min{∞, 0 + 7} = 7 d3= min{∞, 0 + 9} = 9 d6=min{∞,0+14}=14. Now, among the nodes in 2,3, and6, node 2 has the smallest distance value. The status label of node 2 changes to permanent, so its state is (7,p), while the status of 3 and 6 remains temporary. nl Node 2 becomes the current node Step: 3 O So graph is end at the step 2 ity rs We are not done, not all nodes have been reached from node1, so we will ve repeat again step: 2 Node 2 becomes the current node Another Implementation of Step: 2 ni Nodes 3 and 4 can be reached form the current node 2. Update the distance values for theses nodes d3=min{9,7+10}=9 U d6= min{∞,7+15} = 22 Now, between the nodes 3 and 4 node 3 has the smallest distance value. ity The status label of node 3 changes to permanent, while the status of 6 remains temporary. Node 3 becomes the current node. m )A (c Amity Directorate of Distance & Online Education  Graph theory and Combinatorics 33 We are not done (Step 3 fails), so we perform another Step 2 Notes e Another Step: 2 in Node 5 can be reached from the current node 6. Update distance value for node 5. d5= min{∞,11+9} = 20 nl O ity rs Now, node 5 is the only candidate, so its status changes to permanent. Node 5 becomes the current node ve From node 5 we cannot reach any other node. Hence, node 4 gets permanently labeled Problem: 4 ni Find the shortest distance from A to H on the network below U ity Solution: m The fully labeled diagram below shows that the values, both temporary and permanent at each vertex )A (c Amity Directorate of Distance & Online Education  34 Graph theory and Combinatorics Notes e in