is it a or d?

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 _______

(A)4

(B) 5

(C) 6

(D) None of the above

The the size of smallest edge cut of G is _______

(A)4

(B) 5

(C) 6

(D) None of the above

+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

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

@srestha

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

52,223 questions

59,811 answers

201,020 comments

118,086 users