Degree and the handshaking lemma
Master degree and the handshaking lemma in Year 11 VCE Specialist Mathematics. The degree of a vertex counts the edge-ends meeting it (a loop counts twice), and the handshaking lemma states that the degrees sum to twice the number of edges, \(\sum \deg = 2E\). 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 read degrees from a diagram, count edges from a degree sequence, find an unknown degree, and explain why the number of odd-degree vertices is always even — a result used throughout graph theory.
Theory
The degree of a vertex is the number of edge-ends meeting it, where a loop counts twice. The handshaking lemma says the sum of all vertex degrees equals twice the number of edges, \(\sum \deg = 2E\). In Year 11 Specialist Mathematics you use it to count edges, find an unknown degree, and explain why the number of odd-degree vertices is always even.
A graph is a set of vertices joined by edges. The degree of a vertex, written \(\deg(v)\), is the number of edge-ends that meet it — informally, how many edges “stick out” of that vertex.
Each ordinary edge has two ends, so it adds \(1\) to the degree of each of the two vertices it joins. A loop (an edge from a vertex back to itself) has both ends at the same vertex, so it adds \(2\) to that vertex's degree — a loop counts twice.
Writing every degree from largest to smallest gives the graph's degree sequence, for example \((3,2,2,1)\). A vertex is odd or even according to whether its degree is an odd or even number.
Because every edge contributes \(2\) to the total of all the degrees (one to each end, or both to a looped vertex), the sum of all the degrees is always even and equals twice the number of edges. This is the handshaking lemma, and it is the key tool for this subtopic.
The handshaking lemma links the degrees to the number of edges \(E\). Since every edge supplies exactly two edge-ends:
Rearranging gives the number of edges directly from the degree sum:
Two useful consequences follow. First, the degree sum \(2E\) is always even, so a list of numbers with an odd total can never be a degree sequence. Second, splitting the degrees into even and odd:
forces the sum of the odd degrees to be even, which is only possible when there is an even number of odd-degree vertices.
For special graphs the degree sum is quick to write down. In the complete graph \(K_n\) every vertex has degree \(n-1\); in an \(r\)-regular graph every one of the \(n\) vertices has degree \(r\):
Finding a degree, or using the handshaking lemma
- Read a degree off a diagram: count the edge-ends at the vertex, adding \(2\) for each loop and \(1\) for every ordinary edge.
- Form the degree sum: add the degrees of all the vertices — this total is \(\sum\deg\).
- Count edges: the handshaking lemma gives \(E = \tfrac{1}{2}\sum\deg\). If the sum is odd, no such graph exists.
- Find an unknown degree: if the number of edges is known, use \(\sum\deg = 2E\) and subtract the known degrees, \(d = 2E - (\text{known degrees})\).
- Check feasibility: a degree sequence is possible only if its sum is even; the number of odd entries must be even.
For a graph with degree sequence \((4,3,3,2,2)\), the sum is \(14\), so \(E = 14/2 = 7\) edges.
Count the edges meeting \(A\):
| \(\text{edges at } A\) | \(=\) | \(AB,\ AC,\ AD\) |
| \(\deg(A)\) | \(=\) | \(3\) |
The degree of \(A\) is \(\deg(A)=3\).
Separate the ordinary edges from the loop:
| \(\text{ordinary edges at } P\) | \(=\) | \(PQ,\ PR \ \Rightarrow\ 2\) |
| \(\text{loop at } P\) | \(=\) | \(\text{adds } 2\) |
| \(\deg(P)\) | \(=\) | \(2 + 2\) |
| \(=\) | \(4\) |
A loop adds \(2\), so \(\deg(P)=4\).
Add the degrees to get the degree sum:
| \(\sum \deg\) | \(=\) | \(4+3+3+2+2\) |
| \(=\) | \(14\) |
Halve it, using \(E = \tfrac{1}{2}\sum\deg\):
| \(E\) | \(=\) | \(\dfrac{14}{2}\) |
| \(=\) | \(7\) |
The graph has \(7\) edges.
The degree sum is \(2E\):
| \(\sum \deg\) | \(=\) | \(2 \times 8\) |
| \(=\) | \(16\) |
Subtract the four known degrees:
| \(d\) | \(=\) | \(16 - (4+3+3+2)\) |
| \(=\) | \(16 - 12\) | |
| \(=\) | \(4\) |
The unknown degree is \(d=4\).
The degree sum must equal \(2E\), so it must be even. Test each total:
| \(3+3+2+2+1\) | \(=\) | \(11 \ (\text{odd})\) |
| \(3+2+2+2+1\) | \(=\) | \(10 \ (\text{even})\) |
An odd total can never equal \(2E\), so the first sequence is impossible. The second has an even sum, giving \(E = 10/2 = 5\) edges, and its two odd entries \((3,1)\) form an even count of odd-degree vertices, as required.
\((3,3,2,2,1)\) has an odd sum, so it is impossible; \((3,2,2,2,1)\) is possible with \(5\) edges.
Read the degrees, then add them:
| \(\deg(A)=3,\ \deg(C)\) | \(=\) | \(3\) |
| \(\deg(B)=\deg(D)=\deg(E)\) | \(=\) | \(2\) |
| \(\sum \deg\) | \(=\) | \(3+3+2+2+2\) |
| \(=\) | \(12\) |
Apply the handshaking lemma \(\sum\deg = 2E\):
| \(2E\) | \(=\) | \(12\) |
| \(E\) | \(=\) | \(6\) |
Only \(A\) and \(C\) have odd degree \((3)\), so there are \(2\) odd-degree vertices — an even number, exactly as the handshaking lemma guarantees.
\(\sum\deg = 12\), \(E = 6\) edges, and \(2\) vertices have odd degree.
Common pitfalls
Frequently asked questions
What is the degree of a vertex?
It is the number of edge-ends meeting the vertex — each ordinary edge adds \(1\), and a loop adds \(2\) because both of its ends are at that vertex.
What is the handshaking lemma?
It states that the sum of all the vertex degrees equals twice the number of edges, \(\sum\deg = 2E\). Every edge has two ends, so it contributes \(2\) to the total of the degrees.
How do I find the number of edges from the degrees?
Add up all the degrees to get \(\sum\deg\), then halve it: \(E = \tfrac{1}{2}\sum\deg\). For degree sequence \((4,3,3,2,2)\) the sum is \(14\), so \(E = 7\).
How does a loop affect the degree?
A loop adds \(2\) to the degree of its vertex, since both of its ends are attached there. It counts as one edge, so it adds \(2\) to the degree sum and \(1\) to the edge count.
Why is the number of odd-degree vertices always even?
The degree sum \(2E\) is even. The even-degree vertices contribute an even amount, so the odd-degree vertices must also contribute an even amount — which is only possible if there is an even number of them.
How do I find an unknown degree in a graph?
Use \(\sum\deg = 2E\). If the number of edges is known, the missing degree is \(d = 2E - (\text{sum of the known degrees})\). For example, with \(8\) edges and known degrees \(4,3,3,2\), \(d = 16 - 12 = 4\).