Proof of Konig's theorem on matchings I'm trying to work through a proof of Konig's Theorem, and there are a few steps where I am completely stuck.  First I state the theorem and sketch the proof, then mention where I am stuck, and all terminology is defined as an addendum.  I am hoping someone can help me!
$\bf\text{Konig's Theorem}$  Let $(X,Y,E)$ be a $k$-regular bipartite graph.  Then there exists a perfect matching of $X$ and $Y$.
$\bf\text{Proof}$:
$\color{blue}{(1)}$ First the problem is reduced to the case where every two points in $V=X\cup Y$ are joined by a path and both $|X| =|Y| = \infty$.
$\color{blue}{(2)}$ Now fix $x\in X,y\in Y$, and define
$$
Z_{1} = \{x,y\} \cup V(\{x,y\})\text{ and } Z_{n} = V(Z_{n-1})\text{ for all }n\geq 2.
$$
and then $X_{n} = X\cap Z_{n}, Y_{n} = Y\cap Z_{n}$, and $E_{n}$ is the set of all edges in $E$ used in the definition of $Z_{n}$.
$\color{blue}{(3)}$ For each $n\geq 1$, $(X_{n},Y_{n},E_{n})$ is a bipartite subgraph in which each vertex is an endpoint of at most $k$ vertices.
Choose a $k$-regular subgraph $(X_{n}', Y_{n}', E_{n}')$ of $(X,Y,E)$ such that $(X_{n},Y_{n},E_{n})$ is a subgraph of $(X_{n}', Y_{n}', E_{n}')$.
By the Marriage theorem, there is a perfect matching of $X_{n}'$ with $Y_{n}'$, which restricts to a perfect matching of $X_{n}$ with a subset of $Y$.
$\color{blue}{(4)}$ Finally, we define a sequence $(F_{n})_{n=1}^{\infty}$ with the following properties:
(i) $F_{n}$ is a perfect matching of $X_{n}$ with a subset of $Y$.
(ii) $F_{j}\subset F_{n}$ whenever $j\leq n$.
(iii) For all $m > n$, there exists a perfect matching $F_{m}'$ of $X_{m}$ with a subset of $Y$ such that $F_{n}\subset F_{m}$.
$\color{blue}{(6)}$ $F:=\bigcup_{n=1}^{\infty}F_{n}$ is a perfect matching of $X$ with $Y$, which completes the proof.
$\bf\text{Things I am completely stuck on:}$
$\color{red}{(1)}$ I do not see how in step $\color{blue}{(3)}$ we get such a graph $(X_{n}',Y_{n}',E_{n}')$.  I worked out a few examples and it seems easy to do in any specific case: just add enough points/edges wherever they are needed.  But I can't seem to abstract the intuition into a proof.
$\color{red}{(2)}$ I cannot seem to work out the existence of such a sequence.  The details of the proof define the sequence inductively.  By $k$-regularity, there are only finitely many ways to form a perfect matching between $X_{1}$ and a subset of $Y$, therefore $F_{1}$ may be chosen to satisfy $(i)$ to $(iii)$.  If $F_{1}\subset \dots F_{n}$ are defined satisfying $(i)$ to $(iii)$ then since there are only finitely many ways to form a perfect matching between $X_{n+1}$ and a subset of $Y$, $F_{n+1}$ may be chosen to satisfy $(i)$ to $(iii)$.
$\color{red}{(3)}$ Based on the proof, $F$ should be a perfect matching between $X$ and a subset of $Y$.  Why does this give us a perfect matching of $X$ and $Y$?
(Note:  I am mostly concerned with $\color{red}{(2)}$, I feel like $\color{red}{(1)}$ is not important to understand the bigger idea of the proof, and I feel like $\color{red}{(3)}$ will dawn on me soon enough.
Thanks very much to anyone who can explain it to me!
$\bf\text{Background Terminology}$
Let $(V,E)$ be a graph.
$(V,E)$ is $k$-regular if every vertex in $V$ is the endpoint of exactly $k$ edges in $E$.  
$(V,E)$ is bipartite if there exists a partition $\{A,B\}$ of $V$ such that every edge in $E$ joins an element of $A$ with an element of $B$.  In this case $(X,Y,E)$ also means $(V,E)$
For a subset $S\subset V$, $V(S)$ is the set of all vertices in $V$ which are joined to an vertex in $S$ via some edge in $E$.
For subsets $A\subset X,B\subset Y$, a perfect matching of $A$ and $B$ is a subset $F\subset E$ such that $F$ is a bijection from $A$ to $B$.
$\bf\text{Marriage Theorem}$  Let $(X,Y,E)$ be a $k$-regular bipartite graph such that $|X\cup Y| < \infty$.  Then there exists a perfect matching of $X$ and $Y$.
 A: (1) Corrected: Let $G_n(0)=\langle X_n,Y_n,E_n\rangle$. If $G_n(i)$ is not $k$-regular, let $G_n(i+1)$ be the graph obtained by adding the missing neighbors of the vertices of $G_n(i)$; otherwise let $G_n(i+1)=G_n(i)$. Then the union of the $G_n(i)$ for $i\in\Bbb N$ is $k$-regular and has $G_n(0)$ as subgraph. However, this union may be the original graph $\langle X,Y,E\rangle$, as may be seen by considering the case in which $X$ is the set of even integers, $Y$ is the set of odd integers, and $x$ and $y$ are adjacent iff $|x-y|=1$: this graph is $2$-regular and connected and has no finite $2$-regular subgraph. Thus, there seems to be a genuine gap in the argument here, although the graph in question certainly does admit a perfect matching.
What’s really needed is a finite expansion of $\langle X_n,Y_n,E_n\rangle$ to a subgraph $\langle X_n',Y_n',E_n'\rangle$ of $\langle X,Y,E\rangle$ that satisfies the hypotheses of the marriage theorem; I’ll have to think about that a bit.
(2) We know that for each $n$ there is a perfect matching of $X_n$ with a subset of $Y$; let $\mathscr{F}_n$ be the set of all such perfect mappings. If $F_m\in\mathscr{F}_m,F_n\in\mathscr{F}_n$, and $m\le n$, write $F_m\preceq F_n$ iff $F_m$ is the restriction of $F_n$ to $X_m$. Let $\mathscr{F}=\bigcup_{n\in\Bbb Z^+}\mathscr{F}_n$. For each $F\in\mathscr{F}_1$ let $$N(F)=\{n\in\Bbb Z^+:F\preceq F_n\text{ for some }F_n\in\mathscr{F}_n\}\;;$$ $\mathscr{F}_1$ is finite, so there must be some $F_1\in\mathscr{F}_1$ such that $N(F_1)$ is infinite. This implies that $N(F_1)=\Bbb Z^+$; why? Now let $\mathscr{F}_2'=\{F\in\mathscr{F}_2:F_1\preceq F\}$; $\mathscr{F}_2'\ne\varnothing$ by the choice of $F_1$. For $F\in\mathscr{F}_2'$ let $$N(F)=\{n\ge 2:F\preceq F_n\text{ for some }F_n\in\mathscr{F}_n\}\;;$$ by the same reasoning as before there must be some $F_2\in\mathscr{F}_2'$ such that $N(F_2)$ is infinite and therefore equals $\{n\in\Bbb Z^+:n\ge 2\}$. Now let $\mathscr{F}_3'=\{F\in\mathscr{F}_3:F_2\preceq F\}$, and repeat. In this way you can recursively construct a sequence $\langle F_n:n\in\Bbb Z^+\rangle$ such that each $F_n$ is a perfect matching of $X_n$ with a subset of $Y$, and $F_n$ extends $F_m$ whenever $m\le n$. (I’ll leave it to you to write down the general step of the construction, from $F_n$ to $F_{n+1}$.)
Since for each $m,n\in\Bbb Z^+$ the matchings $F_m$ and $F_n$ agree on $X_{\min\{m,n\}}$, $F=\bigcup_{n\in\Bbb Z^+}F_n$ is a matching of $\bigcup_{n\in\Bbb Z^+}X_n=X$ with a subset $Y_0$ of $Y$.
(3) All that remains is to verify that $Y_0=Y$. The construction in $\color{blue}{(3)}$ ensures that if $v\in X_n\cup Y_n$, then every neighbor of $v$ belongs to $X_{n+k}\cup Y_{n+k}$. Thus, if $y\in Y$, there is an $n\in\Bbb Z^+$ such that $y\in Y_n$, and each neighbor of $y$ is in $X_n$. The complete matching of $X_n'$ with $Y_n'$ must include an edge between $y$ and one of these neighbors, and that edge will be part of the restriction of the matching to $X_n$. Thus, $y$ will be used in every matching in $\mathscr{F}_m$ for $m\ge n$, and it follows that $Y_0=Y$.
