Node Connectivity Min Cut Lite

Problem

Compute the vertex connectivity of a small undirected graph: the minimum number of nodes whose removal disconnects it (or leaves fewer than two nodes).

Try all removal sets of size 1, 2, 3, ... in order and return the first size that works. Return 0 when the graph is already disconnected or has at most one node. edges is a list of [u, v] pairs and n is small.

Hint

Removing all but one node always disconnects, so the search needs at most n - 1 vertices.

Test cases

case 1

in: [3,[[0,1],[1,2]]]

expected: 1

case 2

in: [3,[[0,1],[1,2],[2,0]]]

expected: 2

case 3

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]]

expected: 3

case 4

in: [4,[[0,1],[0,2],[0,3]]]

expected: 1

case 5

in: [5,[[0,1],[1,2],[2,0],[2,3],[3,4],[4,2]]]

expected: 1

Starter codePython

from itertools import combinations
def vertex_connectivity(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor