Perhaps I'm missing something but here is a quick proof
There are 16 distinct squares which are adjacent to either 1,2,3 or 4. This means that at least one of these squares will contain an integer which is greater than 19. Hence, one of 1,2,3 or 4 will be adjacent to an integer at least 16 greater.