Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Graph

1 - Question

Which of the following statements for a simple graph is correct?
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) Path and trail have no relation

View Answer

Answer: a
Explanation: In a walk if the vertices are distinct it is called a path, whereas if the edges are distinct it is called a trail.




2 - Question

In the given graph identify the cut vertices.
data-structure-questions-answers-graph-q2
a) B and E
b) C and D
c) A and E
d) C and B

View Answer

Answer: d
Explanation: After removing either B or C, the graph becomes disconnected.




3 - Question

For the given graph(G), which of the following statements is true?
data-structure-questions-answers-graph-q3
a) G is a complete graph
b) G is not a connected graph
c) The vertex connectivity of the graph is 2
d) The edge connectivity of the graph is 1

View Answer

Answer: c
Explanation: After removing vertices B and C, the graph becomes disconnected.




4 - Question

What is the number of edges present in a complete graph having n vertices?
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient

View Answer

Answer: b
Explanation: Number of ways in which every vertex can be connected to each other is nC2.




5 - Question

The given Graph is regular.
data-structure-questions-answers-graph-q5
a) True
b) False

View Answer

Answer: a
Explanation: In a regular graph, degrees of all the vertices are equal. In the given graph the degree of every vertex is 3.




6 - Question

In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
a) True
b) False

View Answer

Answer: b
Explanation: The sum of the degrees of the vertices is equal to twice the number of edges.




7 - Question

A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
a) 15
b) 3
c) 1
d) 11

View Answer

Answer: b
Explanation: By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.




8 - Question

If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________
a) (n*n-n-2*m)/2
b) (n*n+n+2*m)/2
c) (n*n-n-2*m)/2
d) (n*n-n+2*m)/2

View Answer

Answer: a
Explanation: The union of G and G’ would be a complete graph so, the number of edges in G’= number of edges in the complete form of G(nC2)-edges in G(m).




9 - Question

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 multiple edges

View Answer

Answer: a
Explanation: A simple graph maybe connected or disconnected.




10 - Question

What is the maximum number of edges in a bipartite graph having 10 vertices?
a) 24
b) 21
c) 25
d) 16

View Answer

Answer: c
Explanation: Let one set have n vertices another set would contain 10-n vertices.
Total number of edges would be n*(10-n), differentiating with respect to n, would yield the answer.




11 - Question

Which of the following is true?
a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) A graph may contain no vertices and many edges

View Answer

Answer: b
Explanation: A graph must contain at least one vertex.




12 - Question

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

View Answer

Answer: b
Explanation: For any connected graph with no cycles the equation holds true.




13 - Question

For which of the following combinations of the degrees of vertices would the connected graph be eulerian?
a) 1,2,3
b) 2,3,4
c) 2,4,5
d) 1,3,5

View Answer

Answer: a
Explanation: A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.




14 - Question

A graph with all vertices having equal degree is known as a __________
a) Multi Graph
b) Regular Graph
c) Simple Graph
d) Complete Graph

View Answer

Answer: b
Explanation: The given statement is the definition of regular graphs.




15 - Question

Which of the following ways can be used to represent a graph?
a) Adjacency List and Adjacency Matrix
b) Incidence Matrix
c) Adjacency List, Adjacency Matrix as well as Incidence Matrix
d) No way to represent

View Answer

Answer: c
Explanation: Adjacency Matrix, Adjacency List and Incidence Matrix are used to represent a graph.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners