search
Log In
0 votes
1.1k views
A Connected Graph has Cut edge, Then Graph has Cut vertex also.

1. True

2. False

Choose Correct One.
in Graph Theory 1.1k views

1 Answer

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
0
can u give example of viceversa ?
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
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.

Related questions

0 votes
0 answers
2
3 votes
3 answers
4
564 views
How to PROVE S2 is correct?? Consider the statements $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree $S_2$ ) A graph with $13$ vertices, $31$ edges, $3$ vertices of degree $5$ and $7$ vertices of degree $4$ does not ... true B). $S_1$ is true and $S_2$ is false C). $S_1$ is false and $S_2$ is true D). Both $S_1$ and $S_2$ are true
asked Jan 13, 2016 in Graph Theory Tushar Shinde 564 views
...