Cut Space Dimension

Problem

Return the dimension of the cut space of an undirected graph:

n - c

where n is the number of vertices and c the number of connected components. This is the rank of the incidence matrix.

Hint

For a connected graph the cut space dimension is n - 1.

case 1

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

expected: 3

case 2

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

expected: 2

case 3

in: [5,[]]

expected: 0

case 4

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

expected: 3

Starter codePython

def cut_space_dimension(num_vertices, edges):
    # Your code here
    pass

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