CompSci 163/265, Spring 2015, Homework 7

  1. In the stable marriage algorithm described in class (the one in which the men propose to the women in preference order, and each woman accepts the best proposal she has seen so far) must there always exist at least one man who ends up married to his first choice? Either prove that such a man always exists, or find an example where all men settle for later preferences.

  2. Let $n$ be an even number, and form an undirected graph with $n$ vertices numbered from $0$ to $n-1$ by adding edges connecting each vertex numbered $i$ to the three vertices numbered $i-1$, $i+1$, and $i+n/2$ (mod $n$). For instance, when $n$ is four, this graph can be drawn using the sides and diagonals of a square. For which values of $n$ is this graph bipartite? Explain how to find a $2$-coloring of the graph for the values of $n$ that make this graph bipartite, and how to find an odd-length cycle for the values of $n$ that make this graph non-bipartite.

  3. Let $G$ be the bipartite graph shown below. Starting from an empty partial matching, find a sequence of alternating paths that leads to a maximum matching in $G$. Choose your alternating paths in such a way that the first one has one edge, the second one has three edges, the third one has five edges, and the fourth one has seven edges. (Hint: it may be easier to solve the problem by working backwards.)

  4. Let $T$ be a tree with four leaves and two degree-three vertices. Draw a polygon $P$ with axis-parallel sides, such that the vertices of $T$ correspond one-for-one with axis-parallel slices through pairs of $270^\circ$-vertices of $P$, and such that two vertices of $T$ are adjacent if and only if the corresponding two slices cross or touch each other. Find a partition of your polygon into a minimum number of rectangles, and describe which of the slices in your partition correspond to the vertices of a maximum independent set in $T$.