15-451 MINI #4: due midnight Oct 28, 2003.

Note: the second question on this mini is a proof.   You should spend
the time to think it through carefully.

1. One naive algorithm for solving bipartite matching is to do what's
called "chronological backtracking".  You look at the nodes on the
left-hand-side one at a time: for each node, take the first (highest)
available edge and recursively solve the rest of the problem.  If the
recursion returns failure, then try a different edge. If all edges
fail, then return failure.

Describe an n-by-n bipartite graph that has a perfect matching, but
where this algorithm would take exponential time to find it.



2. It turns out that the following simple algorithm, which can be
implemented in linear time, finds a maximum matching when the
underlying graph is a tree (or forest):

   Repeat the following until there are no edges remaining:
      1. pick an arbitrary leaf v.  Let w be v's parent.
      2. put edge (v,w) into the matching.
      3. remove all edges incident to w from the tree (or forest).

It's clear by design that the matching is *legal*: we will never
put in two edges that share an endpoint because every time we put in
an edge (v,w), we remove all edges incident to w (and there
weren't any edges other incident to v since it was a leaf).  

Give a clear, concise proof that the matching found is *maximum*.
I.e., there is no possible matching that has more edges than the one
produced.