Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than 1, that is, they are not relatively prime.
The P-graph of a certain mystery partition of 100 has 10 vertices and 42 edges. I've been told that no other partition of 100 has exactly the same P-graph. What is this mystery partition of 100?
On
I assumed no repetitions in the partition and no self-loops in the graph and found none that satisfied the requirements.
If repetitions are allowed in the partition there are 2977866 possible partitions of length 10 to explore. Regardless, it then becomes unclear whether two vertexes with the same integer should be linked.
Regardless, here is a graph with repetition in the partition having $\{15,12,10,10,10,10,10,10,8,5\}$ having 42 edges:
The 10a, 10b, etc. distinguish nodes that correspond to the repeated element 10.
Here is the graph found by Smylic:
Bernardo shows that they are not isomorphic.
Let $G$ be the desired graph. We can consider possible $\overline{G}$ on 10 vertices with 3 edges. There are 5 of them: $(7K_1, K_3)$, $(6K_1,K_{1, 3})$, $(6K_1, P_4)$, $(5K_1, P_2, P_3)$ and $(4K_1, 3P_2)$.
If $G \cong \overline{(6K_1, P_4)}$ then partition is not unique: $$ \begin{align} 100 &= 2 + 20 + 15 + 3 + 6 + 6 + 12 + 12 + 12 + 12\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 12 + 12 + 18\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 12 + 24\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 18 + 18\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 6 + 30 \end{align}$$
There are exactly 3 pairs of relatively prime numbers: $2$ and $15$, $2$ and $3$, $20$ and $3$, because last $6$ numbers are divisible by $2$ and $3$, $2$ and $20$ are divisible by $2$, $3$ and $15$ are divisible by $3$, $15$ and $20$ are divisible by $5$.
The same for $G \cong \overline{6K_1, K_{1, 3}}$: $$ \begin{align} 100 &= 5 + 6 + 12 + 12 + 10 + 10 + 10 + 10 + 10 + 15\\ &= 5 + 6 + 6 + 18 + 10 + 10 + 10 + 10 + 10 + 15 \end{align}$$
If $G \cong \overline{(7K_1, K_3)}$ then each vertex of $7K_1$ should have at least $3$ prime divisors to have edge with each of 3 pairwise non-adjacent vertices of $K_3$. Therefore there are $7$ numbers in partition that are at least $30$ each. Then it is impossible to get sum of $100$.
If $G \cong \overline{(4K_1, 3P_2)}$ then at least $4$ of vertices of $3P_2$ should have at least $3$ prime factors each (different for each vertex) therefore maximum of them is at least $3 \cdot 5 \cdot 7 = 105 > 100$. So this graph gives no partition.
If $G \cong \overline{(5K_1, P_2, P_3)}$, there is a partition: $$100 = 10 + 10 + 21 + 14 + 15 + 6 + 6 + 6 + 6 + 6.$$ To prove it is unique for this graph let us note that each vertex should have at least $2$ prime factors and there are at least $4$ prime factors in total. As shown above it is possible to take $2, 3, 5$ and $7$ as prime factors and $5$ of $6$ pairs as values for vertices. Also it is easy to see that this way gives minimum sum of values. If we take another prime factors or more then $2$ prime factors for at least $1$ vertex then we get even greater sum. Therefore this partition is unique for its P-graph.