This note introduces graphs made of vertices and edges, the vocabulary used to describe them, and how to store a graph as an adjacency matrix. Powers of that matrix count walks, which gives a quick way to answer questions about routes in networks such as roads, flights or computer links.
Key ideas
A graph is a set of vertices (points) joined by edges (lines). Two vertices joined by an edge are adjacent. Graphs model networks: towns and roads, people and friendships, airports and flights.
- Degree. The degree of a vertex is the number of edges meeting it. The sum of all degrees is twice the number of edges, because each edge has two ends. So the sum of the degrees is always even.
- Simple graph. No loops (an edge from a vertex to itself) and no more than one edge between the same pair of vertices.
- Complete graph. Every pair of vertices is joined by exactly one edge. With \( n \) vertices it has \( \dfrac{n(n-1)}{2} \) edges.
- Connected graph. There is a path between every pair of vertices.
- Subgraph. A graph formed from some of the vertices and some of the edges of a larger graph.
- Directed graph. Each edge has a direction, shown by an arrow. For a vertex, the out-degree counts edges leaving it and the in-degree counts edges arriving.
- Weighted graph. Each edge has a number attached, such as a distance, cost or time.
- Tree. A connected graph with no cycles. A tree with \( n \) vertices has exactly \( n-1 \) edges.
Routes through a graph. A walk is a sequence of edges where each edge starts where the last one ended; edges and vertices can repeat. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A circuit is a trail that starts and ends at the same vertex. A cycle is a circuit with no other repeated vertex. The length of a walk is the number of edges in it.
Adjacency matrices. For a graph with \( n \) vertices, list the vertices in the same order along the rows and columns. The entry in row \( i \), column \( j \) is the number of edges from vertex \( i \) to vertex \( j \). For an undirected graph the matrix is symmetric, and each row sum is the degree of that vertex. For a directed graph, row sums give out-degrees and column sums give in-degrees. For a weighted graph, you can enter the weight of each edge in place of 1; this is sometimes called a weighted adjacency matrix.
Counting walks. If \( \mathbf{M} \) is the adjacency matrix, the entry in row \( i \), column \( j \) of \( \mathbf{M}^k \) is the number of different walks of length \( k \) from vertex \( i \) to vertex \( j \). Use the matrix power function on your GDC.
Definitions and formulae
| Term or formula | Meaning / when to use |
|---|---|
| \( \sum \deg(v) = 2e \) | Sum of degrees equals twice the number of edges \( e \). Use it to check a graph is possible. |
| \( \dfrac{n(n-1)}{2} \) | Number of edges in a complete graph on \( n \) vertices. |
| \( e = n - 1 \) | Number of edges in a tree with \( n \) vertices. |
| Adjacency matrix \( \mathbf{M} \) | Entry \( m_{ij} \) = number of edges from vertex \( i \) to vertex \( j \). |
| \( (\mathbf{M}^k)_{ij} \) | Number of walks of length \( k \) from vertex \( i \) to vertex \( j \). |
| Walk, trail, path | Repeats allowed / no repeated edge / no repeated vertex. |
| Circuit, cycle | Closed trail / closed trail with no other repeated vertex. |
Worked examples
Example 1 A network of five relay stations \( A, B, C, D, E \) has links \( AB, AC, BC, CD, CE, DE \). (a) Write the adjacency matrix and the degree of each vertex. (b) Find the number of walks of length 3 from \( A \) to \( D \), and list them.
(a) With the order \( A, B, C, D, E \), put 1 where two stations are linked:
\( \mathbf{M} = \begin{pmatrix} 0&1&1&0&0 \\ 1&0&1&0&0 \\ 1&1&0&1&1 \\ 0&0&1&0&1 \\ 0&0&1&1&0 \end{pmatrix} \).
Row sums give the degrees: \( A:2,\ B:2,\ C:4,\ D:2,\ E:2 \). The total is 12, which is twice the 6 edges.
(b) On your GDC, calculate \( \mathbf{M}^3 \). The entry in row \( A \), column \( D \) is 2.
The two walks are \( A\to B\to C\to D \) and \( A\to C\to E\to D \).
Answer: degrees \( 2, 2, 4, 2, 2 \); there are 2 walks of length 3 from \( A \) to \( D \).
Example 2 A one-way system between four junctions \( P, Q, R, S \) has directed edges \( P\to Q,\ P\to R,\ Q\to R,\ R\to P,\ R\to S,\ S\to Q \). (a) Write the adjacency matrix. (b) Find the out-degree of \( R \) and the in-degree of \( Q \). (c) How many walks of length 3 go from \( P \) to \( S \)?
(a) Rows are the starting vertex and columns the ending vertex:
\( \mathbf{N} = \begin{pmatrix} 0&1&1&0 \\ 0&0&1&0 \\ 1&0&0&1 \\ 0&1&0&0 \end{pmatrix} \).
(b) Out-degree of \( R \) is the sum of row \( R \): \( 1 + 0 + 0 + 1 = 2 \). In-degree of \( Q \) is the sum of column \( Q \): \( 1 + 0 + 0 + 1 = 2 \).
(c) Compute \( \mathbf{N}^3 \) on your GDC. The entry in row \( P \), column \( S \) is 1.
The single walk is \( P\to Q\to R\to S \). Check: \( P\to R\to P\to\ ? \) cannot end at \( S \), since \( P \) has no edge to \( S \).
Answer: out-degree of \( R \) is 2; in-degree of \( Q \) is 2; exactly 1 walk of length 3 from \( P \) to \( S \).
Example 3 Four towns \( A, B, C, D \) have a weighted adjacency matrix of road lengths in km: \( \begin{pmatrix} 0&3&0&2 \\ 3&0&4&0 \\ 0&4&0&5 \\ 2&0&5&0 \end{pmatrix} \), where 0 means no direct road. (a) State which roads exist. (b) Find the length of the walk \( A\to B\to C\to D \). (c) Is this graph a tree? Is it complete?
(a) Non-zero entries above the diagonal: \( AB = 3,\ AD = 2,\ BC = 4,\ CD = 5 \). The matrix is symmetric, so each road works both ways.
(b) \( AB + BC + CD = 3 + 4 + 5 = 12 \) km.
(c) There are 4 vertices and 4 edges. A tree on 4 vertices would have only 3 edges. Indeed the edges form a cycle \( A\to B\to C\to D\to A \). So it is not a tree. A complete graph on 4 vertices has \( \frac{4 \times 3}{2} = 6 \) edges, so it is not complete either (there is no direct road \( AC \) or \( BD \)).
Answer: roads \( AB, AD, BC, CD \); walk length 12 km; neither a tree nor complete.
Common errors
- Common error: mixing up walk, trail and path. A path cannot repeat a vertex; a walk can repeat both vertices and edges.
- Common error: reading a directed adjacency matrix the wrong way round. Rows are where an edge starts and columns are where it ends.
- Common error: using \( \mathbf{M} \times k \) instead of \( \mathbf{M}^k \). To count walks of length \( k \), multiply the matrix by itself \( k \) times.
- Common error: using different vertex orders for rows and columns, which makes the matrix meaningless.
- Common error: claiming a graph is a tree because it is connected. A tree must also have no cycles.
Exam tip: When you use a matrix power, name the matrix, state the power, and say which row and column you read. Listing the walks as a check is quick when the number is small.
Check yourself
- How many edges does a complete graph on 6 vertices have?
Answer
\( \dfrac{6 \times 5}{2} = 15 \). - Can a simple graph have five vertices with degrees \( 3, 3, 2, 2, 1 \)?
Answer
The degrees sum to 11, which is odd. The sum must equal twice the number of edges, so it must be even. Not possible. - A tree has 8 vertices. How many edges does it have?
Answer
A tree with \( n \) vertices has \( n - 1 \) edges, so 7. - The complete graph on 4 vertices has adjacency matrix \( \mathbf{J} \) with 0 on the diagonal and 1 elsewhere. Use \( \mathbf{J}^3 \) to find the number of walks of length 3 from a vertex back to itself, and then check your answer by counting the walks directly.
Answer
\( \mathbf{J}^3 \) has diagonal entries 6. Check: from vertex \( v \) go to one of 3 other vertices, then to one of the 2 vertices that are neither \( v \) nor the one you are on, then back to \( v \): \( 3 \times 2 = 6 \).