in Graph Theory
2,583 views
0 votes
0 votes
A Connected Graph has Cut edge, Then Graph has Cut vertex also.

1. True

2. False

Choose Correct One.
in Graph Theory
by
5 15 22
2.6k views

Subscribe to GO Classes for GATE CSE 2022

1 Answer

0 votes
0 votes
 
Best answer

True.

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

selected by
by
37 89 187

3 Comments

can u give example of viceversa ?
0
0

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.

Cut Vertex

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)]

Cut Edge

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

0
0
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.
0
0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true