Articulation Point Generator

What this generator does

Builds a connected undirected graph, finds every cut vertex with an iterative Hopcroft–Tarjan search, and reports how many components each one leaves when removed. The list is then re-derived the slow way — every node deleted in turn and the components counted — before it is shown.

How to use this tool

1. Choose how many nodes and how many edges beyond the minimum to connect them.
2. Try to spot the nodes whose removal would split the graph.
3. Generate and compare — each cut vertex shows how many pieces it leaves behind.
4. Lower the density to make cut vertices more common, raise it to remove them entirely.

Understanding the controls

How many nodes

Between 4 and 12. The exhaustive re-check removes every node in turn, which stays instant across the whole range.

Extra edge density (%)

Edges beyond the ones needed to connect everything. Sparse graphs are mostly cut vertices; dense ones usually have none at all.

Seed

Any word reproduces the same graph, so the same problem can be set and marked later.

Common use cases

• Teaching depth-first search and the low-link idea with a checkable answer
• Worked examples of single points of failure in a network
• Test instances for a biconnectivity implementation
• Showing why a redundant link removes a critical node
• Setting the same problem twice from a seed

How this generator works

The graph is built as a random spanning tree plus extra edges, which guarantees it starts connected. Depth-first search then records a discovery time and a low-link value for each node: a node is critical when some child's subtree has no edge climbing back above it, and the root is critical exactly when it has more than one search child. That root rule is the part most hand-written implementations get wrong, which is why the answer is checked against removal rather than against the algorithm.

Randomness and fairness

The graph is random; the cut vertices are computed and then proved. Seeded graphs reproduce exactly and are therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator is used.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• Undirected graphs only — the directed equivalent is a different decomposition.
• The graph always starts connected, so the count before removal is always one.
• Twelve nodes is the ceiling, which keeps the removal check instant.
• Nodes are labelled with letters rather than named, so the page stays about the structure.
• Nothing about the graph is kept — note the seed before you leave.

Privacy and your data

The graph and its cut vertices are computed entirely in your browser. Nothing about the problem or your seed is transmitted or kept.