Edges with a direction
A directed graph gives every edge a direction, drawn as an arrow. A directed edge is often called an arc, and it can be followed only the way its arrow points, like a one-way street.
The graph below has four vertices and five arrows: A to B, B to D, D to C, C to A and B to C. The arrow between B and C lets a route go from B to C, but not from C to B.
Five arrows: A to B, B to D, D to C, C to A and B to C.
In-degree and out-degree
In a directed graph each vertex has two degrees. The in-degree counts the arrows arriving at it, and the out-degree counts the arrows leaving it. One arrow arrives at B, from A, and two leave it, to D and to C, so B has in-degree 1 and out-degree 2.
Count the same way at every vertex. A has in-degree 1 and out-degree 1, C has 2 and 1, and D has 1 and 1. The in-degrees add to 1 + 1 + 2 + 1 = 5, and the out-degrees add to 1 + 2 + 1 + 1 = 5, the number of arrows.
Both totals always equal the number of arrows, because every arrow leaves exactly one vertex and arrives at exactly one: it adds 1 to one out-degree and 1 to one in-degree. Together the two totals make 5 + 5 = 10 = 2 × 5, the handshake count for the same graph with its arrows taken off.
Beside each vertex, its in-degree and then its out-degree. The in-degrees add to 5 and so do the out-degrees, one for each arrow.
Strongly connected
In a directed graph a route must follow the arrows. The graph is strongly connected when, for every pair of vertices, a route along the arrows runs from the first to the second, and another runs back from the second to the first.
Here the arrows A to B, B to D, D to C and C to A make a closed route through all four vertices. Going round it, any vertex reaches any other: from D, the route D-C-A-B reaches C, A and B in turn. So the graph is strongly connected. The fifth arrow, from B to C, is a shortcut that is not needed.
The gold arrows run A-B-D-C-A, through every vertex and back to the start, so each vertex reaches every other along them.
One arrow turned round
Turn the arrow from C to A round, so that it runs from A to C. Now no arrow arrives at A. Its in-degree is 0, so no route from another vertex can reach it, and the graph is no longer strongly connected.
C has lost its only way out as well: its in-degree is now 3 and its out-degree 0, so a route that reaches C stops there. Following the arrows from each vertex, A reaches B, C and D; B reaches C and D; D reaches only C; and C reaches nothing.
With the arrows ignored, the four vertices are still joined, so the graph is connected in the ordinary sense. Strongly connected asks for more: every vertex reached from every other, along the arrows.
The gold arrow now runs from A to C. No arrow arrives at A, and no arrow leaves C.
What the degrees can and cannot tell
In a graph with more than one vertex, a vertex with in-degree 0 can never be reached, and a vertex with out-degree 0 can never be left. Either one settles the question: the graph is not strongly connected.
The reverse is not true. In the graph below, arrows run both ways between P and Q and both ways between R and S, and one arrow runs from Q to R. Every vertex has at least one arrow in and one out: P has 1 and 1, Q 1 and 2, R 2 and 1, S 1 and 1. Yet from R the arrows lead only to S and back, so nothing reaches P or Q from R or S. The degrees can rule strong connectedness out, but only following the routes can confirm it.
One more arrow, from S to P, mends it. From R, the route R-S-P-Q now reaches P and Q, and P and Q already reached R and S through the arrow from Q to R.
Every vertex has an arrow in and an arrow out, but without the dashed arrow nothing leads from R or S back to P or Q. The dashed gold arrow from S to P makes the graph strongly connected.
The usual mistakes
Counting every arrow that touches a vertex. Three arrows touch B, but only 1 arrives, so its in-degree is 1, and 2 leave, so its out-degree is 2.
Giving the out-degree when the in-degree is asked for, or the other way round. Arrows pointing at the vertex count toward the in-degree.
Ignoring the arrows. With the arrow from A to C, the graph is still in one piece, but no route along the arrows reaches A.
Deciding that a graph is strongly connected because every vertex can reach one particular vertex. A route is needed in each direction, between every pair.
One-way streets and a league
In the first application below, one-way streets between junctions make a directed graph, and a junction with out-degree 0 is a dead end. In the second, each game of a league is an arrow from the winner to the loser, so a player’s wins are an out-degree, and the out-degrees add to the number of games.
Worked example: One-Way Streets Between Five Junctions in an Old Town Center, and Which Street to Reverse
Question The old center of a town has five junctions, A, B, C, D and E, joined by six one-way streets: from A to B, from B to C, from C to A, from C to D, from D to E, and from B to E. (a) Can a driver get from every junction to every other junction? Give the count that settles it. (b) The council will reverse the direction of exactly one street. Which street, reversed, lets a driver get from every junction to every other?
1.Model the streets as a directed graph: a vertex for each junction and an arc for each street, pointing the way traffic flows. Every junction reaching every other is what it means for the graph to be strongly connected.
Each junction is a vertex and each street an arc, pointing the way traffic flows. 2.Find each junction's out-degree, the number of arcs leaving it: A 1, B 2, C 2, D 1 and E 0.
The out-degree of a junction counts the streets leaving it. E has out-degree 0. 3.(a) No. Junction E has out-degree 0, so a driver at E cannot leave it, and the graph is not strongly connected.
(a) No: a driver at E cannot leave it, so the graph is not strongly connected. 4.The reversed street must give E an arc out, or E stays a dead end, so it must be one of the two streets into E: D to E or B to E. Reversing D to E would leave D with no arc out, since D's only street led to E. That leaves B to E.
A reversal must give E an arc out: D to E or B to E. Reversing D to E makes D the dead end. 5.Reverse B to E, so that it runs from E to B. The arcs A to B, B to C and C to A form a cycle, and so do B to C, C to D, D to E and E to B. The two cycles share B and C, so every junction can reach every other.
With B to E reversed, two cycles share B and C, so every junction reaches every other. 6.(b) Reverse the street from B to E. Check: from E the route E, B, C, A reaches A, and from A the route A, B, C, D, E reaches E.
(b) Reverse the street from B to E.
Answer: (a) No: junction E has out-degree 0, so no street leaves it; (b) the street from B to E, which then runs from E to B; no other of the 6 streets works
Common mistakes
- Reversing the street from C to D because it is the only street from the cycle A, B, C to D. After that reversal no arc leads into D, so no driver can reach D, and E is still a dead end.
- Deciding that the town is fine because every junction can reach E. Strong connectedness needs a route in each direction between every pair of junctions, and no route leads out of E.
More graphs, degree and trees problems, worked step by step →
Worked example: A Table-Tennis League's Results Table with One Line Smudged, and Whom the Last Player Beat
Question Five players, Ana, Ben, Cal, Dee and Eve, each play every other player once in a table-tennis league, and every game has a winner. The results table shows that Ana won 3 games, Ben 3, Cal 2 and Dee 1, but Eve's line is smudged. (a) How many games did Eve win? (b) Ben lost only to Ana, Cal lost only to Ana and Ben, and Dee's one win was against Eve. Whom did Eve beat?
1.Model the league as a directed graph: a vertex for each player and an arc from the winner to the loser of each game. Every pair plays once, so every pair of vertices is joined by exactly one arc. A player's wins are the out-degree of their vertex.
Each player is a vertex, and every pair plays once: an arc will run from the winner to the loser. 2.There are 5 × 42 = 10 games, one for each edge of K5, and each game gives exactly one win, so the out-degrees add up to 10.
There are 5 × 42 = 10 games and each gives one win, so the out-degrees add up to 10. 3.(a) Eve won 10 − (3 + 3 + 2 + 1) = 10 − 9 = 1 game.
(a) Eve won 10 − 9 = 1 game. 4.Draw the arcs that are given. Ben lost only to Ana, so Ben beat Cal, Dee and Eve. Cal lost only to Ana and Ben, so Cal beat Dee and Eve. Dee's one win was against Eve, so Dee lost to Ana, Ben and Cal.
The given results fix every arc except the one between Ana and Eve. 5.Eve has now lost to Ben, Cal and Dee. Her only other game is against Ana, and she won 1 game, so she won that one.
Eve lost to Ben, Cal and Dee, so her one win came in her game with Ana. 6.(b) Eve beat Ana. Check: Ana then beat Ben, Cal and Dee and lost to Eve, which gives Ana her 3 wins.
(b) Eve beat Ana.
Answer: (a) 1 game; (b) Ana
Common mistakes
- Adding the known wins, 3 + 3 + 2 + 1 = 9, and guessing that Eve won none. Each of the 10 games gives one win, so the wins must add up to 10.
- Taking 5 × 4 = 20 as the number of games. That counts each game once for each of its two players, so the number of games is half of it.
More graphs, degree and trees problems, worked step by step →