Satz von König (Graphentheorie)

Der Satz von König ist ein grundlegender Satz aus dem mathematischen Gebiet der Graphentheorie, der für bipartite Graphen einen Zusammenhang zwischen einer größten Paarung und einer kleinsten Knotenüberdeckung aufzeigt. Er lautet:

In einem bipartiten Graphen ist die Größe einer größten Paarung gleich der Größe einer kleinsten Knotenüberdeckung.

Der Satz ist nach dem ungarischen Mathematiker Dénes Kőnig benannt, der ihn 1931 bewiesen hat. Er ist, wie sich zeigen lässt, als gleichwertig mit dem Hall'schen Heiratssatz aufzufassen, weswegen er auch als Satz von König–Hall (englisch König–Hall theorem) bekannt ist. Darüber hinaus hat der Mathematiker Jenő Egerváry – unabhängig von König und ebenfalls im Jahre 1931 – eine allgemeinere Fassung des Theorems für gewichtete Graphen bewiesen. Deshalb wird der Satz manchmal auch als Satz von König–Egerváry (englisch König–Egerváry theorem) bezeichnet.

Der Satz lässt sich auch auf unendliche Graphen übertragen, wie schon Paul Erdős vermutete und wie Ron Aharoni bewies.