MAT9004 · Mathematical Foundations For Data Science And Ai
Graph Theory
Graph theory is the maths of connection — networks of vertices and edges that model everything from social networks to dependencies in a computation. The chapter defines a graph (simple vs multigraph, directed vs undirected), then proves its first workhorse result, the handshaking lemma: the sum of all vertex degrees equals twice the number of edges, Σ deg(v) = 2|E|. From there come walks, paths, cycles and connectivity, then trees (a connected graph with n vertices and exactly n − 1 edges) and spanning trees. The algebraic tool is the adjacency matrix, whose k-th power counts walks of length k — a direct payoff from the linear-algebra block. The chapter closes with special graphs (complete and bipartite) and the contrast between Euler trails (use every edge) and Hamilton paths (visit every vertex). It is procedural: read the graph, apply the right definition or count.
What this chapter covers
- 016.1 What is a graph? Vertices and edges
- 026.2 Degree and the handshaking lemma Σ deg(v) = 2|E|
- 036.3 Walks, paths, cycles and connectivity
- 046.4 Trees and spanning trees
- 056.5 Adjacency matrices and counting walks with Aᵏ
- 066.6 Reading A and counting walks (worked)
- 076.7 Special graphs: complete and bipartite
- 086.8 Euler trails vs Hamilton paths
Worked example: the handshaking lemma
- +1(a) Sum the degrees: with 7 vertices each of degree 4, Σ deg(v) = 7×4 = 28.
- +1(a) Apply the handshaking lemma: Σ deg(v) = 2|E|, so 28 = 2|E| ⇒ |E| = 14 edges.
- +1(b) Sum the degrees: 5 vertices each of degree 3 give Σ deg(v) = 5×3 = 15, an odd number.
- +1(b) Conclude: the degree sum must equal 2|E|, which is always even, but 15 is odd — so no such graph can exist.
Key terms
- Degree
- The number of edges meeting a vertex. The degree sequence (the list of degrees) is a basic fingerprint of a graph, and the degree sum is governed by the handshaking lemma.
- Handshaking lemma
- In any graph the sum of the vertex degrees equals twice the number of edges, Σ deg(v) = 2|E|. A corollary: the number of odd-degree vertices is always even.
- Tree
- A connected graph with no cycles. Equivalently, a connected graph on n vertices with exactly n − 1 edges — adding any edge creates a cycle, removing any edge disconnects it.
- Adjacency matrix
- A square matrix A where entry Aij records whether vertices i and j are joined by an edge. The entries of the k-th power Ak count the walks of length k between each pair of vertices.
- Euler vs Hamilton
- An Euler trail uses every edge exactly once (it exists iff at most two vertices have odd degree); a Hamilton path visits every vertex exactly once. Euler is about edges, Hamilton about vertices — the classic point of confusion.
Graph Theory FAQ
What is the handshaking lemma good for?
It links the degrees to the edge count: Σ deg(v) = 2|E|. Use it to count edges from a degree sequence (sum the degrees, halve it) and to rule out impossible graphs — if the degree sum is odd, no such graph exists, because 2|E| is always even. That impossibility argument is a recurring exam question.
How do I tell whether a graph is a tree?
Check two things: it must be connected, and it must have no cycles. A useful shortcut: a connected graph on n vertices is a tree exactly when it has n − 1 edges. More than n − 1 edges forces a cycle; fewer than n − 1 forces a disconnection. State which property you are using as your justification.
What does the adjacency matrix power Aᵏ tell me?
The (i, j) entry of Ak counts the number of walks of length exactly k from vertex i to vertex j. So A itself counts length-1 walks (edges), A2 counts length-2 walks, and so on. It is the direct payoff of matrix multiplication from the linear-algebra block, and the exam tests it by asking you to multiply a small adjacency matrix by hand.
What's the difference between Euler and Hamilton?
An Euler trail traverses every edge exactly once; a Hamilton path visits every vertex exactly once. The mnemonic: Euler = edges, Hamilton = vertices. Euler trails have a clean existence test (at most two odd-degree vertices), whereas deciding whether a Hamilton path exists is genuinely hard in general — the exam tests recognition and small cases, not a general algorithm.
Exam move
Lead with the handshaking lemma — degree sequence → count edges is one of the most reliable chains in the unit, and its odd-degree-sum impossibility argument recurs. Learn the tree characterisation cold (connected, no cycles, n − 1 edges) and state which property justifies your answer. For adjacency matrices, practise multiplying a small A by hand and reading Ak as a walk count — it reuses the matrix multiplication from the linear-algebra block, so the two chapters reinforce each other. Keep Euler (edges, clean odd-degree test) and Hamilton (vertices, no easy test) firmly apart, since they are tested as a deliberate point of confusion. Most marks here come from precise definitions applied carefully, so define before you count.
