Graph Theory Multiple Choice Questions and Answers

1 A graph is a collection of.... ?

A Row and columns

B Vertices and edges

C Equations

D None of these

View Answer

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

View Answer

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

View Answer

Answer: Trivial graph

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

View Answer

Answer: Closed

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 }

View Answer

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

View Answer

Answer: Tree

7 A graph is a collection of

A Row and columns

B Vertices and edges

C Equations

D None of these

View Answer

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

View Answer

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

View Answer

Answer: 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

View Answer

Answer: All of above

11 A partial ordered relation is transitive, reflexive and

A Antisymmetric

B Bisymmetric

C Anti reflexive

D Asymmetric

View Answer

Answer: Antisymmetric

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

View Answer

Answer: greater than n–1

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

View Answer

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

View Answer

Answer: a+c

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

View Answer

Answer: Trivial graph

16 A continuous non intersecting curve in the plane whose origin and terminus coincide

A Planer

B Jordan

C Hamiltonian

D All of these

View Answer

Answer: Jordan

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

View Answer

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

View Answer

Answer: 25, 56

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

View Answer

Answer: n–1

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

View Answer