The Gateway to Computer Science Excellence
+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 _______
(B) 5
(C) 6
(D) None of the above
in Graph Theory by Boss | 346 views
is it a or d?

cut edge(edge connectivity) is always <= min degree

cut edge(edge connectivity) = 3 // removing 3 edges from any vertex will disconnect the graph

@nitish @anu answer was given 5, but as graph is 3 regular, then removal of 3 edges can disconnect the graph, right?
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
given answer is wrong..


actually the intention of qsn was actually to ask cut set(group of edges) rather than cut edge(single edge)


Manu small example is Peterson graph 3 regular + 10 vertex here vertex and edge connectivity is 3

thanks anu.
Another example is a Cubic graph with 8 vertices where every vertex has degree 3, Edge and vertex connectivity is also 3.

Please log in or register to answer this question.

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
52,223 questions
59,811 answers
118,086 users