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:

1 / 2

Kommentare (3)

  1. #1 ddg225
    14. August 2019

    Ein wenig off-topic – aber sicher, dass der Kanal RedPig auch von Presh Talwalkar ist?

  2. #2 Karl-Heinz
    15. August 2019

    @Thilo

    Danke für die mehr als ausführliche Interpretation der Lösung. Da macht das Lesen deiner Hinweise ungeheueren Spaß. 😉

  3. #3 Braunschweiger (DE)
    17. August 2019

    Sehr schön. Alles noch einmal nett auf Deutsch erklärt und einige Punkte diskutiert; Punkte, an denen ich auch meine Schwierigkeiten hatte.

    Es fällt nicht nur in diesem Artikel oder hier in Thilos Blog auf, dass Artikel über Graphen gerne mit Bildern von Graphen illustriert werden. Einen netten aufschlussreichen Text gabe es dazu auch von Spektrum.de.

    Graphen können mit Topologie zu tun haben. Dazu mal die Frage an den Fachmann: Können Graphen zur Untersuchung oder auch nur zur Erläuterung von topologischen Fragen vorteilhaft genutzt werden? – Ich meine eben, über das hinaus, was zB. bei der Topologischen Graphentheorie genannt wird.
     

    Anhand dieser Lösung habe ich noch den Graphen #25 aus dem Aufgaben-Thread mit n = 2 zuende geführt und die Reduktionen angewendet; siehe dort hinterm Link.