Graph Theory¶
A graph is the simplest interesting mathematical object: a set of vertices (dots) joined by edges (lines). That's it. Despite the bare setup, a surprising amount of structure follows, and it models everything from road networks to molecules to scheduling.
We'll write \(v = \lvert V \rvert\) for the number of vertices and \(e = \lvert E \rvert\) for the number of edges. The examinable results are few and most have one-line proofs — but they are almost all phrased as "if and only if", and the marks come from handling both directions (or citing the correct one). Keep asking yourself: which direction do I need here?
Degrees¶
The degree \(\deg(x)\) of a vertex is how many edge-ends meet at it — loosely, how many lines come out of that dot.
Handshake lemma
The sum of all degrees is always even — in fact exactly twice the number of edges.
Why. Each edge has two ends, and each end contributes \(1\) to the degree of some vertex. So every edge adds exactly \(2\) to the grand total of degrees. (The name comes from: at a party, the total number of handshake-ends is twice the number of handshakes.)
The move it unlocks: the number of odd-degree vertices must be even. So a question like "is there a graph with degrees \(3,3,3,3,3\)?" is settled instantly — that's five odd degrees summing to \(15\), an odd number, impossible.
Eulerian circuits and paths¶
Named after the problem that started the whole subject (the bridges of Königsberg). An Eulerian circuit is a walk that uses every edge exactly once and ends where it started.
Euler's theorem
A connected graph has an Eulerian circuit if and only if every vertex has even degree.
It has an Eulerian path (every edge once, but allowed to end somewhere else) if and only if it has exactly zero or two odd-degree vertices. If there are two, the path must start at one of them and finish at the other.
Why even degree is the magic condition. Picture the walk passing through a vertex: it comes in along one edge and leaves along another, using edges in in–out pairs. For the walk to use up all edges at a vertex and still be able to leave each time, those edges must pair up perfectly — i.e. the degree must be even. A vertex of odd degree has one edge left unpaired, so the walk can only stop there — which is why odd-degree vertices are exactly the allowed endpoints of a path, and forbidden entirely in a circuit.
Exam (May 2024, Problem 2d)
"Does the graph have an Eulerian circuit?"
A complete answer is two sentences: A connected graph has an Eulerian circuit if and only if every vertex has even degree. Here every vertex has odd degree, so it does not. State the criterion, check it against this graph, conclude. That's the whole mark — nothing is gained by doing more, and marks are lost by doing less (e.g. skipping the criterion).
Hamiltonian cycles¶
Deceptively similar name, wildly different difficulty. A Hamiltonian cycle visits every vertex exactly once and returns to the start.
The contrast with Eulerian is the thing to burn into memory:
| Visits… | How hard to test | |
|---|---|---|
| Eulerian | every edge once | Easy — just check the degrees |
| Hamiltonian | every vertex once | Hard — no known efficient criterion at all |
There is no neat "if and only if" for Hamiltonicity. So the two directions demand different kinds of answer:
- To show one exists: just write it down. A vertex sequence like \(a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_0\) is a complete proof — the reader can verify it by eye, so no further argument is needed.
- To show none exists: you need a structural reason. The usual lever is bipartiteness (below): a Hamiltonian cycle in a bipartite graph must bounce back and forth between the two sides, so it needs the sides to be equal in size. If they aren't, no Hamiltonian cycle can exist.
Bipartite graphs¶
A graph is bipartite if you can split the vertices into two groups so that every edge goes between the groups — none stays inside a group. Think two teams, where players only ever link to the opposing team. Equivalently, it's a graph you can 2-colour with no edge joining same-coloured vertices.
Bipartiteness criterion
A graph is bipartite if and only if it has no cycle of odd length.
Intuition for the criterion. If you 2-colour by alternating along edges (red, blue, red, blue, …), a cycle brings you back to your start — and you only return to the same colour if the cycle had even length. An odd cycle would force a vertex to be both colours, which is the contradiction.
- To prove a graph is bipartite: exhibit the 2-colouring (name the two groups).
- To prove it isn't: exhibit a single odd cycle — a triangle is the smallest and usually easiest.
Isomorphism¶
Two graphs are isomorphic if they're the same graph drawn differently — formally, a relabelling of vertices (a bijection) that turns one graph's edges exactly into the other's.
- To prove isomorphic: give the vertex correspondence explicitly, and check every edge on one side maps to an edge on the other.
-
To prove not isomorphic: find a property that survives relabelling (an invariant) but differs between the two. Cheap invariants to try, roughly easiest first:
- Number of vertices; number of edges.
- The degree sequence — the sorted list of all vertex degrees.
- Number of cycles of each length; the girth (shortest cycle).
- Connectivity; number of connected components.
- Bipartite or not.
If any of these differs, the graphs cannot be isomorphic — done.
Matching degree sequences prove nothing on their own
Equal degree sequences are necessary but not sufficient: there are plenty of pairs of non-isomorphic graphs with identical degree sequences. So if the degree sequences match, you have ruled nothing out — you must either dig up a finer invariant or actually construct the relabelling. Don't declare two graphs isomorphic just because their degree sequences agree.
Trees¶
A tree is a connected graph with no cycles — the "no redundancy" graph, where there's exactly one way to get between any two vertices.
Tree edge count
Every tree satisfies \(v = e + 1\) — one more vertex than edges.
Why. Start from a single vertex (0 edges) and grow the tree by adding one vertex at a time; each new vertex must attach with exactly one new edge (more would make a cycle, fewer would disconnect it). So edges always trail vertices by one.
These characterisations are all equivalent — any one can be the definition, and different problems want different ones: connected and acyclic; connected with \(v = e+1\); acyclic with \(v = e+1\); exactly one path between any two vertices.
A spanning tree of a graph \(G\) is a subgraph that (a) is a tree and (b) includes all of \(G\)'s vertices — a minimal skeleton that still connects everything. Every connected graph has one: repeatedly delete an edge lying on a cycle; deleting a cycle-edge never disconnects the graph, and you stop when no cycles remain — a tree.
Planar graphs¶
A graph is planar if it can be drawn in the plane with no edges crossing. Emphasis on can: planarity is about whether some crossing-free drawing exists. A messy drawing full of crossings doesn't prove a graph non-planar — it might just be a bad drawing of a perfectly planar graph.
Euler's formula
For a connected planar graph drawn without crossings,
where \(f\) is the number of faces — the regions the drawing cuts the plane into, including the single unbounded region on the outside.
The one thing people forget: count the outer face. A triangle drawn in the plane has \(f = 2\), not \(1\) — the inside and the outside.
Exam (May 2024, Problem 2a–c): the 8-vertex graph
(a) "Make a planar drawing." The official solution is literally one sentence — just move two of the parallel inside edges to the outside — a good reminder that the answer to a planarity question is a redrawing, not a calculation. You're being asked to find the crossing-free picture.
(b) "Check Euler's formula." From your redrawing: \(v = 8\), \(e = 8 + 4 = 12\), and counting regions (don't forget the outside) \(f = 6\):
Count \(f\) from your own drawing — Euler's formula is checking that specific drawing.
(c) "Does it have a Hamiltonian cycle?" Yes: \(a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_0\). Writing the cycle down is the entire proof (see Hamiltonian cycles).
Consequences worth knowing¶
Euler's formula has two corollaries that give fast non-planarity proofs. For a connected simple planar graph with \(v \geq 3\):
How to use them: if a graph has too many edges for its vertex count, it can't be planar.
- \(K_5\) (5 vertices, all joined): \(v = 5\), \(e = 10\). But \(3v - 6 = 9 < 10\). So \(K_5\) is not planar.
- \(K_{3,3}\) (two groups of 3, all cross-edges): bipartite, so use the second bound. \(v = 6\), \(e = 9\), but \(2v - 4 = 8 < 9\). Not planar.
These two graphs, \(K_5\) and \(K_{3,3}\), are the fundamental obstructions: Kuratowski's theorem says a graph is planar exactly when it contains no subgraph that is a subdivision of either one. Every non-planar graph hides one of these two inside it.