Graph Theory
HNBGU MCA Previous Question Paper 2022


Discuss permutation and determine the number of permutations
that can be made out of the letters of the word
"PROGRAMMING".

Discuss combination and determine the number of triangles
that are formed by selecting points from a set of 15 points
out of which 8 are collinear.


Differentiate between homogeneous linear recurrence relation
and nonhomogeneous linear recurrence relation. Discuss the
method used to solve the linear homogeneous recurrence
relation with constant coefficients.

Solve the recurrence relation Ar+2  5Ar+1 + 6Ar = 2 by the
method of generating functions satisfying the initial
conditions a0 = 1 and a1 = 2.


Define a connected graph. Prove that a connected graph with
n vertices has at least (n1) edges.

Define the following:
 Planer graph
 Complete Bipartite graph
 Dual of a planer graph
Give one example each.


Check whether the two graphs are isomorphic or not. Justify
your answer.

Define Hamilton and Eulerian graphs. Prove the complete
graph K3,3 is Hamilton but not Eulerian.


Write short notes on the following:
 Tree and fundamental circuit.
 Rooted and Binary tree
 Various operation on graph
 Vector space of a graph

Discuss the Prim's algorithm. Using Prim's algorithm, find a
minimal spanning ttree for the weighted graph shown in the
following:


Define cut set. Find a cutsets of the graph G given below
and also find the edge connectivity of G:

Prove that a connected Planar graph with n vertices and e
edges has en+2 regions.


Differentiate between combinatorial and geometrical dual of
a graph. Draw the geoetric dual of the graph G given below.

Define Incidence matrix and Adjacency matrix of a directed
and undirected graph. Explain with suitable examples.

Write short notes on the following:
 Rule of sum and products.
 Coloring and covering partitioning of a graph
 Graph enumeration
 Four color problem
 Thickness and crossing of a graph