Four-Node Motif Count Lite

Problem

Count induced four-node paths P4 in an undirected graph with n nodes.

A P4 is a set of four nodes that induces exactly a path of length three: the induced degrees must sort to [1, 1, 2, 2] and there must be exactly three induced edges. edges is a list of [u, v] pairs.

Hint

The induced edge count and degree sequence together pin down the P4 shape.

Test cases

case 1

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

expected: 1

case 2

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

expected: 0

case 3

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

expected: 2

case 4

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

expected: 0

Starter codePython

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

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