# Clique number and maximum clique of gcd-based graph

This is from my homework.

Let $$Q_n$$ be the graph with vertex set $$\{1, 2, \ldots, n\}$$. Two vertices are adjacent if and only if their greatest common divisor is $$1$$. Give the clique number of $$Q_{10}$$ and draw a maximum clique of it.

• Just draw $Q_{10}$.. – Berci May 21 at 14:57
• Hint: A maximum clique will be primes and $1$. – Thomas Andrews May 21 at 15:01

The clique number is $$5$$. Note that there can be at most one even number in a clique, as two even numbers would have a common factor of $$2$$. Also note that $$3$$ and $$9$$ cannot be in the same clique as $$3$$ divides both. So not all odd numbers can be used. This gives us a maximum bound of $$5$$ numbers in a clique. $$\{1, 2, 3, 5, 7 \}$$ suffices to show that this is possible.