Kőnig's theorem states that in a bipartite graph the size of the maximal matching equals the size of the minimal vertex cover.
I learned it as an equivalence to Hall's theorem and we proved it using Hall's theorem. We also proved it to be equivalent to Dilworth's theorem.
Both Hall's theorem and Dilworth's theorem have counterexamples on infinite graphs/partially ordered sets. Since they are equivalent I would expect that there exists a counter example to Kőnig's theorem as well, but I didn't manage to find one.
It would make sense to me, if we go to the infinite graphs (matching $M$, vertex cover $U$) $|U| \geq |M|$ still holds. So I need to find either an infinite graph, which has both only finite and fulfills the condition above or have one infinite and the other finite or to have different infinite cardinalities.
Best Answer
For any graph $G$, not necessarily finite or bipartite, let $\beta(G)$ be the minimum size of a vertex cover of $G$.
I believe you know the following two facts:
Theorem 1. In any graph $G$, any matching $M$ satisfies $|M|\le\beta(G)$.
Theorem 2. (Kőnig) Any finite bipartite graph $G$ contains a matching $M$ such that $|M|=\beta(G)$. (In view of Theorem 1, this means that $\beta(G)$ is the maximum cardinality of a matching in $G$.)
Your question (as I understand it) is answered by the following observations:
Theorem 3. Let $G$ be any bipartite graph. If $\beta(G)$ is finite, then $G$ contains a matching $M$ such that $|M|=\beta(G)$.
Proof. Let $M$ be a matching in $G$ of maximum size, and assume for a contradiction that $|M|=m\lt\beta(G)$. Let $U_1,\dots,U_{2^m}$ be all of the $m$-element sets obtained by taking one endpoint of each edge in $M$. For each $i\in\{1,\dots,2^m\}$, since $|U_i|\lt\beta(G)$, we can choose an edge $e_i$ of $G$ which is not covered by $U_i$. Let $H$ be a finite subgraph of $G$ containing the edges of $M$ and the edges $e_i$. By Theorem 2, $H$ contains a matching $N$ of size $|N|=\beta(H)\gt m=|M|$, contradicting the assumption that $M$ is a maximum matching.
Theorem 4. Let $G$ be any graph. If $\beta(G)$ is infinite, then $G$ contains a matching $M$ such that $|M|=\beta(G)$.
Proof. By Zorn's lemma, $G$ contains a maximal (*) matching. Let $M$ be any maximal matching in $G$, and assume for a contradiction that $|M|=\kappa\lt\beta(G)$. Let $U$ be the set of all endpoints of edges in $M$. Since $|U|=2|M|=2\kappa\lt\beta(G)$, there is an edge $e$ of $G$ which is not covered by $U$. Then $M\cup\{e\}$ is a matching in $G$ which properly extends $M$, contradicting the assumed maximality of $M$.
Corollary. Any bipartite graph $G$ contains a matching $M$ with $|M|=\beta(G)$, that is, $\beta(G)$ is the maximum cardinality of a matching in $G$.
(*) A maximAL matching is a matching which cannot be properly extended; not the same thing as maximUM matching, which is a matching of maximum possible cardinality.