Introduction

Generating a random graph is easy; generating one that is both simple and guaranteed to be connected takes more care. If you also want a target sparseness, the cleanest strategy is to build connectivity first and then add random edges until the desired density is reached.

Define the Constraints Clearly

A simple connected graph has three important properties:

• No self-loops
• No duplicate edges between the same pair of vertices
• Every vertex is reachable from every other vertex

Sparseness usually means the graph uses only a fraction of the possible edges. For n vertices, the maximum number of undirected simple edges is n * (n - 1) / 2. If you choose a density value p between 0 and 1, the target edge count is often computed as:

target_edges = round(p * n * (n - 1) / 2)

There is one important lower bound: a connected graph with n vertices needs at least n - 1 edges. So if your formula produces fewer than n - 1, you must raise the target to n - 1.

A Reliable Construction Strategy

The most practical algorithm has two phases.

First, create a random spanning tree. A spanning tree on n vertices is already connected and uses exactly n - 1 edges, which is the minimum possible for connectivity.

Second, add random unused edges until you reach the target edge count. Because you never remove tree edges, connectivity is preserved automatically.

This approach is simpler than repeatedly generating random graphs and rejecting disconnected ones. Rejection sampling becomes wasteful when the desired graph is sparse because many candidates will fail the connectivity test.

Runnable Python Implementation

The code below returns an undirected graph as an adjacency list. It uses a random parent assignment to create a spanning tree, then fills in additional edges from the remaining candidate pairs.

1import random
2from itertools import combinations
3
4
5def generate_connected_graph(num_vertices, density, seed=None):
6    if num_vertices < 1:
7        raise ValueError("num_vertices must be positive")
8    if not 0 <= density <= 1:
9        raise ValueError("density must be between 0 and 1")
10
11    rng = random.Random(seed)
12    max_edges = num_vertices * (num_vertices - 1) // 2
13    target_edges = round(density * max_edges)
14    target_edges = max(target_edges, num_vertices - 1)
15    target_edges = min(target_edges, max_edges)
16
17    edges = set()
18
19    # Build a random spanning tree by attaching each new vertex
20    # to one previously created vertex.
21    for vertex in range(1, num_vertices):
22        parent = rng.randrange(0, vertex)
23        edge = tuple(sorted((vertex, parent)))
24        edges.add(edge)
25
26    remaining_pairs = [
27        pair for pair in combinations(range(num_vertices), 2)
28        if pair not in edges
29    ]
30    rng.shuffle(remaining_pairs)
31
32    needed = target_edges - len(edges)
33    for edge in remaining_pairs[:needed]:
34        edges.add(edge)
35
36    adjacency = {vertex: [] for vertex in range(num_vertices)}
37    for u, v in edges:
38        adjacency[u].append(v)
39        adjacency[v].append(u)
40
41    for neighbors in adjacency.values():
42        neighbors.sort()
43
44    return adjacency, edges
45
46
47if __name__ == "__main__":
48    adjacency, edges = generate_connected_graph(8, density=0.3, seed=42)
49    print("Edge count:", len(edges))
50    for vertex, neighbors in adjacency.items():
51        print(vertex, "->", neighbors)

The tree-building step is what guarantees connectivity. The second step preserves simplicity because candidate pairs come from all possible vertex pairs that are not already present.

Why This Works

The spanning tree gives you a connected backbone. Every later edge only adds redundancy, never disconnects the graph, and never creates an invalid multi-edge because the implementation tracks edges in a set.

The resulting graph is random, but not uniformly random over all connected graphs with the same number of edges. That distinction matters in research settings. If you need an exact uniform sampler, the problem becomes more specialized and this simple construction is not enough.

For many engineering tasks, though, the algorithm is perfectly acceptable:

• Generating synthetic network topologies
• Creating test data for traversal algorithms
• Stress-testing pathfinding or connectivity logic
• Building random puzzle or simulation inputs

Verifying Connectivity

Even though the construction guarantees connectivity, a quick verification function is still useful in tests. A depth-first search is enough.

1def is_connected(adjacency):
2    start = next(iter(adjacency))
3    visited = set()
4    stack = [start]
5
6    while stack:
7        node = stack.pop()
8        if node in visited:
9            continue
10        visited.add(node)
11        stack.extend(adjacency[node])
12
13    return len(visited) == len(adjacency)

You can combine it with the generator:

adjacency, edges = generate_connected_graph(25, density=0.12, seed=7)
print("Connected:", is_connected(adjacency))

For test suites, this kind of assertion protects you from future refactors that accidentally break the construction logic.

Common Pitfalls

The biggest mistake is treating density as if any value between 0 and 1 is feasible for a connected graph. Very low densities can imply fewer than n - 1 edges, which is impossible once connectivity is required. Clamp the target edge count to at least n - 1.

Another common bug is forgetting to normalize undirected edges. If you store (u, v) and (v, u) separately, you can accidentally create duplicates. Always sort the pair or use a canonical representation before inserting into a set.

Some implementations also waste a lot of time by repeatedly sampling random pairs until the graph becomes connected. That approach gets slower as the graph fills up and as duplicate attempts increase. Starting from a spanning tree avoids that problem entirely.

Finally, do not assume this generator is uniformly random over all connected graphs with the same edge count. It is random, but the construction method biases the output. That is fine for many applications, but it should be stated honestly.

Summary

• A connected simple graph must contain at least n - 1 edges.
• The easiest robust approach is: build a random spanning tree, then add random unused edges.
• Tracking edges in a set prevents self-loops and duplicates.
• DFS or BFS is useful for verification even when the construction is theoretically safe.
• This method is practical for testing and simulation, but it is not a uniform sampler over all connected graphs.