**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

**Course Code:**MAT 206

**Course name:**Graph Theory

**Max Marks:**100

**Duration:**3 Hours

**PART-A**

**Ans:**

**Ans:**

**Ans:**

__Euler Graph__

**Eg:**Euler but not Hamiltonian

**Ans:**

**Out of Syllabus**

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

**Ans:**

**Spanning trees are :**

**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

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

**Ans:**

**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**

**Kn**is critical for all

**n > 1.**(3)

**Ans:**Suppose K3

**PART-B**

**(n-1)/2**edge-disjoint Hamiltonian circuits and

**n >= 3**(8)

**Ans 11 (a):**

**OR**

**G1 = (V1, E1)**and

**G2 = (V2, E2)**are isomorphic or not. Give justification. (6)

**n**vertices and

**k**components can have at most

**(n-k) (n-k+1)/2**edges (8)

**Ans 12 (a):**

**Ans 12 (b):**

**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)

**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):**

**OR**

**k + 1.**(8)

**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)

**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)

**G**. (9)

**Ans 15 (a):**

**T**be a tree

**V**has degree 4

**W**has degree 3

**V**have degree 4 ⟹

**V**connected 4 edges

**W**have degree 3 ⟹

**W**connected 3 edges

**Ans 15 (b):**

__Dijkstra's__

__Algorithm__**∞**'

**OR**

**n**vertices is

**(n+1)/2.**(5)

**Ans 16 (a):**

### 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__**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)

**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__

**Proof**

**If G is a tree**

**It is true**

**If G is not a tree**

**Hence it is True and it is prooved**

**OR**

**G**below is not planar. Draw

**G**on the plane without edges crossing. Your drawing should use the labelling of the vertices given. (9)

**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__**Proof:**

**K5**

**Ans 18 (b):**

**Out Of Syllabus**

**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)

**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__**j**th edge belongs to the

**i**th circuit

__Proof__**≅**O (mod 2)

**≤**e - rank (A)

**≤**e - (n-1)

**≤**e - n+1 ------------ 1

**≥**e-n+1 ------------ 2

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

**Ans 19 (b):**

__Chromatic Polynomial__**OR**

**G**with an example. Prove that the rank of an incidence matrix of a connected graph with

**n**vertices is

**n-1.**(4)

**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)

**You May Like :**

- KTU S4 CSE Graph Theory Notes
- KTU S4 CSE Computer Organization and Architecture Notes
- KTU S4 CSE Database Management System Notes
- KTU S4 CSE Operating System Notes
- KTU S4 CSE Design and Engineering Notes
- KTU S4 CSE Constitution Of India Notes

**drop a comment below**and we will get back to you at the earliest.