Question 1

Figure from the original question paper Figure from the original question paper 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 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.