MathDB

We say that the prime numbers

p_1,\dots,p_n

construct the graph

G

if we can assign to each vertex of

G

a natural number whose prime divisors are among

p_1,\dots,p_n

and there is an edge between two vertices in

G

if and only if the numbers assigned to the two vertices have a common divisor greater than

1

. What is the minimal

n

such that there exist prime numbers

p_1,\dots,p_n

which construct any graph

G

with

N

vertices?

Problem Statement