= Solution
Each <vertex> of a <bipartite graph> has a strict <preference> ordering of its <neighbours>; every <neighbour> is preferred to being unmatched. A <stable matching in a bipartite graph> is a <matching in a graph> with no blocking <edge>: an unused <edge> blocks if both endpoints prefer each other to their assigned partners, interpreting an unmatched endpoint as willing to accept any <neighbour>. Stability does not require a perfect <matching in a graph>.
For existence, run the <Gale-Shapley algorithm>. Whenever a <vertex> in the first part is unmatched and has an untried <neighbour>, it proposes to its most preferred untried <neighbour>. A receiver keeps its preferred proposal and rejects the other, including any previously held proposal. At most $e(G)$ proposals occur, so the procedure stops with a <matching in a graph>. Suppose an <edge> $bg$ blocked this final <matching in a graph>. Since $b$ prefers $g$ to its final partner, or is unmatched, $b$ must have proposed to $g$. But a receiver's held proposal only improves, so $g$'s final partner is preferred to $b$ if $b$ was rejected. If $b$ was not rejected, the <edge> is in the <matching in a graph>. Both alternatives contradict blocking. \b[Every finite bipartite preference instance therefore has a <stable matching>.]
For the <mutual-worst edge in stable matchings>, let $M,N$ be <stable matchings> with $bg\in M$ and $bg\notin N$. We give the argument using alternating <graph components> including possible unmatched endpoints. If $b$ were unmatched in $N$, then $g$ would have to prefer its $N$-partner to $b$, since otherwise $bg$ would block $N$. Following the $N$-edge from $g$, stability of $M$ forces its other endpoint to have and prefer an $M$-partner. Stability of $N$ then forces the next <vertex> to have and prefer an $N$-partner. These implications continue along the alternating <graph component> of $M\mathbin\triangle N$. They cannot stop, because at a missing next <edge> the preceding <edge> would block the appropriate <matching in a graph>. They also cannot close into a <cycle in a graph>, since the <graph component> already has endpoint $b$. This contradiction proves that $b$ is matched in $N$. The same reasoning applies to $g$.
Now $b$ prefers its $N$-partner to $g$, because $g$ is its worst choice. Along the alternating <graph component>, stability of $M$ forces that partner to prefer its $M$-partner; stability of $N$ forces the next <vertex> in $b$'s part to prefer its $N$-partner, and so on. A <graph path> <graph component> is impossible by the same endpoint argument, so this is a <cycle in a graph>. Thus throughout this <cycle in a graph> the part containing $b$ prefers $N$ and the part containing $g$ prefers $M$. In particular $g$ must prefer $b$ to its $N$-partner. That contradicts $b$ being $g$'s worst choice. Hence \b[an <edge> ranked last by both endpoints, if present in one <stable matching>, is present in every <stable matching>].
For the <list edge coloring> assertion, let $\Delta$ be the <maximum degree>. We first prove that the <chromatic index> is $\Delta$. Use <induction> on the number of <edges>, with a proper $\Delta$-<edge coloring> of $G-uv$. Some color $a$ is missing at $u$ and some color $b$ is missing at $v$. If $a=b$, color $uv$ with it. Otherwise the <edges> of colors $a,b$ form alternating <graph paths> and even <cycles in a graph>. The <graph component> containing $u$ cannot contain $v$: an alternating <graph path> from $u$, starting with color $b$, would end at $v$ with color $a$, have even length, and place $u,v$ in the same bipartition class. Swap $a,b$ in the <graph component> containing $u$. Now $b$ is missing at both ends of $uv$, so it can be colored $b$. The lower bound $\chi'(G)\ge\Delta$ is immediate at a <vertex> of <vertex degree> $\Delta$.
Fix such a proper <coloring> $c:E(G)\to\{1,\ldots,\Delta\}$. Orient the <line graph> toward the smaller color at <vertices> in the first part of $G$, and toward the larger color at <vertices> in the second part. A <vertex> of the <line graph> corresponding to an <edge> of color $j$ has <outdegree> at most
$$
(j-1)+(\Delta-j)=\Delta-1.
$$
Every <induced subgraph> of this orientation has a <digraph kernel>. Indeed, restrict to its <edge> <set> in the original <bipartite graph>, give first-part <vertices> a preference for smaller colors and second-part <vertices> a preference for larger colors, and choose a <stable matching>. Its <edges> form an <independent set> in the <line graph>. Every <edge> outside the <matching in a graph> has an endpoint whose partner is preferred to it, by stability; thus it has an outgoing <edge> to the <independent set>. This proves that the orientation is a <kernel-perfect directed graph>.
Here is the <kernel list-coloring lemma> with its proof. If a <kernel-perfect directed graph> $D$ has lists satisfying $|L(v)|\ge d_D^+(v)+1$, choose any color $a$ appearing in a list and a <digraph kernel> $K$ of the <induced subgraph> on <vertices> whose lists contain $a$. Color $K$ with $a$, delete $K$, and delete $a$ from the remaining lists. Each remaining <vertex> that loses a color had an outgoing <neighbour> in $K$, so its <outdegree> decreases by at least one; the list inequality persists. <Vertices> not losing a color also retain the inequality. <Induction> on the number of <vertices> completes a proper list <coloring>.
Lists of size $\Delta$ satisfy that lemma for our oriented <line graph>, so $\chi'_\ell(G)\le\Delta$. Identical lists show $\chi'_\ell(G)\ge\chi'(G)$. Consequently the <Galvin theorem for bipartite list edge coloring> gives
$$
\boxed{\chi'_\ell(G)=\chi'(G)=\Delta(G).}
$$
The empty <graph> is immediate; if parallel <edges> are allowed, orient their line-graph adjacency in both directions when the two endpoints prescribe opposite directions. The <outdegree> bound still holds, and the same <stable matching> and <digraph kernel> proof applies with preferences on incident <edges>.
Back to article page
