StartseiteMathlog

Die Facebook-Aufgabe

Von / 10. August 2019 / 33 Kommentare
Mehr

Die folgende Aufgabe stammt von der Internationalen Mathematikolympiade, die Mitte Juli in Bath stattfand, und sie ist erheblich schwieriger als man vielleicht zunächst denken würde.

Ein soziales Netzwerk hat 2019 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet. Ereignisse der folgenden Art können wiederholt nacheinander stattfinden:
Drei Nutzer A, B und C, von denen A mit B und C befreundet ist, aber B und C nicht befreundet sind, wechseln den Status ihrer Freundschaften so, dass jetzt B und C befreundet sind, aber A nicht mehr mit B befreundet ist und auch nicht mehr mit C befreundet ist. Der Status aller anderen Freundschaften bleibt unverändert.

Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet. Man beweise, dass es eine Folge solcher Ereignisse gibt, nach der jeder Nutzer höchstens mit einem anderen Nutzer befreundet ist.

Bei der Olympiade gewann übrigens Jonas Walter aus Rostock eine Goldmedaille. In der (deutschen) Presse scheint das Ereignis dieses Jahr völlig ignoriert worden zu sein.

Stichworte:
Mehr

Kommentare (33)

  1. #1 Mars
    10. August 2019

    häää, … bin nicht bei fazebuck
    als ich abi machte – lang ist her, zu lang
    wäre es mir wohl möglich gewesen der frage zu folgen … und evt eine lösung zu präsentieren.
    aber heute stehe ich wie der ochs’ vor dem berg.
    da warte ich mal ab, was da so kommt – ehrlich!
    sommerliches grüssle

  2. #2 Joseph Kuhn
    10. August 2019

    Wenn sich nach dem ersten – beliebigen – Wechsel außer zwei – dann noch – Befreundeten alle anderen aus dem Netzwerk abmelden, sollte es klappen. Aber diese “Lösung” war vermutlich nicht gemeint.

    Aber warum sollte die Presse darüber schreiben? Die schreibt ja nicht mal drüber, dass die Quersumme des heutigen Datums (in Deutschland, also 9.8.2019, nicht Blogdatum) 29 ist, eine Primzahl, somit die Summe der Teiler 30, also die unmittelbar darauf folgende Zahl. Indische Zahlenmystiker leiten daraus ab, dass morgen Samstag ist. Die Presse wird darüber nicht berichten, meine Vorhersage. Nostradamus wusste es sicher.

  3. #3 Karl-Heinz
    Graz
    10. August 2019

    @Mars

    Man beweise, dass es eine Folge solcher Ereignisse gibt, nach der jeder Nutzer höchstens mit einem anderen Nutzer befreundet ist.

    Ich versuchs mal. Da ich natürlich keine Lust habe, dass ganze in Worten auszudrücken werde ich mal bestimmte Dinge definieren.
    [A] … A hat keinen Freund
    [A][B] … A ist mit B befreundet.
    weiters gilt [A][B] = [B][A]
    [A,B] … A und B sind untereinander nicht befreundet
    [A,B,C] … A, B, C sind untereinander nicht befreundet.
    [A][B,C] … A ist mit B,C befreundet, B und C sind untereinander nicht befreundet
    [A,B][C,D] … A ist mit C und D befreundet und umgekehrt, B ist mit C und D befreundet und umgekehrt, A und B sind untereinander nicht befreundet und ebenso sind C und D untereinander nicht befreundet.

    Versuchen wir den Beweis herzuleiten.
    1) [A] -> [A]
    2) [A][B,C] -> [A] † [B][C] … A hat nach der (->) Operation keinen Freund mehr und B und C sind befreundet.
    3) [A][B] -> [A][B]
    4) [A,B] [C,D] -> [A] † [B][C,D] -> [A] † [B] † [C][D]

    Wie man erkennen kann hat nach einigen Schritten jeder Nutzer keinen oder maximal einen Freund.

  4. #4 Karl-Heinz
    10. August 2019

    Ein anschließender Beweis von einem Profi wäre natürlich cool.

  5. #5 tomtoo
    10. August 2019

    “…ignoriert….”

    Deutschland auf Platz 31 ist halt auch nicht so der Bringer.

  6. #6 Karl-Heinz
    Graz
    10. August 2019

    @tomtoo

    Ich vertraue darauf, dass Deutschland genügend Gaststudenten hat. 😉

  7. #7 Karl-Heinz
    10. August 2019

    Ich hoffe natürlich auch, dass Thilo zum Schluss, den exakten Beweis hier postet.

  8. #8 rolak
    10. August 2019

    hier postet

    postwendend?

  9. #9 Karl-Heinz
    10. August 2019

    @rolak

    postwendend = sofort, gleich

    Wenn möglich, ja. 😉

  10. #10 Thilo
    10. August 2019

    Ist geplant, aber erst für nächste Woche.

  11. #11 Braunschweiger (DE)
    10. August 2019

    Die Frage verstehe ich nicht 100-prozentig, und das scheint mir doch wichtig zu sein. Speziell hier:

    Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet.

    Die Beschreibung scheint in zwei Klassen zu 1010 und 1009 Elementen zu zerfallen. Mit “jeweils genau” scheint zu gelten: in der ersten Klasse hat JEDER einzelne Nutzer genau 1009 Freunde, und in der zweiten jeder Nutzer genau 1010 (richtig so?). Die Klassen sind disjunkt und die Summe der Nutzer ist 2019. Das scheint “sehr vielleicht” zu implizieren, dass Nutzer aus der einen Klasse genau mit Nutzern aus der anderen Klasse verbunden sind. Andererseits steht nirgendwo, dass das genau so sein muss.

    Die Aufgabe würde ich versuchen mit Graphentheorie anzugehen, einer in der Informatik sehr beliebten Methode. Für Netze aller Art scheint es sowieso die beste und die Standardbeschreibungsmethode zu ergeben. Nutzer sind Knoten A, B, C, … und Freundschaften sind ungerichtete Kanten (A,B) == (B,A). Kanten auf sich selbst (A,A) gibt es nicht.

    Die Frage geht also von einem stark verbundenen Netz aus, in dem jeder Knoten entweder 1009 oder 1010 Nachbarn hat. Die Frage ist zunächst, ob das Netz komplett verbunden ist, oder ob es disjunkte Teilgraphen geben kann (und ob das überhaupt von Bedeutung ist). Intuitiv scheint es so, dass der Graph zumindest vollständig zusammenhängend sein KANN, wenn jeder Knoten 1009 oder 1010 Nachbarn hat, von denen keiner er selbst ist.

    Der gesuchte Endzustand scheint nach Beschreibung so zu sein, dass mindestens ein Knoten (oder eine ungerade Anzahl) keine Kanten mehr hat, und dass eine gerade Anzahl und höchstens 1009 von Paaren (B,C) mit nur noch genau einer Kante existieren. Intuitiv scheint das gut möglich erreichbar zu sein, da eine Umverlagerung (A,B)(A,C) ==> (B,C) zu einer monoton abnehmenden Folge von Kanten (aus 2 mach 1) führen müsste, und zu disjunkt zerfallenden Teilnetzen {A,B,C} => {A} + {B,C}.

    So weit meine Überlegung. Mir ist noch nicht klar, welche Sonder- und/oder Grenzfälle ich betrachten muss, bis die Sache rund ist. Klar ist nur, dass im Endzustand die “Freundschaftsumverlagerungs-Operation” nicht mehr anwendbar ist.

  12. #12 Thilo
    10. August 2019

    Dass 1010 Leute genau die 1009 anderen kennen, ist natürlich eine Möglichkeit, aber nicht die einzige. Zum Warmmachen kann man aber erstmal diesen Fall betrachten: n Leute kennen genau die n+1 anderen. n=1 ist leicht, n=2 schon etwas schwerer.

  13. #13 Braunschweiger (DE)
    10. August 2019

    Ad myself, #11 — Eines ist mir noch ein- und aufgefallen:
    Es wären in den Freundschaften Zyklen bzw. Schleifen der Länge 3 denkbar, also quasi Dreiecke: (A,B),(B,C),(C,A). – Diese sind durch die Umformungsregel nicht direkt angreifbar, da die Voraussetzung von zB. nicht-(B,C) nicht zutrifft. Schön wäre es, wenn man feststellen könnte, dass derartige Zyklen von Anfang an nicht auftreten können, zB. indem, wie oben angedeutet, die Freunde immer in eine andere disjunkte Gruppe fallen. Das scheint nach der Antwort von Thilo nicht zwingend der Fall zu sein.

    Also müsste man zeigen, dass solche 3er-Zyklen immer auflösbar sind, indem ein Vorzustand mit einem weiteren Knoten D existiert, auf den die Regel anwendbar ist. Etwa mit der Notation \ “ohne” und explizit nicht existierenden Zuständen: (A,B)(A,D) \ (B,D) => (B,D) \ (A,B)(A,D) ; dies würde (A,B) also entfernen und den o.g. Zyklus zerstören. Solange also Dreiecke existieren, müsste für A immer ein weitere adjunkter (verbundener) Nachbar D existieren, und wenigstens ein gemeinsamer Nachbar B beiden adjunkt sein. Ist das erfüllt?

    In der Graphentheorie ist der Begriff des “Grades” von Bedeutung, die Anzahl der Kanten an einem Knoten. Mit diesem kann man hier vielleicht weiter argumentieren, insbesondere mit geradem oder ungeradem Grad. Durch die Umformungsregel wird für A der Grad um 2 vermindert (er bleibt entweder gerade oder ungerade), für B und C bleibt er jedoch aufgrund der neuen gemeinsamen Kante gleich.

  14. #14 Braunschweiger (DE)
    10. August 2019

    @Karl-Heinz:

    Wie man erkennen kann hat …

    Nein, tut mir leid, kann ich noch nicht erkennen.
    Du diskutierst gerade nicht die Existenz oder Nicht-Existenz bestimmter Zustände, insbesondere von Anfangs- und Endzuständen. Die Auflösung von Dreieckszyklen kommt in deinen Ausführungen nicht vor; diese Zyklen passen noch nicht einmal in deine Notation. Erweitern wir die doch einfach transitiv zu [A][B][C], soll heißen, es existieren die Freundschaften (A,B),(B,C),(C,A); jeder mit jedem. Ist dies, wie oben angesprochen auflösbar oder nicht?

    Deine Notation erklärt auch nicht die Form (term1) -> (term2), vermutlich ein “wird nach Umformung abgebildet auf”. Gilt dies aber nur für einen Umformschritt oder für mehrere; ist die Umformung transitiv oder nicht, und kann man das zielführend anwenden?

    Ich sehe einfach noch nicht, dass deine fortgesetzte Transformation sicher in den Endzustand führt und nicht etwa abgebrochen wird (das ist auch genau das Problem bei meinen eigenen Überlegungen).

  15. #15 Karl-Heinz
    Graz
    11. August 2019

    @Braunschweiger (DE)

    “Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet. “

    Diese Aussage impliziert (hat zur Folge), dass es keine Dreieckszyklen gibt.

    Beweis:
    1010 Nutzer … Gruppe 1 (G1)
    1009 Nutzer … Gruppe 2 (G2)
    Nutzer A, B, C
    Nutzer A ∈ G1 → B, C sind ∈ G2 →B und C können somit keine Freunde sein.

    Quod erat demonstrandum 😉

  16. #16 Braunschweiger (DE)
    11. August 2019

    @Karl-Heinz:
    Wieso? – Nirgendwo steht, dass Nutzer der einen Gruppe zwingend nur mit Nutzern der anderen Gruppe befreundet sein können. Thilo hatte in #12 ausgeschlossen, dass dies die einzige Möglichkeit sein muss; andere Möglichkeiten müssen also auch bedacht werden. Daher meine Frage in #11, und ich hatte das an einer Stelle dann auch schon diskutiert.

    Diese Angabe besagt lediglich, dass es anfangs 1009 Knoten mit geradem Grad gibt und 1010 Knoten mit ungeradem. Möglicherweise weist das auf eine Eigenschaft der Lösung hin, aber es schließt keine 3er-Zyklen aus, ASAIN. Also noch kein q.e.d.

  17. #17 Karl-Heinz
    11. August 2019

    @Braunschweiger (DE)

    Wieso? – Nirgendwo steht, dass Nutzer der einen Gruppe zwingend nur mit Nutzern der anderen Gruppe befreundet sein können.

    Na dann, beweise mir das Gegenteil.
    Ich überlege mir inzwischen den Beweis mit Hilfe von Abbildungen. 😉

  18. #18 Karl-Heinz
    Graz
    11. August 2019

    myself: Summary

    Ein soziales Netzwerk hat 2019 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet.
    Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet.

  19. #19 Karl-Heinz
    Graz
    11. August 2019

    @Braunschweiger (DE)

    Ich mache es spannender. Bevor ich jetzt meinen Beweis poste, bring mir doch nur ein einziges Gegenbeispiel. 😉

  20. #20 Karl-Heinz
    Graz
    11. August 2019

    @Braunschweiger (DE)

    3 Nutzer:
    Ein soziales Netzwerk hat 3 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet.
    Anfangs sind 2 Nutzer mit jeweils genau 1 Nutzern befreundet und 1 Nutzer mit jeweils genau 2 Nutzern befreundet.

    5 Nutzer:
    Ein soziales Netzwerk hat 5 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet.
    Anfangs sind 3 Nutzer mit jeweils genau 2 Nutzern befreundet und 2 Nutzer mit jeweils genau 3 Nutzern befreundet.

    2019 Nutzer:
    Ein soziales Netzwerk hat 2019 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet.
    Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet.

    Topologie des Netzwerkes
    Die Topologie des Nezwerkes ist eindeutig.
    2 Layer, wobei ein Layer einen Nutzer weniger hat als das andere Layer. Jeder Nutzer ist mit dem Nutzer aus dem anderen Layer verbunden.
    Lieber Herr Braunschweiger. In solch einem Netzwerk gibt es keine Schleifen!!!
    Und wenn du mir nicht glaubst, so liefere mir doch einfach nur ein Gegenbeispiel. Wünsche viel Spaß beim Suchen danach. 😉

  21. #21 Braunschweiger (DE)
    11. August 2019

    Lieber Herr @Karl-Heinz,
    es geht hier offenbar um die Definition der Aufgabe und um deine Interpretation. Wenn du deine Interpretation mehr begründen könntest (warum sollte sie richtig sein?) und warum sie Thilos Aussage widersprechen darf, wäre uns schon viel geholfen. War ganz gut, dass ich anfangs danach gefragt habe.

    In solch einem Netzwerk gibt es keine Schleifen!!!

    Das wäre, wie gesagt, zu beweisen. — Für welche Behauptung hättest du denn gerne ein Gegenbeispiel? – Ob sich Schleifen konstruieren lassen, hängt alleine von der Richtigkeit und Akzeptanz der Anfangsbedingungen ab.

    Ich habe etwas viel besseres: ich habe inzwischen die originale Lösung der IMO gefunden, sogar eine doppelte Lösung (warum hast du die noch nicht?), und die spricht sehr viel von Schleifen, sogar zentral. Ich lag in etwa auf dem richtigen Weg. Mehr sage ich dazu nicht, denn Thilo wollte ja demnächst die Lösung selbst bekannt geben.

    Viel Spaß beim Posten und anschließendem Diskutieren deiner Lösung!

  22. #22 Karl-Heinz
    11. August 2019

    @Braunschweiger (DE)

    Ich habe etwas viel besseres: ich habe inzwischen die originale Lösung der IMO gefunden, sogar eine doppelte Lösung (warum hast du die noch nicht?), und die spricht sehr viel von Schleifen, sogar zentral. Ich lag in etwa auf dem richtigen Weg. Mehr sage ich dazu nicht, denn Thilo wollte ja demnächst die Lösung selbst bekannt geben.

    Dann sei doch so nett und poste den Link.
    Was ich nicht ganz verstehe. Schleifen kann man ja mit obiger Operation doch gar nicht auflösen oder?

  23. #23 Thilo
    11. August 2019

    Nein, aber man kann einzelne Kanten der Schleifen auflösen, wenn die Schleife noch mit weiteren Knoten verbunden ist.

  24. #24 Karl-Heinz
    Graz
    11. August 2019

    @Thilo

    Daran hatte ich nicht gedacht.

    Wenn die Bedingung “Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet.“ keine Gültigkeit hat,

    dann änder ich die Vorgabe wie folgt ab:
    Anfangs sind 2019 Nutzer mit jeweils genau 2 Nutzern befreundet. Das ergibt nur einen Kreis und kann nicht aufgelöst werden. 😉

  25. #25 Braunschweiger (DE)
    11. August 2019

    Das Missverständnis mit Schleifen ist vermutlich, dass die auch eine größere Länge als 3 haben können, obwohl 3er auch immer möglich sind. Wenn 2n +1 Knoten im Graphen keine Schleifen bilden würden, dann kann der Graph maximal nur einen Pfad mit 2n Kanten haben. Der gegebene Graph hat jedoch n(n+1) = n² +n Kanten, also mehr. Dadurch sind Schleifen unvermeidlich, quasi Pflicht, und das Ganze passiert, indem die “Layer” hin und her verbunden sind.

    Hier als Beispiel für n = 2 ein Graph mit 2 * 3 = 6 Kanten, der nicht Teil der Lösung ist, nur eine Überlegung für Zyklen verschiedener Länge.
    3 Knoten {A,B,C} haben je 2 Kanten, und 2 Knoten {R,S} haben je 3 Kanten, und zwar auch innerhalb der Gruppe, da das nicht der Definition widerspricht. Alle Kanten x-y sind gedoppelt auch als y-x angegeben, daher 12.

    (A): A-R, A-C ;   (B): B-R, B-S ;   (C‌): C-S, C-A ;
    (R‌): R-A, R-B, R-S ;   (S): S-C, S-B, S-R ;

    der Graph hat 3 Schleifen der Längen 3, 4 und 5:
    3er: – B – R – S – B –
    4er: – A – R – S – C – A –
    5er: – A – R – B – S – C – A –

    Man sieht also leicht, wie Schleifen möglich sind, und bei größerem n geht es dann mit den Schleifen noch exzessiver. Für die Aufgabe war n = 1009.
     

    @Karl-Heinz:
    Suche doch nach “IMO 2019” und klicke auf “Problems”. Das Ganze ist in Englisch.
    Über die Auflösung von 3er-Schleifen habe ich in #13 spekuliert. Ich hatte nur falsch geschrieben, dass ein Nachbar D existieren muss, der 2 weiteren Knoten adjunkt sein soll. Eben nicht, er darf mit dem zu verbindenden Knoten eben noch nicht verbunden sein.

  26. #26 Karl-Heinz
    Graz
    11. August 2019

    Braunschweiger (DE)

    Danke, ich habe IMO 2019 Dokument gefunden. Kann leider erst am Abend die Lösung etwas genauer angucken. Was ich so im ersten Moment gesehen habe, setzen die für den Beweis voll auf die Graphentheorie. Layers werden für den Beweis eigentlich gar nicht benötigt. Mal gucken, ob ich bei der Lösung durchblicke. 😉

  27. #27 Karl-Heinz
    Graz
    13. August 2019

    @Thilo ,Braunschweiger (DE)

    Handelt es sich bei diesem Beispiel um einen vollständigen bipartiten Graphen?

  28. #28 Thilo
    13. August 2019

    In dem speziellen Fall, dass man 1009 mit genau den 1010 anderen verbundene Knoten hat, ja. Das ist aber nicht die einzige Möglichkeit. Man kann z.B. dieses Beispiel abändern, indem man vier Knoten nimmt, bei denen gerade die anderen beiden Paare verbunden sind.

  29. #29 Braunschweiger (DE)
    13. August 2019

    @Karl-Heinz:
    Mein Beispiel oben aus #25 ist kein bipartiter Graph, da ein solcher keine Zyklen ungerader Länge haben kann, also zB. keine Dreiecke und keine 5er.
    Die bipartite Eigenschaft ist nicht aus der Definition der Aufgabe gefordert.

  30. #30 Karl-Heinz
    13. August 2019

    @Thilo, Braunschweiger (DE)

    Danke für die schnellte Antwort

    @Braunschweiger (DE)
    Ich habe mir deinen Graphen G aus #25 mal aufgezeichnet und analysiert.
    a) G ist kein bipartiter Graph ✔
    b) Es gibt eine Folge solcher Ereignisse, nach der jeder Nutzer höchstens mit einem anderen Nutzer befreundet ist. ✔
    c) 5 Nutzer, wobei 3 Nutzer mit 2 Nutzer befreundet sind, und 2 Nutzer mit 3 Nutzer befreundet sind. ✔

    ⇒Gegenbeispiel aus #25 hat mich überzeugt.
    ⇒ Du bist der Beste 😉

    Anzeige

  31. #31 Karl-Heinz
    13. August 2019

    @Braunschweiger (DE)

    Wieso kennst Du dich so gut in Graphentheorie aus? Meines Wissens wird dieses Gebiet, wenn überhaupt, oft nur kurz in der Schule angeschnitten.

  32. #32 Braunschweiger (DE)
    13. August 2019

    @Karl-Heinz:
    Danke. Ich habe Informatik studiert und dafür etwas Mathematik als Grundlage. Graphentheorie gehört einfach als Werkzeug dazu, genauso wie auch etwas Zahlentheorie (Computerzahlen), Lineare Algebra (Vektoren, Matrizen, Tensoren), Geometrie, Analysis, Differentialgleichungen etc. Die gesamte Schulmathematik wird in 2 Semestern in je 2-4 Vorlesungen abgearbeitet, danach kommt das echt Neue, ein Parforce-Ritt (für reine Mathematiker doppelt so schnell).

    Graphentheorie lässt sich nicht nur für explizite Netzwerke aller Art anwenden, sondern im Sinne von “Bäumen” für fast alles, was hierarchisch oder in Folgeschritten strukturiert ist, ob Industrieprozesse oder die Programmierung selbst. Sehr schön auch zusammen mit Vektoralgebra und PDGLen dort, wo Stützstellen als 3-dimensionales Netz organisiert sind, etwa in CAD/CAM oder in Simulationen. – Es geht nicht darum der Beste zu sein; dieses Zeug ist einfach wichtig für den Job, vor allem wenn man ihn vernünftig und rational schnell erledigen will.

    Wenn du schon die Folge der “Ereignisse” für den Graph #25 ermittelt hast, wäre es nett, das hier zu posten. – Ich tippe mal auf 4 Schritte bei 6 Kanten, 2 bleiben übrig, und dass es am besten ist, zuerst immer die Dreiecke zu entfernen, die auch neu entstehen. Sonst kann ich das später auch noch anfügen.

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

    Das Beispiel mit meinem Graphen aus #25 möchte ich hier noch mit der Anwendung der Umfreundungs-Reduktion zuende führen. Thilo hat im Auflösungsartikel die Bedingungen für den Graphen und die Anwendung eines Umformungsschrittes erklärt.

    Hier nochmal der Graph mit n = 2 Knoten mit 3 Kanten/Freunden (ungerader Grad) und 3 Knoten mit je 2 Kanten (gerader Grad). Mit geänderten Bezeichnungen und anschließend einer Darstellung als Bild (pictures suck!).

    A-C, A-D, B-D, B-E, C-E, D-E   mit Δ {B,D,E}

        D --- E
       / \ / \
      A   B   C
       \_____/

    Die Reduktion ist 5-mal anwendbar. Das liegt daran, dass laut Lösung die n+1 Knoten geraden Grades isoliert übrig bleiben müssen und die n Knoten ungeraden Grades paarweise nur noch je eine Kante haben. Das sind hier n / 2 = 1 Kanten; demzufolge müssen von 6 ursprünglichen Kanten 5 reduziert werden, in der Summe eine je Schritt.

    ( A-C, A-D )   ==>   ( C-D )
    ( C-D, B-D )   ==>   ( B-C )   Dreieck auflösen!
    ( C-E, D-E )   ==>   ( C-D )   Dreieck auflösen!
    ( B-C, B-E )   ==>   ( C-E )
    ( C-E, C-D )   ==>   ( D-E )

    Es gibt schon hier in dem kleinen Graphen mehrere Wege, um zum selben Ergebnis zu kommen. Das liegt im Wesentlichen an der Reihenfolge der Kanten, die reduziert bzw. die neu gebildet werden.

    Es bleiben, wie nach Lösung zu erwarten, die drei isolierten Knoten {A, B, C} gerader Parität und die einzelne Kante D-E mit den beiden Knoten ungerader Parität übrig. Insofern habe ich mich mit meiner obigen Einschätzung von Restknoten und Restkanten geirrt. Das lag daran, dass ich das gerade n mit ungerader Parität auf die Kanten und nicht die Knoten angewendet hatte.