[OBJECTIVE]
Subject: Graph Theory
Time Allowed: 10 Minutes
Maximum Marks: 10
NOTE: Attempt this Paper on this Question Sheet only. Please encircle the correct option. Division of marks is given in front of each question. This Paper will be collected back after expiry of time limit mentioned above.
Part-I Encircle the right answer, cutting and overwriting is not allowed. (10)
1. A simple connected graph containing no cycle is
a) forest (b) bipartite
(c) tree (d) regular
2. A closed walk in which no vertex is repeated except initial and final vertex is called
(a) Trail (b) path
(c) cycle (d) none
3. A complete bipartite graph Knm contains edges
(a) n+m (b) nm
(c) max(n,m) (d) n-m
4. For a graph G with n vertices and m edges, the graph G/e (where e is an edge) contains ______ vertices
(a) n (b) n-1
(c) n + 1 (d) n +2
5. If degree of every vertex of a graph G is same then G is called
(a) complete (b) regular
(c) connected (d) none
6. If vertex set of a subgraph is equal to vertex set of graph then subgraph is called
(a) spanning subgraph (b) vertex-induced subgraph
(c) edge-induced subgraph
7. The sum of degrees of the vertices of a non-trivial simple graph is ________
(a) always even (b) always odd
(c) may be even or odd (d) zero
8. The number of edges of Cn is
(a) n-1 (b) n
(c) n + 1 (d) none
9. A cycle that traverse every vertex of graph is called ________ cycle.
(a) eulerian (b) semi-eulerian
(c) closed (d) Hamiltonian
10. A tree must contain vertex
(a) pendant (b) isolated
(c) degree two (d) none
[SUBJECTIVE]
Subject: Graph Theory
Time Allowed: 2 Hours 45 Minutes
Maximum Marks: 50
NOTE: ATTEMPT THIS (SUBJECTIVE) ON THE SEPARATE ANSWER SHEET PROVIDED.
Part-II Give short answers, Each answer carries equal marks. (20)
Q#1: For which values of n, Kn are Hamiltonion and Eulerian?
Q#2: Define Complete bipartite graphs and give example.
Q#3: Define vertex connectivity K(G) and give example of graph with K(G)=2.
Q#4: Draw a non-simple graph with no multiple edges with five vertices and eight edges.
Q#5: Write incidence matrix of K4.
Q#6: What is difference between cubic graphs and cubes?
Q#7: Prove that every tree is bipartite.
Q#8: Which complete bipartite graphs are eulerian?
Q#9: Find the cycle and cutset rank of Petersen graph.
Q#10: Determine whether the following graphs are isomorphic or not?
