Madurai Kamraj University (MKU) 2006-1st Year M.C.A - -university exam paper

MCA 1st Year May 2006

Paper VI GRAPH THEORY

Time: 3 hours Maximum: 100 marks

PART A ans ALL ques.. (8 x five = 40 marks)

1. (a) Establish the relation
_
_Or
(b) If exp (at)

prove that exp(a1t) exp(a2t)=exp(a1+a2) t.

2. (a) If a graph has exactly 2 vertices of odd degree, prove that there must be' a path
joining these 2 vertices.
Or
(b) discuss the travelling-salesman issue.

3. (a) describe a Tree and prove that there is a unique path ranging from every pair of vertices in a
tree.
Or
(b) Prove that a graph is a tree if and only if it is minimally connected.

4. (a) Draw the 2 Kuratowski's graphs and state the properties common to these graphs.
Or
(b) Write a note on thickness and crossings in graphs.

5. (a) If B is a circuit matrix of a connected graph G with e edge arid n vertices, prove
that rank of B=e-n+1.
Or
(b) describe cut-set matrix C(G) and show that the rank of cut-set
matrix is equal to the rank of the incidence matrix.

6. (a)Prove that in a tree every vertex with degree greater than 1 is a cut vertex.
Or.
(b)
Prove that the vertex connectivity of any graph G can never exceed the edge connectivity
of G.

7. (a)Prove that an arborescence is a tree in which every vertex other than the root has an
in-degree of exactly one.
Or
(b) discuss the four-color conjecture.

8. (a) describe chromatic number and determine the chromatic number of the graph provided
beneath .
V2

V3 V5
V1

V4

Or
(b) Prove that every tree with 2 or more vertices is 2-chromatic.

PART B ans ALL ques.. (5 x 12 = 60 marks)

9. (a) describe Euler graph. Prove that a connected graph G is an Euler graph if and only if
all vertices of G are of even degree.
Or
(b) describe the terms eccentricity and center in a
tree. Prove that every tree has either 1 or 2 centers.
10. (a) describe a cut-vertex. Prove that every connected graph with 3 or more vertices
has at lowest 2 vertices that are not cut vertices.
Or
(b) Prove that a connected planar graph with n vertices and e edges has e - n + two regions.

11. (a) describe a bipartite graph. Prove that a graph is bipartite if and only if it contains no
circuit of odd lengths.
Or
(b) Prove that every complete tournament has a directed
Hamiltonian path. .

12. (a) Show that the cycle index of the induced pair group R3 is the identical as that of 83,
Or
(b) Prove that the maximum vertex connectivity 1 can achieve with a graph G on n
vertices and e edges (e = n -1) is the integral part of two e/n .
13. (a) discuss graph enumeration with Polya's theorem for simple graphs when n = three and
n = four .
Or
(b) Prove that there are (n -1)/2 edge disjoint Hamiltonian circuits in a complete
graph on n vertices if n - three is an odd integer.

Earning:   Approval pending.