besteht darin, einen Stundenplan zu erstellen, der in kürzester Zeit alle Unterrichtsstunden abdeckt.

Gibt es an einer Schule z. B. p Lehrer A₁, A₂, …, A_p und q Klassen B₁, B₂, …, B_q, so unterrichte der Lehrer A_i die Klasse B_j für t_ij Stunden. Zur Lösung des Stundenplanproblems konstruiert man einen bipartiten Multigraphen G mit den beiden Partitionsmengen A = {a₁, a₂, …, a_p} und B = {b₁, b₂, …, b_q}, wobei A den Lehrern und B den Klassen entspricht. Dann werden die Ecken a_i und b_j durch t_ij parallele Kanten verbunden.

In jeder Zeiteinheit (z. B. montags von 8.00–9.00 Uhr, 9.00–10.00 Uhr usw.) kann ein Lehrer höchstens eine Klasse unterrichten, und jede Klasse kann von höchstens einem Lehrer unterrichtet werden. Somit entspricht während einer Zeiteinheit die Zuordnung der Lehrer zu den Klassen einem Matching in dem bipartiten Multigraphen G, und umgekehrt entspricht jedes Matching einer möglichen Zuordnung. Daher ist das Stundenplanproblem gleichbedeutend damit, die Kantenmenge von G in möglichst wenige kantendisjunkte Matchings zu zerlegen. Ist Δ (G) der Maximalgrad von G und r(G) die minimale Anzahl solcher kantendisjunkter Matchings, so gilt natürlich r(G) ≥ Δ (G). Nach einem Satz von König aus dem Jahre 1916 gilt aber für bipartite Multigraphen sogar r(G) = Δ (G), womit ein optimaler Stundenplan aus genau.(G) Zeiteinheiten besteht.

Bei der praktischen Durchführung einer solchen Zerlegung in Δ (G)kantendisjunkte Matchings kann man etwa wie folgt vorgehen. Ist ohne Beschränkung der Allgemeinheit q ≤ p, so fügen wir p − q neue Ecken b_q+1, b_q+2, …, b_p zu B hinzu und setzen Y = {b₁, b₂, …, b_p}. Nun verbinden wir die Ecken aus A mit denen aus Y durch \begin{eqnarray}p\Delta (G)-\displaystyle \sum _{x\in A}{d}_{G}(x)=p\Delta (G)-\displaystyle \sum _{y\in Y}{d}_{G}(y)\end{eqnarray}

zusätzliche Kanten, sodaß daraus ein Multigraph H entsteht, der die Bedingung Δ(H) = Δ(G) erfüllt. Nach Konstruktion ist auch H bipartit und darüber hinaus sogar Δ(G)-regulär. Wegen eines Satzes von König läßt sich daher die Kantenmenge von H in Δ(G) disjunkte perfekte Matchings zerlegen. Eine solche Zerlegung kann man sich z. B. mit Hilfe des Ungarischen Algorithmus beschaffen. Entfernt man aus diesen Δ(G) perfekten Matchings von H die neu hinzugefügten Kanten, so erhält man schließlich die gewünschte Zerlegung von K(G) in Δ(G) kantendisjunkte Matchings.