Ein Matching in einem Graphen ist eine Teilmenge der Kanten, die keine Ecke mehrfach enthält. Typische Probleme, die zu Matchings führen, sind Zuordnungsprobleme: Teams sollen in einer Turnierrunde gepaart werden, Veranstaltungen sollen Räume zugeordnet werden. Meistens sucht man dabei möglichst große Matchings. Das kann in beliebigen Graphen recht aufwändig werden, es gibt aber gute Kriterien, die bei der Suche nach maximalen Matchings helfen. Für bipartite Graphen gibt es einen sehr effizienten Algorithmus (ungarische Methode) und ein sehr schönes Kriterium (Heiratssatz von Hall). Außerdem kann man Matchings als unabhängige Kantenmengen auffassen. Das geht analog für Ecken, und man kann jeweils umgekehrt auch Überdeckungen betrachten. Diese vier Typen von Mengen haben interessante Verbindungen, die im letzten Abschnitt des Kapitels erklärt werden.