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