Graph Theory MCQs are the repeated MCQs asked in different public service commission, and jobs test.

Select which one is incorrect?
(A) The number of edges appearing in the sequence of a path is called the
length of the path.
(B) Every simple path of a digraph is also an elementary path
(C) A path which originates and ends with the same node is called a
cycle.
(D) Every elementary path of a digraph is also a simple path.
(E) All of the above
Answer (B) Every simple path of a digraph is also an elementary path

The degree of any vertex of the graph is known as?
(A) Number of edges in a graph
(B) Number of a vertex in a graph
(C) Number of vertices adjacent to that vertex

(D) The number of edges incident with the vertex

(E) None of these
Answer: D The number of edges incident with the vertex

The Empty graph is also known as?
(A) Bipartite graph
(B) Regular graph
(C) Trivial graph
(D) both a and b
(E) None of these
Answer:C Trivial graph
When the origin and terminus of a walk both are the same, the walk is
called?
(A) Open
(B) Path
(C) Closed
(D) way
(E) None of these
Answer: C Closed
The Radius of a graph, denoted by rad(G) is formed by?
(A) { d(u,v): u belongs to v, u does not equal to v }
(B) min { e(v): v belongs to V}
(C) max max {e(v): v belongs to V }
(D) min { d(u,v): u belongs to v, u does not equal to v }
(E) None of these
Answer: C max max {e(v): v belongs to V }
A graph is a group of ?
(A) Vertices and edges
(B) Row and columns
(C) Equations
(D) vertical
(E) None of these
Answer: A Vertices and edges

What is the meaning of it when In a graph if e=(u, v)?
(A) u is the processor and v is the successor
(B) e begins at u and ends at v
(C) u is adjacent to v but v is not adjacent to u
(D) both a and b
(E) None of these
Answer: D both a and b
Select the minimal spanning tree of a graph G
(A) A tree
(B) A spanning subgraph
(C) Minimum weights
(D) All of the above
(E) None of these
Answer: D All of the above
A partial set of relation is transitive, reflexive and____________?
(A) Bisymmetric
(B) Antisymmetric
(C) Anti reflexive
(D) Asymmetric
(E) None of these
Answer: B Antisymmetric
A graph with n vertices will must have a parallel edge the total number
of edges are________?
(A) greater than n(n–1)/2
(B) less than n(n–1)
(C) greater than n–1
(D) less than n2/2
(E) None of these
Answer: C greater than n–1
A vertex of a graph is known as even or odd based on____?
(A) is even or odd Its degree is even or odd
(B) Total number of vertices in a graph is even or odd
(C) Total number of edges in a graph
(D) both a and b
(E) None of these
Answer: C Total number of edges in a graph
Select from the following if expression a+a c is equivalent to
(A) a+c
(B) a
(C) c
(D) 1
(E) None of these
A continuous non-intersecting curve in the plane Select the origin and
terminus coincide
(A) Jordan
(B) Planer
(C) Hamiltonian
(D) All of these
(E) None of these
Answer: A Jordan
Select from the following pair is not congruent modulo 7
(A) 10, 24
(B) -64, -15
(C) -31, 11
(D) 25, 56
(E) None of these
Answer: D 25, 56
Select the maximum degree of any vertex in a simple graph with n vertices
is
(A) 2n–1
(B) n+1
(C) n–1
(D) n
(E) None of these
Answer: C n–1

Select from the following the surjective functions are there from an n-
element (n => 2) set to a 2-element set?
(A) 2n – 2
(B) 2n – 1
(C) 2n – 2
(D) 2(2n – 2)
(E) None of these
Answer: A 2n – 2
the Hasse diagram are drawn by?
(A) Lattices
(B) Partially ordered sets
(C) Boolean algebra
(D) both a and b
(E) None of these
Answer: B Partially ordered sets

Select the ways can 5 balls be chosen so that 2 are red and 3 are black
(A) 990
(B) 910
(C) 970
(D) 980
(E) None of these
Answer: A 990
Th Circle has what?
(A) 8 vertices
(B) Only 1 vertex
(C) No vertices
(D) both a and b
(E) None of these
Answer: C No vertices
The proposition ~qvp is equal to ________?
(A) p?q
(B) q?p
(C) p?q
(D) p?q
(E) None of these
Answer: C p?q

Select the true one If B is a Boolean Algebra
(A) Bis a finite, complemented, and distributive lattice
(B) B is a finite but not complemented lattice
(C) B is a finite, distributive but not complemented lattice
(D) B is not distributive lattice
(E) None of these
Answer: A Bis a finite, complemented, and distributive lattice

Select the number of distinguishable permutations of the letters in the
word BANANA are,
(A) 20
(B) 36
(C) 60
(D) 10
(E) None of these
Answer: C 60

The graph is a tree if and only if
(A) Is minimally
(B) Contains a circuit
(C) Is planar
(D) Is completely connected
(E) None of these
Answer: A Is minimally
Select the number of various words can be taken out of the letters of the
word VARANASI?
(A) 720
(B) 120
(C) 40320
(D) 64
(E) None of these
Answer: A 720
Select the degree of v if v is an isolated vertex in a graph,
(A) 1
(B) 0
(C) 2
(D) 3
(E) None of these
Answer: B 0
33 The full graph with four vertices has k edges where k is______?
(A) 6
(B) 4
(C) 5
(D) 3
(E) None of these
Answer: A 6
Select the incorrect statement from the following?
(A) The number of regions corresponds to the cyclomatic complexity
(B) Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is
the number of predicate nodes contained in the flow graph G
(C) Cyclometric complexity for a flow graph G is V(G) = E–N+2, where E is
the number of edges & N is the number of nodes in the flow graph
(D) Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is
the number of edges and N is the number of nodes in the flow graph
(E) None of these

Answer: A graph drawn in a plane in such a way that any pair of edges
meet only at their end vertices
Select the Length of the walk of a graph _________?
(A) The number of vertices in walk W
(B) Total number of edges in a graph
(C) The number of edges in walk W
(D) Total number of vertices in a graph
(E) None of these
Answer:C The number of edges in walk W
A graph with one vertex and no edges is called
(A) multigraph
(B) trivial graph
(C) isolated graph
(D) digraph
(E) None of these
Answer: B trivial graph
A simple digraph with condition that _____ such that it is known as an
acyclic graph.
(A) it does not contain any loop
(B) it contains a loop i
(C) t does not contain any cycle
(D) it contains a cycle
(E) All of the above
Answer (C) t does not contain any cycle

The sum of each element in the row of the adjacency matrix refer to _____ of
the corresponding node.
(A) indegree
(B) outdegree
(C) total degree
(D) diameter of graph
(E) All of the above

Answer (C) total degree
Select which one is incorrect?
(A) A digraph which does not have any cycle is called an acyclic graph.
(B) A directed tree which has a node with out-degree 0 is called the root of
a tree.
(C) A set of trees is called a forest.
(D) A tree is a connected acyclic graph.
(E) All of the above
Answer (B) A directed tree which has a node with out-degree 0 is called root of a tree.
MCQ No – 28
Select the level of the root of a directed tree is _____.
(A) 2
(B) 1
(C) 0
(D) 3
(E) All of the above
Answer (C) 0

In a directed tree the out-degree of every node is less than or equal to
2 is known as
(A) a full binary tree
(B) a binary tree
(C) m-ary tree
(D) full m-ary tree
(E) All of the above
Answer (B) a binary tree

The node which is reachable from u is known as
(A) descendant
(B) son
(C) root
(D) simple node
(E) All of the above
Answer (A) descendant

A graph is a set of?
(A) Vertices and edges
(B) Row and columns
(C) Equations
(D) both a and b
(E) None of these

Answer: A Vertices and edges