A vertex $v$ is an articulation point of a graph $G$ if the removal of $v$ disconnects the induced subgraph.

Alternate phrasing: When all cycles in the subtree of $w$ are within the subtree of $v$. This means that the backedges cannot go above $v$. If $w$ could build a cycle that goes above $v$, then $v$ would not be an articulation point, because it'll be involved in some cycle $v \mapsto w \mapsto \mapsto p \mapsto v$, which gives us an alternative path to reach $w$ even if $v$ is removed.One way to imagine this maybe to imagine $v$ as the new root, and the other stuff that's above $v$ to be to the left of $w$. That way, if we could go to $w$, we get a cross edge from the "new root"(v) and the "other section" (the part that's connected by a cross edge). If we prevent the existence of these "fake cross edges", we're golden, and $v$ is then an articulation point.

A biconnected component is a maximal subset of edges, such that the induced subgraph is biconnected. Vertices can belong to many components; Indeeed, articulation vertices are those that belong to more than one component.

Two edges belong to the same biconnected component iff there is a cycle containing both of them. [This lemma is silent about biconnected components of single edges]We show that a cycle is always contained in a single binconnected component. If a cycle contains edges from more than one biconnected component, then we can "fuse" the biconnected components together into a single, larger, biconnected component.

- The connectivity of a graph is the smallest number of vertices that need tobe deleted to disconnect the graph.
- If the graph has an articulation vertex, the connectivity is 1. More robustgraphs that don't have a single point of failure/articulation vertex aresaid to be
*binconnected*. - To test for an articulation vertex by brute force, delete each vertex,and check if the graph has disconnected into components. this is $O(V(V+E))$ time.

Joke: an articulate vertex is one that speaks very well, and is thus important to the functioning of the graph. If it is killed, it will disconnect society, as there is no one to fulfil its ability to cross barriers with its eloquent speech.

- If we think of only the DFS tree for a moment of an undirected graph and ignore all other edges, thenall interneal non-leaf vertices become articulation vertices, because theydisconnect the graph into two parts: the part below them (for concreteness,think of a child leaf), and the root component.

- Blowing up a leaf has no effect, since it does not connect two
*components*, a leaf only connects itself to the main tree.

- The root of the tree is special; If it has only one child, then it acts likea leaf, since the root connects itself to the only component. On the otherhand, if there are multiple components, then the root acts like an internalnode, holding these different components together, making the root anarticulation vertex.

- DFS of a general undirected graph also contains
*back edges*. These act assecurity cables that link a vertex back to its ancestor. The securitycable from`x`

to`y`

ensures that none of the nodes on the path`[x..y]`

can be articulation vertices.

- So, to find articulation vertices, we need to see how far back the security cables go.

```
int anc[V]; int dfs_outdeg[V];
void processs_vertex_early(int v) { anc[v] = v; }
void process_edge(int x, int y) {
if (dfsedge[x][y].type == TREE) { dfs_outdeg[x]++; }
// y <-*
// |
// BACK
// |
// x --*
if (dfsedge[x][y].type == BACK && (parent[y] != x)) {
if(entry_time[y] < entry_time[anc[x]]) {
anc[x] = y;
}
}
}
```

In a DFS tree, a vertex v (other than the root) is an articulation vertex iff v is not a leaf and some subtree of v has no back edge incident until a proper ancestor of v.

- Udi Manber: Introduction to algorithms: A creative approach.
- Steven Skeina: The algorithm design manual.
- Codeforces: problems to solve
- A2OJ articulation point problems
- INOI advanced graph algorithms