The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+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
in Graph Theory by Boss (43k points) | 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
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.

Please log in or register to answer this question.

Related questions

+7 votes
1 answer
1
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
50,339 questions
55,765 answers
192,354 comments
90,815 users