We say that the prime numbers p1,…,pn construct the graph G if we can assign to each vertex of G a natural number whose prime divisors are among p1,…,pn 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 p1,…,pn which construct any graph G with N vertices? PuMACIndividual Finalsnumber theoryprime numbers