# Proving NP hardness about graph creation problem with triangle number

I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in the graph. Given the above constraints ($$n+1$$), I have to generate a graph that satisfies all the constraints.

I know that given nodes' degrees, it is possible to construct using Havel–Hakimi algorithm a graph satisfying node degrees. But I am not sure how to fulfill the total triangle count constraint and if it makes the problem NP-hard.

• Are nodes labelled? In other words, is the condition like a graph of three nodes $A,B,C$ and $B$ where the degree of $A$ is 1, degree of $B$ is 1 and the degree of $C$ is 0? Or is it like a graph of three nodes $A,B,C$ where the multi-set of degrees of $A,B,C$ is $\{0,1, 1\}$? Commented Jan 17, 2019 at 20:08
• @Apass.Jack I don't see how that makes the problem any different. Once you have a solution you can relabel the nodes any way you like. Commented Jan 17, 2019 at 20:39
• @TomvanderZanden Thanks. I lost my mind for a moment. Commented Jan 17, 2019 at 21:12
• I was thinking of simplifying the problem of creating a graph to creating a graph maximum possibles triangles. The addition of individual edge acts a value by increasing the number of triangles which turns out to be a supermodular function with obvious degree constraints. Is there any supermodular function that this problem can be reduced to? Commented Jan 18, 2019 at 0:19

This is just a begining of reflexion. I hope it will help. This is not a solution for the very general case but some points that can reduce the problem.

If you consider triangles as unique 3-cliques, you know how many triangles are provided by a k-clique:

• 3-clique : 1 triangle
• 4-clique : 4 triangles
• 5-clique : 10 triangles
• k-clique : C(k, 3) triangles

Thus the number of triangles you have to provide is a combination of these numbers: N = 1*a + 4*b + 10*c ...

You also know that building a clique requires nodes with sufficient neighboors. A k-clique requires k nodes having k-1 edges. And any node with only one edge cannot create any triangle.

On a short example : 10 nodes with (5, 5, 4, 4, 3, 3, 2, 2, 1, 1) edges. A 5-clique is not possible. I think this can do up to 12 triangles with 3 different 4 cliques (5, 5, 4a, 4b), (5, 5, 4a, 3a), (5, 5, 4b, 3b). The remaining (2, 2, 1, 1) cannot provide any triangle.