13

14

15

16

8)
b)

8)

8)
b)

a)

b)

a)

b)

E5840 Pages: 3
Prove that the number of odd degree vertices in a graph is always even.

Show that in any group of two or more people, there are always two with exactly
the same number of friends inside the group.

PART C
Answer all questions, each carries 3 marks
Discuss the dual of a subgraph with example.
Write notes on the fundamental circuit.
Prove that in a tree T(V,E),|V|E|+1.
Define spanning tree with example.

PART D
Answer any two full questions, each carries 9 marks
Prove that the ring sum of any two cut-sets in a graph is either a third cut-set or an
edge-disjoint union of cut-sets.
Prove that a connected planar graph with n vertices and e edges has e-n+2 regions.
Consider the following graph G and any one of its spanning trees, T.List all
fundamental circuits and fundamental cut-sets with respect to T.

a el b

Show that the distance between vertices of a connected graph is a metric.
Discuss the center of a tree with suitable example.

PART E
Answer any four full questions, each carries 10 marks
Define the adjacency matrix X(G) of a graph. Let X(G) be adjacency matrix of a
simple graph 0, then prove that ij" entry in X" is the number of different edge
sequences of r edges between vertices vjand Vj.
Draw the adjacency graph for the following adjacency matrix.

3
10011
>{5) =| 00011
11101
01110

Define the circuit-matrix B(G) of a connected graph G with n vertices and e edges.
Prove that the rank of B(G) is e-n+1.

Write the fundamental circuit matrix with respect to the spanning tree shown in
heavy lines for the following graph.

Page 2 of 3

(4)
(5)

(3)
(3)
(3)
(3)

(9)

(4)
(5)

(6)
(3)

(6)

(4)

(6)

(4)