A graph consists of vertices (nodes) connected by edges. The degree of a vertex is the number of edges meeting it.
Handshaking lemma
\( \sum \deg(v) = 2E \)
The sum of all vertex degrees equals twice the number of edges \( E \)
▶
Key terms:Simple graph = no loops or multiple edges. Connected = path between every pair of vertices. \( K_n \) (complete graph) = every vertex connected to every other.
2
Directed Graphs (Digraphs)
In a directed graph the edges have a direction (arrows). For a vertex \( v \): the out-degree = number of edges leaving \( v \); the in-degree = number of edges entering \( v \).
Digraph adjacency matrix
Entry \( a_{ij} \) = number of edges from \( i \) to \( j \) (so the matrix need not be symmetric).
Row sums = out-degrees · Column sums = in-degrees
Mini-example
A digraph has edges \( A\!\to\!B \), \( B\!\to\!C \), \( A\!\to\!C \). Find the in/out-degree of \( A \).
Out of \( A \): edges to \( B \) and \( C \) → out-degree \( = 2 \)
Into \( A \): no edges arrive → in-degree \( = 0 \)
Answer: out-degree \( = 2 \), in-degree \( = 0 \)
3
Adjacency Matrices & Walks
The adjacency matrixA is an \( n \times n \) matrix where entry \( a_{ij} \) = number of edges between vertex \( i \) and vertex \( j \).
Number of walks
The entry \( (i, j) \) of \( A^k \) gives the number of walks of length \( k \) from vertex \( i \) to vertex \( j \).
For walks of length \( k \) or less, use entry \( (i,j) \) of \( A + A^2 + \cdots + A^k \).
Worked Example
For the triangle \( K_3 \), \( A = \begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix} \). How many walks of length 3 go from vertex 1 to vertex 2?
Compute \( A^3 \) on the GDC: \( A^3 = \begin{pmatrix}2&3&3\\3&2&3\\3&3&2\end{pmatrix} \)
Read entry \( (1,2) \) of \( A^3 \)
Answer: entry \( (1,2) = 3 \), so there are 3 walks of length 3 from vertex 1 to vertex 2
GDC: Matrix Powers
TI-84 Plus CE
Enter adjacency matrix in [A]: [2ND][x⁻¹] (MATRIX) → Edit
Calculate: [A]^3 [ENTER] → read entry (1,2)
TI-Nspire CX II
Define: a := [[0,1,1][1,0,1][1,1,0]]
Calculate: a^3 → read entry (1,2)
Casio fx-CG50
Enter matrix in Mat A: [MENU] → Run-Matrix
Calculate: Mat A ^ 3 [EXE] → read entry (1,2)
Weighted adjacency table
A square table where entry \( (i,j) \) = the weight (cost/distance) of edge \( i\!-\!j \), with “–” or \( \infty \) where there is no edge.
This is the usual input for Prim’s algorithm and TSP nearest-neighbour — Prim’s reads naturally off this table.
An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that starts and ends at the same vertex.
Euler circuit exists if:
Every vertex has even degree
(and graph is connected)
Euler trail exists if:
Exactly 2 vertices have odd degree
Trail starts/ends at the odd-degree vertices
✗
Common error: Confusing Euler (every \( edge \) once) with Hamilton (every \( vertex \) once). Remember: Euler = Edges.
5
Hamiltonian Paths & Cycles
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to the start.
▶
No simple test: Unlike Euler, there is no quick rule to determine if a Hamiltonian path/cycle exists. You must search by trial. The IB only tests small graphs where this is feasible.
Common error: The nearest neighbour does NOT guarantee the optimal route. It is a greedy heuristic. Starting from different vertices may give different (better or worse) results.
8
Chinese Postman Problem
Find the shortest route that traverses every edge at least once and returns to the start. (Think: a postman delivering to every street.)
Algorithm
1. Identify all vertices with odd degree 2. Find the shortest pairings of odd vertices 3. Add these “extra” edges (repeat them) to make all degrees even 4. Total distance = sum of all edges + repeated edges
▶
If all vertices have even degree: the graph already has an Euler circuit. No extra edges needed — total distance = sum of all edge weights.
✗
Common error: With 4 odd vertices (A, B, C, D), there are 3 possible pairings: {AB+CD}, {AC+BD}, {AD+BC}. You must check all three and pick the minimum total. Do not just pick the first pairing.
For a strongly-connected graph (every vertex reachable from every other), you can build a transition matrix \( T \) describing a random walk along the edges.
Constructing \( T \)
Divide each adjacency-matrix entry by the (out-)degree of its column vertex, so each column sums to 1.
Entry \( T_{ij} \) = probability of moving from \( j \) to \( i \) along a randomly chosen available edge. A vertex of out-degree 3 gives column entries of \( \tfrac{1}{3} \) to each neighbour.
Mini-example
From vertex \( A \) there are edges to \( B \), \( C \) and \( D \). Build column \( A \) of \( T \).
Out-degree of \( A = 3 \), so each available move has probability \( \tfrac{1}{3} \)
Answer: column \( A = \left(0, \tfrac{1}{3}, \tfrac{1}{3}, \tfrac{1}{3}\right)^{\mathsf T} \) (entries for \( A,B,C,D \))
▶
Steady state lives elsewhere: long-term Markov-chain analysis (solving \( T\mathbf{s} = \mathbf{s} \), powers \( T^n \), eigenvector with eigenvalue 1) is Statistics topic 4.19 — see the Vectors & Matrices sheet.
✗
Common error: Columns (not rows) of a transition matrix must sum to 1 — divide by the column vertex’s out-degree, not the row vertex’s.
10
Exam Traps & Key Reminders
✗
Show your working. For algorithms (Kruskal, Prim, nearest neighbour), list each step clearly. The IB awards marks for the process, not just the answer.
▶
TSP bounds: Always state both upper and lower bounds. The optimal solution lies between them. If they are equal, you have found the optimal route.
▶
Quick checks: A tree with \( n \) vertices has exactly \( n - 1 \) edges. A complete graph K\( n \) has \( n(n-1)/2 \) edges. There is always an even number of odd-degree vertices.
▶
Formula booklet: The adjacency-matrix walk result is given. The algorithms (Kruskal, Prim, nearest neighbour, Chinese postman) are NOT in the booklet — learn the steps.
Confirm Action
This website uses essential cookies for authentication and security. We respect your privacy and comply with GDPR.
By continuing, you accept our Privacy Policy.
Cookie details
Cookie Information
Essential Cookies
JMaths uses only essential cookies required for the platform to function properly:
Session Cookies
Keep you logged in while using the platform. Deleted when you close your browser.
CSRF Protection
Prevent cross-site request forgery attacks for your security.
Performance Cache
Help load pages faster by storing temporary data.
Privacy-Friendly Analytics
Plausible Analytics
We use Plausible, a privacy-first analytics tool that doesn't use cookies and doesn't collect any personal information. It only tracks anonymous page visits to help improve the platform.
Privacy First: Our analytics are fully GDPR, COPPA, and FERPA compliant. No personal data is collected, and no cookies are used for tracking. We do not use advertising or third-party tracking cookies.
Managing Cookies
You can control cookies through your browser settings, but disabling essential cookies
may prevent the platform from working correctly. For educational use, we recommend
keeping these essential cookies enabled.