Anna University Regulation 2013 Computer Science and Engineering (CSE) CS6702 GTA Important Questions for all 5 units are provided below. Download link for CSE 7th SEM CS6702 Graph Theory & Applications Answer Key is listed down for students to make perfect utilization and score maximum marks with our study materials.

Part B

1 i) In a complete graph having odd number of vertices, how many edge disjoint Hamiltonian circuits exist? Explain 6

ii) State the two theorems to check if a connected graph G is Eulerian. Explain with proof 6

iii) Find a path of length 9 and a circuit of length 8 in the Peterson graph. 4

2 i) Illustrate the search algorithm than can be employed to find the components or blocks in a graph, with an example 10

ii) Explain the following theorem with proof “In a graph the number of the vertices with odd degree is even” 6

3 Give the proof for the following theorem i) If a graph has exactly two vertices of odd degree, there must be a path joining these two vertices. 4

ii) A connected graph is an Euler graph if and only if every vertex has even degree 6

iii) A connected graph is an Euler graph if and only if it can be decomposed into circuits 6

4 i) Show that the ring-sum of any two cut-sets in a graph is either third cut-set or an edge disjoint union of cut-sets. 8

ii) Show that a vertex v in a connected graph G is a cut vertex if and only if there exists two vertices x and y in G such that every path between x and y passes through v 4

iii) Find |v| for the following graph or multigraphs G.

a) G has nine edges and all vertices have degree 3

b) G has ten edges with two vertices of degree 4 and all other of degree 3 (4)

5 i) Give the explanation to prove any undirected graph has an even number of vertices of odd degree 8

ii) Give the explanation to prove that the following graphs G and H are not isomorphic 8

6 Give the explanation to prove that a connected graph G is Eulerian if and only if all the vertices are of even degree 16

7 Prove that graph G is disconnected if and only if its vertex set V can be partitioned into two nonempty subsets V1 and V2 such that there exists no edge in G whose one end vertex is in V1 and the other in V2 16

8 i)Determine whether the following graphs G and H are isomorphic. Give reason 8

ii) Give the proof for the following theorem : A given connected graph G is an Euler graph if and only if all the vertices of G are of even degree 8

9 i) Prove that a simple graph with n vertices and k components cannot have more than 2 (n  k)(n  k 1) edges 8

ii) Which of the following simple graphs have a Hamilton Circuit or if no, a Hamilton Path? 8

10 i)Define isomorphism of graphs. Show that no two of the following three graphs a shown in figure are isomorphic.

ii) Define Euler circuit. Discuss Konigsberg bridge problem 8

11 i)In the undirected graph Find a) an a-a circuit of length 6 b) An a-a cycle of maximum length 8

ii) Seven students of a class have lunch together at a circular table. Using Hamilton cycles, Predict the minimum number of days required for each of them to sit next to every member of the class. 8

12 i) If G is an undirected graph with n vertices and e edges, let min {deg(v)} G vJ and max {deg(v)} ‘ vJ , then prove that G d 2(e / n) d ‘ 8

ii) Define Hamilton cycle. How many edge-disoint Hamilton cycles exist in the complete graph with seven vertices? Also, Design the graph to show these Hamilton cycles. 8

13 i)Let G=(V,E) be the undirected graph in the following figure. How many paths are there in G from a to h? How many of these paths have length 5?

If you require any other notes/study materials, you can comment in the below section.

Search Terms

Anna University 7th SEM CSE GTA Important Questions