4.1Graph basics: degrees and the handshake lemma
The idea
A graph is vertices joined by edges. The degree of a vertex counts its edges, and the handshake lemma says the degrees add up to twice the number of edges, so the number of odd-degree vertices is always even.
Think of it like this: At a party every handshake involves two hands, so the total number of hands shaken is twice the number of handshakes.
Why it exists
Counting edges from degrees, and deciding whether a degree sequence can exist, are the quickest marks in graph theory.
How it works
- Σ deg(v) = 2e.
- So the number of odd-degree vertices is even.
- K_n has n(n−1)/2 edges; an r-regular graph on n vertices has nr/2 edges.
- Havel–Hakimi: sort the sequence, remove the largest d, subtract 1 from the next d terms, repeat. It ends at all zeros iff the sequence is graphical.
Worked example: Can a graph have degrees 4, 4, 4, 1, 1?
The sum 14 is even, but Havel–Hakimi fails: remove 4 and subtract 1 from the next four terms to get 3, 3, 0, 0; remove 3 and subtract from the next three to get 2, −1, −1. A negative degree appears, so the sequence is not graphical. Try it in the lab.
Now play with it
- →Load K₄ and see every degree is 3 and the sum is 12 = 2·6.
- →Test "3 3 2 2 2" and "4 4 4 1 1" in the Havel–Hakimi box.
| vertex | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| degree | 3 | 3 | 3 | 3 |
| Graph | Vertices | Edges | χ | Planar? | Euler circuit? |
|---|---|---|---|---|---|
| K_n | n | n(n−1)/2 | n | n ≤ 4 | n odd |
| C_n (cycle) | n | n | 2 or 3 | ✓ | ✓ |
| P_n (path) | n | n − 1 | 2 | ✓ | ✗ |
| K_{m,n} | m+n | mn | 2 | min(m,n) ≤ 2 | m, n both even |
| Tree | n | n − 1 | 2 | ✓ | ✗ |
| Wheel W_n | n+1 | 2n | 3 or 4 | ✓ | ✗ |
| Hypercube Q_d | 2ᵈ | d·2ᵈ⁻¹ | 2 | d ≤ 3 | d even |
| Petersen | 10 | 15 | 3 | ✗ | ✗ |
These are the graphs GATE keeps reusing: have their numbers ready.
Check yourself
A simple graph has 12 edges and every vertex has degree 3. How many vertices?
Exam notes (the dense version)
A simple graph has no loops or repeated edges. Σ deg(v) = 2e, so the number of odd-degree vertices is even. K_n has n(n−1)/2 edges and is (n−1)-regular. A degree sequence is graphical if it passes Havel–Hakimi. A simple graph on n vertices has at most C(n,2) edges; a regular graph of degree r has nr/2 edges. In a directed graph Σ in-degree = Σ out-degree = e.
Previous year questions: Graph Theory (24)
PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.