Question 1

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.”

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.”

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. Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers. Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by: $$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$$ Based on the above data, answer the given subquestions. Figure from the original question paper Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers. Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by: $$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$$ Based on the above data, answer the given subquestions. Figure from the original question paper