More from Kantharaju H D

Page 1 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Basic Definitions:, In the beginning…, Graph Theory was first introduced by Euler in 1736 through his research paper on, Konigsberg bridge problem., , Konigsberg bridge problem,  Two Islands B and D formed by the Pregel river are connected to each other to the, banks A and C with seven bridges as shown in the figure. The problem was to, “start at any of the four land areas of the city A, B , C or D, walk over each of the, seven bridges exactly once and return to the starting point? ”, , This problem can be represented by a graph. Bridges represent lines and each land, areas represents a point. This produced a graph as shown in the figure (a). Through, this figure, Euler gave the concept of ‘GRAPH’., , Figure (a)

Page 2 :
MATHEMATICS, , GRAPH THEORY, , Definition of a Graph: A graph is a pair G = (V, E), where, V = V(G) = set of vertices (Points), E = E(G) = set of edges (Lines), Example:, V = {s, u, v, w, x, y, z}, E = {(x, s), (x, v)1, (x, v)2, (x, u), (v, w), (s, v), (s, u), (s, w), (s, y), (w, y), (u, y), (u, z), (y, z)}, , Basic Definitions:, Parallel edges: Two or more edges joining a pair of vertices are called parallel edges., In the example below, ‘a’ and ‘b’ are joined by two parallel edges, , Loops, An edge that starts and ends at the same vertex is called a Loop., In the example below, vertex ‘d’ has a loop., , Adjacent Edges: Two non-parallel ‘edges’ are said to be ‘adjacent’ if they incident on a, common vertex.

Page 3 :
MATHEMATICS, , GRAPH THEORY, , In the figure shown, edges e1 and e2, e2 and e3, e1 and e3, e3 and e4 are adjacent to each other., , Adjacent vertices: Two ‘vertices’ are said to be ‘adjacent’ if they are the end vertices of, the same edge., , Degree of a vertex: The degree of a vertex v, denoted by d(v) or deg(v), is the number of, edges incident on v., , For Example:,  d(a) = 4, d(b) = 3, d(c) = 4, d(d) = 6, d(e) = 4, d(f) = 4, d(g) = 3.

Page 4 :
MATHEMATICS, , GRAPH THEORY, , Order and size of a Graph: The number of vertices in a Graph G is called its ‘order’, and the number of edges is its ‘Size’., , The graph shown in the figure has order five and size six., , Isolated vertex: A vertex having no incident edge is called an ‘Isolated vertex’ (or A, vertex with zero degree is called an ‘Isolated vertex’)., , Pendant vertex: A vertex of degree one is called a Pendant vertex or an end vertex., , In the graph shown, vertex 5 is an isolated vertex and vertex 4 is the pendant vertex., , Null graph: A Graph without any edge is called a null graph. In other words, every vertex, in a null graph is an isolated vertex (degree zero)., , Simple graph: A graph without loops or parallel edges is called a ‘simple graph’., Multigraph: Graphs that may have multiple edges connecting the same vertices are called, Multi Graphs.

Page 5 :
MATHEMATICS, , Simple Graph, , GRAPH THEORY, , Multi Graph, , Pseudographs: Graphs that may include loops, and possibly multiple edges connecting, the same pair of vertices or a vertex to itself, are called Pseudographs., , Weighted graph: A graph where each edge is assigned a numerical label or “weight” is, called a ‘Weighted graph’., , Finite graph: A graph G = (V, E) is called a finite graph if the vertex Set V, is finite set.

Page 6 :
MATHEMATICS, , GRAPH THEORY, , Infinite graph: A graph G = (V, E) is called an infinite graph if the vertex Set V is an, infinite set., , Exercise:, 1) Draw all simple graphs of one, two, three and four vertices., 2) Draw graphs representing problems of, a) 2 houses and 3 vertices., b) 4 houses and 4 utilities say water, gas, electricity, telephone., 3) For each of the graphs Nn, Kn, Pn, Cn and Wn, give:, a) a drawing for n = 4 and n = 6;, b) the order, the size, the maximum degree and the minimum degree in terms of n., 4) Can a simple graph have 5 vertices and 12 edges? If so, draw it; if not, explain why it is not, possible to have such a graph., , 5) Show that every simple graph has two vertices of the same degree., 6) What is the largest number of vertices in a graph with?, a)35 edges if all vertices are of degree at least 3., b)24 edges and all vertices of the same degree., 7) Is it possible to have simple graphs with the following degree sequences? If, yes, draw the graphs

Page 7 :
MATHEMATICS, , GRAPH THEORY, , a) 2,3,3,3,3,3,4,5, b) 1,3,3,4,5,6,6, c) 1,2,3,3,4,5,6, , 8) Find the degree of each vertex in the given graph., , 9) Find the degree of each vertex in the given graph., , 10) Let G be a graph in which there is no pair of adjacent edges or parallel edges. What, can you say about the degree of vertices in G?, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., -------------------END-------------------

Page 8 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Basic Definitions:, Complete graph (Kn): The complete graph Kn is the graph with n vertices and every, pair of vertices in Kn is joined by an edge., , Regular graph: A Regular graph is a graph in which each vertex has the same degree., K- Regular graph is a graph in which each vertex has the same degree equal to k., , Bipartite graphs: In a simple graph G, if V can be partitioned into two disjoint sets V1, and V2 such that every edge in the graph connects a vertex in V1 and a vertex V2 (so that no, edge in G connects either two vertices in V1 or two vertices in V2), In a bipartite graph G,  V(G) = V(G1)  V(G2),  |V(G1) | = m, |V(G2) | = n,  V(G1) V(G2) = 

Page 9 :
MATHEMATICS, , GRAPH THEORY, , v, , V1, , 4, , v5, , v, 2, , v, , v, , 6, , 3, , V2, , V1, , Complete Bipartite graph (Km,n): This is the graph that has its vertex set portioned, into two subsets of ‘m’ and ‘n’ vertices, respectively. There is an edge between two vertices, if and only if one vertex is in the first subset and the other vertex is in the second subset., Representation example: K2,3, K3,3, , K2,3, , K3,3, , Complement of a graph: The complement of a graph G is a graph H on the same, vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in, G. (i.e., Complement Graph is a Graph such that it contains only those edges which are not, present in the original graph.)

Page 10 :
MATHEMATICS, , GRAPH THEORY, , Directed graphs (digraphs): G is a directed graph or digraph if each edge has been, associated with an ordered pair of vertices, i.e., each edge has a direction., , Undirected graph: An Undirected Graph is a Graph where all the edges have no, direction.

Page 11 :
MATHEMATICS, , GRAPH THEORY, , Comparison:, Type, , Edges, , Multiple, , Loops, , Edges, , Allowed ?, , Allowed, ?, Simple Graph, , undirected, , No, , No, , Multigraph, , undirected, , Yes, , No, , Pseudograph, , undirected, , Yes, , Yes, , Directed, , directed, , No, , Yes, , directed, , Yes, , Yes, , Graph, Directed, Multigraph, , In degree and out degree: For a Directed Graph and a vertex, the outdegree refers to, the number of edges directed away from the vertex., The Indegree refers to the number of edges directed towards the vertex., In computing the indegree and outdegree of a vertex, we assume that each loop on a vertex, contributes 1 to the indegree and also 1 to the outdegree of that vertex.

Page 12 :
MATHEMATICS, , GRAPH THEORY, In the figure shown,, , Indeg (1) = 0 Outdeg (1) = 3, , Indeg (2) = 1, , Outdeg (2) = 2, , Indeg (3) = 2 Outdeg (3) = 1, , Indeg (4) = 3, , Outdeg (4) = 3, , Indeg (5) = 1 Outdeg (5) = 1, , Indeg (6) = 3, , Outdeg (6) = 0, , Indeg (7) = 2 Outdeg (7) = 1, , Handshaking Theorem:, Statement: Let G (p, q) be a Graph. Then ∑ 𝑑(𝑣𝑖) = 2𝑞, i.e., Handshaking Theorem states in any given graph, Sum of degree of all the vertices is, twice the number of edges contained in it., , Proof: Since the degree of a vertex is the number of edges incident with that vertex, the sum, of degree counts the total number of times an edge is incident with a vertex. Since every edge, is incident with exactly 2 vertices, each edge gets counted twice, once at each end. Thus, the, sum of the degrees is equal twice the number of edges., , Example on Handshaking Theorem

Page 13 :
MATHEMATICS, , GRAPH THEORY, , Conclusions of Handshaking Theorem:, The following conclusions may be drawn from the Handshaking Theorem., In any graph,, •, , The sum of degree of all the vertices is always even., , •, , The sum of degree of all the vertices with odd degree is always even., , •, , The number of vertices with odd degree are always even., , Practice problems based on Handshaking theorem, Problem-01:, A simple graph G has 24 edges and degree of each vertex is 4. Find the number of vertices., , SolutionGiven- Number of edges = 24, Degree of each vertex = 4, Let number of vertices in the graph = n. Using Handshaking Theorem, we haveSum of degree of all vertices = 2 x Number of edges, Substituting the values, we get- n x 4 = 2 x 24. This implies n = 2 x 6, , ∴ n = 12, , Thus, Number of vertices in the graph = 12, , Problem-02:, A graph contains 21 edges, 3 vertices of degree 4 and all other vertices of degree 2. Find, total number of vertices., , SolutionGiven- Number of edges = 21, Number of degree 4 vertices = 3, All other vertices are of degree 2, Let number of vertices in the graph = n.

Page 14 :
MATHEMATICS, , GRAPH THEORY, , Using Handshaking Theorem, we haveSum of degree of all vertices = 2 x Number of edges, Substituting the values, we get- 3 x 4 + (n-3) x 2 = 2 x 21, 12 + 2n – 6 = 42 → 2n = 42 – 6 → 2n = 36, ∴ n = 18, Thus, Total number of vertices in the graph = 18., , Theorem: The number of vertices of odd degree in a Graph is even., Pr o of: 𝑉1 is the set of even degree vertices and V2 refers to odd degree vertices, 2e = ∑ deg(𝑣) = ∑ deg(𝑢) + ∑ deg(𝑣), v∈V, , u ∈ V1, , v ∈ V2, , ⇒ deg (𝑣) is even for v ∈ V1,, ⇒ The first term in the right hand side of the last inequality is even., ⇒ The sum of the last two terms on the right hand side of, the last inequality is even since sum is 2e., Hence second term is also even, ⇒ second term ∑ deg(𝑢) = even, v ∈ V2, , Theorem: Show that the maximum number of edges in a simple graph with n vertices is, 𝑛(𝑛−1), 2, , ., , Proof: Let G be a Graph with one vertex. Then the number of edges e = 0., , G:, , v1, , Let G be a simple graph with 2 vertices. Then the graph can have a maximum of one edge., ∴ e = 1., , Let G be a simple graph with 3 vertices. Then the graph can have a maximum of 3 edges.

Page 15 :
MATHEMATICS, , GRAPH THEORY, , Let G be a simple graph with 4 vertices. Then the graph can have a maximum of 6 edges., , ∴ Maximum number of edges, e = 6, ∴ The series obtained for maximum number of edges in an order is 0, 1, 3, 6, ………, ∴ A simple graph G with n vertices can have a maximum of, , 𝑛(𝑛−1), 2, , edges., , Exercise:, 1) For each of the following statements, find a graph with the required property., a) A 3-regular graph of order at least 5., b) A bipartite graph of order 6., c) A complete bipartite graph of order 7., d) A star graph of order 7., 2) For which values of n, m are these graphs regular? What is the degree?, (i) Kn (ii) Cn (iii) Wn (iv) Qn (v) Km, n, 3) Give the size: 1) of an r-regular graph of order n;, , 𝑛(𝑛−1), 2, , .

Page 16 :
MATHEMATICS, , GRAPH THEORY, 2) of the complete bipartite graph Kr, s., , 4) What is the number of edges in Kn?, , 5) How many edges does a complete graph of 5 vertices have?, 6) Find the number of edges of a 4- regular graph with 6 vertices., 7) How many more edges are there in the complete graph K7 than in the complete graph, K5?, 8) Which of the graphs below are bipartite? Justify your answers., , 9) Construct (i) a 5-regular graph on 10 vertices. (ii) a 4-regular graph on 6 vertices., 10) Draw complete graph each for the case when number of vertices is given by: n=3,, n=4., 11) (a)Can a simple graph exist with 15 vertices, with each of degree five? Justify your, answer., (b) Consider a graph G with 4 vertices: v1, v2, v3 and v4 and the degrees of vertices, are 3, 5, 2 and 1 respectively. Is it possible to construct such a graph G? If not, why?, (Hint: By the handshake lemma), 12) How many vertices does a regular graph of degree four with 10 edges have? (Hint:, By the handshake lemma), 13) A non-directed graph G has 8 edges. Find the number of vertices, if the degree of, each vertex in G is 2.

Page 17 :
MATHEMATICS, , GRAPH THEORY, , 14) There are 25 telephones in Geeks land. Is it possible to connect them with wires, so that each telephone is connected with exactly 7 others?, 15) If 10 people each shake hands with each other, how many handshakes took place?, What does this question have to do with graph theory?, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 18 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Isomorphism:, Definition: Two graphs G1 and G2 are Isomorphic if there exists a one-one, correspondence between their vertices and preserves adjacency., It is denoted by 𝐺1 ≈ 𝐺2, , Graph Isomorphism Conditions, Necessary conditions: For any two graphs to be isomorphic, following 4 conditions must be, satisfied., ➢ Number of vertices in both the graphs must be same., ➢ Number of edges in both the graphs must be same., ➢ Degree sequence (sequence of the degree of all the vertices must be in ascending, order) of both the graphs must be same., ➢ If a cycle of length k is formed by the vertices {v1, v, …..., vk} in one graph, then a, cycle of same length k must be formed by the vertices {f(v1), f(v2), …..., f(vk)} in the, other graph as well., Sufficient Conditions: If any one of the following conditions satisfy, then it can be said that, the graphs are surely isomorphic., ➢ Two graphs are isomorphic if and only if their complement graphs are isomorphic., ➢ Two graphs are isomorphic if their adjacency matrices are same.

Page 19 :
MATHEMATICS, , GRAPH THEORY, , ➢ Two graphs are isomorphic if their corresponding sub-graphs obtained by deleting, some vertices of one graph and their corresponding images in the other graph are, isomorphic., , Practice problems based on Graph Isomorphism, Problem-01: Verify the following two graphs for Isomorphism., , Solution- Checking Necessary Conditions, Condition-01: Number of vertices in graph G1 = 4, Number of vertices in graph G2 = 4, Here, both the graphs G1 and G2 have same number of vertices. So, Condition-01 satisfies., Condition-02: Number of edges in graph G1 = 6, Number of edges in graph G2 = 5, Here, both the graphs G1 and G2 have different number of edges.So, Condition-02 violates., Since Condition-02 violates, so given graphs cannot be isomorphic., ∴ G1 and G2 are not isomorphic graphs.

Page 20 :
MATHEMATICS, , GRAPH THEORY, , Problem-02: Verify the following two graphs for Isomorphism., , Solution- Checking Necessary ConditionsCondition-01: Number of vertices in graph G1 = 8, Number of vertices in graph G2 = 8, Here, both the graphs G1 and G2 have same number of vertices., So, Condition-01 satisfies., Condition-02: Number of edges in graph G1 = 10, Number of edges in graph G2 = 10, Here, both the graphs G1 and G2 have same number of edges., So, Condition-02 satisfies., Condition-03: Degree Sequence of graph G1 = {2, 2, 2, 2, 3, 3, 3, 3}, Degree Sequence of graph G2 = {2, 2, 2, 2, 3, 3, 3, 3}, Here, both the graphs G1 and G2 have same degree sequence., So, Condition-03 satisfies., Condition-04: In graph G1, degree-3 vertices form a cycle of length 4., In graph G2, degree-3 vertices do not form a 4-cycle as the vertices are not adjacent., Here, both the graphs G1 and G2 do not contain same cycles in them., So, Condition-04 violates. Since Condition-04 violates, so given graphs cannot be, isomorphic., ∴ G1 and G2 are not isomorphic graphs.

Page 21 :
MATHEMATICS, , GRAPH THEORY, , Problem-03: Which of the following graphs are isomorphic?, , Solution-, , Checking Necessary Conditions-, , Condition-01: Number of vertices in graph G1 = 4, Number of vertices in graph G2 = 4, Number of vertices in graph G3 = 4, Here, All the graphs G1, G2 and G3 have same number of vertices., So, Condition-01 satisfies., Condition-02: Number of edges in graph G1 = 5, Number of edges in graph G2 = 5, Number of edges in graph G3 = 4, Here, the graphs G1 and G2 have same number of edges., So, Condition-02 satisfies for the graphs G1 and G2., However, the graphs (G1, G2) and G3 have different number of edges., So, Condition-02 violates for the graphs (G1, G2) and G3., Since Condition-02 violates for the graphs (G1, G2) and G3, so they cannot be isomorphic., ∴ G3 is neither isomorphic to G1 nor G2., Since Condition-02 satisfies for the graphs G1 and G2, so they may be isomorphic., ∴ G1 may be isomorphic to G2., Now, let us continue to check for the graphs G1 and G2.

Page 22 :
MATHEMATICS, , GRAPH THEORY, , Condition-03: Degree Sequence of graph G1 = { 2 , 2 , 3 , 3 }, Degree Sequence of graph G2 = { 2 , 2 , 3 , 3 }, Here, Both the graphs G1 and G2 have same degree sequence., So, Condition-03 satisfies., Condition-04: Both the graphs contain two cycles each of length 3 formed by the vertices, having degrees { 2 , 3 , 3 }, It means both the graphs G1 and G2 have same cycles in them., So, Condition-04 satisfies., Thus, All the 4 necessary conditions are satisfied., So, graphs G1 and G2 may be isomorphic., Now, let us check the sufficient condition., Checking Sufficient Condition, We know that two graphs are surely isomorphic if and only if their complement graphs are, isomorphic., So, let us draw the complement graphs of G1 and G2., The complement graphs of G1 and G2 are-, , Clearly, complement graphs of G1 and G2 are isomorphic., ∴ Graphs G1 and G2 are isomorphic graphs.

Page 23 :
MATHEMATICS, , GRAPH THEORY, , Exercise:, 1) How many isomorphism classes are there for simple graphs with 4 vertices? Draw, them., 2) Draw at least 3 non-isomorphic graphs on 4 vertices., 3) Determine whether the following graphs are isomorphic. If yes, justify your answer., , 4) Is it possible for two different (non-isomorphic) graphs to have the same number of, vertices and the same number of edges? What if the degrees of the vertices in the two, graphs are the same (so both graphs have vertices with degrees 1, 2, 2, 3, and 4, for, example)? Draw two such graphs or explain why not., 5) Are the two graphs below equal? Are they isomorphic? If they are isomorphic, give, the isomorphism. If not, explain., 𝑮𝒓𝒂𝒑𝒉 𝟏 ∶ 𝑽 = {𝒂, 𝒃, 𝒄, 𝒅, 𝒆}, 𝑬 = {{𝒂, 𝒃}, {𝒂, 𝒄}, {𝒂, 𝒆}, {𝒃, 𝒅}, {𝒃, 𝒆}, {𝒄, 𝒅}}, 𝑮𝒓𝒂𝒑𝒉 𝟐 ∶, , 6) Determine, up to isomorphism, all the graphs of order four and size two., 7) Let V = {a, b, c, d} and E = {ab, ac, ad, dc}. Determine, up to isomorphism, all the, subgraphs of the graph G = (V, E)., 8) Determine up to isomorphism the number of graphs of order 20 and size 188., 9) Let G = (V, E) and H = (W, B) be two graphs. Prove that G and H are isomorphic if,, and only if, Gc and Hc are isomorphic.

Page 24 :
MATHEMATICS, , GRAPH THEORY, , 10) A graph is self-complementary if it is isomorphic to its complement., Prove that there are no self-complementary graphs of order 3, but there are such, graphs of order 4 and 5., 11) Define isomorphism of graphs. Show that the graphs (a) and (b) are isomorphic., , 12) Define isomorphism. Determine whether the following pair of graphs are isomorphic, , 13) Find whether the given graphs are isomorphic or not., , 14) Are the following graphs isomorphic? If Yes or No justify.

Page 25 :
MATHEMATICS, , GRAPH THEORY, , 15) Check whether the two graphs are isomorphic or not. Justify your answer., , 16) What are the basic conditions to be satisfied for two graphs to be isomorphic? Are the, two graphs below isomorphic? Explain with valid reasons.

Page 26 :
MATHEMATICS, , GRAPH THEORY, , 17) Classify by isomorphism type the graphs of Figure., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., -------------------END-------------------

Page 27 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Subgraphs, A subgraph of a graph G = (V, E) is a graph H =(V’, E’) where V’ is a subset of V and E’ is a, subset of E., , u, , v, , u, , u, , w, , w, , v, , G, , v, H2, , H1, , G = G1 U G2 wherein E = E1 U E2 and V = V1 U V2, G, G1 and G2 are simple graphs of G., , u, u, , w, , w, , G1, , v, , w, , G2, , Consequences from the Definition of Subgraphs, ➢ Every Graph is a Subgraph of itself., ➢ Every Simple Graph of n-vertices is a subgraph of the complete Graph Kn., , v, , G

Page 29 :
MATHEMATICS, , GRAPH THEORY, , Note: Edge disjoint subgraph may have vertices in common but vertex disjoint graph cannot, have common edge, so vertex disjoint subgraph will always be an edge disjoint subgraph., , Spanning Subgraphs, If H=(U,F) is a subgraph of G(V,E) and U = V, then H is called a spanning subgraph of G., i.e., A spanning subgraph is a subgraph that contains all the vertices of the original graph., , Not a Spanning Subgraph of, C, 3, , Induced Subgraph, •, , Graph H is an induced subgraph of graph G, if H is obtained from G by removing the, vertices from V(G)-V(H)., (i.e., An induced subgraph of a Graph is another Graph, formed from a subset of the, vertices of the Graph and all of the edges connecting pairs of vertices in that subset.)

Page 30 :
MATHEMATICS, , GRAPH THEORY, , Example: P5 is an induced subgraph of C6., , H, , G, , Example :, , G, , H1, Not an Induces Subgraph, , Trivial Subgraph, Subgraph H is trivial, if either H = f, or H = G., , Exercise:, 1) Consider the graph, , (i) Give an example of a subgraph of G that is not induced., (ii) How many induced subgraphs does G have? List them., , H2, Induces Subgraph

Page 31 :
MATHEMATICS, , GRAPH THEORY, , (iii) How many subgraphs does G have?, 2) Define a graph and a subgraph. Show that for a subgraph H of a graph G,, , Δ (H) ≤ Δ (G)., 3) Give an example of a subgraph H of a graph G with δ (G) < δ (H) and Δ (H) ≤ Δ (G)., 4) How many Subgraphs does a complete graph have?, 5) What are edge disjoint and vertex disjoint subgraphs? Construct, , two edge disjoint subgraphs of the graph G., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 32 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Operations on Graphs, Union: The union of two simple graphs G = (V1, E1) and H = (V2, E2) is the, simple graph with vertex set V1 ⋃ V2 and edge set E1 ⋃ E2. The union of G and H is, denoted by G ⋃ H., , Intersection: The intersection of two simple graphs G = (V1, E1) and H = (V2, E2) is the, simple graph with vertex set V1 ∩ V2 and edge set E1 ∩ E2. The intersection of G and H is, denoted by G ∩ H. (i.e., consisting only of those vertices and edges that are in both G and H)., , Ring sum of two graphs: The ring sum of two Graphs G1 and G2, denoted by G1⊕ G2, is a graph consisting of the vertex set V (G1) ∪ V (G2) and of edges that are either in G1 or, G2 but not in both.

Page 33 :
MATHEMATICS, , GRAPH THEORY

Page 35 :
MATHEMATICS, , GRAPH THEORY, , Decomposition: A Graph G is said to have been decomposed into two subgraphs G1 and, G2 if G1 ⋃ G2 = G and G1 ∩ G2 = a null Graph., , Deletion, Removal of a vertex from a Graph: Let G(v,e) be a Graph. The removal of a vertex, vi from G gives a subgraph G- vi of G. This Graph contains all the vertices of G except vi.

Page 36 :
MATHEMATICS, , GRAPH THEORY, , Removal of a an edge from a Graph: Let G(v,e) be a Graph. The removal of an edge, ei from G gives a subgraph { G- ei }., , Fusion (Merging): A pair of vertices v1 and v2 in a Graph G are said to be fused, if the, vertices are replaced by single new vertex such that every edge that was incident on either v1, or on v2 or on both is incident on the new vertex., , Exercise:, 1) Consider the graph, , a. Let e be the edge connecting a and d. Draw G − e and G/e, b. Let e be the edge connecting a and c. Draw G − e and G/e, c. Let e be an edge connecting d and c. Draw G + e

Page 37 :
MATHEMATICS, , GRAPH THEORY, , d. Draw 𝐺̅, 2) For the following graph G, draw subgraphs (i) G - e (ii) G - a., , 3) For the following graph G, Find 𝐺1 ∪ 𝐺2, , 4) For the following graph G, Find 𝐺1 ∪ 𝐺2, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran.

Page 38 :
MATHEMATICS, , GRAPH THEORY, , 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 39 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Walks, Paths and Circuits, Walk: A walk is defined as a finite alternating sequence of vertices and edges beginning, and ending with vertex. (Vertex and Edges can be repeated in a walk)., , In the above Graph,, , v1 → e1 → v2 → e2 → v3 → e3 → v4 is a walk, v1 → e7 → v4 → e6 → v6 → e5 → v5 → e4 → v4 → e3 → v3 is another walk., Length of the Walk: The total number of edges covered in a walk is called as Length of, the Walk., In the above Graph,, , v1 → e1 → v2 → e2 → v3 → e3 → v4 is a walk of length three., v1 → e7 → v4 → e6 → v6 → e5 → v5 → e4 → v4 → e3 → v3 is a walk of length five., , Open Walk, A walk is called as an Open walk if•, , Length of the walk is greater than zero, , •, , And the vertices at which the walk starts and ends are different., , Closed Walk, A walk is called as a Closed walk if•, , Length of the walk is greater than zero, , •, , And the vertices at which the walk starts and ends are same.

Page 42 :
MATHEMATICS, , GRAPH THEORY, , Important Chart, The following chart summarizes the above definitions and is helpful in remembering them-, , Problems, Problem-01: Using the graph, classify each sequence as a walk, a path or a circuit., , A, , E, D, , B, C, a) E → C → D → E, b) A → C → D → E → B → A, c) B → D → E → B → C, d) A → B → C → D → B → A

Page 43 :
MATHEMATICS, , GRAPH THEORY, , Solution:, Walk, , Path, , Circuit, , a) No, , No, , No, , b) Yes, , Yes, , Yes, , c) Yes, , No, , No, , d) Yes, , No, , No, , Problem-02: Decide which of the following sequences of vertices determine walks., For those that are walks, decide whether it is a circuit, a path, a cycle or a trail., 1. a , b , g , f , c , b, 2. b , g , f , c , b , g , a, 3. c , e , f , c, 4. c , e , f , c , e, 5. a , b , f , a, 6. f , d , e , c , b, , Solution1. Trail, 2. Walk, 3. Cycle

Page 44 :
MATHEMATICS, 4. Walk, 5. Not a walk, 6. Path, , Problem-03:, Consider the following graph-, , Observe the given sequences and predict the nature of walk in each case1. v1e1v2e2v3e2v2, 2. v4e7v1e1v2e2v3e3v4e4v5, 3. v1e1v2e2v3e3v4e4v5, 4. v1e1v2e2v3e3v4e7v1, 5. v6e5v5e4v4e3v3e2v2e1v1e7v4e6v6, Solution, 1. Open walk, 2. Trail (Not a path because vertex v4 is repeated), 3. Path, 4. Cycle, 5. Circuit (Not a cycle because vertex v4 is repeated), , GRAPH THEORY

Page 45 :
MATHEMATICS, , GRAPH THEORY, , Exercise:, 1) In each of the following graphs, find paths of length 9 and 11, and cycles of length 5,, 6, 8 and 9, if possible., , 2) Find a Walk, trail, path and cycle on the graph below., , 3) Find a path of length 9 and a circuit of length 8 in the Peterson graph?, , 4) Prove that if G is a graph of minimum degree d, then G contains a path of length d., 5) Prove that if a graph has exactly two vertices of odd degree, then there is a path from, one of them to the other., 6) Prove that every graph with n vertices with at least n edges contains a circuit?, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary.

Page 46 :
MATHEMATICS, , GRAPH THEORY, , 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 47 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Connected and Disconnected Graphs, Connected Graph: A graph is said to be connected, if there is at least one path between, every pair of vertices., , Note that Complete graphs, complete bipartite graphs, cyclic graphs and paths etc. are a few, examples of connected graphs., A graph that is not connected is the union of two or more connected subgraphs, each pair of, which has no vertex in common. These disjoint connected subgraphs are called the connected, components of the graph. The number of components of a graph G is denoted by C(G)., If X is connected then C(X) = 1. Let e be an edge of a graph X then it can be easily observed, that C(X) ≤ C(X \ {e}) ≤ C(X) +1., , Disconnected Graph: A graph in which there does not exist any path between at least, one pair of vertices is called as a disconnected graph., , Theorem 1. A graph is disconnected if and only if its vertex set V can be partitioned into, two nonempty disjoint subsets V1 and V2 such that there exists no edge in G whose one end, vertex is in V1 and other is in V2., , Proof: Suppose that such a partitioning exists. Consider two arbitrary vertices a and b of G,, such that 𝑎 ∈ 𝑉1 and 𝑏 ∈ 𝑉2. No path can exist between vertices a and b; otherwise, there

Page 48 :
MATHEMATICS, , GRAPH THEORY, , would be at least one edge whose one end vertex would be in 𝑉1 and the other in 𝑉2. Hence, if, a partition exists, G is not connected., Conversely, let G be a disconnected graph. Consider a vertex ‘a’ in G. Let 𝑉1 be the set, of all vertices that are joined by paths to ‘a’. Since G is disconnected 𝑉1 does not include all, vertices of G. The remaining vertices will form a (nonempty) set 𝑉2. No vertex in 𝑉1 is joined, to any in 𝑉2 by an edge. Hence the partition., , Theorem 2: If a graph (connected or disconnected) has exactly two vertices of odd degree, then there must be a path joining these vertices., , Proof: Let G be a graph that has exactly two vertices, say ‘u’ and ‘v’ of odd degree. Let C, be a connected component of G containing the vertex ‘u’. Since, the number of vertices of, odd degree in any graph is even, C has to contain another vertex of odd degree. But then v is, the only other vertex in G of odd degree and hence v lies in the component C. Thus, there is a, path from ‘u’ to ‘v’., , Theorem 3. A simple graph with n vertices and k components can have at most have, 1, 2, , (𝑛 − 𝑘)(𝑛 − 𝑘 + 1) edges., , Proof. Let the number of vertices in each of the k components of a graph G be 𝑛1 , 𝑛2 ,…,, 𝑛𝑘 . Thus, we have, 𝑛1 + 𝑛2 +…+ 𝑛𝑘 = 𝑛, 𝑛𝑖 ≥ 1., Now the maximum number of edges in the ith component of G (which is a simple connected, 1, , graph) is 𝑛𝑖 (𝑛𝑖 -1)., 2, , Therefore, the maximum number of edges in G is, 1, 2, , ∑𝑘𝑖=1(𝑛𝑖 − 1) 𝑛𝑖 =, , 1, 2, , ( ∑𝑘𝑖=1 𝑛𝑖 2 ) −, , 𝑛, 2, , --(1), , The proof of the theorem depends on an algebraic inequality, 𝑘, , ∑ 𝑛𝑖 2 ≤ 𝑛2 − (𝑘 − 1)(2𝑛 − 𝑘)., 𝑖=1

Page 49 :
MATHEMATICS, , GRAPH THEORY, , Substituting this in (1), we get, 𝑛, , ≤ [𝑛2 − (𝑘 − 1)(2𝑛 − 𝑘)] − 2 ,, 1, , = 2 (𝑛 − 𝑘)(𝑛 − 𝑘 + 1), , Connectedness in Directed graphs:, Weakly connected: A digraph is weakly connected if it is connected as an undirected graph, (a graph in which the direction of the edges is neglected)., Unilaterally connected: If for any pair of nodes of the graph at least one of the nodes of the, pair is reachable from the other., Strongly connected: If for any pair of nodes of the graph both the nodes of the pair are, reachable from one to another., From the definition every strongly connected graph is unilaterally connected and every, unilaterally connected graph is weakly connected graph., , Example

Page 50 :
MATHEMATICS, , GRAPH THEORY, , Examples of five connectivity types of digraphs, , Exercise :, 1) Prove that for every simple graph, either G is connected, or 𝐺̅ is connected, 2) Draw a simple disconnected graph with 10 vertices, 4 components and also calculate, the maximum number of edges., 3) Prove that a simple graph with n vertices must be connected, if it has more than, [(n-1) (n-2)]/2 edges. (Hint: Use Theorem-3), 4) Let G be a disconnected graph with n vertices where n is even. If G has two, components each of which is complete, prove the G has a minimum of [n (n-1)] /4, edges., 5) Draw a connected graph that becomes disconnected when any edge is removed from it., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh.

Page 51 :
MATHEMATICS, , GRAPH THEORY, , 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 52 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Euler Graph, Euler Line: A closed walk covering all the edges of the graph exactly once is called Euler, line., , Euler Graph: A graph that consists of a Euler line is called a Euler graph., Note:, 1. Any connected graph is called as a Euler Graph if and only if all its vertices are of, even degree., 2. A Euler Graph is a connected graph that contains a Euler Circuit., Example:, , Here,, This graph is a connected graph and all its vertices are of even degree., Alternatively, the above graph contains a Euler circuit B-A-C-E-D-C-B, so it is a Euler, graph., , Euler Path: Euler path is also known as Euler Trail or Euler Walk., •, , If there exists a Trail in the connected graph that contains all the edges of the graph,, then that trail is called as a Euler trail., OR, , •, , If there exists a walk in the connected graph that visits every edge of the graph exactly, once with or without repeating the vertices, then such a walk is called as a Euler walk., , Note, A graph will contain a Euler path if and only if it contains at most two vertices of odd degree.

Page 53 :
MATHEMATICS, , GRAPH THEORY, , Euler Circuit: Euler circuit is also known as Euler Cycle., If there exists a Circuit in the connected graph that contains all the edges of the graph, then, that circuit is called as a Euler circuit., , OR, , If there exists a walk in the connected graph that starts and ends at the same vertex and visits, every edge of the graph exactly once with or without repeating the vertices, then such a walk, is called as a Euler circuit. OR, A Euler trail that starts and ends at the same vertex is called as a Euler circuit., A closed Euler trail is called as a Euler circuit., , OR

Page 54 :
MATHEMATICS, , GRAPH THEORY, , Semi-Euler Graph: If a connected graph contains a Euler trail but does not contain a, Euler circuit, then such a graph is called as a semi-Euler graph., Thus, for a graph to be a semi-Euler graph, following two conditions must be satisfied•, , Graph must be connected., , •, , Graph must contain a Euler trail., , This graph contains a Euler trail B-C-D-B-A-D., But it does not contain a Euler circuit., Therefore, it is a semi-Euler graph., , Theorem- 1: A connected multigraph (and simple graph) with at least two vertices has a, Euler circuit if and only if each of its vertices has an even degree., Proof: Every time a circuit passes through a vertex, it adds twice to its degree. Since it is a, circuit, it starts and ends at the same vertex, which makes it contribute degree - one when the, circuit starts and another one when it ends. In this way, every vertex has an even degree., Theorem-2: A connected multigraph (and simple graph) has a Euler path but not a Euler, circuit if and only if it has exactly two vertices of odd degree., Proof: The proof is an extension of the proof given in the previous theorem. Since a path, may start and end at different vertices, the vertices where the path starts and ends are allowed, to have odd degrees., Important Notes, Note-01: To check whether any graph is a Euler graph or not, any one of the following two, ways may be used-

Page 55 :
MATHEMATICS, , GRAPH THEORY, , •, , If the graph is connected and contains a Euler circuit, then it is a Euler graph., , •, , If all the vertices of the graph are of even degree, then it is a Euler graph., , Note-02: To check whether any graph contains a Euler circuit or not,, •, , Just make sure that all its vertices are of even degree., , •, , If all its vertices are of even degree, then graph contains a Euler circuit otherwise not., , Problems, Problem -1: Which graphs shown below have a Euler path or Euler circuit?, , Solution: G1 has two vertices of odd degree a and d and the rest of them have even degree., So, this graph has a Euler path but not a Euler circuit. The path starts and ends at the vertices, of odd degree., , The path is- a, c , d , a ,b , d ., , G2 has four vertices all of even degree, so it has a Euler circuit., The circuit is –a, d , b, a, c, d, a .

Page 56 :
MATHEMATICS, , GRAPH THEORY, , Problem -2: Which of the following are Euler Graphs?, , Solution:, If all the vertices of a graph are of, even degree, then graph is an, Euler Graph otherwise not., Using the above rule, we haveA) It is a Euler graph., B) It is not a Euler graph., C) It is not a Euler graph., D) It is not a Euler graph., E) It is a Euler graph., F) It is not a Euler graph., , Exercise:, 1) Which of the following graphs contain a Euler path? Which contain a Euler circuit?, 𝑎)𝐾4 𝑏)𝐾5 𝑐)𝐾5,7 𝑑) 𝐾2,7 𝑒) 𝐶7 𝑓) 𝑝7, 2) For which n does the graph Kn contain a Euler circuit? Explain.

Page 57 :
MATHEMATICS, , GRAPH THEORY, , 3) For which m and n does the graph Km, n contain a Euler path? A Euler circuits?, Explain., 4) Find out for which values of r and s the complete bipartite graph Kr, s is Eulerian., 5) Let G be a graph with exactly two connected components, both being Eulerian., Which is the minimum number of edges that need to be added to G to obtain a, Eulerian graph?, 6) Prove that the finite connected graph is Eulerian if and only if each vertex has even, degree?, 7) For each of the following graphs, either find a Eulerian circuit or prove that there is, not one., , 8) Find out if the following figures can be drawn without lifting the pencil from the, paper and without repeating any line., , 9) Determine the minimum number of times that one needs to lift the pencil from the, paper to draw each of the figures below without repeating any line., , 10) Consider the graph G given below: Define Euler graph. Is G an Euler? If yes, write an, Euler line from G.

Page 58 :
MATHEMATICS, , GRAPH THEORY, , 11) Check whether the given graph is an Euler graph and if yes, give the Euler line., Justify your answer, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., -------------------END-------------------

Page 59 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Hamiltonian Graph, If there exists a closed walk in the connected graph that visits every vertex of, the graph exactly once (except starting vertex) without repeating the edges, then such, a graph is called as a Hamiltonian graph., , Here,, This graph contains a closed walk A-B-C-D-E-F-A., It visits every vertex of the graph exactly once except starting vertex., The edges are not repeated during the walk., Therefore, it is a Hamiltonian graph., Alternatively, there exists a Hamiltonian circuit ABCDEFA in the above graph, therefore it is, a Hamiltonian graph., , Hamiltonian Path: A simple path in a graph G that passes through every vertex exactly, once is called a Hamiltonian path., , OR, , If there exists a walk in the connected graph that visits every vertex of the graph exactly once, without repeating the edges, then such a walk is called as a Hamiltonian path., Note:, In Hamiltonian path, all the edges may or may not be covered but edges must not repeat.

Page 60 :
MATHEMATICS, , GRAPH THEORY, , Example of a Hamiltonian Path, , Hamiltonian Circuit (Hamiltonian circuit is also known as Hamiltonian Cycle. ):, Hamiltonian Cycle in a graph G is a circuit which contains every vertex of G exactly once., OR, , If there exists a walk in the connected graph that visits every vertex of the graph, , exactly once (except starting vertex) without repeating the edges and returns to the starting, vertex, then such a walk is called as a Hamiltonian circuit., , Example of a Hamiltonian Circuit

Page 61 :
MATHEMATICS, , GRAPH THEORY, , Notes:, 1. A graph with a vertex of degree cannot have a Hamiltonian circuit., 2. No vertex in a Hamiltonian circuit is repeated except the initial vertex., 3. Hamiltonian circuit in a graph of n vertices consists of exactly n edges., 4. Any Hamiltonian circuit can be converted to a Hamiltonian path by removing one of, its edges., 5. Every graph that contains a Hamiltonian circuit also contains a Hamiltonian path but, vice versa is not true., 6. There may exist more than one Hamiltonian paths and Hamiltonian circuits in a, graph., 7. Hamiltonian path in a graph G traverses every vertex of G exactly once., 8. Length of the Hamiltonian path in a graph G of n vertices is n-1, , Theorems, (sufficient conditions for the existence of Hamiltonian graphs), •, , DIRAC’S Theorem: if G is a simple graph with n vertices with n ≥ 3 such that the, degree of every vertex in G is at least n/2 then G has a Hamilton circuit., , •, , ORE’S Theorem: if G is a simple graph with n vertices with n ≥ 3 such that deg (u), + deg (v) ≥ n for every pair of non-adjacent vertices u and v in G, then G has a, Hamilton circuit., , Problems, Problem- 1: Does the following graph have a Hamiltonian Circuit?

Page 62 :
MATHEMATICS, , GRAPH THEORY, , Solution- Yes, the above graph has a Hamiltonian circuit. The solution is –, , Problem- 2: Does the following graph have a Hamiltonian Circuit?, , Solution- No, the above graph does not have a Hamiltonian circuit as there are two vertices, with degree one in the graph., Problem-3: Which of the following are Hamiltonian graphs?

Page 63 :
MATHEMATICS, , GRAPH THEORY, , SolutionsA) The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit. Since graph, does not contain a Hamiltonian circuit, therefore It is not a Hamiltonian Graph., B) The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit. Since graph, does not contain a Hamiltonian circuit, therefore It is not a Hamiltonian Graph., C) The graph contains both a Hamiltonian path (ABCDHGFE) and a Hamiltonian circuit, (ABCDHGFEA). Since graph contains a Hamiltonian circuit, therefore It is a Hamiltonian, Graph., D) The graph contains both a Hamiltonian path (ABCDEFG) and a Hamiltonian circuit, (ABCDEFGA). Since graph contains a Hamiltonian circuit, therefore It is a Hamiltonian, Graph., E) The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit. Since graph, does not contain a Hamiltonian circuit, therefore It is not a Hamiltonian Graph., F) The graph contains both a Hamiltonian path (ABCDEFGHI) and a Hamiltonian circuit, (ABCDEFGHIA). Since graph contains a Hamiltonian circuit, therefore It is a Hamiltonian, Graph., , Exercise:, 1) For which n does Kn contain a Hamilton path? A Hamilton cycles? Explain., 2) For which m and n does the graph Km, n contain a Hamilton path? A Hamilton cycles?, Explain., 3) Prove that a bipartite graph Kr, s of order ≥ 3 is Hamiltonian if, and only, if, r = s., 4) Let G be a graph that has exactly two connected components, both of them, Hamiltonian graphs. Find the minimum number of edges that one needs to add to G to, obtain a Hamiltonian graph., 5) Let G be a Hamiltonian graph that is not a cycle. Prove that G has at least 2 vertices, of degree ≥ 3., 6) A) Suppose a graph has a Hamilton path. What is the maximum number of vertices, of degree one the graph can have? Explain why your answer is correct., B) Find a graph which does not have a Hamilton path even though no vertex has degree one., Explain why your example works.

Page 64 :
MATHEMATICS, , GRAPH THEORY, , 7) Give an example of a graph that has an Eulerian circuit which is also a Hamiltonian, circuit., 8) Give an example of a graph that has an Eulerian circuit and a Hamiltonian circuit,, which are distinct., 9) Give an example of a graph which has an Eulerian circuit but not a Hamiltonian, circuit., 10) Give an example of a graph which has a Hamiltonian circuit but not an Eulerian, circuit., 11) Give an example of a graph that has neither an Eulerian circuit nor a Hamiltonian, circuit., 12) Find three Hamiltonian circuits in dodecahedron?, 13) Find an example of a non-Hamiltonian graph with a Hamiltonian path?, 14) Prove that in a complete graph with n vertices there are (n-1)/2 edge disjoint, Hamiltonian circuits and n >= 3?, 15) Find out the number of edge-disjoint Hamiltonian circuits possible in a complete, graph with five vertices, 16) Consider a complete graph G with 11 vertices. Find the number of edge-disjoint, Hamiltonian circuits in G., 17) Give Hamiltonian circuit of the following graph., , 18) Consider the following graph:

Page 65 :
MATHEMATICS, , a., b., c., d., , GRAPH THEORY, , Find a Hamilton path. Can your path be extended to a Hamilton cycle?, Is the graph bipartite? If so, how many vertices are in each “part”?, Use your answer to part (b) to prove that the graph has no Hamilton cycle., Suppose you have a bipartite graph G in which one part has at least two more vertices, than the other. Prove that G does not have a Hamilton path., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 66 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Some Applications of Eulerian and Hamiltonian Graphs, Konigsberg Bridge Problem, •, , Konigsberg is the former name of a German city that is now in Russia., , •, , The following picture shows the inner city of Konigsberg with the river Pregel., , •, , The river Pregel divides the city into four land areas A, B, C and D., , •, , In order to travel from one part of the city to another, there exists seven bridges., , ➢ Konigsberg Bridge Problem may be stated as“Starting from any of the four land areas A, B, C, D, is it possible to cross each of the seven, bridges exactly once and come back to the starting point without swimming across the river?”, ➢ SolutionIn 1736, a Swiss Mathematician Leon hard Euler solved this problem., He provided a solution to the problem and finally concluded that such a walk is not possible., Euler represented the given situation using a graph as shown below-

Page 67 :
MATHEMATICS, , GRAPH THEORY, , In this graph,, •, , Vertices represent the landmasses., , •, , Edges represent the bridges., , Euler observed that when a vertex is visited during the process of tracing a graph,, •, , There must be one edge that enters into the vertex., , •, , There must be another edge that leaves the vertex., , •, , Therefore, order of the vertex must be an even number., , Based on this observation, Euler discovered that it depends on the number of odd vertices, present in the network whether any network is traversable or not., Euler found that only those networks are traversable that have either•, , No odd vertices (then any vertex may be the beginning and the same vertex will also, be the ending point), , •, , Or exactly two odd vertices (then one odd vertex will be the starting point and other, odd vertex will be the ending point), , Now,, •, , Since the Konigsberg network has four odd vertices, therefore the network is not, traversable., , •, , Thus, It was finally concluded that the desired walking tour of Konigsberg is not, possible.

Page 68 :
MATHEMATICS, , GRAPH THEORY, , Traveling-salesman problem, A problem closely related to the question of Hamiltonian circuits is the Travelling Salesman, Problem stated as follows•, , A salesman has to visit number of cities during a trip., , •, , Given the distances between the cities, in what order should he travel so as to visit, every city precisely once and he has to come back to the city from where he starts his, journey., , •, , What is the shortest possible route that the salesman must follow to complete his tour?, , •, , Representing the cities by vertices and the roads between them by edges, we get a, graph. In this graph, with every edge ei there is associated a real number (the distance, in miles, say), w(ei). Such a graph is called a weighted graph; w(ei) being the weight, of edge ei., , •, , In this problem, if each of the cities has a road to every other city, we have a complete, weighted graph. This graph has numerous Hamiltonian circuits, and we are to pick the, one that has the smallest sum of distances (or weights)., , Example: The following graph shows a set of cities and distance between every pair of, cities-, , If salesman starting city is A, then a Traveling-salesman problem tour in the graph isA→B→D→C→A

Page 69 :
MATHEMATICS, , GRAPH THEORY, , Cost of the tour, = 10 + 25 + 30 + 15, = 80 units, , Exercise:, 1) A bridge builder has come to Konigsberg and would like to add bridges so that, it is possible to travel over every bridge exactly once. How many bridges must be, built?, 2) Below is a graph representing friendships between a group of students (each vertex is, a student and each edge is a friendship). Is it possible for the students to sit around a, round table in such a way that every student sits between two friends? What does this, question have to do with paths?, , 3) Give a travelling salesman’s tour on the graph below.

Page 70 :
MATHEMATICS, , GRAPH THEORY, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 71 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Trees and basic properties, Trees: A tree is an undirected, connected and acyclic graph. In other words, a, connected graph that does not contain even a single cycle is called a tree., The elements of trees are called their nodes and the edges of the tree are called branches., NOTE: A tree is a simple graph having neither a self-loop, nor parallel edge., Examples:, , This Graph is a Tree, , This Graph is not a Tree, , Directed Tree: A polytree (or directed tree or oriented tree or singly connected network) is, a directed acyclic graph (DAG) whose underlying undirected graph is a tree., , Rooted Tree: A tree in which one vertex (called the root) is distinguished from all the others is, called a rooted tree. In general, tree means without any root. They are sometimes called as free trees, (non-rooted trees).

Page 72 :
MATHEMATICS, , GRAPH THEORY, , In the following example, the root is enclosed in a small circle. All rooted trees with one,, two, three and four vertices are shown., , Binary Tree: A binary tree is defined as a tree in which there is exactly one vertex of degree two, and each of the remaining vertices is of degree one or three., , Example:, , ❖ The number of vertices in a binary tree is always odd., ❖ The number of pendant vertices in a binary tree is (n+1)/2 where n is the number of, vertices., Note:, Let G = (V, E) be an undirected graph., The following statements are equivalent,, 1. G is a tree, 2. Any two vertices in G are connected by unique simple path, 3. G is connected, but if any edge is removed from E, the resulting graph is disconnected

Page 73 :
MATHEMATICS, , GRAPH THEORY, , 4. G is connected, and | E | = | V | -1, 5. G is acyclic, and | E | = | V | -1, 6. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle, , Properties of Trees:, Theorem 1: Prove that for a tree (T), there is one and only one path between every pair of, vertices in a tree., Proof: Since tree (T) is a connected graph, there exist at least one path between every pair of, vertices in a tree (T). Now, suppose between two vertices 1 and 6 of the tree (T) there exist, two paths. The union of these two paths will contain a circuit and tree (T) cannot be a tree., Hence the above statement is proved., , Theorem 2: If in a graph G there is one and only one path between every pair of vertices, then graph G is a tree., Proof: There is the existence of a path between every pair of vertices so we assume that, graph G is connected. A circuit in a graph implies that there is at least one pair of vertices ‘a’, and ‘b’, such that there are two distinct paths between ‘a’ and ‘b’. Since G has one and only, one path between every pair of vertices. G cannot have any circuit. Hence graph G is a tree.

Page 75 :
MATHEMATICS, , GRAPH THEORY, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 76 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Trees and basic properties (Continuation from Session 11), Theorem 3: Prove that a tree with n vertices has (n-1) edges., Proof: Let n be the number of vertices in a tree (T)., If n=1, then the number of edges=0., If n=2 then the number of edges=1., If n=3 then the number of edges=2., Hence, the statement (or result) is true for n=1, 2, 3., Let the statement be true for n=m., Now we want to prove that it is true for n=m+1., Let ‘e’ be the edge connecting vertices say Vi and Vj. Since G is a tree, then there exists, only one path between vertices Vi and Vj. Hence if we delete edge ‘e’ it will be disconnected, graph into two components G1 and G2 say. These components have less than m+1 vertices, and there is no circuit and hence each component G1 and G2 have m1 and m2 vertices., Now, the total no. of edges = (m1-1) + (m2-1) +1, = (m1+m2)-1 = m+1-1 = m, Hence for n = m+1 vertices there are m edges in a tree (T)., By the mathematical induction the graph exactly has n-1 edges., , Tree(T), , Theorem 4: Prove that any connected graph G with n vertices and (n-1) edges is a tree., Proof: We know that the minimum number of edges required to make a graph of n vertices, connected is (n-1) edges. We can observe that removal of one edge from the graph G will

Page 77 :
MATHEMATICS, , GRAPH THEORY, , make it disconnected. Thus, a connected graph of n vertices and (n-1) edges cannot have a, circuit. Hence a graph G is a tree., , Graph G, , Theorem 5: Prove that a graph with n vertices, (n-1) edges and no circuit is a connected, graph., Proof: Let the graph G is disconnected then there exist at least two components G1 and G2, say. Each of the component is circuit-less as G is circuit-less. Now to make a graph G, connected we need to add one edge e between the vertices Vi and Vj, where Vi is the vertex, of G1 and Vj is the vertex of component G2., Now the number of edges in G = (n – 1) +1 =n., , Disconnected Graph, Now, G is connected graph and circuit-less with n vertices and n edges, which is impossible, because the connected circuit-less graph is a tree and tree with n vertices has (n-1) edges. So, the graph G with n vertices, (n-1) edges and without circuit is connected. Hence the given, statement is proved.

Page 78 :
MATHEMATICS, , GRAPH THEORY, , Theorem 6: A graph G is a tree if and only if it is minimally connected., Proof: Let the graph G is minimally connected, i.e; removal of one edge make it, disconnected., , Therefore,, , there, , is, , no, , circuit., , Hence, , graph, , G, , is, , a, , tree., , Conversely, let the graph G is a tree i.e; there exists one and only one path between every pair, of vertices and we know that removal of one edge from the path makes the graph, disconnected. Hence graph G is minimally connected., , Minimally Connected Graph, , Theorem 7: Every tree with at-least two vertices has at-least two pendant vertices., Proof: Let the number of vertices in a given tree T is n and n >= 2. Therefore, the number of, edges in a tree T = n -1 using previous theorems., summation of (deg (Vi)) = 2*e = 2*(n-1) = 2n - 2, The degree sum is to be divided among n vertices. Since a tree T is a connected graph, it, cannot have a vertex of degree zero. Each vertex contributes at-least one to the above sum., Thus, there must be at least two vertices of degree 1. Hence every tree with at-least two, vertices has at-least two pendant vertices., , Here a, b and d are pendent vertices of the given graph

Page 79 :
MATHEMATICS, , GRAPH THEORY, , Exercise:, 1) Let T be a tree of order n ≥ 3. Prove that the following statements are equivalent:, a) T is isomorphic to the star K1, n−1., b) T has exactly n − 1 leaves., c) T has maximum degree n − 1., d) T has diameter equal to 2., 2), , Let G be a graph of order n and size m. Prove that the following statements are, , equivalent:, a) The graph G is connected and has only one cycle., b) There is an edge e of G such that G − e is a tree., c) The graph G is connected and n = m., 3) Show that any tree with at least two vertices is bipartite., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 80 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Distance, Eccentricity and Centre of a Tree, Distance: The distance between two vertices in a graph is the number of edges in a shortest, path (also called a graph geodesic) connecting them. This is also known as the, geodesic distance. Notice that there may be more than one shortest path between two vertices., It is denoted by d (vi, vj)., Example:, , d(4,5) = 2,, , d(4,6) = 4,, , d(3,4) = 3,, , d(2,4) = 1,, , d(8,5) = 5, , Eccentricity: The eccentricity E(v) of a vertex ‘v’ in a graph G is the distance from ‘v’ to, the farthest vertex in G. It is denoted by E(v). i.e., E(v)=max d(v,vi), Example- 1:, , Eccentricity from:, (A, A) = 0, (A, B) = 1, (A, C) = 2, (A, D) = 1 , Maximum value is 2,, So, Eccentricity E(A)is 2

Page 81 :
MATHEMATICS, , GRAPH THEORY, , Similarly, E(B) = 1, E(C) = 2, E(D) = 1, Example- 2:, , E(v)=max d(v,vi), d(1,1) = 0, d(1,2) = 1, d(1,3) = 1, d(1,4) = 2, d(1,5) = 2, d(1,6) = 2, d(1,7) = 3,, d(1,8) = 3, d(1,9) = 3, Therefore, E (1) =max d (1, vi) = 3, Similarly, Eccentricity of 2,3,4,5,6,7,8 & 9 can be found., , Centre: A vertex with minimum eccentricity in graph G is called the Center of G., , Center: A, , a, , E(a)=2, E(b)=1, , d, , b, , E(c)=2 & E(d)=2, , c, , Center: b

Page 82 :
MATHEMATICS, , GRAPH THEORY, , Radius of Graph: A radius of the graph exists only if it has the diameter. The minimum, among all the maximum distances between a vertex to all other vertices is considered as the, radius of the Graph G. It is denoted as r(G)., , OR, , The eccentricity of a center vertex in a tree is the radius of a tree., , Radius: 2, All available minimum radius: BC → CF, BC → CE, BC → CD, BC → CA, , Diameter of graph: The diameter of graph is the maximum distance between the pair of, vertices. It can also be defined as the maximal distance between the pair of vertices. Way to, solve it is to find all the paths and then find the maximum of all., , BC → CF → FG, Diameter: 3., Problems:, Problem-1: For the given tree below find distance, eccentricity, and center., , a, d, , b, c

Page 83 :
MATHEMATICS, , GRAPH THEORY, , Solution:, , Distance : d(a,b)= 1, , Eccentricity: E(a)=2, , d(a,c)= 2, , E(b)=1, , d(a,d)= 2, , E(c)=2, , Centre: b, , E(d)=2, Problem-2: For the given tree below find center, radius and diameter., , c, , a, , b, , d, , e, , Solution:, E(a)=4, E(b)=3, E(c) =3, E(d)=2, E(e)=3, E(f)=4, Centre = d, Radius = 2, Diameter = 4, , Exercise:, 1) Consider the tree T, given below, , Label the vertices of T appropriately and find the centre and diameter of T., , f

Page 84 :
MATHEMATICS, , GRAPH THEORY, , 2) Find the eccentricity of all vertices in the graph G given below and also mark the, center, radius and diameter of G., , 3) Find the eccentricity of all vertices in G given below and also mark the center of G., , 4) Prove that the distance between vertices of a connected graph is a metric., 5) Prove that every tree has either one or two centers., 6), , Find the diameter of the following graphs., a) Kn. b) Kr, s., , c) Cn., , d) Wn., , e) Pn., , 7) For each of the following statements, give a connected graph G = (V, E) and a vertex, u ∈ V that satisfies it., a) D(G) = D (G − u)., , b) D(G) < D (G − u)., , c) D(G) > D (G − u)., , Note: D(G) is the diameter of G., 8) Let G = (V, E) be a connected graph and v ∈ V., a) Give an example of a graph with the same radius and diameter., b) Give an example of a graph whose diameter is twice its radius., c) Prove that, for each graph G, r(G) ≤ D(G) ≤ 2r(G), where D(G) is the diameter of G.

Page 85 :
MATHEMATICS, , GRAPH THEORY, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 86 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Spanning Trees, A spanning tree T of an undirected graph G is a subgraph of it and is a tree which includes all, of the vertices of G. Hence, a spanning tree does not have cycles and it is connected. OR, Let G be a connected graph. A spanning tree in G is a subgraph of G that includes all the, vertices of G and is also a tree. The edges of the trees are called branches., Note:, ❖ In general, a graph may have several spanning trees, but a graph that is not connected, will not contain a spanning tree., ❖ Every connected and undirected Graph G has at least one spanning tree., For example, consider the following graph G, , The three spanning trees G are:

Page 87 :
MATHEMATICS, , GRAPH THEORY, , Note: We can find a spanning tree systematically by using either of two methods., 1) Cutting-down Method, 2) Building-up Method, Cutting-down Method, •, , Start choosing any cycle in G., , •, , Remove one of cycle's edges., , •, , Repeat this procedure until there are no cycle left., , For example, given the graph G., , Graph ‘G’, , We remove the edge a-c which destroy the cycle a-d-c-a in the above graph and we get, , We remove the edge c-b, which destroy the cycle a-d-c-b-a in the above graph and we get, , We remove the edge e-c, which destroy the cycle d-e-c-d in the above graph and thus, obtained the following spanning tree.

Page 88 :
MATHEMATICS, , GRAPH THEORY, , Building-up Method, •, , Select edges of G one at a time. in such a way that no cycles are created., , •, , Repeat this procedure until all vertices are included., , For example, for the following graph G, , Graph ‘G’, , 1. Choose the edge a-b, , 2. Next choose the edge d-e as follows:, , 3. After that choose the edge e-c as follows:, , 4. Finally, we choose the edge c-b and thus obtain the following spanning tree., , Spanning Tree

Page 89 :
MATHEMATICS, , GRAPH THEORY, , Note: A bridge is an edge of a graph whose deletion increases the number of connected, components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle., Theorem: A graph is connected if and only if it has a spanning tree., Proof:, , Let G be a connected graph. Delete edges from G that are not bridges until we get a, , connected subgraph H in which each edge is a bridge. Then H is a spanning tree. On the other, hand, if there is a spanning tree in G, there is a path between any pair of vertices in G; thus G, is connected., Problems:, Problem-1: Find all the spanning trees for the following graphs., , Solution:

Page 90 :
MATHEMATICS, Note: A complete graph Kn has n(n-2) different spanning trees., Example: K3 has 3(3-2) =3 different spanning trees., K4 has 4(4-2) =16 different spanning trees., , Graph K3, , Graph K4, , Spanning Trees, , GRAPH THEORY

Page 91 :
MATHEMATICS, , GRAPH THEORY, , Exercise:, 1) How many spanning trees are possible from complete graph?, 2) Consider the following graph G. Give the number of spanning trees in G., , 3) Sketch all spanning trees of the given graph., , 4) Consider the graph G given below and obtain any three spanning trees from G., , 5) Give an example of a graph that has exactly 7 different spanning trees. Note, it, acceptable for some or all of these spanning trees to be isomorphic. [Hint: there is an, example with 7 edges.), 6) Prove that every connected graph which is not itself a tree must have at last three, different (although possibly isomorphic) spanning trees., 7) Unless it is already a tree, a given graph G will have multiple spanning trees. How, similar or different must these be?, a), , Must all spanning trees of a given graph be isomorphic to each other? Explain, why or give a counterexample.

Page 92 :
MATHEMATICS, , GRAPH THEORY, , b) Must all spanning trees of a given graph have the same number of edges? Explain, why or give a counterexample., , c) Must all spanning trees of a graph have the same number of leaves (vertices of, degree 1)? Explain why or give a counterexample., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 93 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Spanning Trees, Branch and chord, An edge in a spanning tree T is called a branch of T. An edge of G is not in a given spanning, tree T is called a chord (tie or link)., , Complement of tree, If T is a spanning tree of graph G, then the complement of T of G denoted by 𝑇 is the, collection of chords., It also called as chord set (tie set or cotree) of T., , Rank and Nullity:, A graph G with ‘n’ number of vertices, ‘e’ number of edges, and ‘k’ number of components, with the following constraints:, The number of components ‘k’ never cross ‘n’, so 𝑛 ≥ 𝑘 ⟹ 𝑛 − 𝑘 ≥ 0 and 𝑒 − 𝑛 + 𝑘 ≥ 0., •, , Rank 𝑟 = 𝑛 − 𝑘, , •, , Nullity 𝜇 = 𝑒 − 𝑛 + 𝑘 (Nullity also called as Cyclomatic number or first betti number)

Page 94 :
MATHEMATICS, , GRAPH THEORY, , •, , Rank of G = number of branches in any spanning tree of G, , •, , Nullity of G = number of chords in G, , Rank + Nullity = 𝑒 = number of edges in G, Example-1:, , Graph G1, , Spanning tree of G1, Rank of G1, r = Number of branches in any spanning tree of G1., Rank, r = 4., Nullity of G1, 𝜇 = number of chords in G1., Nullity, 𝜇 = 3., , Example-2: Graph ‘G’ that has 3 components

Page 95 :
MATHEMATICS, , GRAPH THEORY, , In the above Graph, we have, n = 11, e = 13, k = 3., Rank of G, r = n - k = 11 - 3 = 8., Nullity of G, 𝜇 = e – n + k = 13 – 11 + 3 = 5., Spanning trees in a weighted graph, A spanning tree in a graph G is a minimal subgraph connecting all the vertices of G. If G is a, weighted graph, then the weight of a spanning tree T of G is defined as the sum of the, weights of all the branches in T., A spanning tree with the smallest weight in a weighted graph is called a shortest spanning, tree (shortest-distance spanning tree or minimal spanning tree)., Degree-constrained shortest spanning tree, A shortest spanning tree T for a weighted connected graph G with a constraint 𝑑(𝑣i) ≤ 𝑘 for, all vertices in T. for k=2, the tree will be Hamiltonian path., , Exercise:, 1) Write the complement of a graph given below., , 2) Draw a connected graph G and find two spanning trees T1 and T2 of G such that the, distance (T1, T2) = 3. Find the branch set, chord set, rank and nullity of T1.

Page 96 :
MATHEMATICS, , GRAPH THEORY, , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., , -------------------END-------------------

Page 97 :
MATHEMATICS, , GRAPH THEORY, , UNIT - 1 - Basics of Graph Theory, Minimal Spanning Trees, A minimum spanning tree (minimum weight spanning tree) is a subset of the edges of a, connected, edge-weighted undirected graph that connects all the vertices together, without, any cycles and with the minimum possible total edge weight. i.e., it is a spanning tree whose, sum of edge weights is as small as possible., Example 1:, , w(T) = 10, Example 2:, , 2, 1, , 3, , 24, , 4, 23, , 6, , 6, 5, , 16, , 5, , 8, , 11, , 4, 7, , 14, , 10, , 7, , 9, , 18, , 8, , 21, , G = (V, E), 3, , 2, 1, , 4, , T = (V, F), , 9, , 6, , 6, 5, 8, , 7, , 5, , 11, , w(T) = 50, , 4, 7, , 8

Page 98 :
MATHEMATICS, , GRAPH THEORY, , Minimum Spanning Tree (MST) Computation, Kruskal's Algorithm, Kruskal's algorithm is an algorithm that finds a minimum spanning tree for a connected, weighted graph. It finds a tree of that graph which includes every vertex and the total weight, of all the edges in the tree is less than or equal to every possible spanning tree., Algorithm, •, , Step 1 − Arrange all the edges of the given graph G(V,E) in ascending order as per, their edge weight., , •, , Step 2 − Choose the smallest weighted edge from the graph and check if it forms a, cycle with the spanning tree formed so far., , •, , Step 3 − If there is no cycle, include this edge to the spanning tree else discard it., , •, , Step 4 − Repeat Step 2 and Step 3 until (V−1) number of edges are left in the, spanning tree., , Problems:, 1. Find a minimum spanning tree for the following graph G using Kruskal’s algorithm.

Page 99 :
MATHEMATICS, , GRAPH THEORY, , Solution: From the above graph we construct the following table and rearrange it in the, ascending order with respect to Edge weight –, , Edge, , Vertex, , Edge, , Edge, , Vertex, , Edge, , No, , Pair, , Weight, , No, , Pair, , Weight, , E1, , (a, b), , 20, , E4, , (b, c), , 1, , E2, , (a, c), , 9, , E7, , (c, d), , 2, , E3, , (a, d), , 13, , E8, , (d, e), , 3, , E4, , (b, c), , 1, , E5, , (b, e), , 4, , E5, , (b, e), , 4, , E6, , (b, f), , 5, , E6, , (b, f), , 5, , E2, , (a, c), , 9, , E7, , (c, d), , 2, , E3, , (a, d), , 13, , E8, , (d, e), , 3, , E9, , (d, f), , 14, , E9, , (d, f), , 14, , E1, , (a, b), , 20

Page 100 :
MATHEMATICS, , GRAPH THEORY, , Since we got all the 5 edges in the last figure, we stop the algorithm and this is the minimal, spanning tree and its total weight is (1+2+3+5+9) =20.

Page 103 :
MATHEMATICS, , GRAPH THEORY, , After the 5th iteration: Minimal Spanning Tree T. W(T)=8, , V2, , 3, , V3, , 1, , 2, , V1, , V6, , 1, , V4, , V5, , Prim's Algorithm, Prim's algorithm, discovered in 1930 by Mathematicians, Vojtech Jarnik and Robert C. Prim,, is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It, finds a tree of that graph which includes every vertex and the total weight of all the edges in, the tree is less than or equal to every possible spanning tree. Prim’s algorithm is faster on, dense graphs., , Algorithm, •, , Initialize the minimal spanning tree with a single vertex, randomly chosen from the, graph., , •, , Repeat steps 3 and 4 until all the vertices are included in the tree., , •, , Select an edge that connects the tree with a vertex not yet in the tree, so that the, weight of the edge is minimal and inclusion of the edge does not form a cycle., , •, , Add the selected edge and the vertex that it connects to the tree.

Page 104 :
MATHEMATICS, , GRAPH THEORY, , Problems:, 1. Find a minimum spanning tree for the following graph G using Prim’s algorithm., , Solution:, Here we start with the vertex ‘a’ and proceed.

Page 105 :
MATHEMATICS, , GRAPH THEORY, , This is the minimal spanning tree and its total weight, is (1+2+3+5+9) =20.

Page 106 :
MATHEMATICS, , GRAPH THEORY, , 2. Find a minimum spanning tree for the following graph G using Prim’s, algorithm., , Applications of MST:, MST is central combinatorial problem with diverse applications, •, , Designing physical networks, •, , •, , Approximate solutions to NP-hard problems, •, , •, , telephone, electrical, hydraulic, TV cable, computer, road, , metric TSP (Traveling Salesman Problem), Steiner tree, , Indirect applications.

Page 107 :
MATHEMATICS, , GRAPH THEORY, , •, , describing arrangements of nuclei in skin cells for cancer research, , •, , learning salient features for real-time face verification, , •, , modeling locality of particle interactions in turbulent fluid flow, , •, , reducing data storage in sequencing amino acids in a protein, , Exercise:, 1) Discuss an algorithm to find the minimum spanning tree of a graph G with an, example., 2) Find a minimum spanning tree of the following graph., , 3) Find a minimum spanning tree in the graph below., , 4) Apply Kruskal’s procedure to find the minimum spanning tree from the following, graph G.

Page 108 :
MATHEMATICS, , GRAPH THEORY, , 5) Write Kruskal’s algorithm to find the minimum spanning tree of a graph G. Apply it, to find the MST for the graph given below., , References:, 1) Graph Theory with Applications to Engineering and Computer Science by Narsingh, Deo., 2) Graph Theory by Udit Agarwal and Umesh pal Singh., 3) Graph Theory by Frank Harary., 4) Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 5) Discrete and Combinatorial Mathematics by Ralph P.Grimaldi, 6) Algorithm Design by Jon Kleinberg.Evatardos, 7) A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan., 8) Discrete Mathematical Structures by Dr. N. G. Goudru., 9) Invitation to Graph Theory by S. Arumugam and S. Ramachandran., 10) Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH., 11) Robin J. Wilson, Introduction to Graph Theory, Pearson Education., -------------------END-------------------