Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 6th Semester (Sixth Semester) 2014-2015 Graph Theory Question Paper
lllllljlllljilllsllllljllllllllljlllllll ECSSOS
(Following Paper ID and Roll N o. to be ?lled in your Answer Book
PAPER ID : 113606 '
Roll No.
B. Tech.
(SEM. VI) THEORY EXAMINATION, 2014-15
' GRAPH THEORY
Time : 2 Hours] [Total Marks : 50
Note : Attempt all questions.
1 Attempt any four parts : 4X3=12
(a) State a necessary and suf?cient condition when
a graph G is disconnected. Illustrate with an
example.
(b) State and verify :
(1) Which complete bipartite graphs are
Hamiltonian?
(ii) Which complete graphs are Eulerian?
(iii) Is Peterson graph Hamiltonian?
(c) Let T be a tree with 50 edges. The removal of
ceftain edge from T yields two disjoint trees T1
and T2 . Given that the number of vertices in
T1 equals the number of edges in T2 . Determine
the number of vertices and number of edges in
T1 and T2.
113606] 1 [ Contd...
(d) State and prove Handshaking Lemma. . 3 ttempt any two parts. : ' 2X6=12
(e) State properties of cut-sets and discuss their (a) De?ne incidence matrix of a graph withan
applications, example. Also prove that theer of an incidence
(f) De?ne the vector space associated with a graph. matrix Of a graph Wlth n vertlces 15 11'1-
(b) De?ne isomorphic graphs. Show that the following
2 Attempt any two parts ; 2X6=12 ? graphs are lSOHlOI?phJC.
(a) For the given graph ?nd out the vectors in the
circuit subspace and cut-set subspace. Also ?nd
out the basis for each subspace.?
. ./ (0) Let T be a graph with n vertices. Then prove
W' L ? . . .
J that the followmg statements are equxvaient .
(b) State and prove Euler's formula for planar graphs. V (1) T is a tree
Also show that in a simple 0001160th planar graph (1i) T contains no cycles and has n-l edges
with 6 vertices and 12 edges each of the regions (1h) T is connected has n-] edges
is bounded by 3 edges.
. .. (N) T is connected and each edge is a bridge
(0) Wnte the steps of Dljakstra's algorithm and use
it to ?nd the shortest path in the following graph (V) Any two vertices Of T are connected by
- exactly one path
from vertices O to 4. , ?
(vi) T contains no cycles, but the addition of
any new edge creates exactly one cycle.
4 Attempt any four parts : 4X3.5=l4
(a) What do you mean by Geometrical dual of a
graph? Prove that the complete graph with 4
vertices is self dual. -
113606] 2 [Contd... 113606] 3 ' [Contd...
(b) State and prove four color conjecture.
(c) Using Kruskal's algon'thm to ?nd the minimal
spanning tree of the following graph.
(d) What are Kuratowski's Two Graphs ? Prove that
these graphs are non?planar.
(e) Find : .
(1) The chromatic polynomial of sz.
(1i) Three graphs with chromatic polynomial
. x5?4x4+6x3?4x2+7t
(f) Prove that a binmy tree with n vertices has
n-l edges.
113606] 4 [ 5000 1
This post was last modified on 29 January 2020