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

FirstRanker.com
A Firstranker's choice

AW-1761

--- Content provided by FirstRanker.com ---

--- Content provided by FirstRanker.com ---

Note :— (1) Question No. 1 is compulsory and attempt it at once only.
(2) Solve ONE question from each unit.

1. Choose the correct alternative in the following :
   1. A connected graph G is an Euler graph iff it can be decomposed into : 1
      1. Walks
      2. Paths
      3. Cut sets

      --- Content provided by FirstRanker.com ---

      4. Circuits
   2. A subgraph H = <V, E> of a graph G = <V, E> is called a spanning subgraph if 1
      1. E = ¢
      2. V₁=¢
      3. V₁=V

      --- Content provided by FirstRanker.com ---

      4. E₁ =E
   3. The concept of a tree was introduced by : 1
      1. Euler
      2. Hamiltonian
      3. Cayley

      --- Content provided by FirstRanker.com ---

      4. Kuratowski
   4. If G be a circuitless graph with n vertices and k components then G has : 1
      1. n+ 1 edges
      2. n -1 edges
      3. n + k edges

      --- Content provided by FirstRanker.com ---

      4. n -k edges
   5. A graph can be embedded in the surface of a sphere iff it can be embedded in : 1
      1. a plane
      2. a circle
      3. a sphere

      --- Content provided by FirstRanker.com ---

      4. a straight line
   6. A complete graph of five vertices is : 1
      1. Planar graph
      2. Non-planar graph
      3. Null graph

      --- Content provided by FirstRanker.com ---

      4. Bipartite graph
   7. Minimum number of linearly independent vectors that spans the vectors in a vector space W, is called : 1
      1. Basis of vector space
      2. Dimension of vector space
      3. Span

      --- Content provided by FirstRanker.com ---

      4. None of these
   8. The dimension of the cutspace W is equal to the rank of the graph and the number of cutset vectors including 0 in W_t is : 1
      1. r
      2. 2^r
      3. 3^r

      --- Content provided by FirstRanker.com ---

      4. 4^r
   9. A row with all zeros in incidence matrix represents : 1
      1. Pendent vertex
      2. Isolated vertex
      3. Odd vertex

      --- Content provided by FirstRanker.com ---

      4. Even vertex
   10. If B is a circuit matrix of a connected graph G with n vertices and e edges then rank of B is : 1
       1. e+n-1
       2. e—n-1
       3. e+n+1

       --- Content provided by FirstRanker.com ---

       4. e-n+1

UNIT—I

2. (a) Define (i) Simple graph, (ii) Degree of a vertex. Show that the maximum number of edges in a simple graph of n vertices is E(n(n-1)/2). 2+3
   

   --- Content provided by FirstRanker.com ---

   (b) Define isomorphism between two graphs. Prove that any two simple connected graphs with n vertices, all of degree two are isomorphic. 2+3
3. (p) From the graph given below answer the following :
   V1
   (i) Write the degree of each vertex.
   (ii) Which edges are incident with the vertex V₁ ?
   

   --- Content provided by FirstRanker.com ---

   (iii) Write the adjacent vertices of V₁.
   (iv) Is the graph simple ? Why ? 1+1+1+2
   (q) In a graph G there exists a path from the vertex u to the vertex v iff there exists a walk from u to v. 5

UNIT—II

4. (a) Prove that following statements are equivalent :
   

   --- Content provided by FirstRanker.com ---

   (i) There is exactly one path between every pair of vertices in G.
   (ii) G is minimally connected graph. 5
   (b) Define : (i) Binary tree. (ii) Rooted tree. Show that there are (n + 1)/2 number of pendent vertices in a binary tree with n vertices. 2+3

5. (p) Define eccentricity of a tree. Find out radius and centres. 1+4
   (q) Define spanning tree and find out all possible spanning trees of the following graph. 1+4
   

   --- Content provided by FirstRanker.com ---

UNIT—III

6. (a) Define 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
   (b) Prove that every cutset in a connected graph G must contain at least one branch of every spanning tree of a graph G 5
7. (a) Define fundamental circuits for the following graph G, find rank of G, nullity of G and fundamental circuits with reference to the spanning tree : T = {b₁, b₂, b₃, b₄, b₅, b₆}.
   

   --- Content provided by FirstRanker.com ---

   
   1+4
   (b) Show that Kuratowski’s K_3,3 graph is non-planar. 5

UNIT—IV

8. (a) Prove that in the vector space of a graph the circuit subspace and cutset subspace are orthogonal to each other. 5
   

   --- Content provided by FirstRanker.com ---

   (b) For a graph G with spanning tree T = {e₁, e₂} find W_c, W_t, W_c ∩ W_t and W_c U W_t 5
9. (p) Prove that the set W of all circuit vectors including zero vector in W_c, form a subspace of W_v. 5
   (q) Let G be a graph given as in figure. Find W_c, W_t, W_c ∩ W_t and W_c U W_t where W_c is a circuit subspace and W_t is a cutset subspace. 3
   

UNIT—V

--- Content provided by FirstRanker.com ---

10. (a) Prove that the reduced incidence matrix of graph is non-singular iff the graph is a tree. 5
    (b) Define circuit matrix. Find the circuit matrix of the graph. 1+4
    
11. (p) Find incidence matrix A(G), circuit matrix B(G) and show that AB^T = 0, for the following graph 5
    
    

    --- Content provided by FirstRanker.com ---

    (q) Define the Adjacency matrix. Find the Adjacency matrix of the following graph. 1+4
    

FirstRanker.com