Home › Quizzes › Matching and Covering

Matching and Covering

This quiz covers the concepts of matching and covering in graph theory. Questions will assess your understanding of different types of matchings, covering theorems, and their applications.

15 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

In a graph, a matching is a set of:

  1. Disjoint edges
  2. Disjoint vertices
  3. Disjoint paths
  4. Disjoint cycles
Question 2 Multiple Choice (Single Answer)

Which of the following is a necessary condition for a graph to have a perfect matching?

  1. The graph must be bipartite
  2. The graph must be connected
  3. The graph must have an even number of vertices
  4. The graph must have a cycle
Question 3 Multiple Choice (Single Answer)

Menger's Theorem states that the maximum number of edge-disjoint paths between two vertices in a graph is equal to:

  1. The minimum number of edges in a cut separating the two vertices
  2. The maximum number of edges in a cut separating the two vertices
  3. The minimum number of vertices in a cut separating the two vertices
  4. The maximum number of vertices in a cut separating the two vertices
Question 4 Multiple Choice (Single Answer)

In a graph, a vertex cover is a set of vertices that:

  1. Covers all the edges of the graph
  2. Covers all the paths of the graph
  3. Covers all the cycles of the graph
  4. Covers all the connected components of the graph
Question 5 Multiple Choice (Single Answer)

Which of the following is a necessary condition for a graph to have a vertex cover of size k?

  1. The graph must have at least k vertices
  2. The graph must have at most k edges
  3. The graph must have a cycle of length k
  4. The graph must have a path of length k
Question 6 Multiple Choice (Single Answer)

Which of the following is a sufficient condition for a graph to have a perfect matching?

  1. The graph must be bipartite and have an even number of vertices
  2. The graph must be connected and have an even number of vertices
  3. The graph must be regular and have an even number of vertices
  4. The graph must be complete and have an even number of vertices
Question 7 Multiple Choice (Single Answer)

Which of the following is a sufficient condition for a graph to have a vertex cover of size k?

  1. The graph must have a cycle of length k
  2. The graph must have a path of length k
  3. The graph must have a clique of size k
  4. The graph must have an independent set of size k
Question 8 Multiple Choice (Single Answer)

In a graph, an edge cover is a set of edges that:

  1. Covers all the vertices of the graph
  2. Covers all the paths of the graph
  3. Covers all the cycles of the graph
  4. Covers all the connected components of the graph
Question 9 Multiple Choice (Single Answer)

Which of the following is a necessary condition for a graph to have an edge cover of size k?

  1. The graph must have at least k edges
  2. The graph must have at most k vertices
  3. The graph must have a cycle of length k
  4. The graph must have a path of length k
Question 10 Multiple Choice (Single Answer)

Which of the following is a sufficient condition for a graph to have an edge cover of size k?

  1. The graph must have a cycle of length k
  2. The graph must have a path of length k
  3. The graph must have a clique of size k
  4. The graph must have an independent set of size k
Question 11 Multiple Choice (Single Answer)

In a graph, a maximum matching is a matching that:

  1. Has the maximum number of edges
  2. Has the maximum number of vertices
  3. Has the maximum weight
  4. Has the minimum weight
Question 12 Multiple Choice (Single Answer)

Which of the following is a necessary condition for a graph to have a maximum matching of size k?

  1. The graph must have at least k vertices
  2. The graph must have at most k edges
  3. The graph must have a cycle of length k
  4. The graph must have a path of length k
Question 13 Multiple Choice (Single Answer)

Which of the following is a sufficient condition for a graph to have a maximum matching of size k?

  1. The graph must have a cycle of length k
  2. The graph must have a path of length k
  3. The graph must have a clique of size k
  4. The graph must have an independent set of size k
Question 14 Multiple Choice (Single Answer)

In a graph, a minimum vertex cover is a vertex cover that:

  1. Has the minimum number of vertices
  2. Has the minimum number of edges
  3. Has the minimum weight
  4. Has the maximum weight
Question 15 Multiple Choice (Single Answer)

Which of the following is a necessary condition for a graph to have a minimum vertex cover of size k?

  1. The graph must have at least k vertices
  2. The graph must have at most k edges
  3. The graph must have a cycle of length k
  4. The graph must have a path of length k
← Back to Quizzes