45th Mongolian Mathematical Olympiad

Let us construct graph $G$ with vertices $a_1,a_2,...,a_{2009}$; if two numbers are not relatively prime, then connect them with an edge. Then, the resulting graph $G$ will not have a subgraph that has three vertices and a single edge, by the given of the problem. Therefore, vertices of the graph $G$ can be divided into disjoint sets of independent vertices. Hence, $G$ is a $k$-partite graph with $2009$ vertices. Each arbitrary set of independent vertices will contain no more than $49$ vertices. The least number of disjoint sets is $\frac{2009}{49}=41$. From each of the sets, select an element each, then $41$ numbers that are pairwise relatively prime can be selected.