1
$\begingroup$

Sir i recently started graph theory. Pls clarify my doubt. I understood the reason why edge connectivity is less than min degree(remove all vertices incident to min degree vertex). I have doubt in 2nd part of proof when given graph is not complete graph. Here Pls see case 2 in this link. https://www.imsc.res.in/~vikram/DiscreteMaths/2011/connectivity.pdf (in page num 2)

If graph is not complete then there exists x, y are vertices in S,S' respectively, so that xy is not edge. If that is the case why x and y are in edge set. In proof he says there is indirect path between x,y (x to x neighbour in S and then to y or x or y neighbour in S' and then to y). In this case, my edge set should consist of x neighbour(instead of x) in S to y or x to y-neighbour in S' instead of y. So x,y will not be part of S, S'. Edge set [S,S'] i am assuming as edges between S to S'. Actually i am confused here. Pls clarify my doubt

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.