KTU Graph Theory 2019 Model Question Paper Answer key Solved

KTU Graph Theory Model Question Paper Solved Answer key 2019

Graph Theory is a KTU 2019 Scheme course for S4 CSE students. Here we provide the solved answer key for the Model question paper provided in the syllabus. Why should we solve the model question paper? Graph theory is introduced in the 2019 scheme of KTU. So it is important to solve the model questions in the new pattern. MAT 206 begins with the basics of mathematical logic and logical thinking. 

Here we present model questions that cover many topics related to the field of graph theory. In particular, it incorporates a number of algorithmic techniques for determining the structure of graphs and their algorithm representations of the real world. In particular, they will look at graphs that represent logical details and build algorithms on the basis of the mathematical structure of this information. 

Before moving to the Answer key we can understand the main aim of this course is to give an in-depth understanding of basic results and facts about graphs and their representations in the light of the central role played by graphs in applied problems.

Board KTU
Scheme 2019 New Scheme
Year Second Year
Semester S4  Computer Science
Subject MAT 206 | Graph Theory Solved Model Question Paper
Type Model Question Paper Solved
Category KTU S4 Computer Science 

To fulfil our mission, we try hard to give you qualified and updated study materials. Here is the answer key for the KTU Graph Theory MODEL QUESTION PAPER in the syllabus. Study well & don't forget to share with your friends...  

--------------------------------------------------------

Graph Theory Model Question Paper Solved | 2019 Scheme

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY FOURTH SEMESTER B.TECH DEGREE EXAMINATION

Course Code: MAT 206
Course name: Graph Theory

Max Marks: 100                                                                                                           
Duration: 3 Hours

PART-A

(Answer All Questions. Each question carries 3 marks)

1. Construct a simple graph of 12 vertices with two of them having degree 1, three having degree 3 and the remaining seven having degree 10.   (3)

Ans: 

Sum of degree = 2e

Two of them have degrees  1 
Three of them have degrees  3
Seven of them have degrees  10

So,    2×1+3×3+7×10 = 2e
         2+9+70 = 2e
         81 = 2e
         e = 81/2
            = 40.5
The number of edges 40.5 is not possible, so construction is not possible  

2. What is the largest number of vertices in a graph with 35 edges, if all vertices are of degree at least 3?  (3)

Ans: 

Here  Sum of degree = 2e
          Sum of degree = 2 × 35 = 70
All vertices having a degree of at least 3 means    
KTU Graph Theory mat 206 Model Question Paper Solved Answer key 2019

vertices having degree 3 and 1 vertex having degree 4
So the number of vertices = 22+1
                                          = 23


3. Define an Euler graph. Give an example of an Eulerian graph that is not Hamiltonian  (3)

Ans: 

Euler Graph 

A connected graph G is said to be Euler, If there is a closed trial includes Every edge of the graph.
Eg: Euler but not Hamiltonian
KTU Graph Theory mat 206 Model Question Paper Solved Answer key 2019

4. Give an example of a strongly connected simple digraph without a directed Hamiltonian path.  (3)

Ans:  Out of Syllabus

5. What is the sum of the degrees of any tree of n vertices? (3)

Ans:  Sum of the degree of any tree = 2^(n-1)

6. How many spanning trees are there for the following graph (3)

KTU Graph Theory mat 206 Model Question Paper Solved Answer key 2019
Ans:   Spanning trees are :

 
How many spanning trees are there for the following graph (3)

7. Show that in a simple connected planar graph G having V-vertices, E-edges, and no triangles E <= 3V - 6.    (3)

Ans: 

If G is simple

     2E ≥ 3F

  = 2E / 3 ≥ F

By Euler's Formula

      V+F-E = 2

      V- 2E / 3  - E  ≥ 2

      3V + 2E-3E ≥ 6

     E ≤ 3V – 6

Hence It Proved


8. Let G be the following disconnected planar graph. Draw its dual G* and the dual of the dual (G*)*       (3)
Graph Theory Solved Model Questions Paper 2019 Scheme | Kerala Notes
Ans: 

Let G be the following disconnected planar graph. Draw its dual G* and the dual of the dual (G*)*       (3)

9. Consider the circuit matrix B and incidence matrix A of a simple connected graph whose columns are arranged using the same order of edges. Prove that every row of B is orthogonal to every row of A? (3)

Ans:    Out of Syllabus

10. A graph is critical if the removal of any one of its vertices (and the edges adjacent to that vertex) results in a graph with a lower chromatic number. Show that Kn is critical for all n > 1. (3)

Ans:   Suppose  K3
A graph is critical if the removal of any one of its vertices (and the edges adjacent to that vertex) results in a graph with a lower chromatic number. Show that Kn is critical for all n > 1. (3)
Chromatic number = 3
By removal of one vertex, chromatic number = 2
So k3 is critical
Kn is Critical For n > 1

PART-B 

(Answer any one question from each module. Each question carries 14 Marks)

11. a) Prove that any simple graph with at least two vertices has two vertices of the same degree. (6)

b) Prove that in a complete graph with n vertices there are (n-1)/2 edge-disjoint Hamiltonian circuits and n >= 3    (8)

Ans 11 (a): 

Ans 11 (b): 


OR

12. a) Determine whether the following graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic or not. Give justification.  (6)

Graph Theory Solved Model Questions Paper 2019 Scheme | Kerala Notes

b) Prove that a simple graph with n vertices and k components can have at most (n-k) (n-k+1)/2 edges        (8)

Ans 12 (a): 

Determine whether the following graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic or not. Give justification.  (6)
Ans 12 (b):


 
13 a) Let S be a set of 5 elements. Construct a graph G whose vertices are subsets of S of size 2 and two such subsets are adjacent in G if they are disjoint.
        i. Draw the graph G.
       ii. How many edges must be added to G in order for G to have a Hamiltonian cycle? (8)

b) Let G be a graph with exactly two connected components, both being Eulerian. What is the minimum number of edges that need to be added to G to obtain an Eulerian graph? (6)

Ans 13 (a): 

Determine whether the following graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic or not. Give justification.  (6)
Ans 13 (b): 



OR

14 a) Show that a k-connected graph with no Hamiltonian cycle has an independent set of size k + 1. (8)

b) i. Let G be a graph that has exactly two connected components, both being Hamiltonian graphs. Find the minimum number of edges that one needs to add to G to obtain a Hamiltonian graph.

ii. For which values of n the graph Qn (hyper-cube on n vertices) is Eulerian. (6)

15 a) A tree T has at least one vertex v of degree 4, and at least one vertex w of degree 3. Prove that T has at least 5 leaves. (5)

b) Write Dijkstra’s shortest path algorithm. Consider the following weighted directed graph G(9)

Graph Theory Solved Model Questions Paper 2019 Scheme | Kerala Notes

Find the shortest path between a and every other vertex in G using Dijkstra’s shortest path algorithm.

Ans 15 (a):

Let T be a tree
Suppose V has degree  4
               W has degree 3
Write Dijkstra’s shortest path algorithm. Consider the following weighted directed graph G

V have degree 4 ⟹ V connected 4 edges
W have degree 3 ⟹ W connected 3 edges
     ⟹ Minimum, it has 6 edges
     ⟹ at least 5 leaves

Ans 15 (b):

 Dijkstra's Algorithm
This Algorithm is used to find the shortest distance from one vertex to all other vertexes

Step 1: Draw graph with weighted edge
Step 2: Fix a starting vertex
Step 3: Mark distance on initial vertex as ' 0 ' and all other vertexes as ' '
Step 4: Update all vertex with the shortest distance from the initial vertex

if d(u) + c(u,v) < d(v) then
d(u) + c(u,v) = d(v)
Step 5: Continue this process till all vertex updates
 

KTU Graph Theory mat 206 Model Question Paper Solved Answer key 2019


OR

16 a) Define pendent vertices in a binary tree? Prove that the number of pendent vertices in a binary tree with n vertices is (n+1)/2. (5)

b) Write Prim’s algorithm for finding minimum spanning tree. Find a minimum spanning tree in the following weighted graph, using Prim's algorithm.   (9)

Determine the number of minimum spanning trees for the given graph

Determine the number of minimum spanning trees for the given graph.


Ans 16 (a):

The leaf vertex (also the hanging vertex) is a vertex with one degree. ... The simple vertex is that its neighbors form a cluster: all two neighbors are close by. A universal vertex is the vertex next to all the other vertex in the graph.

The number of vertices of odd degree in an undirected graph is even,(N-1) is even. Therefore, n is odd. Let p be the number of pendant vertices.

2+p+3(n- p-1) = 2(n-1)


or, 3n-2n-3+4 = 2p


or, 2p = n+1


or, P = (n+1)/2

Hence, the number of pendant vertices is (n+1)/2.

Ans 16 (b): 

Primes Algorithm
This algorithm is used to find the minimum spanning tree of a graph

Step 1: Draw graph with weighted edges 
Step 2: Fix a starting vertex
Step 3: Mark an edge with minimum weight from starting index
Step 4: Mark another Edge with minimum weight from the second vertex and previous vertex
Step 5: Continue this process till all vertex occurs once and without forming cycles

Determine the number of minimum spanning trees for the given graph



17 a) i. State and prove Euler's Theorem relating the number of faces, edges and vertices for a planar graph.
         ii. If G is a 5-regular simple graph and |V| = 10, prove that G is non-planar. (9)

b) Let G be a connected graph and e an edge of G. Show that e is a cut-edge if and only if e belongs to every spanning tree. (5)

Ans 17 (a):  (i)

Euler's Theorem
If G is a connected plane graph with V- vertices, E- edges, F- face then V+F-E=2

Proof

If G is a tree

F=1
E=v-1
Then V + F - E   = 2  
                           = V + 1- ( v - 1)        
                           = V-V+2
                           = 2
It is true

If G is not a tree

By mathematical induction, Assume it is true for V vertices E edges F faces
ie; V + F - E = 2 
Then we have to prove, It is true for E-1 edges then 

E = E - 1
F = F - 1
V = V

Then V + F - E = 2  
                         = V+(F-1)-(E-1)
                         = V+F-1-E+1
                         = V+F-E 
                         = 2

Hence it is True and it is prooved

OR

18 a) State Kuratowski's theorem, and use it to show that the graph G below is not planar. Draw G on the plane without edges crossing. Your drawing should use the labelling of the vertices given. (9)

State Kuratowski's theorem, and use it to show that the graph G below is not planar. Draw G on the plane without edges crossing. Your drawing should use the labelling of the vertices given

b) Let G be a connected graph and e an edge of G. Show that e belongs to a loop if and only if e belongs to no spanning tree. (5)

Ans 18 (a):

Kuratowski's Theorem 
A graph is planar if and only if it does not contain a subgraph homeomorphic to K5 or K3

Proof:
Given graph is isomorphic to K5. So not Planar.
K5
State Kuratowski's theorem, and use it to show that the graph G below is not planar. Draw G on the plane without edges crossing. Your drawing should use the labelling of the vertices given


Ans 18 (b):  Out Of Syllabus

19 a) Define the circuit matrix B(G) of a connected graph G with n vertices and e edges with an example. Prove that the rank of B(G) is e-n+1  (7)

b) Give the definition of the chromatic polynomial PG(k). Directly from the definition, prove that the chromatic polynomials of Wn and Cn satisfy the identity PWn(k) = k PCn-1 (k – 1).  (7)

Ans 19 (a): 

Circuit Matrix
A Circuit matrix is a m x n matrix where 
n = No of circuit
m = No of edges
It is defined as Cij =  1, If jth edge belongs to the ith circuit
                              =  0, Otherwise      
Proof
The rank of the circuit matrix is e-n+1 
(e - number of edges, v - number of vertices)

Let's take 
A = incidence matrix of G [rank=n-1] 
B =  Circuit matrix of G  


We have A.B' ≅  O (mod 2)
By 'Sylvester's theorem 

rank (A) +rank (B) = e
rank (B)     e - rank (A) 
rank (B)     e -  (n-1) 
rank (B)     e - n+1 ------------ 1 

For any connected graph 

rank(B)    ≥   e-n+1        ------------ 2  

            From 1 and 2  

rank( B) = e-n+1

Ans 19 (b): 

Chromatic Polynomial 
Chromatic Polynomial counts the number of Graph covering as a function of the number of colours 

OR

20 a) Define the incidence matrix of graph G with an example. Prove that the rank of an incidence matrix of a connected graph with n vertices is n-1.  (4)


b) i. A graph G has chromatic polynomial PG(k) = k4-4k3+5k2-2k. How many vertices and edges does G have? Is G bipartite? Justify your answers.

ii. Find a maximum matching in the graph below and use Hall's theorem to show that it is indeed maximum.    (10)

Graph Theory Solved Model Questions Paper 2019 Scheme | Kerala Notes

Ans 20 (a), (b):

Define the incidence matrix of graph G with an example. Prove that the rank of an incidence matrix of a connected graph with n vertices is n-1.  (4)   b) i. A graph G has chromatic polynomial PG(k) = k4-4k3+5k2-2k. How many vertices and edges does G have? Is G bipartite? Justify your answers.


KTU Graph Theory mat 206 Model Question Paper Solved Answer key 2019


--------------------------------------------------------

You May Like :

We hope the given KTU S4 MAT 206 Graph Theory Solved Model Question based on the 2019 scheme will help you in your upcoming Examinations. If you like this share it with your friends.

"Share KeralaNotes.Com with your friends"

We have solved the Graph theory exemplar question paper in the syllabus for S4 CSE students. Explain all the questions as asked in the sample question paper for this KTU 2019 syllabus lesson. Graph Theory model question paper is for CSE S4 students preparing for the KTU 2019. Examination course. Includes all the chapters in the KTU 2019 syllabus Theory. preparing for the KTU 2019 exam in Graph theory, this questionnaire will help you. Graph Theory is one of the most important topics in the KTU syllabus. Model question paper question bank of graph theory will definitely help you to score good marks with the Answer key provided

If you have any queries regarding the KTU S4 Computer Science (CSE) Study Materials, drop a comment below and we will get back to you at the earliest.

Keralanotes.com      Keralanotes.com      Keralanotes.com      Keralanotes.com      Keralanotes.com      
To Top

Join Our Whatsapp and Telegram Groups now...