Lesson 1: Graphs, vertices, edges and degree
Using the sum of the degrees
SkillDegrees of vertices
Worked example
(a) A graph has 6 vertices and 9 edges. Five of the vertices have degrees 2, 3, 3, 4 and 4. Find the degree of the sixth vertex.
(b) Jordan says that a graph can have vertices of degrees 1, 2, 2, 3 and 3. Is Jordan right? Explain.
Step 1: Find the total of the degrees
The sum of the degrees is twice the number of edges: .
Each edge has two ends, and each end adds 1 to the degree of the vertex it meets.
Step 2: Subtract the known degrees
, so the sixth vertex has degree .
Step 3: Add Jordan's degrees
Step 4: Compare with the rule
The sum of the degrees of any graph is , an even number. 11 is odd, so no graph has these degrees. Jordan is wrong.
Another way to say it: every graph has an even number of odd vertices. Jordan's list has three odd degrees (1, 3 and 3).
Answer
(a) The sixth vertex has degree 2. (b) Jordan is wrong: the degrees add to 11, but the sum of the degrees of any graph is , which is even.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Sum of the degrees the number of edges.
Use it forwards (degrees → edges) or backwards (edges → a missing degree).
An odd total means the graph cannot exist.
Watch out for
Forgetting to double, and using 9 instead of 18 as the degree total.