# 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).

• Do the pairs not on the same line have to be relatively prime? If not, you can just write 10 on all the dots. – Nautilus Apr 15 '17 at 14:19
• If I'm interpreting the question right, why can't I just fill all connected vertices with twos, and assign integers to the lone vertices to make the sum 100? – greenturtle3141 Apr 15 '17 at 14:19
• I have clarified the issue. – Bernardo Recamán Santos Apr 15 '17 at 14:25

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.
• "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." is not true. Consider a graph with vertices 6, 10, 15. Each prime generates a clique, but a clique doesn't necessarily share a prime. – Peter Taylor Apr 15 '17 at 23:17
• @Peter Taylor Yeah I forgot to consider that. – greenturtle3141 Apr 15 '17 at 23:27