# Chapter 17. In-Degree and Out-Degree # Chapter 17. In-Degree and Out-Degree In an undirected graph, the degree of a vertex counts the number of edges incident with that vertex. In a directed graph, this single number splits into two numbers: the number of arcs entering the vertex and the number of arcs leaving the vertex. These two numbers are called the in-degree and the out-degree. They measure how a vertex receives directed connections and how it sends directed connections. Standard graph terminology defines in-degree as the number of directed edges leading into a vertex, and out-degree as the number leading away from it. ## 17.1 Incoming and Outgoing Arcs Let $$ D = (V,A) $$ be a directed graph. The set \(V\) contains the vertices, and the set \(A\) contains the arcs. Each arc is an ordered pair $$ (u,v). $$ The arc \((u,v)\) leaves \(u\) and enters \(v\). The vertex \(u\) is the tail of the arc. The vertex \(v\) is the head of the arc. Thus an arc has two local meanings: | Role | Vertex | Meaning | |---|---:|---| | Tail | \(u\) | the arc leaves this vertex | | Head | \(v\) | the arc enters this vertex | For a fixed vertex \(v\), an arc of the form $$ (u,v) $$ is incoming to \(v\). An arc of the form $$ (v,w) $$ is outgoing from \(v\). Direction matters. The arc \((u,v)\) contributes to the out-degree of \(u\) and to the in-degree of \(v\). It does not contribute to the in-degree of \(u\) or the out-degree of \(v\). ## 17.2 In-Degree The in-degree of a vertex \(v\) is the number of arcs whose head is \(v\). It is denoted by $$ \deg^-(v). $$ Formally, $$ \deg^-(v) = |\{u \in V : (u,v) \in A\}|. $$ This counts all vertices \(u\) that send an arc into \(v\). If the directed graph is a directed multigraph, then repeated arcs are counted with multiplicity. The superscript minus sign suggests movement into the vertex. It records incoming incidence. For example, suppose $$ A = \{(a,c), (b,c), (d,c), (c,a)\}. $$ Then three arcs enter \(c\): $$ (a,c), \qquad (b,c), \qquad (d,c). $$ Therefore, $$ \deg^-(c) = 3. $$ The arc \((c,a)\) leaves \(c\), so it does not increase the in-degree of \(c\). ## 17.3 Out-Degree The out-degree of a vertex \(v\) is the number of arcs whose tail is \(v\). It is denoted by $$ \deg^+(v). $$ Formally, $$ \deg^+(v) = |\{u \in V : (v,u) \in A\}|. $$ This counts all vertices \(u\) reached by an arc leaving \(v\). If repeated arcs are allowed, each repeated outgoing arc is counted separately. The superscript plus sign suggests movement out of the vertex. It records outgoing incidence. For example, suppose $$ A = \{(a,b), (a,c), (a,d), (c,a)\}. $$ Then three arcs leave \(a\): $$ (a,b), \qquad (a,c), \qquad (a,d). $$ Therefore, $$ \deg^+(a) = 3. $$ The arc \((c,a)\) enters \(a\), so it does not increase the out-degree of \(a\). ## 17.4 In-Neighborhood and Out-Neighborhood The in-degree and out-degree are often described through neighborhoods. The out-neighborhood of \(v\) is $$ N^+(v) = \{u \in V : (v,u) \in A\}. $$ It is the set of vertices reached directly from \(v\). The in-neighborhood of \(v\) is $$ N^-(v) = \{u \in V : (u,v) \in A\}. $$ It is the set of vertices that point directly into \(v\). For a simple directed graph, $$ \deg^+(v) = |N^+(v)| $$ and $$ \deg^-(v) = |N^-(v)|. $$ For a directed multigraph, this equality may fail if neighborhoods are treated as sets, because several arcs may connect the same ordered pair of vertices. In that case, degree counts arcs, while neighborhood size counts distinct neighboring vertices. ## 17.5 Example Let $$ V = \{a,b,c,d,e\} $$ and $$ A = \{(a,b), (a,c), (b,c), (c,a), (c,d), (d,c), (e,c)\}. $$ We compute the in-degree and out-degree of each vertex. For \(a\), one arc enters it: $$ (c,a). $$ Two arcs leave it: $$ (a,b), \qquad (a,c). $$ So $$ \deg^-(a)=1, \qquad \deg^+(a)=2. $$ For \(b\), one arc enters it: $$ (a,b). $$ One arc leaves it: $$ (b,c). $$ So $$ \deg^-(b)=1, \qquad \deg^+(b)=1. $$ For \(c\), four arcs enter it: $$ (a,c), \qquad (b,c), \qquad (d,c), \qquad (e,c). $$ Two arcs leave it: $$ (c,a), \qquad (c,d). $$ So $$ \deg^-(c)=4, \qquad \deg^+(c)=2. $$ For \(d\), one arc enters it: $$ (c,d). $$ One arc leaves it: $$ (d,c). $$ So $$ \deg^-(d)=1, \qquad \deg^+(d)=1. $$ For \(e\), no arcs enter it. One arc leaves it: $$ (e,c). $$ So $$ \deg^-(e)=0, \qquad \deg^+(e)=1. $$ The result is summarized below. | Vertex | In-degree | Out-degree | |---|---:|---:| | \(a\) | 1 | 2 | | \(b\) | 1 | 1 | | \(c\) | 4 | 2 | | \(d\) | 1 | 1 | | \(e\) | 0 | 1 | ## 17.6 Sources and Sinks A vertex with in-degree zero is called a source. It has no incoming arcs. A vertex with out-degree zero is called a sink. It has no outgoing arcs. These names are standard in directed graph theory. Thus \(v\) is a source if $$ \deg^-(v)=0. $$ The vertex \(v\) is a sink if $$ \deg^+(v)=0. $$ In the example above, \(e\) is a source, since no arc enters \(e\). There is no sink, since every vertex has at least one outgoing arc. Sources and sinks are important in applications. In a dependency graph, a source may represent a task with no prerequisites. A sink may represent a task on which no later task depends. In a flow network, a source sends flow into the network, while a sink receives flow from the network. ## 17.7 Balanced Vertices and Balanced Directed Graphs A vertex \(v\) is balanced if its in-degree equals its out-degree: $$ \deg^-(v) = \deg^+(v). $$ A directed graph is balanced if every vertex is balanced. Balanced directed graphs are important in the study of Eulerian circuits, because a directed Eulerian circuit requires each vertex to have the same number of incoming and outgoing arcs, together with the appropriate connectivity condition. For example, in the directed cycle $$ a \to b \to c \to a, $$ each vertex has one incoming arc and one outgoing arc. Therefore each vertex is balanced. In contrast, in the directed path $$ a \to b \to c, $$ we have $$ \deg^-(a)=0, \quad \deg^+(a)=1, $$ $$ \deg^-(b)=1, \quad \deg^+(b)=1, $$ $$ \deg^-(c)=1, \quad \deg^+(c)=0. $$ Only \(b\) is balanced. ## 17.8 Total In-Degree and Total Out-Degree For every finite directed graph, $$ \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |A|. $$ This identity is the directed version of the handshaking lemma. Each arc has exactly one tail and exactly one head. Therefore each arc contributes \(1\) to the total out-degree and \(1\) to the total in-degree. The proof is immediate from double counting. Count the arcs by their tails. Each arc is counted once in the out-degree of its tail, so $$ \sum_{v \in V} \deg^+(v) = |A|. $$ Count the same arcs by their heads. Each arc is counted once in the in-degree of its head, so $$ \sum_{v \in V} \deg^-(v) = |A|. $$ Therefore the two sums are equal. This formula is a standard property of directed graphs. ## 17.9 Loops A loop is an arc of the form $$ (v,v). $$ It leaves \(v\) and enters \(v\) at the same time. Therefore a loop contributes \(1\) to the out-degree of \(v\) and \(1\) to the in-degree of \(v\). This convention preserves the identity $$ \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |A|. $$ For example, if \(A = \{(a,a)\}\), then $$ \deg^-(a)=1, \qquad \deg^+(a)=1. $$ The single loop is counted once as incoming and once as outgoing. ## 17.10 Degree Sequences of Directed Graphs The degree sequence of a directed graph records the in-degree and out-degree of each vertex. For a directed graph with vertices $$ v_1, v_2, \ldots, v_n, $$ the directed degree sequence may be written as $$ ((\deg^-(v_1),\deg^+(v_1)), (\deg^-(v_2),\deg^+(v_2)), \ldots, (\deg^-(v_n),\deg^+(v_n))). $$ Some authors list the out-degree first. The convention must be stated before use. A degree sequence is a graph invariant. If two directed graphs are isomorphic, then their degree sequences agree after a suitable relabeling of vertices. The converse does not hold in general. Two non-isomorphic directed graphs may have the same degree sequence. A necessary condition for a list of pairs $$ (d_1^-,d_1^+), \ldots, (d_n^-,d_n^+) $$ to be the degree sequence of a finite directed graph is $$ \sum_{i=1}^n d_i^- = \sum_{i=1}^n d_i^+. $$ Both sums must equal the number of arcs. This condition alone may not be sufficient when loops or multiple arcs are restricted. ## 17.11 Degree and Adjacency Matrices Let \(D=(V,A)\) be a directed graph with vertices $$ v_1,\ldots,v_n. $$ Its adjacency matrix is the \(n \times n\) matrix \(M\) defined by $$ M_{ij} = \begin{cases} 1, & \text{if } (v_i,v_j) \in A, \\ 0, & \text{otherwise.} \end{cases} $$ In a simple directed graph, the out-degree of \(v_i\) is the sum of row \(i\): $$ \deg^+(v_i) = \sum_{j=1}^n M_{ij}. $$ The in-degree of \(v_j\) is the sum of column \(j\): $$ \deg^-(v_j) = \sum_{i=1}^n M_{ij}. $$ Rows describe arcs leaving a vertex. Columns describe arcs entering a vertex. For example, let $$ M = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}. $$ The first row has sum \(2\), so $$ \deg^+(v_1)=2. $$ The first column has sum \(1\), so $$ \deg^-(v_1)=1. $$ This matrix view is useful in algorithms and spectral graph theory. It allows degree calculations through row sums and column sums. ## 17.12 Degree and Incidence Matrices The incidence matrix also records in-degree and out-degree. Let \(B\) be the directed incidence matrix using the convention $$ B_{ik} = \begin{cases} -1, & \text{if } v_i \text{ is the tail of arc } a_k, \\ 1, & \text{if } v_i \text{ is the head of arc } a_k, \\ 0, & \text{otherwise.} \end{cases} $$ Then the number of \(-1\) entries in row \(i\) is the out-degree of \(v_i\). The number of \(1\) entries in row \(i\) is the in-degree of \(v_i\). This representation is especially useful when arcs carry flow. A positive entry means flow enters the vertex through that arc. A negative entry means flow leaves the vertex through that arc. ## 17.13 Interpretation in Networks In-degree and out-degree often have direct meaning. | Network | In-degree | Out-degree | |---|---|---| | Web graph | number of pages linking to a page | number of links from a page | | Social follow graph | number of followers | number of followed accounts | | Citation graph | number of later papers citing a paper | number of cited references | | Dependency graph | number of prerequisites or dependents, depending on convention | opposite direction count | | Road network | number of incoming one-way roads | number of outgoing one-way roads | | Control-flow graph | number of incoming control paths | number of outgoing control paths | The direction convention must always be checked. In a dependency graph, one author may write \(u \to v\) to mean \(u\) must happen before \(v\). Another may write \(u \to v\) to mean \(u\) depends on \(v\). These conventions reverse the interpretation of in-degree and out-degree. The mathematics remains the same. The interpretation depends on the meaning assigned to each arc. ## 17.14 Common Mistakes A common mistake is to count adjacent vertices without considering direction. In a directed graph, adjacency alone does not determine degree. One must distinguish incoming arcs from outgoing arcs. Another mistake is to assume that \((u,v)\) and \((v,u)\) are the same. They are different arcs. If both are present, each contributes separately. A third mistake is to forget the loop convention. A loop contributes to both in-degree and out-degree. It does not contribute twice to either one. A fourth mistake is to interpret degree sequence as a complete description of a graph. Degree sequences give useful summaries, but they rarely determine a directed graph uniquely. ## 17.15 Summary In-degree and out-degree refine the notion of degree for directed graphs. The in-degree of \(v\) counts arcs entering \(v\): $$ \deg^-(v) = |\{u \in V : (u,v) \in A\}|. $$ The out-degree of \(v\) counts arcs leaving \(v\): $$ \deg^+(v) = |\{u \in V : (v,u) \in A\}|. $$ A source has in-degree zero. A sink has out-degree zero. A balanced vertex has equal in-degree and out-degree. For every finite directed graph, $$ \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |A|. $$ This identity follows because every arc has one tail and one head. In-degree and out-degree are elementary local quantities, but they support many later topics: directed paths, strong connectivity, Eulerian circuits, flow networks, ranking systems, dependency graphs, and directed graph algorithms.