Note that we can categorized those $2n$ positive integers based on their square-free part. The sufficient and necessary condition to the matching is so that no two numbers from the same group matched each other. We want to show that if there's one such matching, there're at least $S_n\geq n!$ where $S_n$ is the no. of non-square matching. For the prove, we can use induction on $n\in \mathbb{Z}^+$ that the proposition $P(n)$ is true: P(n) wrote: If there's one non-square matching, then $S_n\geq n!$, and for any two distinct group that can connect to each other, there are at least $n+1$ numbers that some non-square matching connect it to a vertex from those two groups, i.e. the no. ordered pairs of possible-neighbors whose one is from those two groups is at least $n+1$

ThE-dArK-lOrD wrote: Note that we can categorized those $2n$ positive integers based on their square-free part. The sufficient and necessary condition to the matching is so that no two numbers from the same group matched each other. We want to show that if there's one such matching, there're at least $S_n\geq n!$ where $S_n$ is the no. of non-square matching. For the prove, we can use induction on $n\in \mathbb{Z}^+$ that the proposition $P(n)$ is true: P(n) wrote: If there's one non-square matching, then $S_n\geq n!$, and for any two distinct group, there are at least $n+1$ numbers that some non-square matching connect it to a vertex from those two groups, i.e. the no. ordered pairs of possible-neighbors whose one is from those two groups is at least $n+1$. How to induction? Can you elaborate more pls?

Let's consider each positive integer an vertex $v_{1},v_{2},...,v_{2n}$ in graph $G$, and draw edge between $v_{i}$ and $v_{j}$ if product of the numbers is not a perfect square. In this case, $v_{k}$ must have at least one edge to $(v_{i},v_{j})$ which are adjacent each other. Otherwise, $v_{k}$ has same parity of exponents with $v_{i}$, $v_{j}$, which is contradiction. So we can prove this by induction of $n$. where $n=1$, it's trivial. Suppose that proposition holds where $n-1$. Without Loss of Generality, There is an non-square matching in such as $(v_{1},v_{2}),(v_{3},v_{4}),...,(v_{2n-1},v_{2n})$. As mentioned above, we could match $v_{2i-1}$ to $v_{2n-1}$ WLOG. If $v_{2i}$ has edge to $v_{2n}$, proof is completed because we can make new matching like $(v_{2i-1},v_{2n-1}),(v_{2i},v_{2n})$. If not, $v_{2i}$ is connected to $v_{2n-1}$, and $v_{2i-1}$ has edge to $v_{2n}$. In this case, there is new matching such as $(v_{2i-1},v_{2n}),(v_{2i},v_{2n-1})$. By induction, There are at least $n\cdot(n-1)!$ non-square matchings. So we're done.

I will say pair $(i,j)$ is good, if $i\cdot j$ is perfect square, and $(i,j)$ is bad otherwise. Let our initial numbers be $a_1,a_2,\cdots,a_{2n}$ and let $S_1=(a_1,a_2),S_2= (a_3,a_4),\cdots, S_n=(a_{2n-1},a_{2n})$ be non-square maching. The key part is that: $\mathbf{Claim:}$ If we take $2$ pairs, WLOG first to pairs, then both of $K_1=(a_1,a_3)$ and $K_2=(a_2,a_4)$ or both of $K_3=(a_1,a_4)$ and $K_4=(a_2,a_3)$ are good. $\mathbf{Proof:}$ Assume contrary. WLOG $K_1$ is bad. If $K_1$ and $K_3$ are bad, then $(a_3,a_4)$ is bad, which is contra. If $K_1$ and $K_4$ are bad, then $(a_1,a_2)$ is bad, which is contradiction again. So it's proved. Now I will use induction. Base case is obvious. Assume it's true for $n-1$. From $\mathbf{Claim}$ we get for each good $S_i,S_j$ we can create new good $S'_i,S'_j$ such that $S_i\cup S_j=S'_i\cup S'_j$. Now Let's make new match to $a_1$ from set $S_i$, $i\ne1$. Then remaining numbers can make at least $(n-1)!$ macthing. So we get $(n-1)\cdot (n-1)!$ new matching which is equal to $n!-(n-1)!$. Now fix $S_1$ and do same thing for $a_3$ and similarly we will get at least $(n-1)!-(n-2)!$ new matching. Continue doing this until end. So we will get at least $(n!-(n-1)!)+((n-1)!-(n-2)!)+\cdots +(2!-1!)=n!-1$ new matching. Also we have initial matchig $S_1,S_2,\cdots, S_n$. So we get at least $n!-1+1=n!$ matching desired.