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 vJ and max {deg(v)} ‘ vJ , 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?
CS6702 GTA All units Important Questions – Download Here
If you require any other notes/study materials, you can comment in the below section.
Related Links
For CS6702 GTA Previous Year Question Papers – Click here
For CS6702 GTA Question Bank/2marks 16marks with answers – Click here
For CS6702 GTA Lecture Handwritten Notes – Click here
Search Terms
Anna University 7th SEM CSE GTA Important Questions
CS6702 Graph Theory & Applications Answer Key free download
Anna University CSE GTA Important Questions Regulation 2013
CS6702 Answer Key, GTA Unit wise Important Questions- CSE 7th Semester