Skip to main content
1 of 1
Louis D
  • 1.7k
  • 13
  • 27

K"onig's theorem says that in every bipartite graph $G=(U,V; E)$, the size of a maximum matching (a collection of disjoint edges) equals the size of a minimum vertex cover (a collection of vertices which intersects every edge). If the size of the matching is finite, this is a non-trivial result. However, if the size of the matching is infinite, this result is trivial.

Erd"os suggested the following reformulation of K"onig's theorem: in every bipartite graph $G=(U,V; E)$ there exists a matching $M$ and a vertex cover $C$ such that for all $e\in M$, $|e\cap C|=1$. He conjectured that this reformulated version of K"onig's theorem is true for all infinite bipartite graphs.

Aharoni gave a highly non-trivial proof of Erd"os' conjecture (Koenig’s duality theorem for infinite bipartite graphs, J. Lond. Math. Soc., II. Ser. 29, 1-12 (1984). ZBL0505.05049.).

An analogous situation exists for Menger's theorem, so I'm not sure if it's worth spelling it all out, but I will say that the proof of the infinite version of the reformulated Menger's theorem was finally completed in a 62 page paper of Aharoni and Berger (Menger’s theorem for infinite graphs, Invent. Math. 176, No. 1, 1-62 (2009). ZBL1216.05092.).

Louis D
  • 1.7k
  • 13
  • 27