A graph as a table
A graph records only which pairs of vertices are joined, and that fits in a table. Give the table one row and one column for each vertex, and in row X, column Y write the number of edges joining X and Y. When no pair is joined twice, that is 1 where a pair is joined and 0 where it is not. This is the adjacency table.
The graph below has a triangle ABC and a fourth vertex D, joined only to C. Its rows read A: 0, 1, 1, 0; B: 1, 0, 1, 0; C: 1, 1, 0, 1; and D: 0, 0, 1, 0.
A triangle ABC, with D joined only to C: four edges.
Filling one row
To fill row A, look at the edges that meet A: AB and AC. So columns B and C get 1, and columns A and D get 0. Row A, column B holds 1 because the edge AB is there, and row A, column D holds 0 because no edge joins A and D.
The 0 in row A, column A says that A is not joined to itself. With no loops, every entry on the main diagonal, from the top left to the bottom right, is 0.
Row A, column B holds 1, because the edge AB is there.
The matrix
Take the labels off and the numbers stand alone, in brackets: the adjacency matrix. The order of the vertices, here A, B, C, D, has to be agreed beforehand, because the matrix no longer says which row belongs to which vertex. The rows and the columns always use the same order.
The matrix is usually called A, which is also the name of a vertex here. Row A always means the row of the vertex A.
Symmetric across the diagonal
An edge joins its two vertices both ways at once, so the edge AC puts a 1 in row A, column C and another in row C, column A. Every entry matches its mirror image across the main diagonal, and the matrix is symmetric.
Each edge appears twice, once on each side of the diagonal, so this matrix holds eight 1s for its 4 edges.
The adjacency matrix with its main diagonal struck through. Every entry on the diagonal is 0, and the entries on either side mirror each other.
each edge sets aᵢⱼ = aⱼᵢ = 1, so A equals its own transpose
Add edges until the table holds six 1s
With 4 edges, AB, BC, CD and AC, the instrument draws the same graph, turned, and its table holds eight 1s. Each new edge lights two cells, one on each side of the diagonal.
Row totals are degrees
Row C is 1, 1, 0, 1, which adds to 3. C is joined to A, B and D, so its degree is 3. A row total counts the edges meeting that vertex, so it is the vertex’s degree.
The rows add to 2, 2, 3 and 1, the degrees of A, B, C and D. All the entries together add to 2 + 2 + 3 + 1 = 8, twice the 4 edges, which is the handshake lemma read off the table. So the number of edges is half the total of the entries. Because the matrix is symmetric, each column total is a degree too.
Row C adds to 1 + 1 + 0 + 1 = 3, the degree of C.
Two edges, and loops
When two separate edges join the same pair, the entry is 2: the matrix counts edges, not just whether a pair is joined. In the graph below, two edges join B and C, so row B, column C holds 2, and so does row C, column B.
A loop, an edge from a vertex back to itself, goes on the diagonal, and conventions differ on how to enter it. In the first application below a loop is entered once, as a 1. A loop adds 2 to its vertex’s degree, so under that convention a row with a loop adds to 1 less than the degree. In the graph below, A has the loop and the edge AB, so its degree is 2 + 1 = 3, while row A adds to 1 + 1 + 0 = 2.
A loop at A, one edge from A to B, and two edges from B to C.
Its matrix, with rows and columns in the order A, B, C and the loop entered once. Row B, column C, in gold, holds 2 for the two edges from B to C.
Directed graphs
In a directed graph, row X, column Y counts only the arrows from X to Y. An arrow from A to B puts a 1 in row A, column B and nothing in row B, column A, so the matrix is not symmetric. A row total is then an out-degree, the arrows leaving that vertex, and a column total is an in-degree, the arrows arriving.
For the arrows A to B, B to D, D to C, C to A and B to C, the rows read A: 0, 1, 0, 0; B: 0, 0, 1, 1; C: 1, 0, 0, 0; and D: 0, 0, 1, 0. The rows add to 1, 2, 1 and 1, the out-degrees, and the columns add to 1, 1, 2 and 1, the in-degrees.
The matrix of the directed graph A to B, B to D, D to C, C to A and B to C. Column C, in gold, adds to 2: two arrows arrive at C, from B and from D.
The usual mistakes
Swapping 0 and 1. A 1 says the pair is joined; check the edges at the row’s vertex before writing either.
Writing 2 for a pair joined by one edge. A 2 means two separate edges.
Taking the number of edges in the whole graph as the degree of one vertex. The degree is that vertex’s row total: 3 for C, not 4.
Adding the whole table and calling it the number of edges. Each edge is entered twice, so the 8 in this table means 4 edges.
Reading the edges from one row. Row A adds to 2, which counts only the edges at A.
Signposts and a typing slip
In the first application below, a loop road is entered once on the diagonal, so the signpost at its junction needs more arms than the row adds to. In the second, a ranger’s matrix is not symmetric, which shows that one entry was typed wrongly, and the number of trails on the map decides which.
Worked example: Signposts at the Junctions of a Country Park, Read Off the Park's Road Matrix
Question The roads of a country park join four junctions, P, Q, R and S, and the park's map records them in a matrix. The entry in row X and column Y is the number of roads joining junction X directly to junction Y. A loop road, which leaves a junction and comes back to it without passing any other junction, is entered once, as a 1 in that junction's own row and column. With rows and columns in the order P, Q, R, S, the matrix is 0210201111120120. At every junction, a signpost has one arm for each way a driver can leave the junction along a road. (a) How many arms does the signpost at junction R need? (b) How many roads are there in the park?
1.Model the park as a graph: a vertex for each junction and an edge for each road. The signpost at a junction needs one arm for each road end there, so the number of arms is the degree of the vertex. The matrix is symmetric, because a road joining X to Y also joins Y to X.
Each junction is a vertex and each road an edge. The two roads between P and Q and the two between R and S are the 2s; the loop at R is the 1 on the diagonal. 2.Read row R, which is 1, 1, 1, 2. The entries off the diagonal say that R has 1 road to P, 1 road to Q and 2 roads to S, which gives 1 + 1 + 2 = 4 road ends. The 1 in column R is the loop road, and it has both of its ends at R.
Row R, off the diagonal: 1 + 1 + 2 = 4 road ends at R. 3.(a) The degree of R is 4 + 2 = 6, so the signpost at R needs 6 arms. Adding the row alone gives 5, one short, because the loop is entered once but a driver can leave along it in two directions.
(a) The loop adds 2 ends, so R has degree 4 + 2 = 6: the signpost needs 6 arms. 4.For the number of roads, add the entries off the diagonal, row by row: 3 + 4 + 4 + 3 = 14. Each road between two different junctions appears twice in this total, once in the row of each of its junctions, so there are 14 ÷ 2 = 7 such roads.
The entries off the diagonal add up to 14, and each road between two junctions is counted twice: 14 ÷ 2 = 7. 5.(b) The diagonal holds one loop, entered once, so the park has 7 + 1 = 8 roads. Check: the degrees are 3, 4, 6 and 3, which add up to 16 = 2 × 8, as they must, since every road has two ends.
(b) 7 + 1 = 8 roads, and the degrees add up to 16 = 2 × 8.
Answer: (a) 6 arms; (b) 8 roads
Common mistakes
- Taking the row total, 5, as the number of arms at R. The loop road is entered as a single 1, but a driver can set off along it in either direction, so it needs two arms.
- Halving the total of every entry in the matrix, 15 ÷ 2, which is not a whole number. The loop is entered once, not twice, so it has to be counted on its own and not halved.
Worked example: A Ranger's Matrix of Hiking Trails Between Five Huts, With One Entry Typed Wrongly
Question A park ranger types up the trails between five mountain huts, A, B, C, D and E, as a matrix. Every trail can be walked both ways and joins two different huts, and no two trails join the same pair. The entry in row X and column Y is 1 when a trail joins X and Y, and 0 otherwise. With rows and columns in the order A, B, C, D, E, the ranger's matrix is 0111010010100100110100010. Exactly one entry was typed wrongly, and the trail map shows 6 trails. (a) Which entry is wrong, and what should it be? (b) Which hut has the most trails, and how many?
1.Every trail runs both ways, so a correct matrix is symmetric across its main diagonal. Compare each entry above the diagonal with its mirror below it.
The ranger's matrix. A trail joins its two huts both ways, so each entry should equal its mirror across the diagonal. 2.Every pair of mirrored entries matches except the pair for A and D: row A, column D holds 1, but row D, column A holds 0. So one of these two entries is the wrong one.
Only one pair of mirrored entries disagrees: row A, column D and row D, column A. 3.Decide which with the number of trails. If A and D are joined, the trails are A–B, A–C, A–D, B–D, C–D and D–E, which makes 6. If they are not joined, there are only 5. The map shows 6, so the trail between A and D is there.
With the trail A–D the network has 6 trails, as the map shows; without it, only 5. 4.(a) The wrong entry is in row D, column A: it should be 1, not 0. Check: the corrected matrix has entries adding up to 12 = 2 × 6, while the typed one adds up to 11, an odd number, which the matrix of a trail network can never have.
(a) Row D, column A should be 1. The entries then add up to 12 = 2 × 6. 5.(b) The corrected row totals are A 3, B 2, C 2, D 4 and E 1. Hut D has the most trails, 4, to A, B, C and E. The typed matrix gave D only 3, level with A.
(b) Row D now adds up to 4, the most of any hut.
Answer: (a) Row D, column A: it should be 1, not 0; (b) hut D, with 4 trails
Common mistakes
- Changing row A, column D to 0 because the 0 in row D looks like the entry that fits. Either of the two entries could be the slip; only the 6 trails on the map show which one it is.
- Reading the degrees from the typed matrix, which puts A and D level on 3 trails. The wrong entry is in row D, so row D has to be corrected before its total means anything.