On cycles in the coprime graph of integers

  • Paul Erdős
  • Gabor N. Sarkozy


In this paper we study cycles in the coprime graph of integers. We denote by $f(n,k)$ the number of positive integers $m\leq n$ with a prime factor among the first $k$ primes. (If $6|n,$ then $f(n,2)={{2n}\over {3}} $.) We show that there exists a constant $c$ such that if $A\subset \{1, 2, \ldots , n\}$ with $|A| > f(n,2),$ then the coprime graph induced by $A$ not only contains a triangle, but also a cycle of length $2 l + 1$ for every positive integer $l\leq c n .$