<aside> <img src="/icons/exclamation-mark_gray.svg" alt="/icons/exclamation-mark_gray.svg" width="40px" /> Wenn ihr in der Prüfung eine Aussage widerlegen müsst, außerhalb des MC-Teils, dann müsst ihr ein Gegenbeispiel kennen. Es lohnt sich also diese auswendig zu lernen.

</aside>

Allgemein

Liste von potentiellen Gegenbeispielen allgemeiner Art

• vollständiger Graph
• nicht zusammenhängender Graph

Hamiltonkreise

Gegenbeispiele speziell in Bezug auf Hamiltonkreise

• Petersen-Graph – hat keinen Hamiltonkreis, ist aber $3$-regulär

  

Matchings

Gegenbeispiele speziell in Bezug auf Matchings

• $k$-regulärer Graph ohne perfektes Matching

  

• Kreis ungerader Länger, hat offensichtlich kein perfektes Matching