Vertices and edges
A graph is a set of vertices joined by edges. A vertex is drawn as a dot or a small circle, and an edge as a line between two vertices. Only which vertices are joined matters: the lengths of the lines and the places of the dots carry no meaning.
The graph below has five vertices, A, B, C, D and E, and six edges: AB, AC, BC, BD, CD and DE. It could stand for five towns and the roads between them, or five people and which of them know each other.
The degree of a vertex
The degree of a vertex is the number of edge ends that meet it. When no edge joins a vertex to itself, that is the number of edges meeting it.
Three edges meet B: AB, BC and BD. So B has degree 3. The vertex itself is not counted, and edges elsewhere in the graph, such as DE, do not count toward B.
The three gold edges, AB, BC and BD, are the ones meeting B, so B has degree 3.
Every degree, and their total
Count at every vertex in the same way. A meets AB and AC, degree 2. C meets AC, BC and CD, degree 3. D meets BD, CD and DE, degree 3. E meets only DE, degree 1. With B, the degrees are 2, 3, 3, 3 and 1.
They add to 2 + 3 + 3 + 3 + 1 = 12, and the graph has 6 edges. The total is exactly twice the number of edges.
Each vertex carries its degree: 2, 3, 3, 3 and 1, which total 12 for the 6 edges.
Why the total is twice the edges
Every edge has two ends, and each end adds 1 to the degree of the vertex it meets. So each edge adds exactly 2 to the total of the degrees, 1 at each end. With m edges the degrees add to 2m. This is the handshake lemma: if people shake hands, the numbers of hands each person shook add to twice the number of handshakes.
Take the edge DE in the lesson’s graph. It adds 1 to the degree of D and 1 to the degree of E. Remove it, and D drops to 2, E drops to 0, the total drops from 12 to 10, and the edges drop from 6 to 5.
each edge contributes 1 to two vertices, so Σ deg(v) = 2|E|
Add edges until the sum of degrees is 10
Five vertices, each showing its degree. With 6 edges the degrees are 3, 2, 3, 2 and 2, and they total 12 = 2 × 6. Add or remove an edge and two degrees change by 1, so the total changes by 2.
Loops
An edge can join a vertex to itself. Such an edge is a loop, and both of its ends meet the same vertex, so a loop adds 2 to that vertex’s degree. The handshake lemma still holds, because a loop is still one edge with two ends.
In the graph below, P meets PQ, degree 1. Q meets PQ and QR, degree 2. R meets QR and the loop, which counts twice, so its degree is 1 + 2 = 3. The total is 1 + 2 + 3 = 6, twice the 3 edges.
R has a loop, in gold, and one ordinary edge, so its degree is 2 + 1 = 3. The degrees 1, 2 and 3 total 6, twice the 3 edges.
Odd degrees come in pairs
The degree total is always even, because it is twice a whole number. The even degrees add to an even number, so the odd degrees must also add to an even number, and that needs an even count of them. So every graph has an even number of vertices of odd degree.
In the lesson’s graph the odd degrees are at B, C, D and E: four vertices, an even number. It follows that a group of people in which exactly three shake an odd number of hands is impossible.
From degrees back to a graph
A list of degrees fixes the number of edges, even with no drawing. The list 3, 2, 2 and 1 adds to 8, so any graph with those degrees has 8 ÷ 2 = 4 edges. One such graph has edges AB, AC, AD and BC: A meets three of them, B and C two each, and D one.
The list 3, 3, 2 and 1 adds to 9, which is odd. No graph has those degrees, loops or not, because a degree total is always twice the number of edges.
A graph with degrees 3, 2, 2 and 1. They total 8, and there are 4 edges.
The usual mistakes
Counting the vertex itself. B meets 3 edges, so its degree is 3, not 4.
Taking the degree total as the number of edges. The degrees of the lesson’s graph total 12, but each edge was counted at both ends, so there are 6 edges.
Giving a loop 1. A loop meets its vertex at both ends and adds 2.
Accepting a list of degrees with an odd total. However reasonable each number looks, an odd total cannot be twice a whole number of edges.
Friendships and cables
In the first application below, each member of a club reports how many friends they have there, and the friendships are half the total. In the second, an even total is not enough: two routers joined to every other router force every router to have at least 2 cables.
Worked example: Friendships Reported by the Members of a Book Club, and Whether Another Club's Reports Can All Be True
Question Seven members of a book club, Ana, Ben, Cara, Dev, Eli, Fay and Gus, each say how many of the other six members they are friends with. A friendship always goes both ways. Ana says 4, Ben and Cara each say 3, and Dev, Eli, Fay and Gus each say 2. (a) How many friendships are there among the seven members? (b) The seven members of a second club give the counts 5, 4, 3, 3, 2, 2 and 2. Can all seven of these counts be correct? Give the total that settles it.
1.Model the club as a graph: a vertex for each member and an edge for each friendship. Each member's count is the degree of their vertex, so the degrees are 4, 3, 3, 2, 2, 2, 2.
One network that fits the counts: each member is a vertex, each friendship an edge, and each count is a degree. 2.Add the degrees: 4 + 3 + 3 + 2 + 2 + 2 + 2 = 18. Each friendship joins two members, so it is counted once by each of them and appears twice in this total.
The degrees add up to 18, and every edge is counted once at each of its two ends. 3.(a) The number of friendships is 18 ÷ 2 = 9. Check: the network in the figure fits every count and has 9 edges.
(a) 18 ÷ 2 = 9 friendships, the 9 edges drawn. 4.For the second club, add the counts in the same way: 5 + 4 + 3 + 3 + 2 + 2 + 2 = 21.
The second club's counts add up to 21. 5.(b) No. The degrees of any graph add up to twice the number of edges, which is an even number, and 21 is odd. Put another way, three members give an odd count, and a graph always has an even number of vertices of odd degree.
(b) No: 21 is odd, so it is not twice a whole number of friendships.
Answer: (a) 9 friendships; (b) no: the counts add up to 21, which is odd, but the degrees of a graph always add up to an even number
Common mistakes
- Taking 18 as the number of friendships. Ana's friendship with Ben appears in Ana's count and again in Ben's, so the total counts every friendship twice.
- Checking only that no count is more than 6. Each count is possible on its own; it is the total, 21, that cannot be twice a whole number of friendships.
More graphs, degree and trees problems, worked step by step →
Worked example: Cables Planned Between Six Routers in an Office, and Whether Each Plan Can Be Built
Question An engineer is planning cables between six routers, P, Q, R, S, U and V. Two routers are joined by at most one cable, and no cable joins a router to itself. Plan 1 gives the numbers of cables at the routers as P 5, Q 5, R 4, S 2, U 1 and V 1. Plan 2 gives P 5, Q 4, R 4, S 3, U 2 and V 2. (a) Can plan 1 be built? Give the count that decides it. (b) Can plan 2 be built, and if so, how many cables does it use?
1.Model the plan as a graph: a vertex for each router and an edge for each cable. At most one cable between two routers and none from a router to itself means the graph is simple, so a degree can be at most 5, the number of other routers.
Each router is a vertex and each cable an edge. The graph is simple, so no degree can exceed 5. 2.Plan 1 adds up to 5 + 5 + 4 + 2 + 1 + 1 = 18, which is even, so the handshake count alone does not rule it out. Look at the busiest routers instead. P has degree 5, so it is joined to every other router, and so is Q.
Plan 1 totals 18, an even number. P and Q, with degree 5, are each joined to every other router. 3.(a) No. U and V are each joined to both P and Q, so each has at least 2 cables, but plan 1 gives them 1 each. Plan 1 cannot be built.
(a) No: U and V would have at least 2 cables each, not 1. 4.Plan 2: P has degree 5, so join it to all the others, using 5 cables. The degrees still needed are Q 3, R 3, S 2, U 1 and V 1.
Plan 2: P takes its 5 cables first, one to every other router. 5.Join Q to R, S and U, using 3 cables. Still needed: R 2, S 1 and V 1. Join R to S and to V, using 2 cables. Every router now has its planned number.
Q takes 3 more cables and R takes 2, and every degree is met. 6.(b) Yes, plan 2 can be built, with 5 + 3 + 2 = 10 cables. Check: the degrees add up to 5 + 4 + 4 + 3 + 2 + 2 = 20, and 20 ÷ 2 = 10.
(b) Yes: plan 2 uses 10 cables.
Answer: (a) No: P and Q, with 5 cables each, are joined to every other router, so U and V would each have at least 2 cables, not 1; (b) yes, with 10 cables
Common mistakes
- Deciding that plan 1 works because its total, 18, is even. An even total is needed, but it is not enough: the two routers of degree 5 force every other router to have degree at least 2.
- Joining two routers twice, or a router to itself, to use up a spare degree. The cables form a simple graph, with at most one edge between two vertices and no loops.
More graphs, degree and trees problems, worked step by step →