Indegree — Definition, Formula & Examples

Indegree is the number of edges that point into a given vertex in a directed graph. If three arrows lead to vertex

v

, then the indegree of

v

is 3.

For a directed graph $G = (V, E)$ and a vertex $v \in V$ , the indegree of $v$ , denoted $\deg^{-}(v)$ , is the cardinality of the set $\{(u, v) \in E \mid u \in V\}$ , i.e., the number of edges in $E$ whose head (terminal endpoint) is $v$ .

Key Formula

\sum_{v \in V} \deg^{-}(v) = |E|

Where:

$\deg^{-}(v)$ = Indegree of vertex v — number of edges directed into v
$V$ = Set of all vertices in the directed graph
$|E|$ = Total number of directed edges in the graph

How It Works

To find the indegree of a vertex, look at every directed edge in the graph and count how many of them end at that vertex. An edge

(u, v)

contributes 1 to the indegree of

v

and 1 to the outdegree of

u

. A useful identity ties indegree to the total edge count: the sum of all indegrees across every vertex equals the total number of edges, since each edge is counted exactly once as an incoming edge.

Worked Example

Problem: A directed graph has vertices

\{A, B, C, D\}

and edges

\{(A,B),\ (C,B),\ (D,B),\ (A,C),\ (D,A)\}

. Find the indegree of each vertex.

Count incoming edges to A: Only the edge

(D, A)

ends at

A

\deg^{-}(A) = 1

Count incoming edges to B: Edges

(A,B)

(C,B)

, and

(D,B)

all end at

B

\deg^{-}(B) = 3

Count incoming edges to C and D: Only

(A,C)

ends at

C

, and no edge ends at

D

\deg^{-}(C) = 1, \quad \deg^{-}(D) = 0

Verify with the sum formula: The sum of all indegrees should equal the number of edges.

1 + 3 + 1 + 0 = 5 = |E| \checkmark

Answer: The indegrees are:

\deg^{-}(A)=1

\deg^{-}(B)=3

\deg^{-}(C)=1

\deg^{-}(D)=0

Visualization

Why It Matters

Indegree is central to algorithms on directed graphs. PageRank weights a web page's importance partly by its indegree (how many other pages link to it). In topological sorting, vertices with indegree zero serve as the starting points of the algorithm (Kahn's algorithm).

Common Mistakes

Mistake: Confusing indegree with total degree by counting both incoming and outgoing edges.

Correction: Indegree counts only edges directed into the vertex. Outgoing edges contribute to the outdegree, not the indegree. In a directed graph, the total degree of a vertex is the sum of its indegree and outdegree.