10.1 Terminology and the Handshaking Lemma
A graph G = (V, E) is a set of vertices and a set of edges joining pairs of vertices.
| Type | Multiple edges? | Loops? | Directed? |
|---|---|---|---|
| Simple graph | No | No | No |
| Multigraph | Yes | No | No |
| Pseudograph | Yes | Yes | No |
| Digraph | — | — | Yes |
The degree deg(v) is the number of edge-ends at v (a loop adds 2).
Handshaking Lemma: Σ deg(v) = 2|E| — every edge contributes exactly two endpoint-slots. Corollary: the number of odd-degree vertices is even.
Worked check: Can a graph have degree sequence 3, 3, 3, 3, 3? Sum = 15, which is odd — impossible, since the sum must equal 2|E|. But 4, 3, 3, 2, 2 sums to 14, so |E| = 7 is consistent.
10.2 Standard Families
| Graph | Vertices | Edges | Notes |
|---|---|---|---|
| Complete K_n | n | n(n−1)/2 | every pair joined |
| Cycle C_n | n | n | n ≥ 3 |
| Wheel W_n | n + 1 | 2n | C_n plus a hub |
| Complete bipartite K_{m,n} | m + n | m·n | two sides, all cross edges |
| Hypercube Q_n | 2^n | n·2^(n−1) | bit strings differing in 1 bit |
10.3 Isomorphism
G1 ≅ G2 iff a bijection f: V1 → V2 preserves adjacency. Quick invariants to test: |V|, |E|, degree sequence, number of components, cycle lengths. Matching invariants do not prove isomorphism — C6 and 2K3 (two disjoint triangles) both have 6 vertices, 6 edges, all degrees 2, yet C6 is connected and 2K3 is not, so they are not isomorphic. To prove isomorphism you must exhibit the bijection.
10.4 Euler and Hamiltonian Paths
- Euler circuit: closed walk using every edge exactly once. Exists in a connected multigraph iff every vertex has even degree. An Euler path (not closed) exists iff exactly two vertices have odd degree.
- Hamiltonian cycle: cycle visiting every vertex exactly once. No clean characterization exists (the decision problem is NP-complete); sufficient conditions: Dirac — n ≥ 3 and deg(v) ≥ n/2 for all v; Ore — deg(u) + deg(v) ≥ n for every non-adjacent pair.
Worked Example 1 — Königsberg. The famous bridge multigraph has degree sequence 5, 3, 3, 3 — four odd vertices. An Euler circuit needs zero odd vertices, an Euler path needs exactly two; with four, no walk crosses each bridge exactly once. Euler's 1736 argument founded graph theory. Contrast: K5 has all degrees 4 (even) → Euler circuit exists; and by Dirac (deg 4 ≥ 5/2) it is Hamiltonian too.
10.5 Planar Graphs and Euler's Formula
A graph is planar if it can be drawn without edge crossings. For a connected planar graph with v vertices, e edges, f faces (regions, counting the unbounded one):
Euler's formula: v − e + f = 2
Check on K4: v = 4, e = 6, drawn as a triangle with a center vertex → f = 4 regions; 4 − 6 + 4 = 2. ✔
Corollaries (connected simple planar, v ≥ 3): e ≤ 3v − 6; if additionally no triangles exist, e ≤ 2v − 4.
Worked Example 2 — two famous non-planar graphs.
- K5: e = 10, v = 5, but 3v − 6 = 9 < 10 → non-planar.
- K3,3: e = 9, v = 6; it is bipartite, so it has no odd cycles, in particular no triangles → the bound e ≤ 2v − 4 = 8 applies, and 9 > 8 → non-planar. (The plain 3v − 6 = 12 bound would not have caught it.)
Kuratowski's theorem: a graph is non-planar iff it contains a subdivision of K5 or K3,3.
10.6 Graph Coloring
A proper vertex coloring assigns colors so adjacent vertices differ; the least number needed is the chromatic number χ(G). Facts: χ(K_n) = n; χ(C_n) = 2 for even n, 3 for odd n; χ(bipartite) = 2; Four Color Theorem: every planar graph has χ ≤ 4.
Scheduling application: exams D, M, N, P where conflicts (shared students) are D–M, D–N, M–N, N–P. The triangle D, M, N forces 3 time slots; P conflicts only with N, so it reuses D's slot. χ = 3 → 3 exam slots suffice. The same model performs register allocation in compilers (variables = vertices, simultaneous liveness = edges, registers = colors).
10.7 Common Mistakes
- Euler = every edge once; Hamilton = every vertex once — students swap them constantly.
- Applying e ≤ 3v − 6 to disconnected or non-simple graphs, or concluding "satisfies the bound → planar" (the bound is necessary, not sufficient).
- Forgetting the unbounded face when counting f.
🎯 Exam Focus
- State and prove the handshaking lemma; deduce that odd-degree vertices come in pairs.
- Does a simple graph with degree sequence 5, 5, 4, 3, 2, 1 exist? Justify.
- Determine whether K_{2,3} has an Euler path, an Euler circuit, and a Hamiltonian cycle.
- Verify Euler's formula for K_{2,3} drawn in the plane, and prove K_{3,3} is non-planar.
- Define graph isomorphism. Show C6 and 2K3 are not isomorphic despite identical degree sequences.
- Find χ(K5), χ(C7), χ(K_{3,4}), and χ of the Petersen graph's 5-cycle subgraph.