Graph Theory: Dots, Lines and Networks

Graph words you need

A graph G has a set of vertices (also called nodes) and a set of edges (lines joining two vertices). Only connections matter, not how the picture is drawn.

• Adjacent vertices are joined by an edge.
• A loop joins a vertex to itself. Multiple edges join the same pair twice. A simple graph has neither.
• A directed graph (digraph) has one-way arrows, like one-way streets or who-follows-whom online.
• A weighted graph gives each edge a number: distance, time or cost.
• An adjacency matrix is a table: row A, column B holds the number of edges from A to B.

Degree and the handshake lemma

The degree of a vertex, deg(v), is the number of edge-ends at it (a loop counts 2).

Handshake lemma: sum of all degrees = 2 × number of edges. Each edge has two ends, so it adds 2 to the total.

So the total degree is always even, and the number of vertices with odd degree is always even. You can never draw a graph with exactly one odd vertex.

Example: in a party of 6 people, if everyone shakes hands with everyone else, each has degree 5. Total = 30, so there are 15 handshakes.

Walks, paths, cycles, Euler and Hamilton

A walk moves along edges. A trail never repeats an edge. A path never repeats a vertex. A cycle is a path that returns to its start. A graph is connected if you can walk from any vertex to any other.

Euler (1736) solved the bridges of Königsberg puzzle: can you cross 7 bridges once each? He showed a connected graph has:

• an Euler circuit (every edge once, back to start) if all degrees are even;
• an Euler trail (semi-Eulerian) if exactly 2 vertices are odd: start at one, end at the other;
• neither if more than 2 vertices are odd.

A Hamiltonian cycle visits every vertex once and returns. There is no simple rule to test for it; you must search.

A random walk moves to a neighbour chosen by chance at each step. Its long-run behaviour is studied with matrices (Markov chains), which is how early web search ranked pages.

Special graphs, trees, planarity and spanning trees

• Complete graph Kₙ: every pair joined; it has n(n − 1)/2 edges.
• Bipartite graph: vertices split into two groups, edges only between groups. K₃,₃ joins 3 houses to 3 utilities.
• Tree: connected with no cycles. A tree with n vertices has exactly n − 1 edges. Family trees and folder structures are trees.

Isomorphic graphs are the same graph drawn differently: same vertices, same connections, after renaming. Quick checks: same number of vertices, edges and the same list of degrees.

A planar graph can be drawn with no edges crossing. For a connected planar graph, Euler’s formula: V − E + F = 2 (F counts regions, including the outside). K₅ and K₃,₃ are not planar.

A spanning tree uses all vertices with no cycles. The minimum spanning tree has the least total weight. Kruskal: sort edges by weight, add the cheapest that makes no cycle. Prim: grow from one vertex, always adding the cheapest edge to a new vertex. Dijkstra’s algorithm finds shortest paths from one vertex.

Key formulas and definitions

• Σ deg(v) = 2E (handshake lemma)
• Edges in complete graph Kₙ = n(n − 1)/2
• Edges in a tree with n vertices = n − 1
• Euler’s formula for connected planar graphs: V − E + F = 2
• Euler circuit: all degrees even; Euler trail: exactly 2 odd vertices
• Simple planar graph (V ≥ 3): E ≤ 3V − 6

Worked examples

Common mistakes

• Counting a loop as degree 1. A loop touches the vertex twice, so it adds 2.
• Mixing up Euler (every edge once) and Hamilton (every vertex once).
• Forgetting to check the graph is connected before using the Euler degree rule.
• In Euler’s formula, forgetting to count the outside region as a face.