🌳 2026 MATH MARATHON - GRAPH THEORY #4
👑 GRAND FINALE 👑
Graph Theory Mastery
Part 4 FINALE: IMO Problems & Competition Mastery
🔗 Η Πλήρης Διαδρομή:
Part 1 (❤️): Fundamentals, Trees, Handshaking
Part 2 (🔴): Eulerian & Hamiltonian Paths
Part 3 (🧡): Graph Coloring & Planarity
Part 4 (💜 TODAY): IMO Problems - Η Τελική Κατάκτηση!
Σήμερα κατακτούμε:
✅ 7 Classic Graph Theory Problems
✅ Complete Competition Strategy
✅ Master Reference Guide (όλες οι τεχνικές!)
✅ Problem-Solving Framework
✅ Advanced Techniques Integration
✅ ULTIMATE Grand Finale Challenge
✅ Series Celebration & Statistics
Part 1 (❤️): Fundamentals, Trees, Handshaking
Part 2 (🔴): Eulerian & Hamiltonian Paths
Part 3 (🧡): Graph Coloring & Planarity
Part 4 (💜 TODAY): IMO Problems - Η Τελική Κατάκτηση!
Σήμερα κατακτούμε:
✅ 7 Classic Graph Theory Problems
✅ Complete Competition Strategy
✅ Master Reference Guide (όλες οι τεχνικές!)
✅ Problem-Solving Framework
✅ Advanced Techniques Integration
✅ ULTIMATE Grand Finale Challenge
✅ Series Celebration & Statistics
💎 Φιλοσοφία του Part 4:
Φτάσαμε στην κορυφή! Εδώ συνδυάζουμε όλες τις τεχνικές από τα Parts 1-3 για να λύσουμε authentic graph theory problems. Αυτό είναι το Part που σας μετατρέπει από "καλούς" σε "legendary" στα graph problems! 🏔️👑
Φτάσαμε στην κορυφή! Εδώ συνδυάζουμε όλες τις τεχνικές από τα Parts 1-3 για να λύσουμε authentic graph theory problems. Αυτό είναι το Part που σας μετατρέπει από "καλούς" σε "legendary" στα graph problems! 🏔️👑
🎯 1. Competition Problem-Solving Framework
🏆 The Ultimate 8-Step Framework
ΒΗΜΑ 1: Graph Recognition
• Vertices = τι;
• Edges = τι;
• Directed ή undirected;
ΒΗΜΑ 2: Structure Identification
• Tree, cycle, complete, bipartite;
• Planar ή non-planar;
• Regular graph;
ΒΗΜΑ 3: Property Analysis
• Degrees (Handshaking!)
• Connectivity
• Chromatic number bounds
ΒΗΜΑ 4: Technique Selection
• Induction
• Pigeonhole
• Extremal principle
• Coloring
ΒΗΜΑ 5: Apply Theorems
• Euler's formula (planar)
• Brooks, Vizing
• Ramsey theory
ΒΗΜΑ 6: Construct/Prove
• Explicit construction
• Contradiction
• Inductive argument
ΒΗΜΑ 7: Verify
• Check all constraints
• Edge cases
ΒΗΜΑ 8: Write Clearly
• Clear graph definition
• Proof structure
• Final answer explicit
ΒΗΜΑ 1: Graph Recognition
• Vertices = τι;
• Edges = τι;
• Directed ή undirected;
ΒΗΜΑ 2: Structure Identification
• Tree, cycle, complete, bipartite;
• Planar ή non-planar;
• Regular graph;
ΒΗΜΑ 3: Property Analysis
• Degrees (Handshaking!)
• Connectivity
• Chromatic number bounds
ΒΗΜΑ 4: Technique Selection
• Induction
• Pigeonhole
• Extremal principle
• Coloring
ΒΗΜΑ 5: Apply Theorems
• Euler's formula (planar)
• Brooks, Vizing
• Ramsey theory
ΒΗΜΑ 6: Construct/Prove
• Explicit construction
• Contradiction
• Inductive argument
ΒΗΜΑ 7: Verify
• Check all constraints
• Edge cases
ΒΗΜΑ 8: Write Clearly
• Clear graph definition
• Proof structure
• Final answer explicit
🏆 2. Problem Collection
🏅 Πρόβλημα 1: The Friendship Theorem (Erdős–Rényi–Sós, 1966)
Πρόβλημα: Σε ένα party με \(n\) άτομα, κάθε ζεύγος ατόμων έχει ακριβώς έναν κοινό φίλο. Δείξτε ότι υπάρχει ένα άτομο που είναι φίλος με όλους!
Λύση:
Λύση:
Graph Formulation:
Graph \(G\): \(n\) vertices (άτομα), edge = friendship.
Constraint: Κάθε ζεύγος non-adjacent vertices έχει ακριβώς 1 κοινό γείτονα.
Goal: Show ∃ vertex με degree \(n-1\) (universal friend).
Graph \(G\): \(n\) vertices (άτομα), edge = friendship.
Constraint: Κάθε ζεύγος non-adjacent vertices έχει ακριβώς 1 κοινό γείτονα.
Goal: Show ∃ vertex με degree \(n-1\) (universal friend).
⚠️ Ειλικρινής σημείωση: Αυτό είναι το διάσημο Friendship Theorem (γνωστό και ως "Windmill Theorem"), αποδεδειγμένο το 1966 από τους Erdős, Rényi και Sós (όχι 1972 όπως ανέφερε η αρχική εκδοχή). Η πλήρης απόδειξη είναι γνωστά δύσκολη — χρησιμοποιεί γραμμική άλγεβρα (ιδιοτιμές πίνακα γειτνίασης), όχι στοιχειώδη combinatorial επιχειρήματα. Δεν θα προσποιηθούμε μια ψεύτικη "στοιχειώδη" απόδειξη εδώ (όπως έκανε η αρχική εκδοχή) — αντ' αυτού, να ξέρετε ότι το συμπέρασμα είναι: ο γράφος πρέπει να είναι ένας "ανεμόμυλος" (windmill graph) — τρίγωνα που μοιράζονται όλα μία κοινή κορυφή, η οποία είναι ακριβώς ο "universal friend". Αν θέλετε την πλήρη απόδειξη, αναζητήστε "Friendship Theorem proof eigenvalues".
🏅 Πρόβλημα 2: Tournament Hamiltonian Path (Rédei's Theorem, 1934)
Πρόβλημα: Σε tournament με \(n\) teams (κάθε ζεύγος παίζει ακριβώς 1 φορά, δεν υπάρχουν ισοπαλίες), δείξτε ότι υπάρχει Hamiltonian path.
Λύση:
Λύση:
Tournament Graph:
Directed complete graph - για κάθε ζεύγος \(u, v\) υπάρχει ακριβώς ένα directed edge: \((u,v)\) ή \((v,u)\).
Hamiltonian Path: Path που επισκέπτεται κάθε vertex ακριβώς μία φορά.
Directed complete graph - για κάθε ζεύγος \(u, v\) υπάρχει ακριβώς ένα directed edge: \((u,v)\) ή \((v,u)\).
Hamiltonian Path: Path που επισκέπτεται κάθε vertex ακριβώς μία φορά.
Απόδειξη (Induction):
Base: \(n=1,2\) trivial.
Inductive step: Υποθέτουμε ισχύει για \(n-1\).
Έστω tournament \(T\) με \(n\) vertices.
Παίρνουμε vertex \(v\) και θεωρούμε \(T' = T - v\) (με \(n-1\) vertices).
By IH: \(T'\) έχει Hamiltonian path \(v_1 \to v_2 \to \cdots \to v_{n-1}\).
Insert \(v\):
• Αν \((v, v_1) \in E\): Path = \(v \to v_1 \to \cdots \to v_{n-1}\) ✓
• Αν \((v_{n-1}, v) \in E\): Path = \(v_1 \to \cdots \to v_{n-1} \to v\) ✓
• Αλλιώς: το \(v_1\) νικά τον \(v\) και ο \(v\) νικά τον \(v_{n-1}\), άρα ∃ \(i\) με \((v_i, v) \in E\) και \((v, v_{i+1}) \in E\) (σημείο "μετάβασης" κατά μήκος του path)
→ Insert \(v\) μεταξύ \(v_i\) και \(v_{i+1}\): \(v_1 \to \cdots \to v_i \to v \to v_{i+1} \to \cdots \to v_{n-1}\) ✓
Base: \(n=1,2\) trivial.
Inductive step: Υποθέτουμε ισχύει για \(n-1\).
Έστω tournament \(T\) με \(n\) vertices.
Παίρνουμε vertex \(v\) και θεωρούμε \(T' = T - v\) (με \(n-1\) vertices).
By IH: \(T'\) έχει Hamiltonian path \(v_1 \to v_2 \to \cdots \to v_{n-1}\).
Insert \(v\):
• Αν \((v, v_1) \in E\): Path = \(v \to v_1 \to \cdots \to v_{n-1}\) ✓
• Αν \((v_{n-1}, v) \in E\): Path = \(v_1 \to \cdots \to v_{n-1} \to v\) ✓
• Αλλιώς: το \(v_1\) νικά τον \(v\) και ο \(v\) νικά τον \(v_{n-1}\), άρα ∃ \(i\) με \((v_i, v) \in E\) και \((v, v_{i+1}) \in E\) (σημείο "μετάβασης" κατά μήκος του path)
→ Insert \(v\) μεταξύ \(v_i\) και \(v_{i+1}\): \(v_1 \to \cdots \to v_i \to v \to v_{i+1} \to \cdots \to v_{n-1}\) ✓
⚠️ Σημείωση διόρθωσης: Αυτό είναι το κλασικό θεώρημα του Rédei (1934) — όχι "IMO 1992". Η απόδειξη (επαγωγή) είναι σωστή όπως δίνεται.
🏅 Πρόβλημα 3: Ramsey Numbers — R(3,3)=6
Πρόβλημα: Δείξτε ότι σε κάθε party με 6 άτομα, είτε υπάρχουν 3 άτομα που όλοι γνωρίζονται μεταξύ τους, είτε υπάρχουν 3 άτομα που κανείς δεν γνωρίζει κανέναν.
Λύση:
Λύση:
Graph Formulation:
Complete graph \(K_6\) με edges χρωματισμένα: red (φίλοι) ή blue (ξένοι).
Goal: Δείξε ότι υπάρχει monochromatic triangle (όλα red ή όλα blue).
Complete graph \(K_6\) με edges χρωματισμένα: red (φίλοι) ή blue (ξένοι).
Goal: Δείξε ότι υπάρχει monochromatic triangle (όλα red ή όλα blue).
Απόδειξη (Pigeonhole):
Παίρνουμε ένα vertex \(v\).
Το \(v\) συνδέεται με 5 άλλα vertices.
Pigeonhole: Τουλάχιστον 3 edges από \(v\) έχουν το ίδιο χρώμα (red ή blue).
WLOG, έστω 3 red edges: \(v\) συνδέεται με \(a, b, c\) (red).
Case 1: Αν ∃ red edge μεταξύ \(\{a,b,c\}\), πχ \((a,b)\) red:
→ Triangle \(\{v, a, b\}\) all red ✓
Case 2: Αν όλα τα edges μεταξύ \(\{a,b,c\}\) blue:
→ Triangle \(\{a, b, c\}\) all blue ✓
Συμπέρασμα: Ramsey number \(R(3,3) = 6\)! (Κλασικό αποτέλεσμα θεωρίας Ramsey — η απόδειξη είναι σωστή και πλήρης όπως δίνεται.)
Παίρνουμε ένα vertex \(v\).
Το \(v\) συνδέεται με 5 άλλα vertices.
Pigeonhole: Τουλάχιστον 3 edges από \(v\) έχουν το ίδιο χρώμα (red ή blue).
WLOG, έστω 3 red edges: \(v\) συνδέεται με \(a, b, c\) (red).
Case 1: Αν ∃ red edge μεταξύ \(\{a,b,c\}\), πχ \((a,b)\) red:
→ Triangle \(\{v, a, b\}\) all red ✓
Case 2: Αν όλα τα edges μεταξύ \(\{a,b,c\}\) blue:
→ Triangle \(\{a, b, c\}\) all blue ✓
Συμπέρασμα: Ramsey number \(R(3,3) = 6\)! (Κλασικό αποτέλεσμα θεωρίας Ramsey — η απόδειξη είναι σωστή και πλήρης όπως δίνεται.)
🏅 Πρόβλημα 4: Πυκνότητα ακμών και συνεκτικότητα
Πρόβλημα: Δείξτε ότι σε κάθε simple graph με \(n\) vertices και \(m\) edges, αν \(m > \binom{n-1}{2} = \frac{(n-1)(n-2)}{2}\), τότε ο γράφος είναι connected.
Λύση:
Λύση:
Απόδειξη (Contradiction):
Υποθέτουμε \(G\) είναι disconnected. Τότε τα vertices χωρίζονται σε τουλάχιστον 2 components, με μεγέθη \(k\) και \(n-k\) (\(1\leq k \leq n-1\); αν υπάρχουν περισσότερα components, ομαδοποιούμε τα υπόλοιπα).
Μέγιστος αριθμός ακμών με αυτόν τον διαχωρισμό:
\[ E_{\max}(k) = \binom{k}{2} + \binom{n-k}{2} \]
Υποθέτουμε \(G\) είναι disconnected. Τότε τα vertices χωρίζονται σε τουλάχιστον 2 components, με μεγέθη \(k\) και \(n-k\) (\(1\leq k \leq n-1\); αν υπάρχουν περισσότερα components, ομαδοποιούμε τα υπόλοιπα).
Μέγιστος αριθμός ακμών με αυτόν τον διαχωρισμό:
\[ E_{\max}(k) = \binom{k}{2} + \binom{n-k}{2} \]
Κρίσιμο βήμα: Η \(E_{\max}(k)\) είναι κυρτή, άρα μεγιστοποιείται στα ΑΚΡΑ, όχι στη μέση!
Αφού \(\binom{k}{2}=\frac{k(k-1)}{2}\) είναι κυρτή συνάρτηση του \(k\), το άθροισμα δύο κυρτών συναρτήσεων είναι επίσης κυρτό — άρα το μέγιστο σε ένα διάστημα εμφανίζεται στα άκρα (\(k=1\) ή \(k=n-1\)), όχι στο \(k=n/2\) (εκεί είναι το ελάχιστο!).
Στο \(k=1\): \(E_{\max}=\binom{1}{2}+\binom{n-1}{2}=0+\frac{(n-1)(n-2)}{2}\).
Άρα ο μέγιστος δυνατός αριθμός ακμών σε οποιοδήποτε disconnected γράφο με \(n\) κορυφές είναι:
\[ \binom{n-1}{2} = \frac{(n-1)(n-2)}{2} \]
(απομονώνοντας μία μόνο κορυφή από έναν πλήρη γράφο στις υπόλοιπες \(n-1\)).
Αφού \(\binom{k}{2}=\frac{k(k-1)}{2}\) είναι κυρτή συνάρτηση του \(k\), το άθροισμα δύο κυρτών συναρτήσεων είναι επίσης κυρτό — άρα το μέγιστο σε ένα διάστημα εμφανίζεται στα άκρα (\(k=1\) ή \(k=n-1\)), όχι στο \(k=n/2\) (εκεί είναι το ελάχιστο!).
Στο \(k=1\): \(E_{\max}=\binom{1}{2}+\binom{n-1}{2}=0+\frac{(n-1)(n-2)}{2}\).
Άρα ο μέγιστος δυνατός αριθμός ακμών σε οποιοδήποτε disconnected γράφο με \(n\) κορυφές είναι:
\[ \binom{n-1}{2} = \frac{(n-1)(n-2)}{2} \]
(απομονώνοντας μία μόνο κορυφή από έναν πλήρη γράφο στις υπόλοιπες \(n-1\)).
Συμπέρασμα:
Αν \(m > \binom{n-1}{2}\), τότε το \(m\) υπερβαίνει το μέγιστο δυνατό για ΟΠΟΙΟΝΔΗΠΟΤΕ disconnected γράφο — άρα ο \(G\) πρέπει να είναι connected! \(\blacksquare\)
Αν \(m > \binom{n-1}{2}\), τότε το \(m\) υπερβαίνει το μέγιστο δυνατό για ΟΠΟΙΟΝΔΗΠΟΤΕ disconnected γράφο — άρα ο \(G\) πρέπει να είναι connected! \(\blacksquare\)
⚠️ Σημείωση διόρθωσης: Η αρχική εκδοχή ισχυριζόταν λάθος συνθήκη ("\(2m > n(n-1)/2\)") με λάθος παραγώγιση (έλεγε ότι η \(E_{\max}(k)\) μεγιστοποιείται στο \(k=n/2\), ενώ στην πραγματικότητα ΕΚΕΙ ελαχιστοποιείται). Το αρχικό συμπέρασμα ήταν ψευδές: αντιπαράδειγμα — \(K_9\) συν 1 απομονωμένη κορυφή (\(n=10\)) έχει \(m=36\) ακμές· \(36 > n(n-1)/4=22.5\) αλλά ο γράφος δεν είναι συνεκτικός! Η σωστή, αυστηρή συνθήκη είναι \(m>\binom{n-1}{2}\), όπως αποδείχθηκε παραπάνω.
🏅 Πρόβλημα 5: Leaves & Degree-2 Vertices σε Δέντρα
Πρόβλημα: Δείξτε ότι κάθε tree με \(n\geq2\) vertices έχει τουλάχιστον \(\lceil n/2 \rceil\) κορυφές που είναι είτε leaves (βαθμού 1) είτε βαθμού 2.
Λύση:
Λύση:
Setup:
Tree \(T\) με \(n\) vertices, \(n-1\) edges. Έστω:
• \(n_1\) = # leaves (degree 1)
• \(n_2\) = # degree 2 vertices
• \(n_3\) = # vertices με degree \(\geq 3\)
\(n_1+n_2+n_3=n\).
Tree \(T\) με \(n\) vertices, \(n-1\) edges. Έστω:
• \(n_1\) = # leaves (degree 1)
• \(n_2\) = # degree 2 vertices
• \(n_3\) = # vertices με degree \(\geq 3\)
\(n_1+n_2+n_3=n\).
Βήμα 1: Φράγμα από Handshaking
\[ \sum \deg(v) = 2(n-1) \]
Αφού κάθε \(n_3\)-κορυφή έχει βαθμό \(\geq3\):
\[ n_1 + 2n_2 + 3n_3 \leq 2n-2 \]
\[ \sum \deg(v) = 2(n-1) \]
Αφού κάθε \(n_3\)-κορυφή έχει βαθμό \(\geq3\):
\[ n_1 + 2n_2 + 3n_3 \leq 2n-2 \]
Βήμα 2: Απαλοιφή του \(n_1\) χρησιμοποιώντας \(n_1+n_2+n_3=n\)
Από \(n_1=n-n_2-n_3\), αντικαθιστούμε:
\[ (n-n_2-n_3) + 2n_2 + 3n_3 \leq 2n-2 \]
\[ n + n_2 + 2n_3 \leq 2n - 2 \]
\[ n_2 + 2n_3 \leq n - 2 \]
\[ n_3 \leq \frac{n-2-n_2}{2} \leq \frac{n-2}{2} \]
Από \(n_1=n-n_2-n_3\), αντικαθιστούμε:
\[ (n-n_2-n_3) + 2n_2 + 3n_3 \leq 2n-2 \]
\[ n + n_2 + 2n_3 \leq 2n - 2 \]
\[ n_2 + 2n_3 \leq n - 2 \]
\[ n_3 \leq \frac{n-2-n_2}{2} \leq \frac{n-2}{2} \]
Βήμα 3: Συμπέρασμα
\[ n_1+n_2 = n - n_3 \geq n - \frac{n-2}{2} = \frac{n+2}{2} \]
Αφού \(\frac{n+2}{2} = \frac{n}{2}+1 > \frac{n}{2} \geq \lceil n/2 \rceil - \frac{1}{2}\), σε κάθε περίπτωση (n άρτιος ή περιττός) έχουμε \(n_1+n_2 \geq \lceil n/2 \rceil\), όπως ζητούνταν — μάλιστα με "περιθώριο ασφαλείας" τουλάχιστον 1! \(\blacksquare\)
\[ n_1+n_2 = n - n_3 \geq n - \frac{n-2}{2} = \frac{n+2}{2} \]
Αφού \(\frac{n+2}{2} = \frac{n}{2}+1 > \frac{n}{2} \geq \lceil n/2 \rceil - \frac{1}{2}\), σε κάθε περίπτωση (n άρτιος ή περιττός) έχουμε \(n_1+n_2 \geq \lceil n/2 \rceil\), όπως ζητούνταν — μάλιστα με "περιθώριο ασφαλείας" τουλάχιστον 1! \(\blacksquare\)
⚠️ Σημείωση διόρθωσης: Η αρχική εκδοχή εγκατέλειπε την απόδειξη στη μέση ("Hmm, this gives lower bound on... More sophisticated argument needed"). Την ολοκληρώσαμε πλήρως παραπάνω.
🏅 Πρόβλημα 6: Bipartite Matching (Hall's Marriage)
Πρόβλημα: \(n\) boys, \(n\) girls. Κάθε boy γνωρίζει κάποια girls. Πότε μπορούμε να κάνουμε \(n\) marriages (κάθε boy με girl που γνωρίζει);
Λύση:
Λύση:
Hall's Marriage Theorem:
Perfect matching υπάρχει αν και μόνο αν για κάθε subset \(S\) boys:
\[ |N(S)| \geq |S| \]
όπου \(N(S)\) = σύνολο girls που γνωρίζει τουλάχιστον ένας από \(S\).
Hall's Condition: "Marriage condition"
Perfect matching υπάρχει αν και μόνο αν για κάθε subset \(S\) boys:
\[ |N(S)| \geq |S| \]
όπου \(N(S)\) = σύνολο girls που γνωρίζει τουλάχιστον ένας από \(S\).
Hall's Condition: "Marriage condition"
Παράδειγμα:
3 boys: \(B_1, B_2, B_3\)
3 girls: \(G_1, G_2, G_3\)
Connections:
• \(B_1\) knows \(G_1, G_2\)
• \(B_2\) knows \(G_2\)
• \(B_3\) knows \(G_3\)
Ρητή αντιστοίχιση (αποδεικνύει από μόνη της την ύπαρξη matching, χωρίς να χρειάζεται έλεγχος όλων των υποσυνόλων):
\((B_1,G_1),\ (B_2,G_2),\ (B_3,G_3)\) — κάθε ζεύγος έγκυρο, καλύπτει όλους!
3 boys: \(B_1, B_2, B_3\)
3 girls: \(G_1, G_2, G_3\)
Connections:
• \(B_1\) knows \(G_1, G_2\)
• \(B_2\) knows \(G_2\)
• \(B_3\) knows \(G_3\)
Ρητή αντιστοίχιση (αποδεικνύει από μόνη της την ύπαρξη matching, χωρίς να χρειάζεται έλεγχος όλων των υποσυνόλων):
\((B_1,G_1),\ (B_2,G_2),\ (B_3,G_3)\) — κάθε ζεύγος έγκυρο, καλύπτει όλους!
🏅 Πρόβλημα 7: Mantel's Theorem — Extremal Graph Theory
Πρόβλημα: Ποιος είναι ο μέγιστος αριθμός ακμών σε simple graph με \(n\) vertices που ΔΕΝ περιέχει \(K_3\) (triangle);
Λύση:
Λύση:
Mantel's Theorem (1907):
Triangle-free graph με \(n\) vertices έχει το πολύ \(\lfloor n^2/4 \rfloor\) edges.
Extremal graph: Complete bipartite \(K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}\).
Triangle-free graph με \(n\) vertices έχει το πολύ \(\lfloor n^2/4 \rfloor\) edges.
Extremal graph: Complete bipartite \(K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}\).
Απόδειξη:
Έστω \(G\) triangle-free με \(n\) vertices, \(m\) edges.
Βήμα 1 (εδώ χρησιμοποιούμε το "χωρίς τρίγωνα"): Για κάθε ακμή \(\{u,v\}\): \(N(u)\cap N(v)=\emptyset\) (αλλιώς ένα κοινό γειτονικό σημείο θα σχημάτιζε τρίγωνο!). Άρα:
\[ \deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u)\cup N(v)| \leq n \]
Βήμα 2: Αθροίζοντας πάνω από όλες τις \(m\) ακμές:
\[ \sum_{\{u,v\}\in E} \big(\deg(u)+\deg(v)\big) \leq mn \]
Το αριστερό μέλος ισούται με \(\sum_v \deg(v)^2\) (κάθε κορυφή \(v\) συνεισφέρει \(\deg(v)\) φορές τον όρο \(\deg(v)\), μία για κάθε πρόσπτουσα ακμή). Άρα:
\[ \sum_v \deg(v)^2 \leq mn \]
Βήμα 3 (Cauchy-Schwarz):
\[ \left(\sum_v \deg(v)\right)^2 \leq n\sum_v \deg(v)^2 \leq n \cdot mn = mn^2 \]
Αφού \(\sum \deg(v)=2m\):
\[ 4m^2 \leq mn^2 \;\Rightarrow\; 4m \leq n^2 \;\Rightarrow\; m \leq \frac{n^2}{4} \]
(με πιο προσεκτική ακέραια ανάλυση, \(m\leq\lfloor n^2/4\rfloor\)). \(\blacksquare\)
Έστω \(G\) triangle-free με \(n\) vertices, \(m\) edges.
Βήμα 1 (εδώ χρησιμοποιούμε το "χωρίς τρίγωνα"): Για κάθε ακμή \(\{u,v\}\): \(N(u)\cap N(v)=\emptyset\) (αλλιώς ένα κοινό γειτονικό σημείο θα σχημάτιζε τρίγωνο!). Άρα:
\[ \deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u)\cup N(v)| \leq n \]
Βήμα 2: Αθροίζοντας πάνω από όλες τις \(m\) ακμές:
\[ \sum_{\{u,v\}\in E} \big(\deg(u)+\deg(v)\big) \leq mn \]
Το αριστερό μέλος ισούται με \(\sum_v \deg(v)^2\) (κάθε κορυφή \(v\) συνεισφέρει \(\deg(v)\) φορές τον όρο \(\deg(v)\), μία για κάθε πρόσπτουσα ακμή). Άρα:
\[ \sum_v \deg(v)^2 \leq mn \]
Βήμα 3 (Cauchy-Schwarz):
\[ \left(\sum_v \deg(v)\right)^2 \leq n\sum_v \deg(v)^2 \leq n \cdot mn = mn^2 \]
Αφού \(\sum \deg(v)=2m\):
\[ 4m^2 \leq mn^2 \;\Rightarrow\; 4m \leq n^2 \;\Rightarrow\; m \leq \frac{n^2}{4} \]
(με πιο προσεκτική ακέραια ανάλυση, \(m\leq\lfloor n^2/4\rfloor\)). \(\blacksquare\)
⚠️ Σημείωση διόρθωσης: Η αρχική απόδειξη έγραφε "\(\Sigma\deg(v)^2\leq n\cdot\Sigma\deg(v)\)" χωρίς να χρησιμοποιεί πραγματικά την ιδιότητα "χωρίς τρίγωνα" — αυτή η ανισότητα ισχύει τετριμμένα για οποιονδήποτε γράφο (αφού \(\deg(v)<n\) πάντα), άρα δεν αποδείκνυε το ζητούμενο (θα έδινε μόνο το ασθενές \(m\leq n^2/2\)). Η σωστή απόδειξη (παραπάνω) χρησιμοποιεί ουσιαστικά το \(N(u)\cap N(v)=\emptyset\) σε κάθε ακμή.
📚 3. Master Reference Guide
🎯 Complete Technique Reference
| Technique | When to Use | Key Formula/Idea | Part |
|---|---|---|---|
| Handshaking Lemma | Degree sums | Σ deg = 2E | 1 |
| Tree Properties | Acyclic connected | E = V - 1 | 1 |
| Euler's Formula | Planar graphs | V - E + F = 2 | 3 |
| Brooks' Theorem | Vertex coloring | χ ≤ Δ | 3 |
| Four Color | Planar coloring | χ ≤ 4 | 3 |
| Kuratowski | Planarity test | No K₅, K₃,₃ | 3 |
| Pigeonhole | Ramsey-type | Distribution | All |
| Induction | Structural proofs | Remove vertex/edge | All |
| Hall's Marriage | Matching | |N(S)| ≥ |S| | 4 |
| Mantel's Theorem | Triangle-free extremal | m ≤ ⌊n²/4⌋ | 4 |
🎯 4. Advanced Competition Tips
💡 Pro Tips για Graph Problems
1. Model First
• Ξεκαθάρισε: τι είναι vertices, τι edges
• Draw small examples!
2. Use Extremal Principle
• Max/min degree vertex
• Longest path
• Largest component
3. Induction Strategy
• Remove leaf (trees)
• Remove low-degree vertex
• Remove edge (cycles)
4. Counting Arguments
• Count edges two ways
• Handshaking always
• Pigeonhole when stuck
• Πάντα ελέγξτε αν χρησιμοποιήσατε ΟΛΕΣ τις υποθέσεις του προβλήματος (π.χ. "χωρίς τρίγωνα") — αν μια ανισότητα ισχύει τετριμμένα χωρίς κάποια υπόθεση, μάλλον δεν αποδεικνύει αυτό που θέλετε!
5. Structure Recognition
• Is it bipartite? (2-colorable)
• Is it planar? (Euler's formula)
• Regular? (all same degree)
1. Model First
• Ξεκαθάρισε: τι είναι vertices, τι edges
• Draw small examples!
2. Use Extremal Principle
• Max/min degree vertex
• Longest path
• Largest component
3. Induction Strategy
• Remove leaf (trees)
• Remove low-degree vertex
• Remove edge (cycles)
4. Counting Arguments
• Count edges two ways
• Handshaking always
• Pigeonhole when stuck
• Πάντα ελέγξτε αν χρησιμοποιήσατε ΟΛΕΣ τις υποθέσεις του προβλήματος (π.χ. "χωρίς τρίγωνα") — αν μια ανισότητα ισχύει τετριμμένα χωρίς κάποια υπόθεση, μάλλον δεν αποδεικνύει αυτό που θέλετε!
5. Structure Recognition
• Is it bipartite? (2-colorable)
• Is it planar? (Euler's formula)
• Regular? (all same degree)
👑 ULTIMATE GRAND FINALE CHALLENGE
💎 THE ULTIMATE CHALLENGE 💎
Το τελικό boss battle του Graph Theory! 🏔️
🎯 THE GRAND FINALE PROBLEM
Πρόβλημα:
Σε ένα δίκτυο \(n\) υπολογιστών (\(n \geq 4\)), κάθε υπολογιστής συνδέεται με ακριβώς 3 άλλους. Δείξτε ότι μπορούμε να χρωματίσουμε τους υπολογιστές με (το πολύ) 3 χρώματα έτσι ώστε κάθε υπολογιστής να έχει τουλάχιστον έναν γείτονα του ίδιου χρώματος.
Πρόβλημα:
Σε ένα δίκτυο \(n\) υπολογιστών (\(n \geq 4\)), κάθε υπολογιστής συνδέεται με ακριβώς 3 άλλους. Δείξτε ότι μπορούμε να χρωματίσουμε τους υπολογιστές με (το πολύ) 3 χρώματα έτσι ώστε κάθε υπολογιστής να έχει τουλάχιστον έναν γείτονα του ίδιου χρώματος.
🥉 Hint 1: Τι γίνεται αν χρωματίσεις ΟΛΟΥΣ τους υπολογιστές με το ίδιο χρώμα;
📮 Πλήρης Λύση:
Χρωματίζουμε όλους τους υπολογιστές με το ίδιο χρώμα (π.χ. χρώμα 1).
Αφού κάθε υπολογιστής έχει βαθμό 3 (συνδέεται με 3 άλλους), και ΟΛΟΙ οι υπολογιστές (άρα και οι 3 γείτονές του) έχουν το ίδιο χρώμα, κάθε υπολογιστής έχει και τους 3 γείτονές του στο ίδιο χρώμα — άρα σίγουρα τουλάχιστον έναν! \(\blacksquare\)
💡 Γιατί είναι τόσο απλό; Το πρόβλημα ζητά "χρωματισμό με το πολύ 3 χρώματα" (δηλαδή έχουμε τη δυνατότητα να χρησιμοποιήσουμε έως 3, όχι υποχρέωση να τα χρησιμοποιήσουμε όλα), και ζητά "τουλάχιστον 1 ομόχρωμο γείτονα" — το ΑΝΤΙΘΕΤΟ constraint από τον proper coloring (όπου θέλουμε ΚΑΝΕΝΑΝ ομόχρωμο γείτονα). Ο "χειρότερος δυνατός" proper coloring (δηλαδή κανένας διαχωρισμός καθόλου) λύνει τετριμμένα αυτή την αντίστροφη συνθήκη.
Χρωματίζουμε όλους τους υπολογιστές με το ίδιο χρώμα (π.χ. χρώμα 1).
Αφού κάθε υπολογιστής έχει βαθμό 3 (συνδέεται με 3 άλλους), και ΟΛΟΙ οι υπολογιστές (άρα και οι 3 γείτονές του) έχουν το ίδιο χρώμα, κάθε υπολογιστής έχει και τους 3 γείτονές του στο ίδιο χρώμα — άρα σίγουρα τουλάχιστον έναν! \(\blacksquare\)
💡 Γιατί είναι τόσο απλό; Το πρόβλημα ζητά "χρωματισμό με το πολύ 3 χρώματα" (δηλαδή έχουμε τη δυνατότητα να χρησιμοποιήσουμε έως 3, όχι υποχρέωση να τα χρησιμοποιήσουμε όλα), και ζητά "τουλάχιστον 1 ομόχρωμο γείτονα" — το ΑΝΤΙΘΕΤΟ constraint από τον proper coloring (όπου θέλουμε ΚΑΝΕΝΑΝ ομόχρωμο γείτονα). Ο "χειρότερος δυνατός" proper coloring (δηλαδή κανένας διαχωρισμός καθόλου) λύνει τετριμμένα αυτή την αντίστροφη συνθήκη.
🎓 Πιο ενδιαφέρουσα εκδοχή (χωρίς πλήρη απόδειξη εδώ): Αν απαιτούσαμε να χρησιμοποιηθούν και τα 3 χρώματα (κάθε χρωματική κλάση μη-κενή), το πρόβλημα γίνεται γνήσια μη-τετριμμένο και χρειάζεται πιο προσεκτική (π.χ. τοπικής βελτίωσης) κατασκευή.
🎊 SERIES CELEBRATION
🎊🎊🎊 GRAPH THEORY MARATHON COMPLETE! 🎊🎊🎊
Φτάσατε στην Κορυφή! 🏔️👑
🏆 Τι Κατακτήσατε:
Part 1 (❤️): Fundamentals, Trees, Handshaking
Part 2 (🔴): Eulerian & Hamiltonian Paths
Part 3 (🧡): Graph Coloring & Planarity
Part 4 (💜): Competition Mastery
📊 Στατιστικά:
✅ 4 Ολοκληρωμένα Parts
✅ 28+ αναλυτικά παραδείγματα
✅ 7 κλασικά προβλήματα
✅ Πλήρες competition framework
Είστε τώρα MASTERS στη Graph Theory! 🎓👑
Part 1 (❤️): Fundamentals, Trees, Handshaking
Part 2 (🔴): Eulerian & Hamiltonian Paths
Part 3 (🧡): Graph Coloring & Planarity
Part 4 (💜): Competition Mastery
📊 Στατιστικά:
✅ 4 Ολοκληρωμένα Parts
✅ 28+ αναλυτικά παραδείγματα
✅ 7 κλασικά προβλήματα
✅ Πλήρες competition framework
Είστε τώρα MASTERS στη Graph Theory! 🎓👑
🔗 Αν σου διέφυγε: Part 3 - Graph Coloring & Planarity
🌟 Ολοκληρώσατε το Graph Theory Marathon! 🌟
Ready to conquer ANY olympiad! 🚀👑📚
Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ
PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify
📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα
Δες τα βιβλία →
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου