How do I find all cut vertices (aka articulation points) in a graph?

Question

Given a connected graph $G = (V,E)$, we say that a vertex $v \in V$ is a cut vertex of $G$ if the removal of $v$ from $G$ causes $G$ to become disconnected.

How can I find all cut vertices of a given graph using Mathematica? Apparently there was an ArticulationVertices function in Combinatorica, which the docs say has been superseded by FindVertexCut. However, this new function only finds one cut vertex (if one exists), where the old one found all of them.

I should note that I'm working with some code that uses native Graph objects, and would prefer not to have to deal with Combinatorica`Graphs if possible.

Answer 1

IGraph/M has the function IGArticulationPoints.

g = PathGraph[{1, 2, 3, 4}, VertexLabels -> "Name"]

IGArticulationPoints[g]
(* {3, 2} *)

---

Speed comparison with KVertexConnectedComponents[g,2] for tiny and huge graphs. The timings are for IGraph/M 0.1.5.

g = ExampleData[{"NetworkGraph", "CondensedMatterCollaborations2005"}];

{VertexCount[g], EdgeCount[g]}
(* {40421, 175692} *)

RepeatedTiming[IGArticulationPoints[g];, 2]
(* {0.064, Null} *)

RepeatedTiming[KVertexConnectedComponents[g, 2];, 2]
(* {0.13, Null} *)

g = PathGraph@Range[10];

RepeatedTiming[IGArticulationPoints[g];, 2]
(* {0.000078, Null} *)

RepeatedTiming[KVertexConnectedComponents[g, 2];, 2]
(* {7.0*10^-6, Null} *)

Answer 2

One (not particularly efficient) way that occurs to me is to first find the biconnected components of a graph g, for which there is a built-in function (KVertexConnectedComponents). Then, use the fact that a vertex is a cut vertex if and only if it appears in two biconnected components.

components = KVertexConnectedComponents[g, 2];
cutVertices = Flatten[Intersection @@@ Subsets[components, {2}]];