From Edges to Arcs
An undirected edge records that two vertices are related, without distinguishing a first endpoint from a second. Many models need that distinction: a link may represent a one-way connection, a message sent from one person to another, or a task that must precede another. A directed graph, or digraph, records such relationships as ordered pairs. The order matters: the arc from \(u\) to \(v\) points from \(u\) toward \(v\), and does not by itself imply an arc back from \(v\) to \(u\).
Because arcs are ordered pairs, \(u\to v\) and \(v\to u\) are different arcs. A pair of opposite arcs between the same two vertices is sometimes called a reciprocal pair. By contrast, an undirected simple graph has edges that are unordered pairs and has no loops or multiple edges. Keeping these two descriptions distinct prevents ambiguity when counting degrees.
Thus an arc \(u\to v\) contributes one to \(d^+(u)\) and one to \(d^-(v)\). It contributes nothing to the in-degree of \(u\) or the out-degree of \(v\). A vertex can have zero in-degree, zero out-degree, or both. Degrees are counts, so a vertex with no incident arcs has both degrees equal to zero.
Counting Arcs by Their Tails and Heads
Proof. Count the arcs by their tails. Each arc in \(A\) has exactly one tail, so it is counted exactly once in the out-degree of a vertex. Therefore the sum of all out-degrees is \(|A|\). Counting the same arcs by their heads gives the in-degree identity, since each arc has exactly one head. Adding the two equalities gives the stated total-degree identity. This also covers \(A=\varnothing\): every degree is zero and all three quantities are zero. \(\square\)
The theorem is a useful audit for an arc list. If the out-degrees do not sum to the number of listed arcs, some arc has been omitted or counted more than once. The same check applies to in-degrees. The equality of the two sums does not mean that each vertex has equal in-degree and out-degree; it is a total over all vertices.
Worked Example: Reading an Arc List
Let \(D\) have vertex set \(V(D)=\{a,b,c,d\}\) and arc set \(A(D)=\{a\to b,a\to c,b\to c,c\to a,d\to c\}\). Find the in-degree and out-degree of every vertex.
Count arcs with each tail first. The arcs with tail \(a\) are \(a\to b\) and \(a\to c\), so \(d^+(a)=2\). The only arc with tail \(b\) is \(b\to c\), so \(d^+(b)=1\). The only arc with tail \(c\) is \(c\to a\), so \(d^+(c)=1\). The only arc with tail \(d\) is \(d\to c\), so \(d^+(d)=1\).
Now count arcs with each head. The only arc with head \(a\) is \(c\to a\), so \(d^-(a)=1\). The only arc with head \(b\) is \(a\to b\), so \(d^-(b)=1\). The arcs with head \(c\) are \(a\to c,b\to c,d\to c\), so \(d^-(c)=3\). No arc has head \(d\), so \(d^-(d)=0\).
| Vertex | \(d^-(v)\) | \(d^+(v)\) | Total degree |
|---|---|---|---|
| \(a\) | 1 | 2 | 3 |
| \(b\) | 1 | 1 | 2 |
| \(c\) | 3 | 1 | 4 |
| \(d\) | 0 | 1 | 1 |
Check: There are five arcs. The out-degree sum is \(2+1+1+1=5\), and the in-degree sum is \(1+1+3+0=5\). The total-degree sum is \(3+2+4+1=10=2\cdot5\), as required.
Orientations of Undirected Graphs
An orientation preserves which vertex pairs are adjacent, but assigns a direction to each such pair. If \(D\) is an orientation of \(G\), then every edge incident with \(v\) contributes exactly one to either \(d^+(v)\) or \(d^-(v)\). Therefore the undirected degree \(\deg_G(v)\) splits into the two directed degrees.
Proof. Fix a vertex \(v\). Each edge of \(G\) incident with \(v\) is assigned exactly one direction. If it points away from \(v\), it contributes one to \(d^+(v)\); if it points toward \(v\), it contributes one to \(d^-(v)\). It contributes to exactly one of these two counts. Edges not incident with \(v\) contribute to neither. Hence their sum is the number of edges incident with \(v\), namely \(\deg_G(v)\). For the total identities, each edge is oriented into exactly one arc. The directed handshaking identities give each of the in-degree and out-degree sums as the number of arcs, which is \(|E(G)|\). If \(G\) has no edges, both sums and \(|E(G)|\) are zero, so the result also holds in that case. \(\square\)
Worked Example: Orienting Every Edge
Let the undirected graph \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,13,23,24,34,45\}\). Orient its edges as \(1\to2,3\to1,2\to3,2\to4,4\to3,5\to4\). Calculate the directed degrees and compare them with the degrees in \(G\).
From the arc list, vertex \(1\) has one outgoing arc, \(1\to2\), and one incoming arc, \(3\to1\). Thus \(d^+(1)=1\), \(d^-(1)=1\). Vertex \(2\) has outgoing arcs \(2\to3,2\to4\) and incoming arc \(1\to2\), giving \(d^+(2)=2,d^-(2)=1\). Vertex \(3\) has outgoing arc \(3\to1\) and incoming arcs \(2\to3,4\to3\), giving \(d^+(3)=1,d^-(3)=2\). Vertex \(4\) has outgoing arc \(4\to3\) and incoming arcs \(2\to4,5\to4\), giving \(d^+(4)=1,d^-(4)=2\). Vertex \(5\) has outgoing arc \(5\to4\) and no incoming arcs, so \(d^+(5)=1,d^-(5)=0\).
The undirected degrees, counted from the edge list, are \(\deg_G(1)=2\), \(\deg_G(2)=3\), \(\deg_G(3)=3\), \(\deg_G(4)=3\), and \(\deg_G(5)=1\). The comparison is:
| Vertex | \(d^-(v)\) | \(d^+(v)\) | \(d^-(v)+d^+(v)\) | \(\deg_G(v)\) |
|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 2 |
| 2 | 1 | 2 | 3 | 3 |
| 3 | 2 | 1 | 3 | 3 |
| 4 | 2 | 1 | 3 | 3 |
| 5 | 0 | 1 | 1 | 1 |
Check: The six listed edges produce six arcs. The out-degrees sum to \(1+2+1+1+1=6\), and the in-degrees sum to \(1+1+2+2+0=6\). Independently, the undirected degree sum is \(2+3+3+3+1=12=2\cdot6\); each vertex’s two directed degrees add to its listed undirected degree.
Reciprocal Arcs Are Not an Orientation
A digraph need not be an orientation of its underlying undirected graph. To obtain the underlying graph, forget the directions and make \(uv\) an edge whenever at least one of \(u\to v\) and \(v\to u\) is present. If both are present, they still give just one undirected edge in this construction. This distinction matters: a reciprocal pair uses two arcs, not one, in the directed handshaking identities.
Worked Example: A Reciprocal Pair and an Isolated Vertex
Let \(D\) have \(V(D)=\{p,q,r,s\}\) and \(A(D)=\{p\to q,q\to p,p\to r,r\to q\}\). Find all directed degrees and describe the underlying undirected graph.
At \(p\), the arcs \(p\to q,p\to r\) leave and \(q\to p\) enters, so \(d^+(p)=2,d^-(p)=1\). At \(q\), the arcs \(p\to q,r\to q\) enter and \(q\to p\) leaves, so \(d^+(q)=1,d^-(q)=2\). At \(r\), \(p\to r\) enters and \(r\to q\) leaves, so \(d^+(r)=1,d^-(r)=1\). No arc touches \(s\), so \(d^+(s)=d^-(s)=0\).
Forgetting directions gives the edge set \(\{pq,pr,rq\}\): the two opposite arcs between \(p\) and \(q\) produce only the edge \(pq\). The underlying graph is a triangle on \(p,q,r\), together with the isolated vertex \(s\). It is not an orientation of this graph, because the edge \(pq\) corresponds to both \(p\to q\) and \(q\to p\), rather than exactly one of them.
Check: There are four arcs, and \(d^+(p)+d^+(q)+d^+(r)+d^+(s)=2+1+1+0=4\). The in-degree sum is \(1+2+1+0=4\) as well. The underlying graph has three edges, not four, because its edge \(pq\) comes from two arcs.
Common Mistake: Counting Incidence Instead of Direction
Suppose \(D\) has \(V(D)=\{a,b,c\}\) and \(A(D)=\{a\to b,b\to c,a\to c\}\). A common error is to say that \(a\) has in-degree \(2\), because two arcs are incident with \(a\). But both of those arcs leave \(a\), so the correct values are \(d^+(a)=2\) and \(d^-(a)=0\). For \(b\), one arc enters and one leaves, giving \(d^-(b)=1,d^+(b)=1\). For \(c\), both arcs enter, giving \(d^-(c)=2,d^+(c)=0\).
Check: The out-degree sum is \(2+1+0=3\), and the in-degree sum is \(0+1+2=3\), matching the three arcs. The lesson is to classify each arc by its tail and head, not merely by whether it touches the vertex.
These basic counts are used whenever a directed model is first specified. The arc list states the actual direction choices; the degree table summarizes how many relationships enter and leave each vertex. The directed handshaking identities provide an immediate consistency check, while an orientation additionally lets us compare the directed counts with the degrees of the original undirected graph.
Check Your Understanding
For each question, use an explicit count of arcs or edges to justify your answer.
- Let \(V(D)=\{u,v,w\}\) and \(A(D)=\{u\to v,v\to u,v\to w\}\). Find the in-degree and out-degree of each vertex, and identify any reciprocal pair.
- Can a digraph with five arcs have out-degree sum six? Explain using the directed handshaking identities.
- Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,14\}\). Give an orientation and verify the directed-degree sum at every vertex.
- Explain why a reciprocal pair contributes two to the number of arcs but only one edge to the underlying simple graph.
- Prove directly from the definitions that an isolated vertex has in-degree and out-degree zero.