Using Graph Theory to solve an IMO 2021 problem

Question

Here is a question from IMO 2021:

Let $n>100$ be an integer. Ivan writes the numbers $n,n+ 1,\dots,2n$ each on different cards. He then shuffles these $n+ 1$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square.

Algorithm:

1. First find those duplets whose addition will lead to perfect squares.

2. Next try to form a bipartite graph from those duplets.

Proof to show: A bipartite graph is not possible.

Am I going correctly? Basically, I want to solve this using graph theory. It will be very helpful for me if I get some insight on how to approach this more accurately.

EDIT:- If I am able to check whether the graph is 2-colorable or not then my job will be done.

Taking an instance

It is not possible here to make different colors for adjacent.

Hence Proved

Answer 1

Hint:

You can find an odd cycle in the graph of the form $(2k^2-4k, 2k^2+1, 2k^2+4k)$.