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

[Demetres]

Η Μαρία λέει πως χθες βράδυ ήταν σε ένα πάρτυ και χόρεψε με άλλα τέσσερα άτομα. Ισχυρίζεται επίσης πως όλοι οι άλλοι χόρεψαν από ακριβώς τρεις φορές ο καθένας. Δεν θυμάται πόσα άτομα ήταν στο πάρτυ αλλά θυμάται σίγουρα πως κάθε αγόρι χόρεψε μόνο με κορίτσια και κάθε κορίτσι χόρεψε μόνο με αγόρια.

Ο Γιάννης λέει πως η Μαρία έκανε λάθος στο μέτρημα. Πως το ξέρει;

[Marios V.]

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

[Demetres]

Ωραία.

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

Αυτό που ουσιαστικά έχει δείξει ο Μάριος είναι ότι σε κάθε διμερές γράφημα με μέρη και , έχουμε όπου με εννοούμε ότι προσθέτουμε όλα τα για όλες τις κορυφές του κ.τ.λ.