06000CS309122001

7 93) There are 20 people in a room. Suppose some pairs of the people shake hands
and some don’t. As the people leave the room you (who were not in the room)
ask each person whether they shook hands an odd number of times or an even
number of times. Prove that the number of people who answer “‘odd” is an even

number.

b) Label the vertices and edges in the graph given below, find and separately draw
any four different Hamiltonian circuits contained in the given graph. (Note: The

Hamiltonian circuits need not be edge-disjoint).

PART C

Answer all questions, each carries 3 marks.

8 Find the number of spanning trees in a complete graph of 4 labelled vertices.

9 Prove the statement, “A graph with n vertices, 0-1 edges and no circuits is
connected”.

10 Prove that “Every cut set in a connected graph G must contain at least one

branch of every spanning tree of G ^

1] Find the center and radius and of the tree shown below:
‏رن ہن‎ &
‏زم‎ 6

(1) 2

PART D
Answer any two full questions, each carries 9 marks.

12 a) Prove that a graph is a tree if and only if it is loop-less and has exactly one

spanning tree

Page 2 of 5

(4)

(5)

(3)

(3)

(3)

(3)

(4)