Problem of the Week 1241

Petersen Graph with Small Labels

Show how to label the vertices of the Petersen graph with positive integers so that

1. a graph edge exists if and only if the labels of the two ends of the edge have a common divisor greater than 1, and
2. the sum of the 10 labels is under 100,000.

An interesting problem is to get this sum to be as small as possible.

The Petersen graph has 10 vertices and 15 edges; you can see it at MathWorld.

Source: Bernardo Recamán and Freddy Barrera, Colombia Aprendiendo, Bogotá, Colombia.

[View the solution]