The Dinitz Problem - proof This theorem is the one that the proof is for

Consider $n^2$ cells arranged in an $(n × n)$-square, and let $(i, j)$
  de- note the cell in row $i$ and column $j$. Suppose that for every
  cell $(i, j)$ we are given a set $C(i, j)$ of $n$ colors. Is it then
  always possible to color the whole array by picking for each cell $(i,
 j)$ a color from its set $C(i, j)$ such that the colors in each row
  and each column are distinct?

Lemma 1: Let $\overrightarrow G =(V,E)$ be a directed graph, and suppose that for each
  vertex $v \in V$ we have a color set $C(v)$ that is larger than the
  outdegree, $|C(v)| \ge d^+(v) +1$. If every induced subgraph of G
  possesses a kernel, then there exists a list coloring of $\overrightarrow G$ with a
  color from $C(v)$ fo each $v$.

Lemma 2: A stable matching always exits.

Proof:

As before we denote the vertices of $S_n$ by $(i, j), 1 ≤ i, j ≤ n$
  Thus $(i, j)$ and $(r, s)$ are adjacent if and only if $i = r$ or $j = s$. Take any Latin square $L$ with letters from ${1, 2, . . . , n}$
  and denote by $L(i, j)$ the entry in cell $(i, j)$. Next make $S_n$
  into a directed graph $S_n$ by orienting the horizontal edges $(i, j)→(i, j ′ )$ if $L(i, j) < L(i, j ′ )$ and the vertical edges $(i, j)→ (i′ , j)$ if $L(i, j) > L(i′ , j)$. Thus, horizontally we orient
  from the smaller to the larger element, and vertically the other way
  around. (In the margin we have an example for $n = 3$.) Notice that we
  obtain $d^+ (i, j) = n − 1$ for all $(i, j)$. In fact, if $L(i, j) = k$, then $n − k$ cells in row $i$ contain an entry larger than $k$,
  and $k − 1$ cells in column $j$ have an entry smaller than $k$. 
  By
  Lemma 1 it remains to show that every induced subgraph of $S_n$
  possesses a kernel. Consider a subset $A ⊆ V$ , and let $X$ be the set
  of rows of $L$, and $Y$ the set of its columns. Associate to $A$ the
  bipartite graph $G = (X ∪ Y, A)$, where every $(i, j) \in A$ is
  represented by the edge $ij$ with $i \in X$, $j \in Y$ . In the
  example in the margin the cells of $A$ are shaded.
  The orientation on $S_n$ naturally induces a ranking on the
  neighborhoods in $G = (X ∪ Y, A)$ by setting $j ′ > j$ in $N (i)$ if
  $(i,j)→ (i,j′)$ in $S_n$ respectively $i′ > i$ in $N (j)$ if $(i, j) → (i′,j)$.
  By Lemma 2, $G = (X ∪ Y, A)$ possesses a stable
  matching $M$ . This $M$ , viewed as a subset of $A$, is our desired
  kernel! To see why, note first that$ M$ is independent in $A$ since as
  edges in $G = (X ∪ Y, A)$ they do not share an endvertex $i$ or $j$.
  Secondly, if $(i,j) ∈ A$\ $M$ , then by the definition of a stable
  matching there either exists $(i,j′) \in M$ with $j′> j$ or $(i′ , j) ∈ M$ with $i′ > i$, which for $S_n$ means $(i,j) → (i, j ′) \in M$
  or $(i,j)→ (i′,j)\in M$ , and the proof is complete.

I'd like to ask if someone can help me out with this proof from
M. Aigner, Günter M. Ziegler: Proofs from THE BOOK (4th edition)
I don't get the part under the line. I'd be grateful if someone can explain the proof more detailed. Sorry for not posting whole article but it is too long. Here is a LINK for that proof. If someone could clarify me that second part I'd be grateful.

EDIT: Added theorem.
EDIT2: Added lemmas.
EDIT3: Added bounty-> changed requirements.
 A: Since no one else has responded with an answer to date, I’ll offer a few annotations to the exposition in Aigner and Ziegler’s “Proofs From the Book” in the hope that it may clarify matters a bit for the person who posted the question.


*

*When Aigner and Ziegler refer to $V$ in the proof, they mean the vertex set of the directed graph $\vec S_n$.

*The subset $A$, in the context of the Dinitz problem, represents the set $A\left( c \right) = \left\{ {v \in V|c \in C\left( v \right)} \right\}$  where $C\left( v \right)$ is the list of colors available to vertex $v$ (this set was described in the proof of Lemma 1 in the book).  That is, pick a color $c$.  Then $A\left( c \right)$ represents all of the vertices which contain $c$ in their color list.  Since the Dinitz problem applies to all possible assignments of color lists of size $n$ to the $n^2$ cells in a square grid, $A$ can be any possible subset of $V$ (except the empty set, since that would imply that $c$ is not in any vertex’s color set).  To apply Lemma 1 to the Dinitz problem, we have to show that every induced subgraph of $\vec S_n$ by $A$ has a kernel, where we allow $A$ to be any nonempty subset of $V$.

*The edges of the bipartite graph $G = \left( {X \cup Y,A} \right)$ are simply defined using the coordinates $\left( {i,j} \right)$ of the elements of $A$ as described in the text.

*The purpose of the Latin square $L$ is to generate a directed graph $\vec S_n$ that (i) satisfies the hypotheses of Lemma 1, and (ii) which can be used to generate a list of rankings for each of the vertices of the bipartite graph $G = \left( {X \cup Y,A} \right)$.  Regarding (i), this is guaranteed by the observation that $d^+\left( {i,j} \right) = n - 1$ (recall that $\left| C\left( v \right) \right| = n$ for the Dinitz problem).  Regarding (ii), note that any Latin square will suffice to generate a strict ordering along each row and column given the recipe provided in the text to orient the directed graph $\vec S_n$. This then translates directly into a ranking for the neighborhoods of the bipartite graph (more on the ranking below).  Lemma 2 then guarantees the existence of the stable matching $M$.

*The stable matching $M$ can be viewed as a subset of $A$ by converting the edges $uv$ of $M$ back into vertices described by the coordinates $(u,v)$.  Let $\vec G_A$ denote the subgraph of $\vec S_n$ induced by $A$.  Consider the subgraph of $\vec G_A$ by induced by $M$ (call it $\vec G_M$).  $\vec G_M$ has no edges since if it did, that would violate the definition of a matching (“no bigamy” per Aigner and Ziegler’s description).  So we have that $M$ is independent in $A$.

*To complete the demonstration that $M$ is a kernel for the subgraph of $\vec S_n$ induced by $A$ (which we’re calling $\vec G_A$), Aigner and Ziegler note that since $M$ is a stable matching, then if $\left( {i,j} \right) \in A\backslash M$ we know that either (i) $\left( {i,j'} \right) \in M$ with $j' > j$ or (ii) $\left( {i',j} \right) \in M$ with $i' > i$.  Consider case (i).  Recall that Aigner and Ziegler’s ranking scheme says that $j' > j$ if the edge $\left( {i,j} \right) \to \left( {i,j'} \right)$ belongs to $\vec S_n$, and therefore this edge belongs to the $\vec G_A$ if $j' > j$.  For case (ii), we similarly see that the edge $\left( {i,j} \right) \to \left( {i',j} \right)$ belongs to the $\vec G_A$ if $i' > i$.  But this is all we needed, in addition to the observation that $M$ is independent in $A$, to demonstrate that $M$ is a kernel for $\vec G_A$.


If you still have questions about the proof that I haven't answered here, let me know specifically what your question is and I'll try to address it.
