solved using permutation and combination , explaning with an example 8 1 2 r 2 3 b 3 4 b 4 5 b 5 6 r 6 7 b 7 8 r

lets say there are n nodes

First find groups of nodes with direct connected black edges, so for above example

multi_edge_grp = 1 group with 4 nodes :- 2,3,4,5 (lets say there are q groups with diff nodes count (qc))

single_edge_grp = 1 group with 2 nodes :- 6,7 (lets say there are p groups with 2 nodes)

calculations:-

total_no_of_tuples = nC3

single_edge_grp_invalid_tuple_count = p * (n - 2)C1

multi_edge_grp_invalid_tuple_count = Σ(over q) [ qcC2 * (n - 2)C1 - qcC2 * (qc - 2)C1 + qcC3]

total_valid_tuples = total_no_of_tuples - (single_edge_grp_invalid_tuple_count + multi_edge_grp_invalid_tuple_count)