Download SGBAU BSc 2019 Summer 6th Sem Mathematics Graph Theory Question Paper

Download SGBAU (Sant Gadge Baba Amravati university) BSc 2019 Summer (Bachelor of Science) 6th Sem Mathematics Graph Theory Previous Question Paper

AW-l 761
B.Sc. Part-lll (Scmester-Vl) Examination
MATHEMATICS
(Graph Theory)
Paper?Xll
Time : Three Hours] [Maximum Marks : 60
Note :?(1) Question No. l is compulsory and attempt it at once only.
(2_) Solve ONE question from each unit.
1. Choose the correct alternative in the following :
(i) A connected graph G is an Euler graph iff it can be decomposed into : 1
(a) Walks (b) Paths
(c) Cut sets (d) Circuits
(ii) A subgraph H = < Vl, EI > of a graph G = < V, E > is called a spanning subgraph
if : 1
(a) E,=? (b) vl=?
(c) VI = V (d) E1 = E
(iii) The concept of a tree was introduced by : l
(a) Euler (b) Hamiltonian
(c) Cayley (d) Kuratowski
(iv) If G be a circuitless graph with n vertices and k components then G has : 1
(a) n + l edges (b) n - 1 edges
(c) n + k edges (d) n ? k edges
(v) A graph can be embedded in the surface of a sphere iff it can be embedded in : l
(a) a plane (b) a circle
(c) a sphere (d) a straight line
(vi) A complete graph of five vertices is : 1
(a) Planar graph (b) Non-planar graph
(c) Null graph (d) Bipartite graph
(vii)Minimum number of linearly independent vectors that spans the vectors in a vector
space W0 is called : l
(a) Basis of vector space (b) Dimension of vector space
(c) Span (d) None of these
(viii) The dimension of the cutspace WS is equal to the rank of the graph and the number of
cutset vectors including 0 in Ws is : 1
(a) r (b) 2'
(c) 3' (d) r2
YBC 45329 1 (Could)

(ix) A row with all zeros in incidence matrix represents : 1
(X)
(a)
(b)
(p)
(a) Pendent vertex (b) Isolated vertex
(c) Odd vertex (d) Even vertex
If B is a circuit matrix of a connected graph G with n vertices and e edges then rank
of B is : 1
(a) c+n?1 (b)e~n?l
(c)c+n+1 (d) c?n-rl
L'NlT?I
De?ne (i) Simple graph, (ii) Degree of a vertex. Show that the maximum number of
edges in a simple graph of n vertices is 2%1). , 2+3
De?ne isomorphism between two graphs. Prove that any two :iimple connected graphs
with n vertices, all of degree two are isomorphic. 2+3
From the graph given below answer the following :
(i) Write the degree of each Vertex.
(ii) Which edges are incident with the vertex V3 ?
(iii) Write the adjacent vertices of Vv
(iv) Is the graph simple ?? Why ? l+l+l+2
(q) In a graph G there ethts a path from the vertex u to the vertcx v it?f there exists a walk
from u to v. 5
UNIT?Il
(a) Prove that following statements are equivalent :
(i) There is exactl) one path between every pair of vertices in G.
(ii) G is minimally connected graph. 5
(b) De?ne : (i) Binary tree. (ii) Rooted tree. Show that therc: are (n + 1)/2 number of
pendent vertices in :1 binary tree with n vertices. 2 L3
YBC~15329
(C0md.)

5- (p)
(q)
6. (a)
(b)
(q)
0))
De?ne eccentricity of a vertex. Show that every tree has either one or two
centres. 1+4
De?ne spanning tree and ?nd out all possible spanning trees of the following
graph. 1+4
UNIT?III
De?ne planar graph. If G is planar graph with n vertices, e edges, f faces and
k components then prove that n ? e + f = k + 1. 1+4
Prove that every cutset in a connected graph G must contain at least one branch of
every spanning tree of a graph G. 5
De?ne fundamental circuits for the following graph G, ?nd rank of G, nullity of G and
fundamental circuits with reference to the spanning tree : T = (bl, b2, D}, b?, b,, be}.
1+4
b cI
b2 c2
b
c, 3 c4 c3 1)5 c7 b6
13?
c3
c6
Graph G
Show that Kuratowski's K33 graph is non-planar. 5
UNIT?IV
Prove that in the vector space of a graph the circuit subspace and outset subspace are
orthogonal to each other. 5
For a graph G with spanning tree T = {e1, e2} find W6, W3, Wr, Wr 0 WS and
W r U W5. 5
Prove that the set Wr of all circuit vectors including zero vectot in WG form a subspace
of W5. 5
YBC?15329 3 (Contd.)

(q) Let G be a graph given as in ?gure. Find Wr, W5, WI- 0 ?'5 and Wr n WS where
Wr is a circuit subspace and WS is a outset subspace. S
C
V I ?? V4
e.? C,
V': e: ' V3
Group G
UNIT?V
10. (a) Prove that the reduced incidence matrix of graph is non-singular ?T the graph is a
tree. 5
(b) De?ne circuit matrix. Find the circuit matrix of the graph. 1+4
V
11. (p) Find incidence matrix A(G), circuit matrix 3(0) and show that ABr = 0, for the
following graph. 5
,1 3 1
Graph G
(q) De?ne ?the Adjacency matrix. Find the Adjaccncy matrix of ?he following graph. 1+4
YBC??15329 4 525