Satz von Hall

Def: Graph G = (V, E) heißt bipartit (paar), falls existieren X, Y mit X $\cap$ Y = $\emptyset$, X $\cup$ Y = V, E $\subseteq$ X×Y $\cup$ Y×X.

Bezeichnung: G = (X, Y, E).

Def: Für S $\subseteq$ V, setze G(S) = {y | $\exists$x $\in$ S, y $\in$ V : xy $\in$ E}.

Satz (Hall): Für bipartite Graphen G = (X, Y, E) sind äquivalent:

• G besitzt Matching, das X sättigt
• $\forall$S $\subseteq$ X : | S|$\le$| G(S)|

Aufgabe: beweise (durch Beispiele), daß die Voraussetzung ,,G bipartit`` nötig ist.