Let ‘G’ be a connected graph. A vertex V ∈ G is called a cut vertex of ‘G’, if ‘G-V’ (Delete ‘V’ from ‘G’) results in a disconnected graph. Removing a cut vertex from a graph breaks it in to two or more graphs.
Note − Removing a cut vertex may render a graph disconnected.
A connected graph ‘G’ may have at most (n–2) cut vertices.
In the following graph, vertices ‘e’ and ‘c’ are the cut vertices.
By removing ‘e’ or ‘c’, the graph will become a disconnected graph.
Cut Edge (Bridge)
Let ‘G’ be a connected graph. An edge ‘e’ ∈ G is called a cut edge if ‘G-e’ results in a disconnected graph.
If removing an edge in a graph results in to two or more graphs, then that edge is called a Cut Edge.
In the following graph, the cut edge is [(c, e)]
By removing the edge (c, e) from the graph, it becomes a disconnected graph.