Graph Theory 6th Sem MCQ
Graph Theory 6th Sem MCQ
Graph Theory 6th Sem MCQ
Prepared by : Sreehari T
Asst professor in mathematics
SDE, Calicut university
1. Which of the following statements for a simple graph is correct.
(a) Every trail is a path (b) Every path is a trail
(c) path (d) Path and trail have no relation
7. Which of the following is true for any simple connected graph with more than 2
vertices.
(a) No two vertices have same degree (b) At least two vertices have same de-
gree
(c) At least 3 vertices have same degree (d) All vertices have same degree
10. Which of the following will be an upper bound for minimum degree of a graph with
10 vertices.
(a) 9 (b) 8 (c) 7 (d) 6
11. A vertex which is not adjacent to every other vertex is called vertex.
(a) Isolated (b) Pendant (c) Incident (d) Simple
12. Let n1 and n2 be the number of edges of graphs G1 and G2 respectively, then the
number of edges of G1 ∨ G2 is
(a) n1 + n2 (b) n1 + n2 − 1 (c) n1 (d) n2
13. For a given graph G having v vertices and e edges which is connected and has no
cycles, which of the following statements is true?
(a) v = e (b) v = e + 1 (c) v + 1 = e (d) v = e − 1
14. Which of the following statements is/are TRUE for undirected graphs?
P:Number of odd degree vertices is even.
Q:Sum of degrees of all vertices is even.
(a) P only (b) Q only (c) Both P and Q (d) Neither P and Q
17. A graph is if it has at least one pair of vertices without a path between
them.
(a) Complete (b) Connected (c) Disconnected (d) Trivial
18. What is the total number of edges of a k− regular graph with n vertices
kn
(a) kn (b) 2
(c) k + n (d) kn2
22. Let κ(G) = vertex connectivity , λ(G) = edge connectivity and δ(G) = minimum
degree of graph G.Then
(a) κ(G) ≤ δ(G) ≤ λ(G) (b) λ(G) ≤ δ(G) ≤ κ(G)
(c) δ(G) ≤ κ(G) ≤ λ(G) (d) κ(G) ≤ δ(G) ≤ λ(G)
Page 2
23. Let G be a simple graph with every pair of vertices is connected. Then G is
(a) trivial (b) complete
(c) disconnected (d) self complementary
26. Let G = Kn where n ≥ 5 . Then number of edges of any induced sub graph of G
with 5 vertices
(a) 10 (b) 5 (c) 6 (d) 8
32. If a simple graph G, contains n vertices and m edges, the number of edges in the
Graph G’(Complement of G) is
n2 +n−2m n2 +2n−2m n2 −n−2m n2 −2n−2m
(a) 2
(b) 2
(c) 2
(d) 2
33. Which of the following properties does a simple graph not hold?
(a) Must be connected (b) Must be unweighted
(c) Must have no loops or multiple edges(d) Must have no edges
Page 3
34. A graph with n vertices will definitely have a parallel edge or self loop if the total
number of edges are
(a) Greater than n − 1 (b) Less than n(n − 1)
n(n−1) n2
(c) Greater than 2
(d) Less than 2
35. The number of elements in the adjacency matrix of a graph having 7 vertices is
36. The graph in which, there is a closed trail which includes every edge of the graph is
known as?
(a) Hamiltonian graph (b) Euler graph
(c) Directed graph (d) Planar graph
39. What is the maximum number of possible non zero values in an adjacency matrix of
a simple graph with n vertices?
n(v−1) n(n+1)
(a) n2 (b) 2
(c) 2
(d) n
40. How many of the following statements are correct?
1. All cyclic graphs are complete graphs.
2. All complete graphs are cyclic graphs.
3. All paths are bipartite.
4. All cyclic graphs are bipartite.
5. There are cyclic graphs which are complete.
41. The degree sequence of a simple graph is the sequence of the degrees of the nodes
in the graph in decreasing order. Which of the following sequences can not be the
degree sequence of any graph?
1. 7, 6, 5, 4, 4, 3, 2, 1
2. 6, 6, 6, 6, 3, 3, 2, 2
3. 7, 6, 6, 4, 4, 3, 2, 2
4. 8, 7, 7, 6, 4, 2, 1, 1
Page 4
42. Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a
connected graph, then the number of bounded faces in any embedding of G on the
plane is equal to
(a) 4 (b) 5 (c) 6 (d) 7
43. Let G be a Null graph. Then
(a) V (G) = ϕ (b) E(G) = ϕ (c) |E(G)| = Even (d) |E(G)| = Odd
44. G is a simple undirected graph. Some vertices of G are of odd degree. Add a node
v to G and make it adjacent to each odd degree vertex of G. The resultant graph is
sure to be
(a) Regular (b) Complete (c) Hamiltonian (d) Euler
45. Radius of a graph, denoted by rad(G) is defined by ?
(a) Max{e(v) : v ∈ V (G)} (b) Min {e(v) : v ∈ V (G)}
(c) Max {d(v, v) : v, u ∈ V (G)} (d) Min {d(u, v) : v, u ∈ V (G)}
46. The minimum degree (δ) of the Petersen graph
(a) 1 (b) 2 (c) 3 (d) 4
47. I. Every bipartite graph contains an odd cycle.
II. Every tree is a bipartite graph.
(a) I is true and II is false (b) I is false and II is true
(c) I and II are false (d) I and II are true
48. If a graph is planar, then it is embeddable on a
(a) Circle (b) Square (c) Sphere (d) Triangle
49. In a 2-connected graph G, any two longest cycles have at least —— vertices in
common.
(a) 0 (b) 1 (c) 2 (d) 3
n−1
50. If a graph G is simple and δ ≥ n
, then G is
(a) Complete (b) Bipartite (c) Connected (d) Planar
51. A simple graph has ——
(a) loops (b) parallel edges
(c) loops and parallel edges (d) None of the above
52. P:Let G1 , G2 and G3 be simple graphs. If G1 ∼
= G2 and G2 ∼
= G3 then G1 ∼
= G3 .
Q: If G1 and G2 are isomorphic then they have a common edge.
(a) P is true and Q is false (b) P is false and Q is true
(c) P and Q are false (d) P and Q are true
53. Total number of edges of a complete graph Km,n
mn
(a) m + n (b) m − n (c) mn (d) 2
Page 5
54. Let G be a bipartite graph. P: Any vertex deleted graph G − v is also a bipartite
graph.
Q: There exist two disjoint trivial induced subgraphs of G.
(a) P is true and Q is false (b) P is false and Q is true
(c) P and Q are false (d) P and Q are true
Page 6
ANSWER KEY
Question No Answer Question No Answer Question No Answer
1 a 21 c 41 d
2 b 22 b 42 c
3 a 23 c 43 d
4 a 24 a 44 d
5 b 25 b 45 c
6 d 26 d 46 b
7 c 27 a 47 d
8 b 28 b 48 d
9 c 29 a 49 b
10 d 30 d 50 c
11 b 31 d 51 d
12 d 32 b 52 a
13 b 33 c 53 c
14 c 34 a 54 d
15 a 35 b
16 a 36 b
17 c 37 d
18 c 38 a
19 d 39 b
20 b 40 c
Page 7