The blossom algorithm and a M'-altemating tree I (plain edges), that are depieted in (b) (a) (1 point) How many nodes of G are M-exposed? Identify the root of T, the nodes in A(T) and B(Tv), and the psendonodes of T. (b) ( 2 points) Does G admit a perfect matching? Justify your answer formally and in detail, and explicity state any lemma/proposition/theorem seen in class that you use in your reasoning. c) (1 point) Extend M to a matching M of G with the same number of exposed nodes. You can write your answer on the graph G in (a). (2 points) Is M a maximum matching of G ? If not, find a maximum matching M of G, and prove its optimality by using the upper bound of Observation 1