Vollständiger Graph/Paarung/Maximal und optimal/Aufgabe/Kommentar

In einem vollständigen Graphen ${}K_{n}$ sind je zwei Knotenpunkte miteinander durch eine Kante verbunden. Eine Paarung ${}P$ in ${}K_{n}$, die mindestens zwei Knotenpunkte ${}u,v$ von ${}K_{n}$ nicht abdeckt, ist somit nicht maximal, da ${}P\cup \{u,v\}$ wieder eine Paarung in ${}K_{n}$ ist. Dies bedeutet, dass jede maximale Paarung in ${}K_{n}$ mindestens ${}n-1$ Knotenpunkte abdecken muss (oder genauer: jede maximale Paarung in ${}K_{n}$ abdeckt genau ${}2\lfloor n/2\rfloor$ Knotenpunkte und enthält genau ${}\lfloor n/2\rfloor$ Kanten). Daher muss jede maximale Paarung optimal sein.

Zur kommentierten Aufgabe