Graph Theory

A graph G = (V, E) has a set of vertices V and a set of edges E, each joining two vertices. Graph theory began in 1736 when Leonhard Euler proved that nobody could walk across all seven bridges of Königsberg exactly once.

#Kinds of graphs

#Degree and the handshake lemma

The degree deg(v) is the number of edges at v (a loop counts twice). In every undirected graph:

Σ deg(v) = 2|E|

So the number of odd-degree vertices is always even. In a directed graph, Σ in-degree = Σ out-degree = |E|.

#Special graphs

A graph is bipartite if and only if it has no odd-length cycle — checkable by 2-colouring with BFS.

#Isomorphism

Two graphs are isomorphic if there is a bijection between their vertices that preserves adjacency — they are the same graph drawn differently. Isomorphic graphs share every invariant: number of vertices and edges, degree sequence, number of cycles of each length, connectedness. Different invariants prove two graphs are not isomorphic; equal invariants do not prove that they are.

#Paths, circuits and connectivity

• A path is a sequence of edges from one vertex to another; a circuit (cycle) returns to its start.
• A graph is connected if every pair of vertices has a path between them.
• A cut vertex (articulation point) or bridge is a vertex or edge whose removal disconnects the graph.

#Euler paths and circuits

An Euler circuit uses every edge exactly once and returns to the start; an Euler path uses every edge once without returning.

A connected graph has an Euler circuit iff every vertex has even degree. It has an Euler path (but no circuit) iff it has exactly two odd-degree vertices — the path starts at one and ends at the other.

Königsberg had four land masses with degrees 5, 3, 3, 3 — four odd vertices, so no Euler path exists.

from collections import Counter

def euler_status(edges):
    deg = Counter()
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
    odd = [v for v in deg if deg[v] % 2]
    if not odd:
        return "Euler circuit exists"
    if len(odd) == 2:
        return f"Euler path from {odd[0]} to {odd[1]}"
    return f"neither ({len(odd)} odd vertices)"

konigsberg = [("A","B"), ("A","B"), ("A","C"), ("A","C"), ("A","D"), ("B","D"), ("C","D")]
house = [(1,2), (2,3), (3,4), (4,1), (1,5), (2,5), (1,3), (2,4)]
square = [(1,2), (2,3), (3,4), (4,1)]
for name, g in [("Konigsberg", konigsberg), ("envelope house", house), ("square", square)]:
    print(f"{name:15} {euler_status(g)}")

Konigsberg      neither (4 odd vertices)
envelope house  Euler path from 3 to 4
square          Euler circuit exists

#Hamilton paths and circuits

A Hamilton circuit visits every vertex exactly once and returns to the start. Unlike the Euler case, no simple test is known — deciding whether one exists is NP-complete. Sufficient conditions exist: Dirac's theorem says a simple graph with n ≥ 3 vertices where every vertex has degree ≥ n/2 has a Hamilton circuit.

#Planar graphs

A graph is planar if it can be drawn without edges crossing. For a connected planar graph, Euler's formula holds:

V − E + F = 2 (F = number of faces, including the outer one)

Consequence: a connected simple planar graph with V ≥ 3 has E ≤ 3V − 6. K₅ has E = 10 > 3·5 − 6 = 9, so K₅ is not planar. By Kuratowski's theorem, a graph is planar iff it contains no subdivision of K₅ or K₃,₃.

#Graph colouring

A proper colouring gives adjacent vertices different colours; the minimum number of colours is the chromatic number χ(G).

• χ(Kₙ) = n; χ(Cₙ) = 2 if n is even, 3 if odd; χ of a bipartite graph = 2.
• Four colour theorem (1976, proved with a computer): every planar graph has χ ≤ 4.
• Applications: exam timetabling (subjects sharing a student cannot share a slot), register allocation in compilers, frequency assignment.