Γαλαξιακή Γερουσία

Σε έναν πολύ μακρινό γαλαξία, υπάρχει μια Ενωμένη Γαλαξιακή Γερουσία με $100$ γερουσιαστές. Κάθε γερουσιαστής δεν έχει περισσότερα από τρεις εχθρούς. 

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

Αποδείξτε ότι μπορούν να το κάνουν αυτό.

(Σημείωση: Αν ο ${\rm A}$ είναι εχθρός του ${\rm B}$, τότε ο ${\rm B}$ είναι εχθρός του ${\rm A}$).

Σάρωση για να αποθηκεύσετε ή να κοινοποιήσετε την ανάρτηση