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


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.