Graph Theory Tutorial - Sankalchand Patel College of Engineering

FACULTY OF ENGINEERING & TECHNOLOGY SANKALCHAND PATEL COLLEGE OF ENGINEERING VISNAGARB. B.TECH. SEMESTER –III CE , IT & AI&DS...

FACULTY OF ENGINEERING & TECHNOLOGY SANKALCHAND PATEL COLLEGE OF ENGINEERING VISNAGARB. B.TECH. SEMESTER –III CE , IT & AI&DS UNIT 3: GRAPH THEORY 1) Define (1) simple graph (2) multi graph (3) Isolated vertex (4) Pendent vertex (5) Size of a graph (6) in-degree of a vertex (7) out-degree of a vertex (8)null graph (9) degree of a vertex (10) trivial graph (11) complete graph (12) bipartite graph (13) sub graph (14) Weighted Graph (15) Cyclic graph Illustrate each with an example. 2) How many edges has each of the following graphs (1) 𝐾5 (2) 𝐾6 (3) 𝐾2,3 (4) 𝐾3,3. 3) 𝐷𝑟𝑎𝑤 𝐾2,3 𝑎𝑛𝑑 𝐾3,3 𝑔𝑟𝑎𝑝ℎ𝑠. 4) Draw a complete bipartite graph, which is not regular. 5) Draw 𝐾5 and 𝐾6 𝑔𝑟𝑎𝑝ℎ𝑠 6) Find the number of edges in r-regular graph with n-vertices. 7) Does 3- regular graph with 5-vertices exist ? 8) Identify Isolated vertex/vertices from the following graph. 9) What do you mean by degree of a vertex? What are the degrees of an isolated vertex and a pendant vertex? 10) Define regular graph. Can a regular graph be a complete graph? 11) Define graph isomorphism and give an example of two isomorphic graphs 12) How many nodes are necessary to construct a graph with exactly 8 edges in which each node is of degree 2. 13) State and prove the hand-shaking theorem. 14) Find the number of edges in G if G has (1) 16 vertices each of degree 2. (2) 3 vertices of degree 4, 2 vertices of degree 3 and other 4 vertices of degree 1. 15) Prove that any graph has even number of odd vertices. 16) Does there exists a 4- regular graph with 6 vertices? If so, construct the graphs. 17) Does there exists a regular graph of degree 5 on 9 vertices? If so, construct the graphs. 18) Determine the number of edges in a graph with 6 vertices,2 vertices of degree 4 and 4 vertices of degree 2.draw two such graphs.  FACULTY OF ENGINEERING & TECHNOLOGY SANKALCHAND PATEL COLLEGE OF ENGINEERING VISNAGARB. B.TECH. SEMESTER –III CE , IT & AI&DS 19) Draw the undirected graph G = (V, E)where, V = {a, b, c, d, e}and E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 } and its incidence relation given as: e1 = (a, b), e2 = (a, b), e3 = (b, c), e4 = (c, d), e5 = (b, b), e6 = (a, d) & e7 = (e, d). 20) Define Isomorphic Graphs. Determine whether the following graphs are isomorphic or not 21) Check whether the following graphs are isomorphic. 22) Verify that the sum of the in-degrees, the sum of the out-degree of the vertices and the number of edges in the following graphs are equal. Figure 1 Figure 2  FACULTY OF ENGINEERING & TECHNOLOGY SANKALCHAND PATEL COLLEGE OF ENGINEERING VISNAGARB. B.TECH. SEMESTER –III CE , IT & AI&DS 23) Find the in-degree and out-degree of each vertex in the graph G with directed edges shown in Figure 24) Define converse of a digraph and find it for given graph G. 25) Define node deleted sub graph and edge deleted sub graph. Also find sub graphs from the given graph G by deleting (I) node 𝑣1 (𝐺 − {𝑣1 }) (II) Edge 𝑒4 (G − {𝑒4 }). 26) Consider the following graphs: Determine the degree of each node and verify Handshaking theorem. *****