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. It has been shown (A labelling of the vertices of the Petersen graph with integers) that the smallest possible sum of these labels is 37294.

Petersen graph

Is there a largest number which cannot be the sum of the labels of the Petersen graph in such a labelling? If so, what is it?


1 Answer 1


I can prove that all sufficiently large integers are representable.

Firstly, observe that there is a unique way, up to isomorphism, to choose three edges $p, q, r$ of the Petersen graph such that the subgraph induced by their six endpoints is just the union of $p, q, r$.

Now, observe that we can write $2^{16}$ as the sum of semiprimes in three ways such that no prime is repeated:

$$ 101 \times 103 + 13 \times 4241 = 65536 $$ $$ 107 \times 109 + 17 \times 3169 = 65536 $$ $$ 3 \times 7 + 5 \times 13103 = 65536 $$

Label the other 12 edges of the Petersen graph with these 12 distinct primes, such that, for each edge $s \in \{p, q, r \}$, the sum (over both endpoints) of the products (over both incident edges excluding $s$) is equal to $65536$.

Moreover, do this labelling in such a way that the edges $5, 13, 17$ are incident at a vertex $v$.

Now, for each of the $2^{17}$ residue classes $R_i := \{ 2^{17}x + i : x \in \mathbb{N} \}$, we can find some $k_i \in R_i$ which is coprime to each of the aforementioned 12 primes (by Chinese Remainder Theorem). Let $K = \max \{ k_i : 0 \leq i < 2^{17} \}$ be a huge upper bound.

We're going to label each vertex with the product of the incident edges, with the exception of $v$ which will be labelled by $(5 \times 13 \times 17)k_i$ for some $i$. This means that we can attain any integer of the form:

$$ C + (5 \times 13 \times 17) k_i + 2^{16} (p + q + r) $$

for any $0 \leq i < 2^{17}$, where $C$ is a universal constant (the sum of the labels at the 3 vertices which are neither $v$ nor endpoints of $p,q,r$) and $p,q,r$ are distinct primes larger than $K$.

But by Vinogradov's theorem, any sufficiently large odd integer $N$ can be written as $p + q + r$ for three distinct primes larger than $K$ (because the number of representations asymptotically dominates $N^2$, so we can throw away the $O(N^2)$ representations involving repeated primes or primes beneath $K$).

So to represent an integer $I$, choose $k_i$ to make the following true:

$$ C + (5 \times 13 \times 17) k_i + 2^{16} \equiv I \mod 2^{17} $$

Then $I - C - (5 \times 13 \times 17) k_i = 2^{16} N$, where $N$ is a large odd integer expressible as the sum of three distinct primes larger than $K$. The result follows.

  • $\begingroup$ This settles in the affirmative the issue of the existence of a largest number which cannot be the sum of labels. What that largest number doesn't matter as much. $\endgroup$ Jun 6, 2017 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.