The vertices of the Petersen graph (or any other simple graph) can be labelled in infinitely many ways with positive integers so that two vertices are joined by an edge if, and only if, the corresponding labels have a common divisor greater than 1. (One such labelling is with the numbers 645, 658, 902, 1085, 1221, 13243, 13949, 14053, 16813, and 17081, whose sum is 79650). Of all such ways of labelling the Petersen graph, what is the minimum the sum of the 10 corresponding integers can be?

The reason to single out the Petersen graph over all other graphs of order ten or less is that it is one particularly difficult to label if one is trying to achieve the minimum sum. Is there some systematic why of finding that minimum other than brute force?

edgesby the 15 smallest primes. The Petersen graph has symmetry group $S_5$ so that means that there are, in principle, $15!/5!$ possibilities to check, which is probably still too much to check one by one by computer. $\endgroup$2more comments