Graphs

A graph G = (V, E) is a set of vertices V (also called nodes) and a set of edges E, each joining two vertices. Graphs model road maps, friendships, computer networks, course prerequisites and web links.

• In an undirected graph an edge {u, v} goes both ways (a friendship). In a directed graph an edge (u, v) has a direction (a one-way road, a web link).
• A simple graph has no loops (edges from a vertex to itself) and no repeated edges.
• Two vertices joined by an edge are adjacent. The degree of a vertex is the number of edges at it.

The handshake lemma

Each edge has two ends, so it adds 2 to the total degree:

sum of all degrees = 2 × number of edges

So the number of vertices with odd degree is always even. At a party, the number of people who shook an odd number of hands is even.

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

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 ×", len(edges), "edges")
odd = [v for v in degree if degree[v] % 2 == 1]
print("odd vertices:", odd, "(always an even number of them)")

Special graphs

A graph is bipartite exactly when it has no cycle of odd length. A tree with n vertices always has n − 1 edges, and there is exactly one path between any two of its vertices.

Computers store graphs as an adjacency list (for each vertex, the list of its neighbours: small for sparse graphs) or an adjacency matrix (an n × n table of 0s and 1s: quick to test one pair). The Data Structures course builds both.

Paths, and the bridges of Königsberg

A path is a sequence of vertices joined by edges; a circuit (or cycle) is a path that ends where it starts. A graph is connected if there is a path between every pair of vertices.

The city of Königsberg had seven bridges joining four land areas. Could you walk across every bridge exactly once? In 1736 Euler proved you could not, and founded graph theory. An Euler path uses every edge exactly once; an Euler circuit also returns to its start. For a connected graph:

• an Euler circuit exists exactly when every vertex has even degree,
• an Euler path (not a circuit) exists exactly when exactly two vertices have odd degree, and it must start at one of them and end at the other.

Each time a walk passes through a vertex, it uses two of its edges, one in and one out; only the start and end can be left with one. Königsberg's four land areas all had odd degree.

def euler(edges):
    degree = {}
    for u, v in edges:
        degree[u] = degree.get(u, 0) + 1
        degree[v] = degree.get(v, 0) + 1
    odd = sorted(v for v in degree if degree[v] % 2 == 1)
    if not odd:
        return "an Euler circuit"
    if len(odd) == 2:
        return f"an Euler path from {odd[0]} to {odd[1]}"
    return f"neither: {len(odd)} odd vertices"

# The seven bridges: N and S are the river banks, I is the island, E the east land
konigsberg = [("N", "I"), ("N", "I"), ("S", "I"), ("S", "I"), ("N", "E"), ("S", "E"), ("I", "E")]
house = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A"), ("A", "C"), ("B", "D"), ("C", "E"), ("D", "E")]

print("Königsberg:", euler(konigsberg))
print("envelope house:", euler(house))
print("square:", euler([("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]))

A Hamilton path visits every vertex exactly once. It sounds similar, but no simple test is known: deciding whether one exists is NP-complete, among the hardest problems in computing (more in the Theory of Computation course).

Colouring and planar graphs

A colouring gives adjacent vertices different colours; the fewest colours needed is the chromatic number. Exam timetables are colourings: courses are vertices, an edge joins two courses with a shared student, and colours are time slots.

A graph is planar if it can be drawn with no edges crossing. For a connected planar graph, Euler's formula holds: v − e + f = 2, where f counts the faces (regions), including the outside. K₅ is not planar. The four colour theorem says every planar graph, so every map, needs at most 4 colours; its 1976 proof was the first major proof that needed a computer.

Mark lesson complete