Graph theory: practice problems with step-by-step solutions

1Vertices, edges and degrees

A graph consists of vertices (points) and edges (lines between two vertices). In a simple graph there are no loops and no double edges.

The degree of a vertex is the number of edges that meet it. Every edge has two ends, so it adds 1 to the degree of each end. That gives the handshake lemma:

Two consequences: the sum of the degrees is always even, and the number of vertices with odd degree is even too.

• The complete graph K_n joins every pair: n(n − 1)/2 edges.
• The complete bipartite graph K_m,n joins every vertex on one side to every vertex on the other: m·n edges.
• A k-regular graph on n vertices has n·k/2 edges.

The adjacency matrix has a 1 at (i, j) when i and j are joined. For an undirected graph it is symmetric, a row sum is a degree, and the entry (i, j) of Mᴸ counts the walks of length L from i to j.

2Euler and Hamilton

An Euler circuit uses every edge exactly once and returns to its start. An Euler path uses every edge once but may end elsewhere. For a connected graph:

• all degrees even: an Euler circuit exists;
• exactly two odd degrees: an Euler path exists, from one odd vertex to the other;
• more than two odd degrees: neither.

A Hamilton circuit visits every vertex exactly once. There is no simple degree test for it. In K_n there are (n − 1)!/2 different Hamilton circuits: fix the start, order the other n − 1 vertices, and divide by 2 for the two directions.

3Trees

A tree is a connected graph without cycles. Every tree with n vertices has exactly n − 1 edges. Adding any edge creates a cycle; removing any edge disconnects it.

A forest of c trees on n vertices has n − c edges. A connected graph with m edges keeps a spanning tree after removing m − n + 1 edges.

The handshake lemma counts leaves: Σ deg = 2(n − 1). A short form is L = 2 + Σ (d − 2) over the vertices with degree d ≥ 3. A tree with two vertices of degree 3 and the rest leaves has 2 + 1 + 1 = 4 leaves.

4Dijkstra and minimum spanning trees

Dijkstra’s algorithm finds shortest distances from a start vertex in a graph with nonnegative weights.

1. Give the start distance 0 and every other vertex ∞.
2. Settle the unsettled vertex with the smallest distance; its distance is now final.
3. For each neighbour v, update d(v) = min(d(v), d(u) + w(u, v)).
4. Repeat until the target is settled.

A minimum spanning tree connects all vertices with the smallest total weight. Kruskal sorts the edges from light to heavy and takes each one unless it closes a cycle. Prim grows one tree from a start vertex, always adding the lightest edge that leaves it. Both stop after n − 1 edges.

5Common mistakes

• Forgetting to divide the degree sum by 2 to get the number of edges.
• Testing for an Euler circuit without checking that the graph is connected.
• Settling a vertex in Dijkstra before it has the smallest tentative distance.
• Taking the n − 1 lightest edges without checking for cycles.
• Counting Hamilton circuits of K_n as n! instead of (n − 1)!/2.

6How exam questions look

• Easy: degrees and edges. You use the handshake lemma, count the edges of K_n, K_m,n, regular graphs and trees, read an adjacency matrix, or click the vertex with a given degree.
• Medium: Euler paths and trees. You decide whether a graph has an Euler circuit or path, count leaves of a tree, count edges to remove for a spanning tree, or count Hamilton circuits in K_n.
• Hard: shortest paths and spanning trees. You run Dijkstra’s algorithm, find the vertex settled in a given round, find the weight of a minimum spanning tree, click the edge Kruskal or Prim adds next, or count walks with the adjacency matrix.