Graph Properties - Learning Module

Loading content...

0/276

Degree of a Vertex (In-Degree, Out-Degree)

Measuring Connectivity at Each Vertex

In a social network, some people have thousands of connections while others have just a handful. In a citation network, some papers are cited by hundreds of others while most receive few citations. In a transportation network, major hubs connect to dozens of destinations while small airports serve only a few routes.

This variation in how connected each vertex is—measured by the number of edges touching it—is called the degree of the vertex. Degree is one of the simplest yet most informative properties of a graph, revealing:

Hub identification: High-degree vertices are often critically important
Network structure: Degree distribution characterizes network types
Algorithm behavior: Many algorithms depend on degree for complexity analysis
Existence conditions: Whether certain paths or cycles exist

What You Will Learn

By the end of this page, you will understand degree, in-degree, and out-degree precisely. You'll learn the Handshaking Lemma and its implications, compute degree statistics efficiently, understand degree sequences and their properties, and see how degree analysis applies to real-world problems from social network analysis to Eulerian paths.

Degree: The Fundamental Definition

The degree of a vertex measures how many edges are connected to it. This seemingly simple concept requires careful definition to handle edge cases.

For Undirected Graphs

The degree of vertex v, denoted deg(v) or d(v), is the number of edges incident to v.

deg(v) = |{e ∈ E : v is an endpoint of e}|

Special case — Self-loops: A self-loop (edge from v to itself) contributes 2 to the degree of v, not 1. This maintains the Handshaking Lemma (discussed later).

For Directed Graphs

Directed graphs distinguish between incoming and outgoing edges:

In-degree: deg⁻(v) = number of edges pointing to v
Out-degree: deg⁺(v) = number of edges pointing from v
Total degree: deg(v) = deg⁻(v) + deg⁺(v)

deg⁻(v) = |{(u, v) ∈ E}| (edges ending at v) deg⁺(v) = |{(v, u) ∈ E}| (edges starting from v)

Degree Terminology Summary
Term	Notation	Definition	Graph Type
Degree	deg(v), d(v)	Number of incident edges	Undirected
In-degree	deg⁻(v), d⁻(v)	Number of incoming edges	Directed
Out-degree	deg⁺(v), d⁺(v)	Number of outgoing edges	Directed
Total degree	deg(v)	In-degree + Out-degree	Directed

Visual Example

Converting Mermaid diagram...

Degree in Weighted Graphs

In weighted graphs, we sometimes distinguish between 'degree' (count of edges) and 'weighted degree' or 'strength' (sum of edge weights). Unless specified, 'degree' typically refers to edge count, not weight sum.

The Handshaking Lemma

One of the most fundamental results in graph theory is the Handshaking Lemma, which relates vertex degrees to edge count.

Statement

For any undirected graph G = (V, E):

∑ deg(v) = 2|E| (sum of all degrees equals twice the number of edges)

The name comes from imagining edges as handshakes: if you count to how many people each person shook hands, and sum these counts, you've counted each handshake twice (once per participant).

Proof Intuition

Each edge has exactly two endpoints. When we sum degrees, each edge is counted once for each of its endpoints—hence counted exactly twice.

Immediate Corollaries

Powerful Consequences

•The sum of degrees is always even — You can't have an odd total degree sum
•The number of odd-degree vertices is always even — Enables Eulerian path existence checks
•Average degree = 2|E|/|V| — A key graph density metric
•If all degrees are even, Eulerian cycle may exist — Foundational for Euler's theorem

Directed Graph Version

For directed graphs, we have two versions:

∑ deg⁻(v) = ∑ deg⁺(v) = |E| (sum of in-degrees = sum of out-degrees = edge count)

This makes sense: every edge starts from some vertex (counted in out-degrees) and ends at some vertex (counted in in-degrees). The total must equal |E| for both.

Practical Application: Degree Validation

degree_validation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def validate_degree_sum(graph: dict[int, list[int]], is_directed: bool = False) -> bool:
    """
    Validate that a graph's degree sum is consistent with edge count.
    Uses the Handshaking Lemma for verification.
    
    For undirected: sum of degrees = 2 * edge_count
    For directed: sum of in-degrees = sum of out-degrees = edge_count
    """
    if is_directed:
        out_degree_sum = sum(len(neighbors) for neighbors in graph.values())
        # Count in-degrees
        in_degree = {v: 0 for v in graph}
        for vertex in graph:
            for neighbor in graph[vertex]:
                in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
        in_degree_sum = sum(in_degree.values())
        
        print(f"Out-degree sum: {out_degree_sum}")
        print(f"In-degree sum: {in_degree_sum}")
        return out_degree_sum == in_degree_sum
    else:
        # Undirected: count edges, then verify
        degree_sum = sum(len(neighbors) for neighbors in graph.values())
        # Each undirected edge appears twice in adjacency list
        expected_edge_count = degree_sum // 2
        
        print(f"Sum of degrees: {degree_sum}")
        print(f"Expected edge count: {expected_edge_count}")
        print(f"Handshaking Lemma satisfied: {degree_sum % 2 == 0}")
        return degree_sum % 2 == 0  # Must be even
 
 
def count_odd_degree_vertices(graph: dict[int, list[int]]) -> int:
    """
    Count vertices with odd degree.
    By Handshaking Lemma, this count must be even.
    """
    odd_count = sum(1 for v in graph if len(graph[v]) % 2 == 1)
    return odd_count
 
 
# Example: Undirected graph
undirected_graph = {
    0: [1, 2, 3],  # deg = 3
    1: [0, 2],     # deg = 2
    2: [0, 1],     # deg = 2
    3: [0]         # deg = 1
}
# Sum = 3 + 2 + 2 + 1 = 8, edges = 4, 8 = 2*4 ✓
 
validate_degree_sum(undirected_graph, is_directed=False)
print(f"Odd-degree vertices: {count_odd_degree_vertices(undirected_graph)}")  # 2 (vertices 0 and 3)

Computing Degrees Efficiently

Degree computation depends heavily on the graph representation. Let's analyze both major representations.

Adjacency List Representation

For an adjacency list, the degree of a vertex is simply the length of its neighbor list:

Undirected: deg(v) = len(adj[v])
Directed out-degree: deg⁺(v) = len(adj[v])
Directed in-degree: Requires scanning all lists or maintaining a separate in-neighbor list

Adjacency Matrix Representation

For an adjacency matrix, degrees are computed by summing rows/columns:

Undirected degree: Sum of row v (or column v, they're equal)
Out-degree: Sum of row v
In-degree: Sum of column v

degree_computation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from typing import List
 
# ============================================
# Adjacency List Implementation
# ============================================
 
def degree_adj_list(graph: dict[int, list[int]], vertex: int) -> int:
    """Degree in undirected graph. O(1)."""
    return len(graph.get(vertex, []))
 
 
def out_degree_adj_list(graph: dict[int, list[int]], vertex: int) -> int:
    """Out-degree in directed graph. O(1)."""
    return len(graph.get(vertex, []))
 
 
def in_degree_adj_list(graph: dict[int, list[int]], vertex: int) -> int:
    """In-degree in directed graph. O(V + E) if not cached."""
    count = 0
    for v in graph:
        if vertex in graph[v]:
            count += 1
    return count
 
 
def compute_all_in_degrees(graph: dict[int, list[int]]) -> dict[int, int]:
    """Compute in-degrees for all vertices. O(V + E)."""
    in_deg = {v: 0 for v in graph}
    for v in graph:
        for neighbor in graph[v]:
            in_deg[neighbor] = in_deg.get(neighbor, 0) + 1
    return in_deg
 
 
# ============================================
# Adjacency Matrix Implementation
# ============================================
 
def degree_adj_matrix(matrix: List[List[int]], vertex: int) -> int:
    """Degree in undirected graph. O(V)."""
    return sum(matrix[vertex])
 
 
def out_degree_matrix(matrix: List[List[int]], vertex: int) -> int:
    """Out-degree in directed graph. O(V)."""
    return sum(matrix[vertex])  # Sum of row
 
 
def in_degree_matrix(matrix: List[List[int]], vertex: int) -> int:
    """In-degree in directed graph. O(V)."""
    return sum(matrix[v][vertex] for v in range(len(matrix)))  # Sum of column
 
 
# ============================================
# Degree Statistics
# ============================================
 
def degree_statistics(graph: dict[int, list[int]]) -> dict:
    """
    Compute comprehensive degree statistics.
    
    Returns min, max, average degree, and degree distribution.
    """
    if not graph:
        return {"min": 0, "max": 0, "avg": 0, "distribution": {}}
    
    degrees = [len(graph[v]) for v in graph]
    
    # Degree distribution: degree -> count of vertices with that degree
    distribution = {}
    for d in degrees:
        distribution[d] = distribution.get(d, 0) + 1
    
    return {
        "min": min(degrees),
        "max": max(degrees),
        "avg": sum(degrees) / len(degrees),
        "sum": sum(degrees),
        "distribution": distribution,
        "vertices": len(degrees)
    }
 
 
# Example usage
graph = {
    0: [1, 2, 3, 4],  # Hub vertex, deg=4
    1: [0, 2],
    2: [0, 1],
    3: [0],
    4: [0]
}
 
stats = degree_statistics(graph)
print(f"Min degree: {stats['min']}")  # 1
print(f"Max degree: {stats['max']}")  # 4
print(f"Average degree: {stats['avg']:.2f}")  # 2.0
print(f"Distribution: {stats['distribution']}")  # {4: 1, 2: 2, 1: 2}

Degree Computation Complexity
Operation	Adjacency List	Adjacency Matrix
Degree of one vertex	O(1)	O(V)
Out-degree of one vertex	O(1)	O(V)
In-degree of one vertex	O(V + E)	O(V)
All degrees	O(V + E)	O(V²)
All in-degrees	O(V + E)	O(V²)

Degree Sequences and Graph Realization

A degree sequence is the list of all vertex degrees in a graph, typically sorted in non-increasing order. For example, a triangle (3 vertices, all connected) has degree sequence [2, 2, 2].

The Realizability Question

Given a sequence of numbers, can we construct a graph with exactly these degrees? Not every sequence is graphical (realizable as a simple graph).

Example: Can [3, 3, 3, 3] be realized?

Sum = 12, which is even ✓ (Handshaking Lemma)
Each vertex needs 3 neighbors, but we only have 4 vertices total
Each vertex connects to exactly the other 3 → Yes! This is the complete graph K₄.

Example: Can [3, 3, 3, 1] be realized?

Sum = 10, which is even ✓
But the vertex with degree 1 can only connect to one other vertex
Three vertices need degree 3 each = need 3 edges each
The degree-1 vertex can only 'absorb' one of these needs
Not enough connections possible → No!

Erdős–Gallai Theorem

A sequence d₁ ≥ d₂ ≥ ... ≥ dₙ is graphical if and only if:

The sum is even
For each k from 1 to n: ∑ᵢ₌₁ᵏ dᵢ ≤ k(k-1) + ∑ᵢ₌ₖ₊₁ⁿ min(dᵢ, k)

degree_sequence.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
def is_graphical_erdos_gallai(sequence: list[int]) -> bool:
    """
    Check if a degree sequence is graphical using Erdős–Gallai theorem.
    
    A sequence is graphical if a simple graph exists with those degrees.
    
    Time Complexity: O(n²) but can be optimized to O(n log n)
    """
    sequence = sorted(sequence, reverse=True)  # Sort descending
    n = len(sequence)
    
    # Condition 1: Sum must be even (Handshaking Lemma)
    if sum(sequence) % 2 != 0:
        return False
    
    # Check for negative degrees
    if any(d < 0 for d in sequence):
        return False
    
    # Check for degrees exceeding n-1 (can't have more edges than vertices-1)
    if sequence and sequence[0] > n - 1:
        return False
    
    # Condition 2: Erdős–Gallai inequality for each k
    for k in range(1, n + 1):
        left_sum = sum(sequence[:k])
        right_sum = k * (k - 1) + sum(min(d, k) for d in sequence[k:])
        if left_sum > right_sum:
            return False
    
    return True
 
 
def construct_graph_from_sequence(sequence: list[int]) -> dict[int, list[int]] | None:
    """
    Construct a simple graph with the given degree sequence.
    Uses the Hakimi algorithm (greedy construction).
    
    Returns adjacency list or None if not graphical.
    """
    if not is_graphical_erdos_gallai(sequence):
        return None
    
    n = len(sequence)
    # Create (degree, vertex_id) pairs
    degrees = [[d, i] for i, d in enumerate(sequence)]
    graph = {i: [] for i in range(n)}
    
    while True:
        # Sort by degree descending
        degrees.sort(key=lambda x: -x[0])
        
        # Remove vertices with degree 0
        degrees = [d for d in degrees if d[0] > 0]
        
        if not degrees:
            break  # Done!
        
        # Take vertex with highest remaining degree
        d, v = degrees[0]
        degrees[0][0] = 0  # Used up this vertex's edges
        
        if d > len(degrees) - 1:
            return None  # Not enough vertices to connect to
        
        # Connect to next d highest-degree vertices
        for i in range(1, d + 1):
            neighbor_degree, neighbor = degrees[i]
            degrees[i][0] -= 1
            
            # Add edge
            graph[v].append(neighbor)
            graph[neighbor].append(v)
    
    return graph
 
 
# Examples
print(is_graphical_erdos_gallai([3, 3, 3, 3]))  # True (K4)
print(is_graphical_erdos_gallai([3, 3, 3, 1]))  # False
print(is_graphical_erdos_gallai([2, 2, 2]))     # True (triangle)
print(is_graphical_erdos_gallai([3, 2, 1, 0]))  # False (odd sum)
 
# Construct a graph
graph = construct_graph_from_sequence([2, 2, 2])
print(f"Triangle graph: {graph}")  # {0: [1, 2], 1: [0, 2], 2: [0, 1]}

Quick Checks Before Erdős–Gallai

Before running the full theorem, quick necessary conditions: (1) Sum must be even, (2) All degrees must be non-negative, (3) Maximum degree ≤ n-1. If any fail, the sequence is definitely not graphical.

Special Vertex Classifications by Degree

Vertices with certain degree values have special names and significance:

Isolated Vertices (Degree 0)

A vertex with degree 0 is called isolated. It has no edges and forms its own connected component. Isolated vertices:

Don't participate in any path
Form singleton components
Sometimes arise from data cleaning or sparse graphs

Pendant Vertices / Leaves (Degree 1)

A vertex with degree 1 is called a pendant vertex or leaf. It connects to exactly one other vertex. In trees:

All terminal nodes are leaves
Removing a leaf doesn't disconnect the tree
Trees with n vertices have between 1 and n-1 leaves

Regular Graphs

A graph is k-regular if every vertex has exactly degree k:

0-regular: No edges (all isolated)
1-regular: Perfect matching (pairs of vertices)
2-regular: Collection of cycles
3-regular (cubic): Common in chemistry and network topology
(n-1)-regular on n vertices: Complete graph Kₙ

Special Degree Classifications
Classification	Degree	Example	Properties
Isolated vertex	0	Deleted user in social network	Own component, unreachable
Pendant / Leaf	1	File in directory tree	Can be removed easily
k-regular graph	All vertices: k	K₄ is 3-regular	Highly symmetric
Hub vertex	Significantly > average	Popular influencer	Critical for connectivity
Degree centrality	Normalized to [0,1]	Network analysis metric	Measures importance

Hubs and Authorities

In real-world networks, hub vertices have unusually high degree. Identifying them is important for:

Attack resilience: If hubs are removed, networks may fragment
Information spread: Hubs accelerate diffusion
Load balancing: Hubs may become bottlenecks
Influence measurement: High degree often correlates with importance

Degree Centrality

Degree centrality normalizes degree to allow comparison across graphs:

Cᴰ(v) = deg(v) / (|V| - 1)

This gives a value between 0 (isolated) and 1 (connected to everyone). It's one of the simplest centrality measures but remains useful for initial network analysis.

degree_classification.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def classify_vertices(graph: dict[int, list[int]]) -> dict:
    """
    Classify vertices by their degree characteristics.
    """
    n = len(graph)
    degrees = {v: len(graph[v]) for v in graph}
    avg_degree = sum(degrees.values()) / n if n > 0 else 0
    
    result = {
        "isolated": [],      # degree 0
        "leaves": [],        # degree 1
        "hubs": [],          # degree > 2 * average
        "degree_centrality": {}
    }
    
    for v, deg in degrees.items():
        if deg == 0:
            result["isolated"].append(v)
        elif deg == 1:
            result["leaves"].append(v)
        elif deg > 2 * avg_degree:
            result["hubs"].append(v)
        
        # Degree centrality: deg / (n-1)
        result["degree_centrality"][v] = deg / (n - 1) if n > 1 else 0
    
    return result
 
 
def is_regular(graph: dict[int, list[int]]) -> tuple[bool, int | None]:
    """
    Check if graph is k-regular (all vertices same degree).
    
    Returns (is_regular, k) where k is the common degree or None.
    """
    if not graph:
        return True, 0
    
    degrees = set(len(neighbors) for neighbors in graph.values())
    
    if len(degrees) == 1:
        return True, degrees.pop()
    return False, None
 
 
# Example: Star graph (one hub connected to many leaves)
star_graph = {
    0: [1, 2, 3, 4, 5],  # Hub
    1: [0],              # Leaf
    2: [0],              # Leaf
    3: [0],              # Leaf
    4: [0],              # Leaf
    5: [0],              # Leaf
}
 
classification = classify_vertices(star_graph)
print(f"Leaves: {classification['leaves']}")  # [1, 2, 3, 4, 5]
print(f"Hubs: {classification['hubs']}")      # [0]
 
# Example: Complete graph K4 (4-regular minus 1)
k4 = {
    0: [1, 2, 3],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [0, 1, 2],
}
is_reg, k = is_regular(k4)
print(f"K4 is {k}-regular: {is_reg}")  # K4 is 3-regular: True

Degree and Eulerian Path/Cycle Existence

One of the most elegant applications of degree is determining whether Eulerian paths and cycles exist. These are paths/cycles that traverse every edge exactly once.

Euler's Theorem (Undirected Graphs)

For a connected undirected graph:

Eulerian cycle exists ⟺ Every vertex has even degree
Eulerian path exists ⟺ Exactly 0 or 2 vertices have odd degree
- If 0 odd: The path is actually a cycle
- If 2 odd: The path starts at one odd and ends at the other

Euler's Theorem (Directed Graphs)

For a strongly connected directed graph:

Eulerian cycle exists ⟺ For every vertex, in-degree = out-degree
Eulerian path exists ⟺ At most one vertex has (out-degree - in-degree) = 1 (start), and at most one has (in-degree - out-degree) = 1 (end)

eulerian_check.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def check_eulerian_undirected(graph: dict[int, list[int]]) -> str:
    """
    Check if an undirected graph has an Eulerian path or cycle.
    Assumes graph is connected.
    
    Returns:
        'cycle' - Eulerian cycle exists
        'path'  - Eulerian path exists (but not cycle)
        'none'  - No Eulerian path or cycle
    """
    odd_degree_count = sum(1 for v in graph if len(graph[v]) % 2 == 1)
    
    if odd_degree_count == 0:
        return 'cycle'  # All even degrees
    elif odd_degree_count == 2:
        return 'path'   # Exactly 2 odd-degree vertices
    else:
        return 'none'   # More than 2 odd-degree vertices
 
 
def check_eulerian_directed(graph: dict[int, list[int]]) -> str:
    """
    Check if a directed graph has an Eulerian path or cycle.
    Assumes graph is strongly connected.
    """
    # Compute in-degrees
    in_degree = {v: 0 for v in graph}
    out_degree = {v: len(graph[v]) for v in graph}
    
    for v in graph:
        for neighbor in graph[v]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
    
    # Count vertices where in-degree ≠ out-degree
    start_candidates = 0  # out > in by 1
    end_candidates = 0    # in > out by 1
    
    for v in graph:
        diff = out_degree[v] - in_degree[v]
        if diff == 0:
            continue
        elif diff == 1:
            start_candidates += 1
        elif diff == -1:
            end_candidates += 1
        else:
            return 'none'  # Difference too large
    
    if start_candidates == 0 and end_candidates == 0:
        return 'cycle'  # All balanced
    elif start_candidates == 1 and end_candidates == 1:
        return 'path'   # Exactly one start, one end
    else:
        return 'none'
 
 
# Examples
# Bridge of Königsberg (famously has no Eulerian path)
konigsberg = {
    'A': ['B', 'B', 'C', 'D'],
    'B': ['A', 'A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'B', 'C'],
}
# Degrees: A=4, B=4, C=3, D=3 (two odd) - wait, recounting for multi-edges
# Actually with multi-edges: A=4, B=4, C=3, D=3 → 2 odd → path exists
# But this famous problem actually has 4 odd vertices when properly modeled
 
# Simple example
triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}  # All degree 2
print(f"Triangle: {check_eulerian_undirected(triangle)}")  # 'cycle'
 
path_graph = {0: [1], 1: [0, 2], 2: [1]}  # degrees: 1, 2, 1
print(f"Path: {check_eulerian_undirected(path_graph)}")  # 'path'

The Seven Bridges of Königsberg

Euler's theorem originated from the famous Königsberg bridge problem (1736). The city had 7 bridges connecting 4 land masses. Euler proved no walk could cross each bridge exactly once because all 4 land masses had odd degree (3, 3, 3, 5). This is considered the birth of graph theory.

Real-World Applications of Degree Analysis

Degree analysis appears throughout network science and practical applications:

Applications Across Domains

•Social Network Analysis: Follower count (out-degree in who-follows-whom) and followed-by count (in-degree) reveal influence patterns. High in-degree users are influential; high out-degree users are highly engaged
•Web Page Ranking: Early PageRank variants used in-degree (number of incoming links) as a quality signal. Modern algorithms still consider degree in their calculations
•Citation Networks: Paper citation count is in-degree. Highly cited papers are influential; papers citing many others may be surveys
•Protein Interaction Networks: High-degree proteins ('hubs') are often essential for organism survival. Targeting hubs is a strategy for drug development
•Power Grid Resilience: Identifying high-degree substations helps prioritize protection against failures. Removing hubs can cause cascading blackouts
•Airport Networks: Hub airports (Chicago O'Hare, Atlanta) have high degree. Degree analysis helps understand flight routing and delays

Degree Distributions and Network Types

The degree distribution P(k)—the probability that a random vertex has degree k—characterizes network structure:

Distribution Type	Description	Example Networks
Regular	All same degree	Carefully designed networks, lattices
Poisson	Bell-shaped, most near average	Erdős-Rényi random graphs
Power-law	Many low-degree, few hubs	Web, social networks, citations
Bimodal	Two peaks	Networks with two vertex types

Power-law networks (scale-free networks) are particularly important: they have P(k) ∝ k⁻ᵞ, meaning high-degree vertices are rare but exist. This makes them robust to random failures but vulnerable to targeted attacks on hubs.

Interview Pattern

When asked to find 'influential nodes,' 'central vertices,' or 'important users,' degree analysis is often the first step. It's simple, fast (O(V + E)), and provides valuable insights. More sophisticated measures (betweenness, closeness, PageRank) can follow for deeper analysis.

Summary: Mastering Vertex Degree

Vertex degree is deceptively simple yet incredibly powerful. It quantifies local connectivity and reveals global structure. Let's consolidate the key concepts:

Key Takeaways

•Degree counts incident edges; in directed graphs, we distinguish in-degree and out-degree
•The Handshaking Lemma states ∑deg(v) = 2|E|, implying the sum of degrees is always even
•Degree computation is O(1) per vertex in adjacency lists for undirected/out-degree, but O(V+E) for all in-degrees
•Degree sequences characterize graphs; Erdős–Gallai theorem tests if a sequence is realizable
•Special vertices: isolated (degree 0), leaves (degree 1), hubs (high degree); k-regular graphs have all degrees equal
•Eulerian existence depends on degree: even degrees for cycles, exactly 0 or 2 odd for paths
•Degree distributions reveal network type: power-law for scale-free networks, Poisson for random

What's Next:

With connectivity, cycles, and degrees covered, we now explore complete graphs and subgraphs—the extreme case where every vertex connects to every other, and how we extract meaningful portions from larger graphs.

Page Complete

You now understand vertex degree deeply—from basic definitions through the Handshaking Lemma, degree sequences, vertex classification, Eulerian criteria, and practical applications in network analysis. Next, we'll explore complete graphs and subgraphs.