Graph Theory — Degrees, Handshaking Lemma, Paths, Euler and Hamiltonian Circuits, Trees, Bipartite and Planar Graphs, Colouring

Maps, social networks, the internet, course prerequisites, dependency graphs in build tools — all graphs. DSA teaches algorithms on graphs (BFS, DFS, Dijkstra); discrete maths gives the theory and vocabulary behind them.

1. Basic terms

A graph G = (V, E): vertices (nodes) and edges connecting pairs of them.

2. The handshaking lemma

The sum of all degrees = 2 × number of edges (each edge has two ends).

Consequence: the number of odd-degree vertices is always even. (So "a party of 7 where everyone shook hands with exactly 3 others" is impossible: 7 × 3 = 21 is odd.)

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("D", "E"), ("B", "D")]
degree = {}
for u, v in edges:
    degree[u] = degree.get(u, 0) + 1
    degree[v] = degree.get(v, 0) + 1
print("degrees:", degree)
print("sum of degrees =", sum(degree.values()), "= 2 x edges =", 2 * len(edges))
print("odd-degree vertices:", [v for v, d in degree.items() if d % 2])

degrees: {'A': 2, 'B': 3, 'C': 3, 'D': 3, 'E': 1}
sum of degrees = 12 = 2 x edges = 12
odd-degree vertices: ['B', 'C', 'D', 'E']

3. Euler and Hamiltonian circuits

The graph in section 2 has four odd-degree vertices (B, C, D, E) — so, just like the Königsberg bridges, it has neither an Euler path nor an Euler circuit. A simple square (every degree 2) has an Euler circuit:

from itertools import permutations

def euler_status(edges):
    deg = {}
    for u, v in edges:
        deg[u] = deg.get(u, 0) + 1
        deg[v] = deg.get(v, 0) + 1
    odd = [v for v, d in deg.items() if d % 2]
    return "Euler circuit" if not odd else f"Euler path between {odd}" if len(odd) == 2 else "neither"

def has_hamiltonian_cycle(vertices, edges):
    E = {frozenset(e) for e in edges}
    first, rest = vertices[0], vertices[1:]
    for p in permutations(rest):
        cycle = [first, *p, first]
        if all(frozenset((cycle[i], cycle[i + 1])) in E for i in range(len(cycle) - 1)):
            return cycle
    return None

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("D", "E"), ("B", "D")]
print(euler_status(edges))
print("Hamiltonian cycle:", has_hamiltonian_cycle(list("ABCDE"), edges))
square = [("1", "2"), ("2", "3"), ("3", "4"), ("4", "1")]
print(euler_status(square), "| Hamiltonian:", has_hamiltonian_cycle(list("1234"), square))

neither
Hamiltonian cycle: None
Euler circuit | Hamiltonian: ['1', '2', '3', '4', '1']

Vertex E has degree 1, so no cycle can pass through it — no Hamiltonian cycle. The brute-force search tries all orderings (n! of them), which is exactly why Hamiltonian problems are hard for large graphs.

4. Trees

A tree is a connected graph with no cycles. Facts (any one follows from the others):

• a tree with n vertices has exactly n − 1 edges;
• there is exactly one path between any two vertices;
• removing any edge disconnects it; adding any edge creates a cycle.

A spanning tree connects all vertices of a graph using n − 1 of its edges; a minimum spanning tree (Kruskal, Prim) does it with least total weight — network cabling, road planning. By Cayley's formula, the complete graph Kₙ has nⁿ⁻² spanning trees.

5. Bipartite graphs

Vertices split into two groups with edges only between groups (students ↔ courses, applicants ↔ jobs). A graph is bipartite iff it has no odd-length cycle — test it by 2-colouring with BFS:

from collections import deque

def is_bipartite(adj):
    colour = {}
    for start in adj:
        if start in colour:
            continue
        colour[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in colour:
                    colour[v] = 1 - colour[u]
                    q.append(v)
                elif colour[v] == colour[u]:
                    return False
    return True

square = {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [3, 1]}
triangle = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
print("square (4-cycle) bipartite:", is_bipartite(square))
print("triangle (3-cycle) bipartite:", is_bipartite(triangle))

square (4-cycle) bipartite: True
triangle (3-cycle) bipartite: False

6. Planar graphs and Euler's formula

A graph is planar if it can be drawn with no crossing edges. For a connected planar graph: V − E + F = 2 (F = faces, including the outer one). Consequences for simple planar graphs with V ≥ 3: E ≤ 3V − 6. So K₅ (V = 5, E = 10 > 9) is not planar; K₃,₃ isn't either (Kuratowski).

7. Graph colouring

Colour vertices so that adjacent ones differ. The minimum number of colours is the chromatic number χ(G).

Real use: exam timetabling (subjects = vertices, edge if a student takes both, colours = time slots), register allocation in compilers, frequency assignment.

Common mistakes

• Confusing Euler (edges) with Hamiltonian (vertices).
• Forgetting the outer face in Euler's formula.
• Assuming a graph with n − 1 edges is a tree (it must also be connected / acyclic).
• Claiming "odd cycle ⇒ bipartite" (it's the opposite).

Quick recap

• Σ deg(v) = 2|E|; the number of odd-degree vertices is even.
• Euler circuit ⇔ connected + all degrees even; Euler path ⇔ exactly 2 odd vertices. Hamiltonian: no easy test.
• Tree: connected, acyclic, n − 1 edges; Kₙ has nⁿ⁻² spanning trees.
• Bipartite ⇔ no odd cycle (2-colourable).
• Planar: V − E + F = 2, E ≤ 3V − 6; colouring: planar ≤ 4 colours.