Prove that given graph consisting of vertices numbered with composite numbers is not eulerian We have the following graph definition:
$$V(G_n)=\{1\leq m\leq n : m = pq\}$$ (so vetices of $G_n$ are composite numbers)
$$E(G_n)=\{\{i,j\}:i\perp j\}$$ (so vertices $i,j$ are connected if and only if they are realtively primes)
The problem asks us to prove that $G_{1000}$ is not eulerian. So it seems easy - we only need to find two vertices, such that the parity of degree of first is different than that of the second (or - even simpler - find a vertex with odd degree). Unfortunately I've been struggling with finding such pair for quite some time now. Where should I look then?

Consider the prime $223$ , consider the neighbors of $2\cdot 223$, they are all the odd composite numbers except for $3\cdot 223$.
Consider the neighbors of $4$. They are all the odd composite numbers. These two sets differ by one element, hence vertices $4$ and $2\cdot 223$ have orders of distinct parity. This implies there is a vertex of odd order, so the graph is not Eulerian.
