calculation puzzle - Labelling a graph with a partition of 100

Label the vertices of this graph with positive integers (repetitions allowed) whose sum is 100 in such a way that any pair of vertices are joined by an edge if (and only if) they have labels with a common divisor greater than 1 (i.e. they are not relatively prime).

Answer

My solution:

In text, that is represented as:

Starting from the lonely vertices and working clockwise: $1, 1, 42, 30, 7, 6, 5, 3, 3, 2$. For convenience, let us label these vertices A, B, C, D, E, F, G, H, I, J.

---

Logic

• For every $K_n$ subgraph (set of n vertices in which all vertices are connected to each other), it's vertices must all share a unique prime factor that no other vertex outside this set has (Edit: OK this isn't always true, but it does help to use each prime to fill in each $K_n$).


• Notice the $K_5$ subgraph (CDFHI). To minimize the sum, assign a factor of $2$ to each.


• Then, each vertex of the nearby $K_4$ (CDFJ) can be assigned factor of $3$, and the two $K_2$s (DG, CE) factors of $5$, and $7$, in some order (It won't matter: C and D are both part of the $K_5$ and $K_4$).



• This gives a sum of $97$, but we cannot get to $100$ with the last two vertices.


• Trying another path, we give the $K_5$ vertices a factor of $3$ instead, and the $K_4$ a factor of $2$.


• This bumps the sum to $98$, where we can now assign $1$s to the lone remaining vertices.