Counting Arcs at a Vertex
In an undirected graph, an edge joins two vertices without distinguishing their roles. A directed graph records a direction on each edge, so an arc has a tail, where it starts, and a head, where it ends. This gives two different counts at each vertex: the number of arcs that arrive there and the number that leave. Keeping these counts separate is essential when describing directed networks, such as one-way routes or directed communication links.
Throughout, a directed graph has a finite vertex set \(V\) and an arc set \(A\). Each arc has a specified tail and head. Unless a graph is explicitly called a directed multigraph, assume there are no loops or parallel arcs. In a directed multigraph, arcs are treated as distinct objects even if they have the same tail and head. A loop is an arc whose tail and head are the same vertex.
In an arc written \(u\to v\), the tail is \(u\) and the head is \(v\). Thus this arc contributes one to the out-degree of \(u\) and one to the in-degree of \(v\). It makes no contribution to the in-degree of \(u\) or the out-degree of \(v\), unless \(u=v\), in which case it is a loop and contributes to both degrees of that one vertex. A vertex with no incident arcs has in-degree and out-degree both equal to zero.
When recording counts, an arc list should preserve every arc. In a directed multigraph, listing \(p\to q\) twice means that there are two distinct arcs from \(p\) to \(q\); they both count. This convention also makes the degree totals precise: the number of arcs, denoted \(|A|\), includes repeated arcs as separate objects.
Worked Counts from Arc Lists
Worked Example: A Directed Graph with No Loops
Let \(G=(V,A)\) be the directed graph with \(V=\{a,b,c,d\}\) and arc set \(A=\{a\to b,\ a\to c,\ b\to c,\ c\to a,\ c\to d,\ d\to b\}\). Find the in-degree and out-degree of every vertex.
Read each arc once. The arcs leaving \(a\) are \(a\to b\) and \(a\to c\), so \(\deg^+(a)=2\). The only arc entering \(a\) is \(c\to a\), so \(\deg^-(a)=1\). The arcs leaving \(b\) consist of \(b\to c\), giving \(\deg^+(b)=1\); the arcs entering \(b\) are \(a\to b\) and \(d\to b\), giving \(\deg^-(b)=2\).
The arcs leaving \(c\) are \(c\to a\) and \(c\to d\), so \(\deg^+(c)=2\). The arcs entering \(c\) are \(a\to c\) and \(b\to c\), so \(\deg^-(c)=2\). Finally, \(d\) has one outgoing arc, \(d\to b\), and one incoming arc, \(c\to d\), so \(\deg^+(d)=1\) and \(\deg^-(d)=1\).
| Vertex | Incoming arcs | \(\deg^-\) | Outgoing arcs | \(\deg^+\) |
|---|---|---|---|---|
| \(a\) | \(c\to a\) | 1 | \(a\to b,\ a\to c\) | 2 |
| \(b\) | \(a\to b,\ d\to b\) | 2 | \(b\to c\) | 1 |
| \(c\) | \(a\to c,\ b\to c\) | 2 | \(c\to a,\ c\to d\) | 2 |
| \(d\) | \(c\to d\) | 1 | \(d\to b\) | 1 |
Check: There are \(6\) arcs in the list. Adding the displayed in-degrees gives \(1+2+2+1=6\), and adding the displayed out-degrees gives \(2+1+2+1=6\).
Worked Example: A Loop and Parallel Arcs
Let \(G=(V,A)\) be a directed multigraph with \(V=\{p,q,r\}\) and distinct arcs \(e_1:p\to q,\ e_2:p\to q,\ e_3:q\to q,\ e_4:r\to q,\ e_5:q\to r\). The arcs \(e_1\) and \(e_2\) are parallel, and \(e_3\) is a loop. Compute both degrees at each vertex.
At \(p\), no arc enters, while \(e_1\) and \(e_2\) leave. Therefore \(\deg^-(p)=0\) and \(\deg^+(p)=2\). At \(q\), the incoming arcs are \(e_1,e_2,e_3,e_4\), so \(\deg^-(q)=4\). The outgoing arcs are \(e_3,e_5\), so \(\deg^+(q)=2\). The loop \(e_3\) appears in both lists, once as an arc entering \(q\) and once as an arc leaving \(q\). At \(r\), \(e_5\) enters and \(e_4\) leaves, giving \(\deg^-(r)=1\) and \(\deg^+(r)=1\).
Check: The arc list contains \(5\) distinct arcs. The degree totals are \(0+4+1=5\) for in-degree and \(2+2+1=5\) for out-degree. The two parallel arcs have both been counted separately. The loop contributes one to each degree total, not two to either individual degree.
Worked Example: Including an Isolated Vertex
Let \(G=(V,A)\) have \(V=\{u,v,w,x\}\) and \(A=\{u\to v,\ v\to w,\ w\to u,\ u\to w\}\). The vertex \(x\) is isolated. Find the degrees, and identify any vertices with equal in-degree and out-degree.
At \(u\), the incoming arc is \(w\to u\), and the outgoing arcs are \(u\to v\) and \(u\to w\). Thus \(\deg^-(u)=1\) and \(\deg^+(u)=2\). At \(v\), the incoming arc is \(u\to v\) and the outgoing arc is \(v\to w\), so both degrees are \(1\). At \(w\), the incoming arcs are \(v\to w\) and \(u\to w\), while the outgoing arc is \(w\to u\); hence \(\deg^-(w)=2\) and \(\deg^+(w)=1\). No arc enters or leaves \(x\), so both its degrees are \(0\).
Therefore \(v\) and \(x\) have equal in-degree and out-degree. Check: The in-degree total is \(1+1+2+0=4\), the out-degree total is \(2+1+1+0=4\), and the arc list contains \(4\) arcs.
The Directed Degree-Sum Identities
The examples exhibit a general rule: every arc is counted once among all in-degrees and once among all out-degrees. This remains true when the graph has isolated vertices, loops, or parallel arcs, provided that parallel arcs are counted as distinct arcs.
Proof. Assume \(G\) is finite, and regard each arc as a distinct element of \(A\), with one specified tail and one specified head. For the in-degree sum, count pairs \((e,v)\) for which \(e\) is an arc with head \(v\). Counting these pairs by vertex gives \(\sum_{v\in V}\deg^-(v)\). Counting them by arc gives \(|A|\), because every arc has exactly one head. Thus \(\sum_{v\in V}\deg^-(v)=|A|\). For the out-degree sum, count pairs \((e,v)\) for which \(e\) has tail \(v\). Counting by vertex gives \(\sum_{v\in V}\deg^+(v)\), while counting by arc gives \(|A|\), because every arc has exactly one tail. Therefore \(\sum_{v\in V}\deg^+(v)=|A|\). These arguments include loops: a loop has one head and one tail, both at the same vertex. If \(A\) is empty, both sums are zero; if \(V\) is empty, then \(A\) is empty as well, and the same identities hold. \(\square\)
Proof. Add the two identities in the theorem. The left sides combine as \(\sum_{v\in V}(\deg^-(v)+\deg^+(v))\), and the right sides add to \(|A|+|A|=2|A|\). \(\square\)
The corollary does not mean that an arc has two heads or two tails. Each arc contributes one count at its head to the in-degree total and one count at its tail to the out-degree total. A loop has both endpoints at the same vertex, so it contributes \(2\) to that vertex's sum of in-degree and out-degree, but still contributes only \(1\) to each of the two separate global totals.
Reading the Counts Reliably
A useful way to avoid confusion is to process an arc list in two passes. For each arc \(u\to v\), add \(1\) to the out-degree count at \(u\), then add \(1\) to the in-degree count at \(v\). If \(u=v\), both updates apply to the same vertex, but to different counts. For a parallel arc, repeat the two updates for that distinct arc.
Write \(\deg^-(v)=0\) and \(\deg^+(v)=0\) for every vertex, including isolated vertices.
For every listed arc \(u\to v\), increase \(\deg^+(u)\) by \(1\) and \(\deg^-(v)\) by \(1\).
Add all in-degrees and all out-degrees separately. Each total must equal the number of listed arcs, counted with multiplicity.
This procedure computes the degrees because the definition of each degree is exactly a count of arcs with a specified head or tail. Each arc contributes once to the appropriate count at its head and once at its tail. The sum checks can reveal an omitted arc or a mistaken count, although matching totals alone do not guarantee that every individual vertex count is correct.
Common Mistakes
Reversing the direction of the count. For an arc \(a\to b\), the arc leaves \(a\), so it contributes to \(\deg^+(a)\); it enters \(b\), so it contributes to \(\deg^-(b)\). A common incorrect calculation is to add \(1\) to \(\deg^-(a)\) and \(\deg^+(b)\), as if the arc pointed from \(b\) to \(a\). The correction is to identify the tail and head before updating either count.
Counting a loop only once overall. If the arc is \(q\to q\), it contributes \(1\) to \(\deg^+(q)\) and \(1\) to \(\deg^-(q)\). It is incorrect to put it into only one of those counts. Conversely, it is also incorrect to count the loop twice in \(\deg^+(q)\) or twice in \(\deg^-(q)\): it has one tail and one head.
Ignoring repeated arcs. In a directed multigraph, two distinct arcs with the same ordered endpoints each contribute separately. If the list includes two arcs \(p\to q\), then they add \(2\) to \(\deg^+(p)\) and \(2\) to \(\deg^-(q)\), not \(1\). Finally, do not omit isolated vertices from a degree table: their two counts are both zero, and the degree-sum identities include every vertex.
Check Your Understanding
For each question, count arcs by their tails and heads, then use the degree-sum identities as a check.
- Let \(V=\{a,b,c\}\) and \(A=\{a\to b,\ b\to a,\ a\to c\}\). Find \(\deg^-(v)\) and \(\deg^+(v)\) for each vertex.
- A directed multigraph has vertices \(\{p,q\}\) and arcs \(p\to q,\ p\to q,\ q\to q\). Find the two degrees at each vertex and verify both degree totals.
- Explain why a loop at \(v\) contributes \(1\) to each of \(\deg^-(v)\) and \(\deg^+(v)\), rather than \(2\) to either one.
- A finite directed graph has \(9\) arcs. What are the sums of all its in-degrees and all its out-degrees? State the counting reason.
- Give an example of a vertex whose in-degree and out-degree are equal, and explain why equality of these two counts does not require the vertex to be isolated.