+1 vote
259 views
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
| 259 views
0
is it a or d?
+2

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

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

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

@srestha

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

+1

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
thanks anu.
+2
Another example is a Cubic graph with 8 vertices where every vertex has degree 3, Edge and vertex connectivity is also 3.

1