Given a multiset (a set with repeated elements allowed) 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 35 edges. I've been told that no other partition of 100 has exactly the same P-graph. What is this mystery partition of 100?
Found by extensive computer search, the partition in question is $2,4,4,6,10,10,14,14,15,21$. The P-graph of this partition has exactly 35 edges. The computer search verified that no other partition of 100 has precisely this P-graph.
This is the P-graph of the partition and its complement.
My approach is a parity observation, and is helped by the fact that it is a multiset. Otherwise it would be a bit time consuming.
So, among 10 numbers, there can be ${10 \choose 2}=45$ pairs, that is, $45$ edges and there are only 35 edges, so that means we can find $10$ pairs only that have gcd $1$.
Now, if we let one of the numbers be $1$, then already $9$ edges go off from $45$, since gcd$(a,1)=1$ for any $a \in \mathbb{Z}$.
We need to let only one edge go off.
So among the remaining $9$ numbers that add up to $99$ we need to have two numbers that are relatively prime themselves, but not to the other numbers.
Since them sum is odd, there should be an odd number of odd numbers, so we simply take one odd number and a power of two (these two will have gcd 1) and try to make all the other numbers have both $2$ and some factor of this odd number in them.
A very intuitive construction is the following $\big\{4,10,10,10,10,10,10,10,25\big\}$. Here, only the pair $(25,4)$ has gcd $1$, and all the other pairs have either a $5$ or a $2$ common in them.
Check that $\big\{1,4,10,10,10,10,10,10,10,25\big\}$ is indeed a partition satisfying the given criterion.
