For the graph below a Determine all the bridges b Determine

For the graph below (a) Determine all the bridges. (b) Determine all the cutvertices.

Solution

(a) Bridge: An edge e is said to be a bridge of a connected graph G if G- e is disconnected.

The Bridges in the given graphs are ab, cd,ef because if you remove any of the above edges then the resulting graph is disconnected.

(b)Cut vertices: A vertex v is said to be a cut vertex of a connected graph G if G- v is disconnected.

The cut vertices in the given graphs are b, c,d,e because if you remove any of the above vertices then the resulting graph is disconnected.