Proving NP hardness about graph creation
If you are given just the degree sequence (the number of neighbors of each vertex), then the Havel–Hakimi algorithm is an efficient algorithm that constructs a graph conforming to the degree sequence, if possible, and alerts you otherwise. If you are given the second-order degree sequence (the number of vertices at distance 1 and at distance 2 from each vertex), then the problem of determining whether such a graph exists becomes NP-complete, as shown by Erdős and Miklós in their paper Not all simple looking degree sequence problems are
easy.