Angenommen also, wir haben keinen Baum, dann gibt es einen minimalen Kreis. Dieser minimale Kreis kann nicht durch alle Ecken gehen, denn sonst hätten wir ein n-Eck, was wie oben gesagt, nicht möglich ist. Also gibt es (weil der Graph i, er noch zusammenhängend ist) mindestens einen weiteren mit dem Kreis verbundenen Knoten. Wenn dieser nicht mit den benachbarten Knoten des Kreises verbunden ist, dann sind wir fertig. Wenn doch, dann haben wir zwei Dreiecke. Weil wir von einem minimalen Kreis ausgegangen sind, muß dieser auch ein Dreieck gewesen sein. Man kann jetzt wie folgt argumentieren: die verschiedeneren Dreiecke können sich zu einem größeren vollständigen Graphen zusammensetzen, dieser kann aber nicht der vollständige Graph auf 2019 Ecken sein, weil der Ausgangsgraph nicht vollständig war und im Laufe des Prozesses die Kantenzahl reduziert wurde. Man betrachtet also einen maximalen vollständigen Teilgraphen (ggf. nur ein Dreieck), dazu findet man wegen der Maximalität einen benachbarten Knoten, der mit einem anderen Knoten des vollständigen Teilgraphen nicht benachbart ist. Durch die Knoten des vollständigen Teilgraphen kann man dann einen Kreis legen, der die am Ende des vorigen Abschnitts formulierte Bedingung erfüllt, also zu dem man einen weiteren verbundenen Knoten findet, der mit einem Knoten des Kreises, aber nicht dessen einem Nachbarn verbunden ist.
Man kann also, solange es noch Kreise gibt, auf jeden Fall den Prozeß fortführen und die Anzahl der Kanten reduzieren (und den Graphen zusammenhängend halten) bis man nach endlich vielen Schritten keine Kreise und damit einen Baum hat, von dem man dann auf den gewünschten Graphen aus 505 isolierten Kanten kommt.
Das war die zweite Lösung der Musterlösungen, die erste ist aufwändiger, weil sie mehr Fallunterscheidungen benötigt.
Man kann das Problem auch noch in einen allgemeineren Kontext stellen, indem man für jeden beliebigen Graphen beweist, dass er sich durch Anwenden dieser Operation entweder in einen Baum oder in ein n-Eck verwandeln läßt. Da, wie oben gesagt,aus dem Graphen in der Aufgabenstellung (weil es Knoten ungeraden Grades gibt) kein n-Eck erzeugt werden kann, muß man diesen Graphen also in einen Baum verwandeln können. Diesen allgemeinen Beweis führt Presh Talwalkar RedPig (Retired Contestants of Math Olympiads) im folgenden Video vor:
Kommentare (3)