Graphs, vertices, edges and adjacency matrices
Master graphs, vertices, edges and adjacency matrices in Year 11 VCE Specialist Mathematics. A graph is a set of vertices joined by edges, which you can record as a diagram, an edge list or an adjacency matrix. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Graph theory topic of Unit 1.
You will learn to move between the three representations, read the degree of a vertex as a row sum, handle multiple edges and loops, count edges as half the total of the matrix entries, and apply the handshaking lemma — the foundations of the graph theory that follows.
Theory
A graph is a set of vertices joined by edges. In Year 11 Specialist Mathematics you represent an undirected graph three equivalent ways — a diagram, an edge list and an adjacency matrix — and read the degree of each vertex and the number of edges from any of them. A loop adds \(2\) to a vertex's degree and \(2\) to the diagonal of the matrix.
A graph is a collection of vertices (points, also called nodes) together with edges that join pairs of vertices. In an undirected graph an edge has no direction: the edge \(AB\) is the same as \(BA\).
The degree of a vertex, written \(\deg(v)\), is the number of edge-ends meeting it. Two special features change how you count:
- Multiple edges (parallel edges): two or more edges joining the same pair of vertices. Each one is counted separately.
- A loop: an edge joining a vertex to itself. Both of its ends meet that vertex, so a single loop adds \(2\) to the degree.
A graph can be recorded in three equivalent ways:
- a diagram — vertices drawn as points, edges as lines (curved when parallel) and loops as small circles;
- an edge list — every edge written once as an unordered pair, e.g. \(\{AB,\ BC,\ CD\}\), a repeated pair recording a multiple edge;
- an adjacency matrix — a square array whose entry in row \(u\), column \(v\) is the number of edges joining \(u\) and \(v\).
For an undirected graph the adjacency matrix is symmetric (\(M_{uv}=M_{vu}\)). A multiple edge shows as a number greater than \(1\) off the diagonal; a loop shows as a \(2\) on the diagonal.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 2 | 0 | 0 |
| B | 2 | 0 | 1 | 0 |
| C | 0 | 1 | 2 | 1 |
| D | 0 | 0 | 1 | 0 |
Let \(M\) be the adjacency matrix of an undirected graph. The key facts follow straight from what each entry counts.
The degree of a vertex is the sum of the entries in its row (equivalently, its column):
Every edge contributes \(2\) to the total of all the entries (a non-loop edge fills two symmetric cells; a loop puts \(2\) in one diagonal cell), so the number of edges is half that total:
Because each edge is counted at both of its ends, the sum of all the vertex degrees is twice the number of edges — the handshaking lemma:
Moving between diagram, edge list and matrix
- List the vertices and fix an order (e.g. \(A,B,C,D\)); the matrix uses this order for both its rows and its columns.
- Read the edges. From a diagram, write each edge once as a pair; a curved pair of lines is a double edge, a small circle at a vertex is a loop.
- Fill the matrix. For each ordinary edge \(uv\) add \(1\) to cell \((u,v)\) and cell \((v,u)\); for a loop at \(v\) add \(2\) to the diagonal cell \((v,v)\).
- Reverse the process to draw a graph from a matrix: an off-diagonal entry \(k\) means \(k\) edges between those two vertices, and a diagonal \(2\) means a loop.
- Count from the matrix. A row sum is the degree of that vertex; half the grand total of all entries is the number of edges.
Always check with the handshaking lemma: the degrees should add to \(2E\). If they do not, a loop or a double edge has been miscounted.
List each edge once as an unordered pair, writing the repeated pair twice for the double edge \(A\!B\):
| \(\text{edge list}\) | \(=\) | \(\{AB,\ AB,\ BC,\ CD,\ DA\}\) |
Now count every edge, including each line of the double edge:
| \(AB\) | \(=\) | \(2 \ \text{(double edge)}\) |
| \(BC,\ CD,\ DA\) | \(=\) | \(3\) |
| \(E\) | \(=\) | \(2 + 3\) |
| \(=\) | \(5\) |
The edge list is \(\{AB, AB, BC, CD, DA\}\) and the graph has \(5\) edges.
Each square edge puts a \(1\) in two symmetric cells; the loop at \(A\) puts a \(2\) on the diagonal:
| \(AB=AD\) | \(=\) | \(1,\quad BC=CD = 1\) |
| \(A\!A\) | \(=\) | \(2 \quad(\text{loop at } A)\) |
Filling every cell (blank cells are \(0\)) gives:
| A | B | C | D | |
|---|---|---|---|---|
| A | 2 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
The adjacency matrix has diagonal entry \(2\) at \(A\) and \(1\)s for \(AB, BC, CD, DA\).
| A | B | C | D | |
|---|---|---|---|---|
| A | 2 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
The degree of \(A\) is the sum of the entries in row \(A\); the diagonal \(2\) is a loop and counts fully:
| \(\text{row } A\) | \(=\) | \((2,\ 1,\ 1,\ 0)\) |
| \(\deg(A)\) | \(=\) | \(2 + 1 + 1 + 0\) |
| \(=\) | \(4\) |
Add every entry of the matrix, then halve (each edge is counted twice):
| \(\text{row sums}\) | \(=\) | \(4,\ 2,\ 2,\ 2\) |
| \(\text{total}\) | \(=\) | \(4+2+2+2 = 10\) |
| \(E\) | \(=\) | \(\dfrac{10}{2} = 5\) |
Vertex \(A\) has degree \(4\) (including the loop), and the graph has \(5\) edges.
By the handshaking lemma the sum of the degrees equals twice the number of edges:
| \(\textstyle\sum \deg\) | \(=\) | \(2+3+3+4+4\) |
| \(=\) | \(16\) | |
| \(2E\) | \(=\) | \(16\) |
| \(E\) | \(=\) | \(\dfrac{16}{2} = 8\) |
The graph has \(8\) edges.
Common pitfalls
Frequently asked questions
What is the difference between a vertex and an edge?
A vertex is a point (node) of the graph; an edge is a connection joining two vertices. A graph is described by its set of vertices and the edges between them.
How do I find the degree of a vertex from an adjacency matrix?
The degree of a vertex is the sum of the entries in its row (or, equally, its column). A diagonal entry of \(2\) is a loop and is included in that sum.
How does a loop affect the degree and the matrix?
A loop joins a vertex to itself, so both of its ends meet that vertex: it adds \(2\) to the degree and appears as a \(2\) on the diagonal of the adjacency matrix.
How do I count the number of edges from an adjacency matrix?
Add every entry of the matrix and divide by \(2\), because each edge is counted at both of its ends. Equivalently, halve the sum of all the vertex degrees.
What is the handshaking lemma?
It states that the sum of all the vertex degrees equals twice the number of edges, \(\sum \deg(v)=2E\). It follows because every edge contributes to the degree of each of its two ends.
What does a multiple (parallel) edge look like in each representation?
In a diagram it is two or more curves joining the same pair of vertices; in an edge list the pair is repeated; in the adjacency matrix it is an off-diagonal entry greater than \(1\).