2 votes 2 votes Let G be a 3-regular graph and S be a minimum vertex cut of G with |S| = 5 The the size of smallest edge cut of G is _______ (A)4 (B) 5 (C) 6 (D) None of the above Graph Theory graph-theory discrete-mathematics graph-connectivity + – Manu Thakur asked Dec 3, 2017 Manu Thakur 1.2k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Anu007 commented Dec 3, 2017 reply Follow Share is it a or d? 0 votes 0 votes joshi_nitish commented Dec 3, 2017 reply Follow Share cut edge(edge connectivity) is always <= min degree cut edge(edge connectivity) = 3 // removing 3 edges from any vertex will disconnect the graph 2 votes 2 votes Manu Thakur commented Dec 3, 2017 reply Follow Share @nitish @anu answer was given 5, but as graph is 3 regular, then removal of 3 edges can disconnect the graph, right? 0 votes 0 votes Anu007 commented Dec 3, 2017 reply Follow Share Actually here vertex connectivity is 5 i dont know how it possible since we know: vertex connectivity <= edge connectivity <= min degree by this they give 5 .... but in 3 regular min degree is 3 so vertex connectivity cannot more than that 4 votes 4 votes srestha commented Dec 3, 2017 reply Follow Share I think cut edge 0 ans d) https://math.stackexchange.com/questions/457159/cut-vertices-and-cut-edges-did-i-answer-these-correctly 0 votes 0 votes joshi_nitish commented Dec 3, 2017 reply Follow Share given answer is wrong.. 0 votes 0 votes joshi_nitish commented Dec 3, 2017 reply Follow Share @srestha actually the intention of qsn was actually to ask cut set(group of edges) rather than cut edge(single edge) 0 votes 0 votes Anu007 commented Dec 3, 2017 reply Follow Share Manu small example is Peterson graph 3 regular + 10 vertex here vertex and edge connectivity is 3 https://math.stackexchange.com/questions/2195657/what-is-the-edge-connectivity-and-vertex-connectivity-of-the-petersen-graph 1 votes 1 votes Manu Thakur commented Dec 3, 2017 reply Follow Share thanks anu. 1 votes 1 votes Hemant Parihar commented Dec 3, 2017 reply Follow Share Another example is a Cubic graph with 8 vertices where every vertex has degree 3, Edge and vertex connectivity is also 3. 2 votes 2 votes Please log in or register to add a comment.