2,583 views
A Connected Graph has Cut edge, Then Graph has Cut vertex also.

1. True

2. False

Choose Correct One.

### Subscribe to GO Classes for GATE CSE 2022

True.

If a graph has a cut edge then there is definitely a cut vertex but vice versa is not true.

by
37 89 187

can u give example of viceversa ?

## Cut Vertex

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.

### Example

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.

### Example

In the following graph, the cut edge is [(c, e)]

By removing the edge (c, e) from the graph, it becomes a disconnected graph.

I don't think it is true to consider that a graph having a cut edge will definitely have cut vertex.

Consider a graph with a single edge A------B, if we remove this edge graph will get disconnected but if we remove vertex A, a graph will be connected as a graph with the single vertex is still consider connected.