Cartesian Product Edge Count

Problem

Compute the number of edges in the Cartesian product G1 x G2 of two undirected graphs.

The product has n1 * n2 nodes and m1 * n2 + n1 * m2 edges. Return the count given the node counts and edge lists of the two factors.

Hint

Each edge of one factor is copied once for every node of the other factor.

case 1

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

expected: 7

case 2

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

expected: 1

case 3

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

expected: 2

case 4

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

expected: 7

Starter codePython

def cartesian_product_edges(n1, edges1, n2, edges2):
    # Your code here
    pass

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