Homework 6:
10.4.6: Suppose there are $x$ degree 8 on the left and $y$ degree 5 on the left. Counting edges we have $$ 8x+5y=5(16-y) $$ or $$ 8x+10y=80. $$ The non-negative solutions are $(x,y)=(10,0),(5,4),(0,8)$, so we take $x=5$, $y=4$.
10.4.9:
Let's check the matching condition $$ |S|\le |R(S)|. $$ If $|S|\le m/2$ this is clear since a single vertex will do. So Suppose that $|S|\gt m/2$. Then any point in the complement of $R(S)$ would be connected less than $m/2$ vertices which is impossible. So $R(S)$ is everything, $|R(S)|=m.$
10.4.8:
Add a fake new vertex on the right which is connected to all vertices on the left. The new graph now does have the matching condition, and delete the edge of the fake vertex.
12.3.1: Yes.
12.3.4: We need n at least 2. Each face has at least 4 edges since each cycle has even length, so $2e\ge 4f.$ So $f=2-n+e$ implies $e/2 \ge 2-n+e$, or $e\ge 2(n-2).$
13.4.2: Delete a vertex v of degree strictly less than d. Then $G-v$ has components where each vertex has degree at most d, and some vertex (which was connected to v) has degree less than d. By induction each component is d-colorable. Reinsert v, and since v has degree less than d, at least one color remains for v.
E1: Impossible. Imagine that this occurs and 2 men M1, M2, are matched to their last choices W1, W2. Consider the the second to last round in Gale-Shapley. If M1 is in W1's room, he has visited all rooms, and the algortihm must have stopped already. Same for M2. So M1 is not in W1's room, and M1 has visited all rooms but W1. Same for M2 and W2. So all rooms have been visited.
E2: If $M$ is not matched to $W$, they would both drop their spouses for each other, not stable.
E3: This is easy.
E4: The matching is $M_j-W_{j+k-1}$ where the indices are taken mod n. Each man gets his $k$th
choice, and each woman her $n-k+1$ choice.
(b) Yes. Imagine them sitting around a circle $M_1W_1M_2W_2\cdots M_n W_n$ clockwise.
The women $M_j$ prefers to his match sit between him and his match $W_{j+k-1}$ in a clockwise
direction. But each of these women prefer men clockwise before $M_j$, so $M_j$ is in a stable
marriage.
E5: TRUE. If not let e1 and e2 be the two cheapest edges. Then adding e2 to T creates a cycle of lenght at least 3, which must have a more expansive edge to drop.
E6: Use $6f=2e$ and $2e \ge 3v$ and $v-e+f=2$ to get $$ 2e/3+2=v\le 2e/3 $$ which is impossible.