Consider the $9$-digit integers; there are $9\cdot 10^8$ of them. For each of them, consider the set made of the $10$ integers obtained by appending a last digit from $0$ to $9$. If we select more than $9\cdot 10^8$ $10$-digit integers, two of them will belong to the same set, thus differ in just the last digit, thus being neighbours. On the other hand, we can select $9\cdot 10^8$ mutually non-neighbouring $10$-digit integers by attaching to each $9$-digit integer as last digit the residue of the sum of its digits modulo $10$. A more difficult problem, based on the same idea, was Problem 3, 2008 Zhautykov http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1013356&sid=d634fb78f9db26fe9f08ada332d3b643#p1013356.