Degree, handshaking and parity
Count every edge end exactly once by its attached vertex. The general argument includes loops, parallel edges and disconnected graphs
- Count ends, not distinct neighbours Each ordinary edge contributes one end at each endpoint. A loop has both ends at its single endpoint, so it contributes two
- Double-count the same edge ends Counting by vertices gives the degree sum; counting by edges gives twice the edge count. Both count exactly the same finite collection \(\displaystyle \sum_{v\in V}\deg(v)=2|E|\)
- No connectedness assumption Separate components, parallel edges, loops and isolated vertices do not change the two-ends-per-edge count
- Read matrix degree with its convention When each loop is recorded once on the diagonal, row sum counts it once but degree counts it twice. Add the diagonal entry once more \(\displaystyle \deg(v_i)=\sum_j a_{ij}+a_{ii}\)
- Odd-degree vertices come in an even number The whole degree sum and the sum of all even degrees are even. The remaining sum of odd degrees is therefore even, which requires an even number of odd terms
Worked example
An undirected graph has vertices A, B, C and D. At A there is one loop, two parallel edges join A to B, and one edge joins A to C. The other vertex degrees are 3, 2 and 2, and the graph has 6 edges. Find the degree of A and verify the degree sum
- \(\displaystyle \deg(A)=2+1+1+1=5\)The loop contributes two and the three other attached edges contribute one each
- \(\displaystyle 5+3+2+2=12\)Add the four vertex degrees to obtain the degree sum
- \(\displaystyle 2\times6=12\)Twice the 6 edges is 12, so the degree sum is verified
Common mistakes
Difficulty levels
Questions about this topic
What is the degree of a vertex?+
It is the number of edge-ends attached to that vertex. A loop contributes two because both ends are attached there
Why does a loop add two to degree but one to the edge count?+
A loop is one edge, so it adds one to the number of edges. Its two ends are both attached to the same vertex, so it adds two to that vertex's degree
Why is the sum of degrees twice the number of edges?+
Every edge has two ends. Counting all attached ends therefore counts each edge twice, giving the degree-sum identity
Must the graph be connected?+
No. The edge-end count includes all components and gives zero for each isolated vertex
Is a row sum always the degree?+
Not with once-counted diagonal loops. Under this convention, add the diagonal entry to the row sum. Without loops, the row sum already equals degree
Does an even degree sum prove a proposed simple graph exists?+
No. It is necessary, not sufficient. For example, a simple graph with three vertices cannot have a vertex of degree 4, even though 4, 1, 1 sum to an even number
What is graded here?+
Numeric degree calculations and selected steps are graded. The complete handshaking/parity proof on paper is ungraded, and a correct computation does not establish independent proof attainment
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 11, VCE Units 1 & 2, Specialist Mathematics, chapter 2: Graph theory