Label the vertices (or nodes) of this graph with positive integers so that any two nodes are joined by a edge (or line) if and only if the corresponding integers have a common divisor greater than 1 (i.e. they are not relatively prime). Do so in such a way that the total sum of the 13 numbers is minimum.
My best (manually)
With a sum of
79623
Update:
An exhaustive search of all 28.74 billion distinct arrangements with the lowest primes in the center has confirmed that this is the optimal solution. The C code for this search can be viewed here.
Edit: I made an assertion previously about the minimum which turns out to be wrong due to a bug in my code. The strategy of Bass is the right one and using the reasoning of 2012rcampion, we must put the smallest numbers in the centre
Here is the best answer I have found so far using this strategy
For a total of
$79685$
Breaking these numbers into their prime factorisations looks as follows
It seems as though this is still not optimal, as suggested here so please feel free to keep investigating.
To get started, let's see what the final answer must look like:
Since there are no fully connected triangles in the graph, each edge must be represented by a distinct prime. That gives us this basic shape:
bd ar abc def fg pqr cehknq ghi op mno jkl ij lm(Each letter a-r is a distinct prime.)
Then, you take out a computer, and find the best assignment for a-r. I didn't, so I did this instead:
Take the primes from 2 to 61.
1. Put the six smallest primes in the middle.
2. Arrange the same on the concave corners so that the differences between "neighbours" are big.
3. Pair the smallest concave corners with the largest remaining primes.
4. Repeat.
5. For the points, pair small with big, and midsize with midsize
The basic idea is to avoid multiplying big by big, because that's what makes huge numbers fast. To further improve the result, steps 3 and 4 should really be combined, so that the products at the concave spots are as close to each other as possible, but that seemed too tedious to do by hand. (If you do that, the optimal order for step 2 might change, too.)
That gave me this:
61,17
37,47 2,61,37 13,41,17 31,41
7,47,23 2,3,5,7,11,13 3,59,31
53,23 5,53,29 11,43,19 19,59
29,43
Which, when multiplied out, looks like
1037
1739 4514 9061 1271
7567 30030 5487
1219 7685 8987 1121
1247
For a baseline sum of
1037 + 1739 + 4514 + 9061 + 1271 + 7567 + 30030 + 5487 + 1219 + 7685 + 8987 + 1121 + 1247 = 80965.
Using the labeling provided by Bass we have that the sum is equal to:
$$b d + a r + a b c + d e f + f g + p q r + c e h k n q + g h i + o p + m n o + j k l + i j + l m$$
We want to find an assignment of unique primes to the variables $a$ through $r$ such that the sum is minimized. It is easy to see that we must use the smallest 18 primes ($p_1=2$ through $p_{18}=61$) to minimize the sum, so the problem reduces to finding a permutation of the first 18 primes.
We can reduce the search space by testing what happens if we interchange two numbers. We'll assume we have the optimal solution, so any change will increase the sum (or keep it the same). For example, swapping $a$ and $b$ gives us
$$ b d + a r + a b c \leq a d + b r + a b c $$
(Note I have kept only the terms containing $a$ and $b$, as the others do not change.) We can reduce this to $b(d-r) \leq a(d-r)$. Since all the variables are positive and distinct, this means that either $b<a$ and $d>r$, or $b>a$ and $d<r$.
Doing this for an outer edge and its adjacent inner edge, $a$ and $c$ for example, gives us:
$$ c < a \equiv r < e h k n q \\ $$
Note the form of the second half, comparing one variable to the product of five variables. If we compare the largest prime, $p_{18}=61$, to the five smallest primes, $p_1 p_2 p_3 p_4 p_4=2\cdot 3\cdot 5\cdot 7\cdot 11=2310$, we can see that this inequality must always be satisfied. Therefore the first half must be true, and all outer edges must be larger than their adjacent inner edges.
Swapping an outer edge and a non-adjacent inner edge, e.g. $a$ and $e$, gives:
$$ e < a \equiv b c + r < d f + c h k n q $$
To see if we can violate the right-hand inequality we'll ignore the uniqueness constraint between terms and test $p_{18}c + p_{18} < p_1 p_2 + c p_1 p_2 p_3 p_4$, i.e. $61c+61<6+210c$, which yields $c>\frac{55}{149}$. Since $c$ must be at least $p_1=2$, this inequality cannot be violated. Therefore, all outer edges must be larger than all inner edges.
This confirms that hexomino's answer is optimal.
I have got a slightly lower answer than either @hexomino or @FreddyBarrera in this question. @DanielMathias did an exhaustive search and found one slightly better (I confess I didn't even try the exhaustive approach once I ballparked how many permutations there were).
My answer is: 79627
\begin{align} a &= 7\\ g,h &= 23,43\\ b &= 5\\ i,j &= 31,47 \\ c &= 13 \\ k,l &= 29,19 \\ d &= 2 \\ m,n &= 59,61 \\ e &= 11 \\ o,p &= 17,37 \\ f &= 3 \\ q,r &= 41,53\\ \end{align}
Then
$abcdef + agh + bij + ckl + dmn + eop + fqr + hi + jk + lm + no + pq + rg = 79627$
But, you may ask, how did I find this marvel of optimization?
I'm glad you asked. :-)
My intuition told me that we need to balance the "middle" nodes (agh,bij,ckl,...). The product of all these numbers is simply the product of the first 18 primes or 117,288,381,359,406,970,983,270. The 6th root of this is about 6996. So I figured that picking triplets such that the product was close to 6996 would be a winning idea.
So I generated all the triplets and ordered them by how far the product was from 6996.
eg
5, 23, 61, 19
7, 17, 59, 25
7, 19, 53, 53
7, 23, 43, 73
11, 17, 37, 77
13, 17, 31, 145
3, 43, 53, 159
13, 19, 29, 167
5, 29, 47, 181
2, 59, 61, 202
5, 23, 59, 211
3, 37, 61, 225
...
where the first three are the primes and the 4th is the absolution value of the product minus 6556.
Then I treated these as nodes in a maze and used dijkstra's algorithm to find the shortest route (using the abs(product-6996) as the distance to each node).
This led to:
[[7, 23, 43], [11, 17, 37], [13, 19, 29], [2, 59, 61], [5, 31, 47], [3, 41, 53]] (Total distance from 6996 is 1285).
Finally, I ran through the possible permutations (there's not too many) which led to the solution shown.
