# Relation between vertex connectivity and independent set

What is the relationship between vertex connectivity and independent set of a connected graph?

Suppose we have a graph on $$20$$ vertices which is connected.

If the independent set has cardinality $$3$$ what can we conclude about the vertex connectivity of the graph?

Another question :

Is there any algorithm to find the separating set of a graph?

Given a graph $$G$$ does there exist any command in SageMath or in any other software which can say the minimum separating set of a graph?

• When you say "independent set", do you mean "maximal independent set"? – M. Winter Aug 5 '19 at 6:12
• @M.Winter; not exactly ! I meant minimal independent set – Math_Freak Aug 5 '19 at 13:59
• Ok, it seems you do not mean "cardinality-wise minimal independent set", as this would be the empty set, which is independent and certainly minimal in size. What do you mean then? – M. Winter Aug 8 '19 at 8:00

## 1 Answer

Addressing just this:

"Given a graph 𝐺 does there exist any command in SageMath or in any other software which can say the minimum separating set of a graph?"

This set is known as a minimum vertex cut.

For the icosahedral graph $$G$$ below, Mathematica's FindVertexCut[G] yields {3, 5, 6, 9, 10}, which surround and isolate vertex $$1$$.