Download PDF
Free download in PDF Graph Theory Multiple Choice Questions and Answers for competitive exams. These short objective type questions with answers are very important for Board exams as well as competitive exams. These short solved questions or quizzes are provided by Gkseries.
(1)
A graph is a collection of.... ?
[A]
Row and columns
[B]
Vertices and edges
[C]
Equations
[D]
None of these
Answer: Vertices and edges
(2)
The degree of any vertex of graph is .... ?
[A]
The number of edges incident with vertex
[B]
Number of vertex in a graph
[C]
Number of vertices adjacent to that vertex
[D]
Number of edges in a graph
Answer: The number of edges incident with vertex
(3)
A graph with no edges is known as empty graph. Empty graph is also known as... ?
[A]
Trivial graph
[B]
Regular graph
[C]
Bipartite graph
[D]
None of these
(4)
If the origin and terminus of a walk are same, the walk is known as... ?
[A]
Open
[B]
Closed
[C]
Path
[D]
None of these
(5)
Radius of a graph, denoted by rad(G) is defined by.... ?
[A]
max {e(v): v belongs to V }
[B]
min { e(v): v belongs to V}
[C]
max { d(u,v): u belongs to v, u does not equal to v }
[D]
min { d(u,v): u belongs to v, u does not equal to v }
Answer: max {e(v): v belongs to V }
(6)
A graph G is called a ..... if it is a connected acyclic graph
[A]
Cyclic graph
[B]
Regular graph
[C]
Tree
[D]
Not a graph
(7)
A graph is a collection of
[A]
Row and columns
[B]
Vertices and edges
[C]
Equations
[D]
None of these
Answer: Vertices and edges
(8)
How many relations are there on a set with n elements that are symmetric and a set with n elements that are reflexive and symmetric ?
[A]
2n(n+1)/2 and 2n.3n(n–1)/2
[B]
3n(n–1)/2 and 2n(n–1)
[C]
2n(n+1)/2 and 3n(n–1)/2
[D]
2n(n+1)/2 and 2n(n–1)/2
Answer: 2n(n+1)/2 and 2n(n–1)/2
(9)
In a graph if e=(u, v) means
[A]
u is adjacent to v but v is not adjacent to u
[B]
e begins at u and ends at v
[C]
u is processor and v is successor
[D]
both b and c
(10)
A minimal spanning tree of a graph G is
[A]
A spanning sub graph
[B]
A tree
[C]
Minimum weights
[D]
All of above
(11)
A partial ordered relation is transitive, reflexive and
[A]
Antisymmetric
[B]
Bisymmetric
[C]
Anti reflexive
[D]
Asymmetric
(12)
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)
[C]
greater than n(n–1)/2
[D]
less than n2/2
(13)
A vertex of a graph is called even or odd depending upon
[A]
Total number of edges in a graph is even or odd
[B]
Total number of vertices in a graph is even or odd
[C]
Its degree is even or odd
[D]
None of these
Answer: Its degree is even or odd
(14)
The expression a+a c is equivalent to
[A]
a
[B]
a+c
[C]
c
[D]
1
(15)
A graph with no edges is known as empty graph. Empty graph is also known as
[A]
Trivial graph
[B]
Regular graph
[C]
Bipartite graph
[D]
None of these
(16)
A continuous non intersecting curve in the plane whose origin and terminus coincide
[A]
Planer
[B]
Jordan
[C]
Hamiltonian
[D]
All of these
(17)
A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are
[A]
more than n
[B]
more than n+1
[C]
more than (n+1)/2
[D]
more than n(n-1)/2
Answer: more than n(n-1)/2
(18)
Which of the following pair is not congruent modulo 7?
[A]
10, 24
[B]
25, 56
[C]
-31, 11
[D]
-64, -15
(19)
The maximum degree of any vertex in a simple graph with n vertices is
[A]
n–1
[B]
n+1
[C]
2n–1
[D]
n
(20)
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true ?
[A]
Weight (u, v) <= 12
[B]
Weight (u, v) = 12
[C]
Weight (u, v) >= 12
[D]
Weight (u, v) > 12
Answer: Weight (u, v) >= 12
Take Mock Tests