Given a partition of an integer $N$, its $P$-graph is the graph whose vertices are its parts, two of which are joined by an edge if and only if they have a common divisor greater than one (i.e. they are not relatively prime).


For an integer $N$, let $k(N)$ be the least number such that a graph on $k(N)>1$ vertices exists that is the P-graph of exactly one partition of $N$ into $k(N)$ parts. It has been shown, for example, that $k(200)=6$. Determining $k(N)$ in general seems hopeless, but perhaps satisfactory estimates can be found. In particular, how big is, say, $k(1000)$? Less than $12$, as estimated by this proposer?



Least number of vertices in a graph with which one can uniquely recover some partition of N
Old $13$-graph solution put at the bottom.


Edited to add: I think I've found a $11$-vertex $P$-graph that is unique: $187, 143, 91, 133, 95, 85, 87, 69, 46, 58, 6$.


This has a $P$-graph with a $6$-cycle and a $4$-wheel. Proof it's unique:


Assume we have a partition with this $P$-graph. This graph has an odd number of vertices, so there are an odd number of parts in the partition, so the number of even parts of the partition must be odd. As the largest clique in this graph is a triangle, $2$ either doesn't appear as a connecting prime, or it appears as a triangle. In the former case, a version of the AM-GM argument below shows the total would be too large. As such, $2$ must be one of the triangles in the $4$-wheel. 


We now ignore the center of the $4$-wheel temporarily, and consider the rest: a $4$-cycle with a $2$, and a $6$-cycle. The goal is to minimize the total from them.


Assume the $29$ is in the $6$-cycle. Then we could decrease the total by "breaking" the $6$-cycle next to the $29$ (on either side), breaking the $4$-cycle (on either side of the $2$), and connecting them, with the $29$ next to the $2$. This will give us a $10$-cycle, which must have total at least $1002$, which is too large. 


Similar reasoning puts $23$ on the other side of the $2$, and $3$ across. The filling of the $6$-cycle goes similarly. A generalization of this argument should show that the minimal sum of products from cycles comes from putting together $4$-cycles, with one "extra" cycle; these get filled in sequentially, starting with the most extreme to the least extreme. I don't think there is necessarily any restriction on where the "extra" cycle goes in the sequence, though.


This gives us a total of $994$. Remembering the center of the "wheel", we can now see that it must be divisible by at least $2$ primes, so it must be at least $6$. This gets us to $1000$, so we are done.


Along with @BrianHopkins modified $11$-graph, I think we've likely reached as small as we can get. Here's why:


The most effective technique so far seems to be to find some graph that has a minimum total near $1000$ (possibly using a parity criterion), and then adding to it to get to $1000$ exactly. It is possible to get a (slightly low) estimate for this total using the AM-GM inequality:


Let $k$ be the number of vertices in the "initial graph", and let $n$ be the minimum number of connecting primes in that graph. The product of all of the numbers at the vertices (the elements of the partition) is then at least the square of the product of those primes. The geometric mean is then the $k$th root of that square; the arithmetic mean must be at least as large, so the total is at least


$$\left( \prod\_{i=1}^n p\_i \right)^{\frac{2}{k}} k$$


This estimate is usually pretty good (low by ~50), as long as the cliques for each prime don't get too large (which may be the next avenue to check). We therefore want to know for which $n,k$ this is near, but below, $1000$.


For $k = 5$, the best $n$ is $7$, with an estimate of around $960$. This is too many edges to not form a triangle; there is no way to force $7$ connecting primes.


For $k=6$, the best $n$ is $7$, with an estimate of around $480$. Interestingly, the "odd-only" version is just over $1000$.


For $k=7$, the best $n$ is $8$, with an estimate of around $694$.


For $k=8$, the best $n$ is $9$, with an estimate of around $978$. This estimate is likely too large to allow a solution under $1000$, given all the approximations used. However, the $n=8$ odd-only version (estimate $824$) is what inspired my original answer.


For $k=9$, the best $n$ is still $9$, with an estimate of around $645$. 


For $k=10$, the best $n$ is $10$, with an estimate of around $918$. This is the solution that underlies both my and @BrianHopkins answer.


As we have a solution for $11$, we don't need to go any further.


So if there is a smaller solution, my guess is that it will require some newer, slicker technique. 


I did find a modification of this technique that may be useful: adding "tails" to graphs can make the minimum total higher, effectively by forcing larger differences between vertices. This modifies the above formula by allowing one of the prime factors to only appear once, rather than twice.


A graph that might be helpful: take a $6$-cycle and add a lengh $2$ "tail" at one vertex. If the $8$ connecting primes are odd, I think the minimum is $964$. I think it may be possible to get a $9$-graph with this, though adding an isolated point doesn't work. 


Similarly, $K\_{2,3}$ with a length $2$ "tail" at one of the $3$ vertices of degree $2$ can be under $1000$ (I got $903$ as a minimum), with no parity condition. I'm guessing this is the best chance for a smaller graph using this technique.


The "theta-hexagon" with a single tail seems possible; the minimum I got was $911$.


The odd-only two-tailed pentagon can get $939$.


Old $13$-graph:


Consider the $13$-vertex graph consisting of one $8$-cycle, one complete $4$-graph, and a singleton. This is a $P$-graph for $1000$ with the partition $115, 85, 187, 143, 91, 133, 57, 69, 29, 29, 29, 29, 4$. I claim this is the only such partition.


Proof: Take a partition with this graph. Because the number of vertices is odd, the number of even elements of the partition must be odd. $2$ correspondingly can only appear in edges that are parts of triangles - so it is a "connecting prime" in the complete $4$-graph, or not at all. Most importantly, it doesn't appear in the $8$-cycle.


The $8$-cycle must then use $8$ odd connecting primes. Simple construction shows the total for the $8$-cycle must be at least $880$ (which is reached by the solution above) - so the total for the $4$-graph must be less than $120$. Furthermore, the primes $3, 5, 7, 11, 13, 17$ must be there for the total to remain below $1000$, as the minimal total for $3, 5, 7, 11, 13, 19, 23, 29$ is exactly 1000. 


A parity argument shows that at least one of the elements at the vertex of the $4$-graph must be odd. Then as $19\*23>120$, the primes connecting to that vertex must all be the same - so the entire $4$-graph must be divisible by that odd prime, and that prime is at least $19$. The total from the $4$-graph is therefore at least $76$. Then the total in the $8$-cycle is at most $924$. This implies that the $8$-cycle must have the lowest $8$ primes $3, 5, 7, 11, 13, 17, 19, 23$, and the prime in the $4$-graph must be at least $29$. 


The total from the $4$-graph is at least $116$, while the total from the $8$-cycle is at least $880$, and the total from the singleton is at least $1$. This clearly only leaves room for the singleton to be $4$.


