Ποιοι Γράφοι Δεν Ζωγραφίζονται Χωρίς Διασταυρώσεις; Το Θεώρημα του Kuratowski

Το θεώρημα του Kuratowski είναι ένα θεμελιώδες αποτέλεσμα στη θεωρία γράφων, που δίνει έναν χαρακτηρισμό των επιπέδων γράφων — δηλαδή, των γράφων που μπορούν να σχεδιαστούν στο επίπεδο χωρίς να τέμνονται οι ακμές τους.

Διατύπωση του θεωρήματος:

Ένας γράφος είναι επίπεδος αν και μόνο αν δεν περιέχει υπογράφο που να είναι ισομορφικός με υπογράφο του $K_5$​ ή του $K_{3,3}$ μετά από ακολουθία κατασκευών τύπου διαμέρισης ακμών (δηλαδή subdivisions).

Δηλαδή:

• $K_5$ είναι ο πλήρης γράφος με 5 κορυφές (κάθε κορυφή συνδέεται με όλες τις άλλες).
• $K_{3,3}$​ είναι ο πλήρης διμερής γράφος με 2 ομάδες των 3 κορυφών, όπου κάθε κορυφή της μιας ομάδας συνδέεται με όλες της άλλης.
• Ένας subdivision ενός γράφου είναι μια εκδοχή του γράφου στην οποία μπορεί να έχουμε "διασπάσει" ακμές, εισάγοντας νέες κορυφές σε αυτές (δηλαδή, αντικαθιστούμε μια ακμή με μονοπάτι μεγαλύτερου μήκους).

Επομένως:

Οποιοσδήποτε γράφος που περιέχει ως υπογράφο έναν "αναδιαμορφωμένο" $K_5​$ ή $K_{3,3​}$ δεν μπορεί να σχεδιαστεί επίπεδα (χωρίς διασταυρώσεις). Αντίστροφα, αν δεν περιέχει τέτοιον υπογράφο, τότε είναι επίπεδος.