Lesson 1: Graphs, vertices, edges and degree
Degrees in a graph with a loop and multiple edges
SkillsDegrees of verticesGraph vocabulary
Worked example
For the graph shown:
(a) find the degree of each vertex
(b) use the degrees to find the number of edges, then check by counting the edges.
Step 1: Count the edge-ends at P
Edges and meet , and so does the loop. The loop has both of its ends at , so it counts twice: .
The degree counts edge-ends. A loop starts and finishes at , so it brings two ends to .
Step 2: Count the edge-ends at Q, R and S
meets , the two edges to , and , so . meets the two edges to and , so . meets , and , so .
The two edges between Q and R are separate edges, so each one counts once at Q and once at R.
Step 3: Add the degrees
Step 4: Halve the total to get the number of edges
Every edge adds 2 to the total, one for each end, so there are edges.
Step 5: Check by counting
, (twice), , , and the loop at : 7 edges. ✓
Answer
, , and . The graph has 7 edges.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Count the edge-ends at each vertex; a loop adds 2.
Count each of a set of multiple edges separately.
Check: the sum of the degrees is twice the number of edges.
Watch out for
Counting the loop once gives and a total of 13. An odd total is a sure sign of a mistake.
Counting the two edges between Q and R as one edge.