Graph theory / vertex-set list representation

Question

If I were to consider a graph with vertex-set V= {1, 2, 3, ... 10} with the edges taken as all the pairs {x, y} of distinct members of V that have a prime factor in common, how would one write the list representation of the graph? Any advice/help is appreciated.

Answer 1

Hint: Consider each number separately. What pairs $\{1,x\}$ have a prime factor in common? $1$ has no prime factors, so there is no such $x$. What pairs $\{2,x\}$ have a prime factor in common? $2$ is the only prime factor of $2$, so only even numbers would share a prime factor with $2$. So far we have:

$1 \rightarrow \emptyset$

$2 \rightarrow \{4,6,8,10\}$

You should continue in this manner. Of course if this is a homework problem, as I assume it is, you should consult your course notes or book for the preferred notation for adjacency list representation, since there isn't a standard notation.