# Matching Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Matching”.

1. Which of the following refers to a set of edges with no shared endpoints?
a) Dominating set
b) Matching
c) Independent set
d) Cut edge

Explanation: In a simple graph G, a matching or any edge set in a graph, is a set of edges with no vertices in common. It can also be an entire graph consisting of edges with no common vertices. Hence, matching refers to a set of edges with no shared endpoints.

2. In a perfect matching of graph G, every vertex is connected to how many edges?
a) At most one
b) At least one
c) Exactly one
d) Zero

Explanation: In a graph G, perfect matching is said to be the matching, that saturates every vertex of the graph. It is a maximal matching set such that it induces the degree of all the vertices as exactly one. Every perfect matching is a maximal matching set.

3. In a graph G, the total number of edges in maximum matching is called?
a) Matching number
b) Chromatic number
c) Domination number
d) Independence number

Explanation: In a graph G, maximum matching is a matching of maximum size among all matchings in the graph. It is also known as the largest maximal matching. The cardinality of the maximum matching set is the matching number.

4. Which of the following refers to the perfect matching for the graph given below?

a)

b)

c)

d)

Explanation: In a graph G, a perfect matching is a maximal matching set such that it induces the degree of all the vertices as exactly one. Hence, from all the given graphs, the graph with degree of all the vertices as 1 and covering all the vertices of the graph will be an appropriate perfect matching.

5. In a graph, perfect matching exists only if the number of vertices is even.
a) True
b) False

Explanation: In a graph G, perfect matching saturates every vertex of the graph. All the vertices are to be covered in it. So the number of edges in perfect matching is half the number of vertices. Hence, perfect matching exists if the number of vertices is even.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Which of the following refers to the maximal matching graph for the graph given below?

a)

b)

c)

d)

Explanation: In a graph, maximal matching means a matching of maximal cardinality, which cannot be increased by adding any edge. If we add any edge to the graph, it violates the matching of the graph. Hence, from all the given graphs, the graph which doesn’t violates the matching by adding any vertex will be an appropriate maximal matching.

7. In a graph, every maximum matching is a maximal matching.
a) True
b) False

Explanation: A maximal matching in a graph is a matching, which cannot be increased by adding any edge and a maximum matching is a matching of maximum size among all matchings in the graph. Hence, we can say that the given statement is correct.

8. Which among the following is an application of graph matching?
a) Traveling salesperson problem
b) Graph coloring
c) Knapsack problem
d) Maximum subset problem

Explanation: One of the applications of graph matching is graph coloring. In graph coloring, all the vertices of the graph are labeled with colors, such that two adjacent vertices do not share the same color. Apart from vertex coloring, it is used in scheduling, flow networks, stable marriage problem and many more.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.