The sum of ten, not necessarily different, positive integers is 100. If placed adequately on the vertices of this graph, two of them will be joined by a line if, and only if, they have a common divisor greater than 1 (i.e. they are not relatively prime).
What are those ten integers?
Start by labeling as follows:
Solution process:
The only pairs of integers that could possibly be equal are $U$ and $X$, and $W$ and $Z$. This is because if two integers are equal to each other then they're certainly relatively prime to the same integers. Thus, for example, $Q \ne R$ because $R$ and $Y$ are not relatively prime but $Q$ and $Y$ are.
Unfortunately we can't automatically deduce that $U = X$ or $W = Z$. It may be possible that, without loss of generality, $U = X^k$ for some integer $k$, with a similar possible relationship between $W$ and $Z$.
Because $U$ and $X$ are only joined to each other, I suspect that each has only one prime factor (that is, each is some power of the same prime). Theoretically it's possible that, say, $U = pq$ for two distinct primes $p$ and $q$, but then no other vertex aside from $X$ can have $p$ or $q$ as a factor, and that seems very limiting since we're trying to sum to $100$.
I started by building systematically and had to adjust as I went along. My graph theory and number theory skills are rusty so if there's a more systematic way that doesn't involve guess-and-check, I don't know what it is.
First, $S,T,Y$ are all adjacent to each other (adjacent = "joined by an edge" in graph theory terms [edge = "line segment" in graph theory terms]), so $S,T,Y$ must have at least one prime factor in common. This common factor is $3$.
Since $S$ is adjacent to $V$, and $T$ and $Y$ are not, then $S$ must have a prime factor that $T$ and $Y$ do not. This factor is $7$.
Also, $Y$ is adjacent to $R$, while $S$ and $T$ are not. Thus $Y$ must have a prime factor that $S$ and $T$ do not. This factor is $2$.
$R$ must have another prime factor that no other vertex has yet, since $R$ is adjacent to $Q$ and no other vertex is adjacent to $Q$. This factor is $5$.
If we assume the simplest case, i.e., no powers of primes and just the primes themselves, then we have $Q = 5, R = 10, S = 21, T = 3, V = 7, Y = 6.$
Thus the total sum so far is $5+10+21+3+7+6 = 52$. This means we need $U+X+W+Z = 48$. What luck! $48 = 22 + 26 = 11 + 11 + 13 + 13$. Take $U = X = 13$ and $W = Z = 11$ and we get one possible answer:
If I understand correctly, there should be many solutions to this. Then again, English is not my native language. Clockwise, starting from the topmost left: 26, 16, 8, 8, 10, 10, 10, 2, 8, 2.
I assume that I am wrong since this seems very easy, so please do correct me and explain if I haven't understood.
