‹
✏️
Graph Theory
· Examples✏️ Worked Examples — Step by Step
E1
EasyA tree has 12 vertices. How many edges?
💡 For a tree: n − 1.
👁 Show Solution
Trees always have n − 1 edges → 12 − 1 = 11. ✅ Answer: 11
✅11
E2
MediumSum of degrees in a graph with 7 edges:
💡 Handshake lemma: Σ deg = 2|E|.
👁 Show Solution
2 × 7 = 14. ✅ Answer: 14
✅14
E3
ChallengingDoes a graph with vertex degrees {3, 3, 3, 3, 3} exist?
💡 Sum of degrees must be even (handshake lemma).
👁 Show Solution
Sum = 15 (odd). But Σ deg must equal 2|E|, which is even. Contradiction → no such graph. ✅ Answer: No (sum is odd)
✅No