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.

  • 2
    $\begingroup$ Just draw $Q_{10}$.. $\endgroup$ – Berci May 21 at 14:57
  • 1
    $\begingroup$ Hint: A maximum clique will be primes and $1$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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