B.Tech. Pt-III (IT) 1 st Semester Examination, 2023. Subject: Graph Theory (Elective I). Paper: IT506B

 

B.Tech. Pt-III (IT) 1st Semester Examination, 2023 Subject: Graph Theory (Elective I) Paper: IT506B

Department of Engineering and Technological

 Studies, University of Kalyani

B.Tech. Pt-III (IT) 1^st Semester

 Examination, 2023

Subject: Graph Theory (Elective I)

Paper: IT506B

Full marks=70 Time: 3 Hours

The figures in the right-hand margin indicate 

marks.

Candidate are required to give their answers 

in their own words as far as possible.

The notations follow their 

standard meanings.

Answer question number one and any 

five from rest.

1. Answer any ten questions: (2 x 10 = 20)

a) Define a graph and a subgraph.

b) What are the edge and vertex labeling?

c) Define order and size of a graph.

d) What do you mean by cut edge and

 cut vertex?

e) Explain union and intersection of two graphs.

f) A non-directed graph G has 8 edges. 

Find the number of vertices, 

if the degree of each vertex in G is 2.

g) What is cycle graph, 

differentiate it from wheel graph?

h)What is meant by complement of a graph? 

Find the complement of the cycle (C₅) graph?

i) What is a complete graph? 

Find the degree of each vertex in a 

complete(K₅) graph?

j) If G is a simple connected graph with 

70 vertices, 

then the number of edges of G is 

between --------- 

and --------- . Explain.

k) Suppose that G is a graph such that 

each vertex has degree 4 and 

|E|=4*|V| - 36. Then |V| = --------- 

and |E| = --------- .

l) What is rooted tree? 

Define level of a vertex in a rooted tree.

m) Determine the order and size of 

k-partite complete K_n1,n2,...nk graph.

n) Define simple path and circuit in a graph.

o) Define loop-graph and multi-graph.

2. a) Prove that, in any non-directed graph

 there is an even number of vertices of odd

 degree.

b) How many different simple graphs are 

there with the give verticex set

 {v₁, v₂,...., v_n}? 

c) Suppose that G is a non directed graph 

with 12 edges. Suppose that G has 

6 vertices of degree 3 and the rest 

have degrees less than 3. 

Determine the minimum number of vertices

 G can have. 

                                                                                                               

          (2+4+4)

3. a) Is there a graph with degree sequence

 (1, 3, 3, 3, 5, 6, 6) ?

b) Draw a nonsimple graph ‘G’ with degree 

sequence (1, 1, 3, 3, 3, 4, 6, 7) .

c) For any simple graph G, 

prove that the number of edges of G is less 

than or equal to n(n-1)/2, where n is the 

number of vertices of G.                                                                 

                                                                                                                                                                                                                                                                                                    ( 2+3+5)

4. a) Define isomorphism. 

Determine whether the following 

pair of graphs ‘H’ and ‘I’ are isomorphic.

b) Determine the graph G with adjacency

 matrix A such that

and (5+5)

5. a) If G is a connected planar graph,

then prove that the Euler’s formula

 (|V|-|E|+|R| = 2).

b) In a connected simple-plane graph G,

with |E| > 1, prove that |E| ≤ 3|V| - 6.

c) A complete graph K_n is planar iff n ≤ 4,

 justify. 

                                                                                                               

      (4+4+2)

6. a) What do you mean by planar graphs?

b) Define dual graph and self-dual graph?

c) Show that the graph ‘I’ given below is

 planar. 

Find the dual graph of a planar graph ‘J’. 

Is it self-dual graph?

7. a) Differentiate between Euler path and

 Hamiltonian path.

b) Define chromatic number X(G). 

Find the X(G) of a graph ‘M’. 

c) What do you mean by a bipartite graph?

d) Find number of all possible binary tree of 

3-node.

                                                                                                                       (2+3+2+3)

8. Short notes:

                                                                        (2 x 5)

Answer any two of the following:

a) The four-color Problem.

b) The Hamiltonian Graphs.

c) The Königsberg Bridges Problem.

d) The Catalan numbers.

--------End---------------------