Discrete Mathematics 21-228: Summer II 2000
Homework 7 Solutions

The Lazy Postman

We'd like for P and H to be the only vertices of odd degree duplicating as cheap as a set of edges as possible. Thus changing the parity of the degree of the colored vertices above suffices. There are many ways of doing this paying a cost 16; one way is highlighted above.

A $k$ for 1 sale

Let's do this by induction on $k$. If $k = 1$ then our graph is iteslf a perfect matching. Suppose the claim holds for $k-1$-regular bipartite graphs. By the Marriage Theorem we know our $k$-regular bipartite graph $G$ has a perfect matching. Deleting the edges of this perfect matching yields a $k-1$-regular bipartite graph, which by the induction hypothesis can be partioned into $k-1$ perfect matchings. Adding the matching we removed gives us a total of $k$.

Note that the proof above actually gives us an algorithm assuming we can find one. Find a perfect matching, delete its edges, and repeat until the resulting graph is itself a perfect matching.

Extra Credit

Recall that for any graph, $\vert M\vert \leq \vert VC\vert$, where $M$ is a matching and $VC$ is a vertex cover. In particular the red vertices comprise a vertex cover of size 20, hence we have that $\vert M\vert \leq 20$ for any matching $M$. Thus the graph cannot have a perfect matching, which needs 21 edges.

Here's another proof. A perfect matching of the graph needs to match all the red vertices to the black ones, since the red-black coloring is a proper 2-coloring. But there are 20 red vertices and 22 black vertices, so this is impossible.