Given an undirected graph with some cycles:
we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:
In this case, disconnecting a single vertex makes the graph acyclic.
- What is a term for the smallest number of vertices that must be "disconnected" like this, to make the graph acyclic?
- What is an algorithm for finding a smallest such set of vertices?
(I found some related concepts, but they are different: