Key Idea: A graph is a set of points (vertices) joined by lines (edges), such as towns and roads. You name types of graph, count degrees, and describe routes through them.
| Route | Rule |
|---|---|
| Walk | Any route; vertices and edges may repeat |
| Trail | No repeated edge (a vertex may repeat) |
| Path | No repeated vertex (so no repeated edge) |
| Cycle | A path that returns to its start |
Key facts
- Handshake: Σ deg = 2E, so odd-degree vertices come in even numbers.
- Kₙ: every pair joined; n(n − 1)/2 edges; each degree n − 1.
- Tree: connected + no cycles ⇒ exactly n − 1 edges.
Trail = don't reuse a road; path = don't revisit a town; cycle = a path that loops back home.
Route A → B → C → A → D uses four different edges. What is it? A trail: no edge repeats, but A is visited twice.
How many edges does K₅ have? 5 × 4 / 2 = 10.
A tree has 8 vertices. How many edges? 7.
A graph has degrees 3, 3, 2, 2. How many edges? The degrees add to 10, so 5 edges.