9.8 Degree and Connectivity

Problem

You need basic measurements that describe the local and global structure of a graph.

Before choosing an advanced algorithm, it is often useful to ask simple structural questions:

How many edges touch this vertex?
Is the graph connected?
Which vertices form separate regions?
Are there isolated vertices?
Which vertices act as hubs?

These questions are answered by degree and connectivity analysis.

Solution

Use degree to measure local edge structure, and use traversal to measure connectivity.

For an undirected graph, the degree of a vertex is the number of incident edges.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

degree_a = len(graph["A"])

Here:

degree(A) = 2

For a directed graph, use two measurements:

in-degree  = number of incoming edges
out-degree = number of outgoing edges

The out-degree is immediate from the adjacency list.

out_degree = len(graph["A"])

The in-degree usually requires scanning edges.

def indegrees(graph):
    result = {vertex: 0 for vertex in graph}

    for source in graph:
        for target in graph[source]:
            result[target] += 1

    return result

Connectivity is measured by running DFS or BFS from one or more starting vertices.

Discussion

Degree is a local property. It tells you how a single vertex participates in the graph.

Connectivity is a global property. It tells you how vertices relate through paths.

Both are simple, but they reveal a large amount of useful information. A vertex with high degree may be a hub. A vertex with degree zero may be isolated. A graph with several connected components may represent multiple independent networks. A directed graph with many zero in-degree vertices may contain many independent starting points.

These measurements are also inputs to larger algorithms.

Topological sorting uses in-degree. Euler path algorithms use degree conditions. Network resilience algorithms care about connectivity. Clustering often begins with components. Build systems use zero in-degree vertices to find tasks that can run immediately.

Degree in Undirected Graphs

In an undirected graph, each edge contributes one to the degree of both endpoints.

Given:

A -- B
A -- C
B -- D

The adjacency list is:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

The degrees are:

Vertex	Degree
A	2
B	2
C	1
D	1

A direct implementation:

def degrees(graph):
    return {
        vertex: len(neighbors)
        for vertex, neighbors in graph.items()
    }

Output:

{
    "A": 2,
    "B": 2,
    "C": 1,
    "D": 1,
}

This runs in O(V) time if the adjacency lists are already built, because each degree is stored implicitly as the length of a neighbor list.

Degree in Directed Graphs

Directed graphs distinguish outgoing and incoming edges.

Given:

A -> B
A -> C
B -> C

The adjacency list is:

graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": [],
}

The degrees are:

Vertex	In-Degree	Out-Degree
A	0	2
B	1	1
C	2	0

Out-degree is local:

def outdegrees(graph):
    return {
        vertex: len(neighbors)
        for vertex, neighbors in graph.items()
    }

In-degree is computed by scanning all edges:

def indegrees(graph):
    result = {
        vertex: 0
        for vertex in graph
    }

    for source, neighbors in graph.items():
        for target in neighbors:
            result[target] += 1

    return result

The in-degree computation runs in O(V + E) time.

Recipe: Find Isolated Vertices

An isolated vertex has degree zero.

In an undirected graph:

def isolated_vertices(graph):
    return [
        vertex
        for vertex, neighbors in graph.items()
        if len(neighbors) == 0
    ]

Example:

graph = {
    "A": ["B"],
    "B": ["A"],
    "C": [],
}

Output:

["C"]

For directed graphs, a vertex is usually considered isolated if both its in-degree and out-degree are zero.

def isolated_directed_vertices(graph):
    incoming = indegrees(graph)

    return [
        vertex
        for vertex in graph
        if incoming[vertex] == 0
        and len(graph[vertex]) == 0
    ]

This distinction matters. A sink vertex has out-degree zero but may still receive edges. A source vertex has in-degree zero but may still send edges.

Connectivity in Undirected Graphs

An undirected graph is connected if every vertex can reach every other vertex.

You can test this with one traversal.

def is_connected(graph):
    if not graph:
        return True

    start = next(iter(graph))
    visited = set()

    def dfs(vertex):
        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)

    return len(visited) == len(graph)

Example:

graph = {
    "A": ["B"],
    "B": ["A"],
    "C": [],
}

print(is_connected(graph))

Output:

False

Vertex C is disconnected.

The traversal costs O(V + E).

Connected Components

When an undirected graph is not connected, decompose it into connected components.

def connected_components(graph):
    visited = set()
    components = []

    def dfs(vertex, component):
        visited.add(vertex)
        component.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor, component)

    for vertex in graph:
        if vertex in visited:
            continue

        component = []
        dfs(vertex, component)
        components.append(component)

    return components

Example:

graph = {
    "A": ["B"],
    "B": ["A"],
    "C": ["D"],
    "D": ["C"],
    "E": [],
}

print(connected_components(graph))

Output:

[
    ["A", "B"],
    ["C", "D"],
    ["E"],
]

Connected components are fundamental because many graph algorithms assume connectivity. If the graph has multiple components, you often run the algorithm once per component.

Weak and Strong Connectivity

Directed graphs require more precise language.

A directed graph is weakly connected if it becomes connected after ignoring edge directions.

Example:

A -> B
C -> B

Ignoring direction gives:

A -- B -- C

so the graph is weakly connected.

A directed graph is strongly connected if every vertex can reach every other vertex while respecting edge direction.

Example:

A -> B
B -> C
C -> A

This graph is strongly connected.

From any vertex, you can reach the other two.

Weak connectivity is useful when direction exists but you only care whether vertices belong to the same underlying region. Strong connectivity is useful when mutual reachability matters, such as in state machines, web graphs, and dependency cycles.

Strongly connected components are covered later in this chapter.

Recipe: Weak Connectivity

To test weak connectivity, convert the directed graph to an undirected view.

def undirected_view(graph):
    view = {
        vertex: set()
        for vertex in graph
    }

    for source, neighbors in graph.items():
        for target in neighbors:
            view[source].add(target)
            view[target].add(source)

    return view

Then reuse the ordinary connectivity test.

def is_weakly_connected(graph):
    return is_connected(undirected_view(graph))

This works because weak connectivity intentionally ignores edge direction.

Recipe: Find Hubs

A hub is a vertex with high degree.

For undirected graphs:

def top_by_degree(graph, limit=5):
    items = [
        (vertex, len(neighbors))
        for vertex, neighbors in graph.items()
    ]

    items.sort(
        key=lambda item: item[1],
        reverse=True
    )

    return items[:limit]

Example:

graph = {
    "A": ["B", "C", "D"],
    "B": ["A"],
    "C": ["A"],
    "D": ["A"],
}

Output:

[
    ("A", 3),
    ("B", 1),
    ("C", 1),
    ("D", 1),
]

In directed graphs, hub analysis may use in-degree, out-degree, or both.

A high in-degree vertex is often an authority, destination, or dependency target.

A high out-degree vertex is often a broadcaster, source, or fan-out point.

Complexity Characteristics

For adjacency-list graphs:

Operation	Complexity
Undirected degree lookup	O(1)
Out-degree lookup	O(1)
Compute all in-degrees	O(V + E)
Connectivity test	O(V + E)
Connected components	O(V + E)
Weak connectivity	O(V + E)
Find isolated vertices	O(V + E) directed, O(V) undirected

These operations are usually cheap enough to run as preprocessing or validation before more specialized graph algorithms.

Common Pitfalls

Do not use undirected degree logic on directed graphs.

Do not confuse a source with an isolated vertex.

Do not confuse a sink with an isolated vertex.

Do not assume a graph is connected because every vertex has nonzero degree. Two separate cycles each have degree two at every vertex, but the graph is still disconnected.

Do not omit isolated vertices from the representation. If they are missing from the graph dictionary, component counting and connectivity tests will be wrong.

Do not treat weak connectivity and strong connectivity as interchangeable. They answer different questions.

Takeaway

Degree describes local graph structure; connectivity describes global graph structure. In undirected graphs, degree and connected components are often the first tools used to understand the network. In directed graphs, in-degree, out-degree, weak connectivity, and strong connectivity provide separate views of flow and reachability. These measurements are simple to compute, but they are central to topological sorting, component decomposition, Euler paths, network analysis, and graph validation.