Cycle Space Dimension

Problem

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

m - n + c

where m is the number of edges, n the number of vertices, and c the number of connected components. This is the nullity of the incidence matrix.

Hint

Every independent cycle contributes one dimension; a forest has cycle space dimension 0.

case 1

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

expected: 1

case 2

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

expected: 0

case 3

in: [5,[]]

expected: 0

case 4

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

expected: 2

Starter codePython

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

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