🔴 2026 Math Marathon: Graph Theory #2 - Eulerian & Hamiltonian Paths | Königsberg Problem

🌳 2026 MATH MARATHON - GRAPH THEORY #2

Graph Theory Mastery

Part 2: Eulerian & Hamiltonian Paths - Η Τέχνη της Διάσχισης

🔗 Σύνδεση με Part 1:
Part 1: Graphs, trees, paths, Handshaking Lemma ❤️
Part 2 (σήμερα): Eulerian & Hamiltonian - Special Traversals! 🔴

Τι θα μάθετε σήμερα:
✅ Eulerian Paths & Circuits (Königsberg!)
✅ Euler's Theorem - complete characterization
✅ Hamiltonian Paths & Cycles
✅ Ore's & Dirac's Theorems
✅ Matching Theory basics
✅ Bipartite Matching
✅ 7 advanced examples
✅ Competition techniques

🤔 Η Μεγάλη Ερώτηση:
Πότε μπορούμε να διασχίσουμε **όλες** τις ακμές ενός γράφου ακριβώς μία φορά; Πότε μπορούμε να επισκεφτούμε **όλες** τις κορυφές ακριβώς μία φορά; Αυτές είναι οι Eulerian και Hamiltonian ερωτήσεις - και είναι **πολύ διαφορετικές**! 🎯

🎯 1. Eulerian Paths & Circuits

📌 Ορισμοί: Eulerian

Eulerian Path:
Ένα path που διασχίζει **κάθε ακμή** του γράφου **ακριβώς μία φορά**.
• Μπορεί να επαναλάβει κορυφές
• Αρχή ≠ τέλος (γενικά)

Eulerian Circuit (or Eulerian Cycle):
Ένα Eulerian path που **αρχίζει και τελειώνει** στην ίδια κορυφή.
• Κλειστό path
• Κάθε ακμή ακριβώς μία φορά

Eulerian Graph:
Ένας γράφος που έχει Eulerian circuit.

🌉 The Königsberg Bridge Problem

History (1736): Euler έλυσε το famous πρόβλημα των γεφυρών του Königsberg!

Πρόβλημα: Η πόλη Königsberg είχε 7 γέφυρες. Μπορείς να διασχίσεις όλες τις γέφυρες ακριβώς μία φορά;

Euler's Insight: Μοντελοποίησε ως γράφο!
• Vertices = land masses (4)
• Edges = bridges (7)

Degrees: 3, 3, 3, 5 (όλοι περιττοί!)

Απάντηση: ❌ Αδύνατο! (Euler's theorem)

👑 Euler's Theorem (1736)

Ένας **connected** γράφος έχει:

1. Eulerian Circuit αν και μόνο αν:

Κάθε κορυφή έχει **άρτιο** βαθμό

2. Eulerian Path (όχι circuit) αν και μόνο αν:

Ακριβώς **2 κορυφές** έχουν περιττό βαθμό

(Αυτές είναι η αρχή και το τέλος του path)

3. Αν > 2 κορυφές έχουν περιττό βαθμό:
Δεν υπάρχει Eulerian path!

📐 Απόδειξη (Sketch)

⇒ (Eulerian Circuit → All even degrees):

Αν υπάρχει Eulerian circuit, κάθε φορά που το path μπαίνει σε μια κορυφή, πρέπει και να βγαίνει.

Άρα κάθε κορυφή χρησιμοποιεί edges σε ζεύγη → άρτιος βαθμός!

⇐ (All even degrees → Eulerian Circuit exists):

Constructive Algorithm (Hierholzer's):

1. Ξεκινάμε από οποιαδήποτε κορυφή \(v\)
2. Ακολουθούμε edges που δεν έχουμε χρησιμοποιήσει
3. Αφού όλοι έχουν άρτιο degree, θα επιστρέψουμε στο \(v\) (cycle!)
4. Αν δεν έχουμε χρησιμοποιήσει όλες τις edges, επεκτείνουμε το cycle
5. Επαναλαμβάνουμε μέχρι να χρησιμοποιήσουμε όλες!

🚀 2. Hamiltonian Paths & Cycles

📌 Ορισμοί: Hamiltonian

Hamiltonian Path:
Ένα path που επισκέπτεται **κάθε κορυφή** του γράφου **ακριβώς μία φορά**.
• Δεν χρειάζεται να χρησιμοποιεί όλες τις ακμές!
• Αρχή ≠ τέλος (γενικά)

Hamiltonian Cycle (or Circuit):
Ένα cycle που επισκέπτεται **κάθε κορυφή** ακριβώς μία φορά και επιστρέφει στην αρχή.

Hamiltonian Graph:
Ένας γράφος που έχει Hamiltonian cycle.

⚡ Eulerian vs Hamiltonian

Property	Eulerian	Hamiltonian
Traverses	All edges once	All vertices once
May repeat	Vertices	Edges
Characterization	Easy! (degree condition)	Hard! (NP-complete)
Decision	Polynomial time	NP-complete
Necessary condition	≤2 odd degrees	No simple condition!

⚠️ ΚΡΙΣΙΜΟ:
Δεν υπάρχει **simple characterization** για Hamiltonian graphs όπως υπάρχει για Eulerian!

Το Hamiltonian Cycle Problem είναι **NP-complete** - ένα από τα πιο δύσκολα προβλήματα στην επιστήμη των υπολογιστών!

📐 Sufficient Conditions για Hamiltonian Cycles

Παρόλο που δεν έχουμε necessary and sufficient, έχουμε **sufficient conditions**:

Dirac's Theorem (1952):
Αν \(G\) έχει \(n \geq 3\) κορυφές και:

\(\deg(v) \geq \frac{n}{2}\) για κάθε κορυφή \(v\)

τότε \(G\) έχει Hamiltonian cycle.

Ore's Theorem (1960):
Αν \(G\) έχει \(n \geq 3\) κορυφές και:

\(\deg(u) + \deg(v) \geq n\) για κάθε μη-adjacent ζεύγος \(u, v\)

τότε \(G\) έχει Hamiltonian cycle.

Σημείωση: Ore's theorem generalizes Dirac's!

📚 3. Παραδείγματα

🔹 Παράδειγμα 1: Checking Eulerian Πρόβλημα: Ένας γράφος με degree sequence (2, 2, 3, 3, 4). Έχει Eulerian path ή circuit;

Λύση:

Step 1: Count odd-degree vertices

Degrees: 2 (even), 2 (even), 3 (odd), 3 (odd), 4 (even)

Odd-degree vertices: **2**

Euler's Theorem:
• 0 odd → Eulerian circuit ✓
• 2 odd → Eulerian path ✓ ← This case!
• >2 odd → No Eulerian path ✗

Απάντηση:
✅ Έχει **Eulerian path** (από μία odd-degree κορυφή στην άλλη)
❌ Δεν έχει Eulerian circuit (αφού έχει odd-degree vertices)

🔹 Παράδειγμα 2: Complete Graph \(K_n\) Πρόβλημα: Για ποια \(n\) το \(K_n\) έχει Eulerian circuit;

Λύση:

Degree Analysis:

Στο \(K_n\), κάθε κορυφή συνδέεται με όλες τις άλλες \(n-1\) κορυφές.

Άρα: \(\deg(v) = n - 1\) για κάθε \(v\).

Euler's Condition:
Χρειαζόμαστε όλους τους βαθμούς άρτιους.

\(n - 1\) άρτιος ⟺ \(n\) περιττός

Απάντηση:
✅ \(K_n\) έχει Eulerian circuit αν και μόνο αν \(n\) είναι **περιττός**!

Παραδείγματα:
• \(K_3\): Eulerian ✓ (triangle)
• \(K_4\): Not Eulerian ✗
• \(K_5\): Eulerian ✓
• \(K_6\): Not Eulerian ✗

🔹 Παράδειγμα 3: Dirac's Theorem Application Πρόβλημα: Ένας γράφος με 10 κορυφές όπου κάθε κορυφή έχει degree ≥ 5. Έχει Hamiltonian cycle;

Λύση:

Check Dirac's Condition:

\(n = 10\), χρειαζόμαστε \(\deg(v) \geq \frac{n}{2} = 5\) για κάθε \(v\).

Δεδομένο: κάθε κορυφή έχει degree ≥ 5 ✓

Dirac's Theorem → Hamiltonian cycle exists!

Απάντηση: ✅ Ναι, έχει Hamiltonian cycle!

🔹 Παράδειγμα 4: Cube Graph Πρόβλημα: Το graph του κύβου (8 vertices, 12 edges). Eulerian ή/και Hamiltonian;

Λύση:

Cube Graph Structure:

8 vertices (κορυφές του κύβου)
12 edges (ακμές του κύβου)
Κάθε vertex: degree = 3 (3 ακμές συναντιούνται σε κάθε κορυφή)

Eulerian Check:
Όλες οι 8 κορυφές έχουν odd degree (3).
8 > 2 odd vertices → ❌ Not Eulerian!

Hamiltonian Check:
Μπορούμε να κατασκευάσουμε Hamiltonian cycle:
(1,2,3,4,5,6,7,8,1) following cube edges → ✓ Hamiltonian!

Απάντηση:
❌ Not Eulerian
✅ Hamiltonian!

🎮 4. Matching Theory

📌 Matching

Ένα matching σε έναν γράφο είναι ένα σύνολο ακμών όπου **καμία** δύο ακμές δεν μοιράζονται κορυφή.

Perfect Matching:
Ένα matching που καλύπτει **όλες** τις κορυφές.
• Κάθε κορυφή incident σε ακριβώς 1 edge του matching

Maximum Matching:
Matching με τον μέγιστο αριθμό ακμών.

Maximal Matching:
Matching που δεν μπορεί να επεκταθεί (αλλά όχι απαραίτητα maximum).

🔹 Παράδειγμα 5: Bipartite Matching Πρόβλημα: \(K_{3,3}\) (complete bipartite with 3+3 vertices). Έχει perfect matching;

Λύση:

Structure:

Two sets: \(A = \{a_1, a_2, a_3\}\), \(B = \{b_1, b_2, b_3\}\)
Every vertex in \(A\) connected to every vertex in \(B\).

Perfect Matching:
Match: \(\{a_1b_1, a_2b_2, a_3b_3\}\)
• Covers all 6 vertices ✓
• No shared vertices ✓

Απάντηση: ✅ Ναι, έχει perfect matching!

Σημείωση: \(K_{n,n}\) πάντα έχει perfect matching!

📐 Hall's Marriage Theorem

Για ένα bipartite graph \(G = (A \cup B, E)\), υπάρχει matching που καλύπτει όλες τις κορυφές του \(A\) αν και μόνο αν:

Για κάθε \(S \subseteq A\): \(|N(S)| \geq |S|\)

όπου \(N(S)\) = neighbors του \(S\) στο \(B\).

Με λόγια: Κάθε σύνολο κοριτσιών έχει τουλάχιστον τόσους γείτονες (αγόρια) όσο το μέγεθός του!

🔹 Παράδειγμα 6: Hall's Theorem Application Πρόβλημα: 5 students, 5 projects. Each student interested in some projects. Can we assign each student a different project?

Student interests:
• S1: {P1, P2}
• S2: {P2, P3}
• S3: {P1, P3, P4}
• S4: {P4, P5}
• S5: {P1, P5}

Λύση:

Check Hall's Condition:

Need: For every subset \(S\) of students, \(|N(S)| \geq |S|\).

Check all subsets (or key ones):
• \(\{S1\}\): \(N = \{P1,P2\}\), \(|N| = 2 \geq 1\) ✓
• \(\{S1, S2\}\): \(N = \{P1,P2,P3\}\), \(|N| = 3 \geq 2\) ✓
• ...

If all checks pass → Perfect matching exists!

Possible assignment:
S1→P1, S2→P2, S3→P3, S4→P4, S5→P5 ✓

🔹 Παράδειγμα 7: Petersen Graph The Famous Petersen Graph:
• 10 vertices, 15 edges
• 3-regular (every vertex degree 3)
• Non-planar
• No Hamiltonian cycle! (famous counterexample)

Properties:

Eulerian:
All vertices degree 3 (odd) → 10 odd vertices → ❌ Not Eulerian

Hamiltonian:
Despite high connectivity, NO Hamiltonian cycle exists!
(Proof requires detailed case analysis)

Perfect Matching:
✅ Has perfect matching (covers all 10 vertices with 5 edges)

🎯 5. Competition Strategy

🏆 Problem-Solving Framework

For Eulerian Questions:
1. Count vertices with odd degree
2. Apply Euler's Theorem:
• 0 odd → Eulerian circuit
• 2 odd → Eulerian path
• >2 odd → No Eulerian path

For Hamiltonian Questions:
1. Try Dirac's or Ore's theorems (sufficient conditions)
2. For small graphs: try constructing
3. Look for obstructions (cuts, degree sequences)
4. No simple characterization - be creative!

For Matching:
1. Identify if bipartite
2. Apply Hall's theorem
3. Construct matching greedily or systematically

🚨 Common Mistakes

⚠️ Τα 6 Πιο Συχνά Λάθη

1. Eulerian ↔ Hamiltonian Confusion
❌ "Traverses all edges = all vertices"
✅ Eulerian = edges, Hamiltonian = vertices!

2. Assuming Hamiltonian is easy
❌ "Just check degrees like Eulerian"
✅ Hamiltonian is NP-complete!

3. Forgetting connectivity
❌ Applying Euler without checking connected
✅ Graph must be connected first!

4. Dirac/Ore confusion
❌ Thinking they're necessary conditions
✅ They're only SUFFICIENT!

5. Perfect vs Maximum matching
❌ Confusing the definitions
✅ Perfect covers ALL vertices, maximum is largest size

6. Hall's theorem misapplication
❌ Using on non-bipartite graphs
✅ Hall's is specifically for bipartite!

🏆 CHALLENGE PROBLEM - Part 2

🎯 THE CHALLENGE

Πρόβλημα: Ένας γράφος με 8 κορυφές. Degree sequence: (3, 3, 3, 3, 4, 4, 4, 4).

Ερωτήσεις:
(a) Είναι δυνατός τέτοιος γράφος;
(b) Αν ναι, μπορεί να έχει Eulerian path;
(c) Αν ναι, μπορεί να είναι bipartite;

🎁 Hints σε 3 Επίπεδα:

🥉 Hint 1: Check handshaking lemma first!

🥈 Hint 2: For (b), count odd-degree vertices.

🥇 Hint 3: For (c), remember bipartite ↔ no odd cycles.

📮 Πλήρης Λύση:

(a) Is such a graph possible?

Handshaking: \(\sum \deg = 4(3) + 4(4) = 12 + 16 = 28\)
\(2|E| = 28 → |E| = 14\) ✓ (even sum)

Απάντηση (a): ✅ Ναι, δυνατός!

(b) Can it have Eulerian path?

Odd-degree vertices: 4 vertices με degree 3
4 > 2 → No Eulerian path! ❌

Απάντηση (b): ❌ Όχι, δεν μπορεί!

(c) Can it be bipartite?

Bipartite requires no odd cycles.
With degree sequence (3,3,3,3,4,4,4,4), it's POSSIBLE to construct bipartite.

Example: \(K_{4,4}\) minus some edges can achieve this!

Απάντηση (c): ✅ Ναι, μπορεί!

📊 Σύνοψη & Επόμενα Βήματα

🎓 Τι Μάθαμε:

✅ Eulerian Paths/Circuits: Degree conditions (0 or 2 odd)
✅ Euler's Theorem: Complete characterization
✅ Königsberg: Historical problem
✅ Hamiltonian Paths/Cycles: Vertex traversal
✅ Dirac's & Ore's Theorems: Sufficient conditions
✅ Matching Theory: Perfect & maximum matchings
✅ Hall's Theorem: Bipartite matching condition
✅ 7 Examples: From \(K_n\) to Petersen graph

🎊 Συγχαρητήρια!

Ολοκληρώσατε το Part 2 του Graph Theory Marathon!

Τι κατακτήσατε:
✅ Eulerian theory mastery
✅ Hamiltonian understanding
✅ Euler's theorem complete
✅ Dirac's & Ore's theorems
✅ Matching theory basics
✅ Hall's Marriage Theorem
✅ 7 αναλυτικά examples
✅ Competition techniques

📅 Επόμενο Part:
Part 3: Graph Coloring & Planarity
Chromatic numbers & Four Color Theorem! 🧡

Μείνετε συντονισμένοι...
Η περιπέτεια συνεχίζεται! 🚀🌳