In this problem you are given as input a graph T = (V, E) that is a tree (that is, T is undirected, connected, and acyclic). A perfect matching of T is a subset F \subset E of edges such that every vertex v \in V is the endpoint of exactly one edge of F. Equivalently, F matches each vertex of T with exactly one other vertex of T. For example, a path graph has a perfect matching if and only if it has an even number of vertices. Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it. Algorithm A: 1 While T has at least one vertex: 2 If T has no edges: 3 halt and output ”T has no perfect matching.” 4 Else: 5 Let v be a vertex of T with maximum degree. 6 Choose an arbitrary edge e incident to v. 7 Delete e and its two endpoints from T. 8 (end of while loop] 9 Halt and output ”T has a perfect matching.” Algorithm B: 1 While T has at least one vertex: 2 If T has no edges: 3 halt and output ”T has no perfect matching.” 4 Else: 5 Let v be a vertex of T with minimum non-zero degree. 6 Choose an arbitrary edge e incident to v. 7 Delete e and its two endpoints from T. 8 (end of while loop] 9 Halt and output ”T has a perfect matching.” Is either algorithm correct? Hint: Recall that every tree with at least two vertices has at least one degree one vertex.

(C) Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.

(A) Neither algorithm always correctly determines whether or not a given tree graph has a perfect matching.

(B) Both algorithms always correctly determine whether or not a given tree graph has a perfect matching.

(D) Algorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.

Advanced Algorithms · End Term · 31 Aug 2025 · May 2025 term · Set QDB3

Question 1: In this problem you are given as input a graph T = (V, E)…

Question 1

+3 marksOne correct option

In this problem you are given as input a graph $T = (V, E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A perfect matching of $T$ is a subset $F \subset E$ of edges such that every vertex $v \in V$ is the endpoint of exactly one edge of $F$ .

Equivalently, $F$ matches each vertex of $T$ with exactly one other vertex of $T$ . For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it.

Algorithm A:

text

11 While T has at least one vertex:
22   If T has no edges:
33       halt and output ”T has no perfect matching.”
44   Else:
55       Let v be a vertex of T with maximum degree.
66       Choose an arbitrary edge e incident to v.
77       Delete e and its two endpoints from T.
88 (end of while loop]
99 Halt and output ”T has a perfect matching.”

Algorithm B:

text

11 While T has at least one vertex:
22   If T has no edges:
33       halt and output ”T has no perfect matching.”
44   Else:
55       Let v be a vertex of T with minimum non-zero degree.
66       Choose an arbitrary edge e incident to v.
77       Delete e and its two endpoints from T.
88 (end of while loop]
99 Halt and output ”T has a perfect matching.”

Is either algorithm correct?

Hint: Recall that every tree with at least two vertices has at least one degree one vertex.

A
Neither algorithm always correctly determines whether or not a given tree graph has a perfect matching.
B
Both algorithms always correctly determine whether or not a given tree graph has a perfect matching.
C
Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.
D
Algorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.

Show answer

Correct answer

C
Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.

See the whole paper Take it as a mock test

Question 1 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 31 Aug 2025, in the May 2025 term (IIT M IMPROVEMENT FN EXAM QIA1 31 Aug 2025). It carries 3 marks.

This question was also asked in

Advanced Algorithms End Term — 1 Sept 2024, Set QDB3 · question 49
Advanced Algorithms End Term — 31 Aug 2025, Set QIA1 · question 1

Question 1: In this problem you are given as input a graph T = (V, E)…

Question 1

This question was also asked in

More questions from this paper