Total number of printed pages–5
37 (MAT-4) 4·1
2021
MATHEMATICS
Paper : 4·1
(Graph Theory )
Full Marks : 80
Time : Three hours
The figures in the margin indicate
full marks for the questions.
PART– A
(Objective-type Questions)
Marks-32
1. What do you mean by a connected graph ?
What is the minimum number of
components of a disconnected graph ? Give
one example of a disconnected graph.
2+1+1
2. (i) Find the maximum number of lines in
the graph K 3,3.
(ii) Find the girth of the graph K 3,3.
2+2
Contd.
3. A tree T with 50 endpoints has an equal
number of points of degree 2, 3, 4 and 5
and no points of degree greater than 5. Find
the order of T. 4
4. (i) What is the connectivity of the graph
K5 ?
(ii) Find the line connectivity of a graph
which contains a bridge.
2+2
5. Give an example of a graph which is —
(i) Eulerian but not Hamiltonian.
(ii) Hamiltonian but not Eulerian.
2+2
6. Display a 1-factorization of K 4. 4
7. Invalidate the statement “K5 is a plannar
graph”. 4
⎡ 0 1 1 0⎤
⎢ ⎥
⎢ 1 0 0 1 ⎥
8. Let A (G ) = ⎢ be the adjacency
1 0 0 1 ⎥
⎢ ⎥
⎢⎣ 0 1 1 0 ⎥⎦
matrix of a graph G. Draw the graph and
find the degree of each point of the graph.
Is the graph regular ? 2+1+1
37 (MAT-4) 4·1/G 2
PART – B
(Subjective-type Questions)
Marks-48
9. Answer any two parts : 6×2=12
(a) A certain graph G has order 14 and
size 27. The degree of each point of G
is 3, 4 or 5. There are 6 points of degree
4. How many points of G have degree
3 and how many points of G have
degree 5 ?
(b) Let G be a connected ( p ,q ) graph with
p > 3 points and let ω ( G ) be the
intersection number of G. Show that
ω (G) = q if and only if G has no
triangles.
(c) Prove that, if G is a tree then every two
points of G are joined by a unique path.
10. Answer any two parts : 6×2=12
(a) Let G be a connected regular graph
that is not Eulerian. Prove that if G is
connected, than G is Eulerian.
(b) Express K 7 as the sum of three
spanning cycles.
37 (MAT-4) 4·1/G 3 Contd.
(c) For any non-trivial connected (p,q)
graph G, prove that
α0 + β 0 = p = α1 + β 1
(symbols have their usual meaning)
11. Answer any two parts : 6×2=12
(a) Define plannar graph with a suitable
example.
If G is a (p,q) plane graph in which
every face is an n-cycle, then show
n ( p − 2)
that q = . 2+4
n −2
(b) State Kuratowski’s theorem on planar
graphs.
Using this theorem, prove that the
following graph G is non-planar.
2+4
u1
v1 u2 y1
v2 y2
w2 x2
x1
w1
G
37 (MAT-4) 4·1/G 4
(c) Define a maximal outerplanar graph
with a suitable example. Prove that
every maximal outerplanar graph G
with p points has 2p – 3 lines. 2+4
12. Answer any two parts : 6×2=12
(a) Define spectrum of a graph G.
Determine the spectrum of the graph
K4. 2+4
(b) Define adjacency matrix of a graph G.
Find the number of distinct walks of
length 3 from the point a to b of the
following graph G using its adjacency
matrix. 2+4
c
a f
e1 e2
e8 e5 e4 e3
e7
e6
d b e
e9
(c) If is an eigenvalue of a bipartite graph
G with multiplicity m (), then prove that
– is also an eigenvalue of G and
m (− λ ) = m (λ ) .
37 (MAT-4) 4·1/G 5 100
