Θεωρία Γραφημάτων 4

[Demetres]

Να εξεταστεί αν υπάρχει γράφημα με δέκα κορυφές οι οποίες να έχουν βαθμούς (δηλαδή αριθμό ακμών που περνούν από αυτές) 1,2,2,3,4,4,4,7,8,9 αντίστοιχα.

[Demetres]

Επαναφορά.

[Υπόδειξη: Εξετάσετε αν υπάρχει γράφημα με οκτώ κορυφές οι οποίες να έχουν βαθμούς 1,1,2,3,3,3,6,7 αντίστοιχα.]

[Demetres]

Δίνω την απάντηση.

Αν υπάρχει τέτοιο γράφημα, τότε η κορυφή με βαθμό 9 θα είναι γειτονική με όλες τις άλλες κορυφές. Αφαιρώντας την, θα έχουμε ένα γράφημα με 9 κορυφές και βαθμούς 0,1,1,2,3,3,3,6,7 αντίστοιχα. Αφαιρώντας την κορυφή που με βαθμό 0 παίρνουμε ένα γράφημα με 8 κορυφές και βαθμούς 1,1,2,3,3,3,6,7 αντίστοιχα. Συνεχίζουμε στο ίδιο μοτίβο. Η κορυφή βαθμού 7 είναι γειτονική με όλες τις άλλες. Αφαιρώντας την παίρνουμε ένα γράφημα με 7 κορυφές και βαθμούς 0,0,1,2,2,2,5 αντίστοιχα και άρα υπάρχει και ένα γράφημα με 5 κορυφές και βαθμούς 1,2,2,2,5 αντίστοιχα. Αυτό όμως είναι αδύνατον αφού σε κάθε γράφημα με 5 κορυφές μια κορυφή μπορεί να έχει βαθμό το πολύ 5.