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:
- The circuit rank is the number of edges that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components.
- The vertex connectivity is the number of vertices that have to be removed to make the graph disconnected.)