Degree of a Vertex
What you'll learn: You'll learn how to count the connections at each node in a graph—called the vertex's degree.
What Is Vertex Degree?
The degree of a vertex is simply the count of how many edges touch that vertex. Think of it like counting how many roads meet at an intersection—the more roads, the higher the degree.
In an undirected graph (where edges have no direction), the degree counts all edges connected to a vertex. If vertex A connects to vertices B, C, and D, then A has degree 3.
Degree in Directed Graphs
For directed graphs (where edges have arrows showing direction), we split degree into two types:
- In-degree: The number of edges coming into the vertex
- Out-degree: The number of edges going out from the vertex
Imagine a social media "following" network: your in-degree is your follower count, and your out-degree is how many people you follow.
Examples
Undirected graph:
- Vertex A connects to B and C → degree = 2
- Vertex B connects to A, C, and D → degree = 3
Directed graph:
- Vertex A has arrows pointing to B and C → out-degree = 2, in-degree = 0
- Vertex C has arrows coming from A and B → out-degree = 0, in-degree = 2
Why Does Degree Matter?
Vertex degree helps us understand graph structure. High-degree vertices are "hubs" (like major airports), while low-degree vertices are peripheral. Degree also appears in many graph algorithms and theorems you'll encounter later.
Key Takeaway: The degree of a vertex counts its incident edges—simply the total for undirected graphs, or split into in-degree and out-degree for directed graphs.