Γράφοι: τα βασικά: θεωρία για μαθηματικούς διαγωνισμούς

Πολλά προβλήματα με ανθρώπους που γνωρίζονται, πόλεις με δρόμους ή αγώνες ανάμεσα σε ομάδες είναι στην ουσία προβλήματα γράφων.

τα βασικά

Λήμμα χειραψιών: το άθροισμα των βαθμών όλων των κορυφών ισούται με το διπλάσιο του πλήθους των ακμών. Άρα οι κορυφές περιττού βαθμού είναι άρτιες σε πλήθος.
Ο πλήρης γράφος με \(n\) κορυφές έχει \(\dfrac{n(n-1)}2\) ακμές.
Ένα δέντρο με \(n\) κορυφές έχει \(n-1\) ακμές.
Σε κάθε ομάδα 6 ατόμων υπάρχουν 3 που γνωρίζονται όλοι μεταξύ τους ή 3 που δεν γνωρίζονται κανένας. Με 5 άτομα αυτό δεν ισχύει πάντα.
Ένας γράφος χωρίζεται σε δύο ομάδες χωρίς ακμές μέσα σε καμία ομάδα αν και μόνο αν δεν έχει κύκλο περιττού μήκους.

Μπορούν 7 άτομα να δώσουν το καθένα τα χέρια με ακριβώς 3 άλλα;

Λύση. Το άθροισμα των βαθμών θα ήταν \(7\cdot3=21\), περιττό. Όμως πρέπει να είναι διπλάσιο του πλήθους των χειραψιών, άρα άρτιο. Αδύνατο.

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