0 votes 0 votes A Connected Graph has Cut edge, Then Graph has Cut vertex also. 1. True 2. False Choose Correct One. Graph Theory graph-theory engineering-mathematics + – parthbkgadoya asked Jan 20, 2017 parthbkgadoya 4.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 0 votes 0 votes True. If a graph has a cut edge then there is definitely a cut vertex but vice versa is not true. Ashwani Kumar 2 answered Jan 20, 2017 selected Jan 21, 2017 by Sushant Gokhale Ashwani Kumar 2 comment Share Follow See all 4 Comments See all 4 4 Comments reply Wanted commented Jan 26, 2017 reply Follow Share can u give example of viceversa ? 0 votes 0 votes shruti pujar commented Feb 2, 2017 reply Follow Share 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. 0 votes 0 votes Prashank commented Jun 6, 2018 reply Follow Share 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. 1 votes 1 votes Urvesh commented Aug 9, 2022 reply Follow Share @Prashank same question because everywhere this statement is given "whenever cut edges exist, cut vertices also exist because at least one vertex of a cut edge is a cut vertex." But this statement is not valid for K2 0 votes 0 votes Please log in or register to add a comment.