Disagreement with professor about Cauchy Sequence
A sequence $(a_n)$ is a Cauchy sequence if and only if for every $\epsilon\gt 0$ there exists an $N\gt 0$ such that for all $n,m\geq N$, $|a_n-a_m|\lt \epsilon$.
Because the condition must be met by all pairs $n,m$, provided only that they be large enough, you cannot establish this condition by checking only those pairs in which, say, $m$ is a function of $n$, $m=f(n)$.
What you wrote is insufficient: even if the difference between the $2n$th and the $(2n-1)$st term goes to zero, it is possible for the sequence to diverge (and hence not be Cauchy).
For a simple example, consider the sequence with $a_{2n}=n$ and $a_{2n-1}=n$. That is, the sequence is $1,1,2,2,3,3,4,4,5,5,\ldots$. This sequence is not Cauchy, but it still satisfies that $$\lim_{n\to\infty}(a_{2n}-a_{2n-1}) = 0.$$
More generally, you can always arrange for $|a_n-a_{f(n)}|$ to go to $0$, and yet for the sequence to diverge: just arrange for all those pairs to be equal, and yet for $a_n$ to get arbitrarily large for sufficiently large $n$.
As to the original problem, here is one way to do it: let $\epsilon\gt 0$. We know that there is an $N$ such that if $2n\gt N$, then $|a_{2n}-a|\lt {\epsilon}$. And we know that there is an $M\gt 0$ such that if $2n-1\gt M$, then $|a_{2n-1}-a|\lt \epsilon$.
Take $K=\max{N,M}$. Then if $r\gt K$, then either $r$ is even, in which case $r=2n\gt K\geq N$, so $|a_r-a|\lt \epsilon$; or $r$ is odd, in which case $r=2n-1\gt K\geq M$, so $|a_r-a|\lt\epsilon$. Either way, $|a_r-a|\lt\epsilon$ for $r\gt K$. Thus, we conclude that the sequence converges to $a$.
I think this example may get to the heart of the issue. Consider the truncated harmonic series $$H_n = \sum^n_{k=1} \frac 1 k.$$ We know that $\lim H_n =\infty$. However, we also see that $$H_{2n} - H_{2n-1} = \frac 1 {2n} \to 0.$$ To elaborate: clearly $H_n$ is not a Cauchy sequence, since it doesn't converge, and yet, if we fix $j \in \mathbb N$, we see that $$\lim_{n\to \infty} (H_{n+j} - H_{n}) = 0.$$ I believe this is what your professor means when he says that $n$ and $m$ cannot be related. To prove that $H_n$ is Cauchy, we need to fix $\epsilon > 0$ and find $N \in \mathbb N$ such that for all $n,m \ge N$, we have $$\lvert H_n - H_m \rvert < \epsilon.$$ As you have it written, it seems like you are fixing $\epsilon > 0$, finding $N \in \mathbb N$ and choosing a particular pair $n,m \ge N$ such that $\lvert H_n - H_m\rvert < \epsilon$, so the inequality will hold for this particular pair $n,m$ but will not hold for all $n,m \ge N$.
If this doesn't help, I would still encourage you to apply your exact line of reasoning to $H_n$ and see if your reasoning implies convergence, because if so, there is some mistake in the reasoning.
In general, I would say that any proof of this property that doesn't very critically invoke the fact that $x_{2n} \to a$ and $x_{2n-1} \to a$, is probably not the best proof. What I mean is: your proof should probably set $\epsilon > 0$ and explicitly take $N_1, N_2 \in \mathbb N$ such that for $n \ge N_1$ you have $\lvert x_{2n} - a\rvert < \epsilon$ and for $n \ge N_2$ you have $\lvert x_{2n-1} - a \rvert < \epsilon$, and work from there.
It seems like you've defined Cauchy sequence to mean $$\lim_{n\rightarrow\infty, m\rightarrow\infty}x_n-x_m=0.$$ This is indeed a correct definition, but it seems like you're a bit confused on how this expands formally. In particular, this statement is defined to mean:
For all $\varepsilon>0$, there exists an $N\in\mathbb N$ such that for all $n,m\in\mathbb N$ such that $n\geq N$ and $m\geq N$ we have $|x_n-x_m| < \varepsilon$.
Note that $n$ and $m$ cannot be assumed to bear any relation to each other, aside from both being large - any use of this definition would not repeat this statement, since it is implicit in the definition of the limit. This sentence is also sometimes directly taken to be the definition of a Cauchy sequence.
You've proven the weaker statement that
For all $\varepsilon>0$, there exists an $N\in\mathbb N$ such that for all $n,m\in\mathbb N$ such that $n\geq N$ and $m = n+1$, we have $|x_{2n}-x_{2n+1}| < \varepsilon$.
While you're correct that you haven't fixed any variables, you have assumed a relationship between them that you are not allowed to.
If your intention in using statements like $$\lim x_{2n}-x_{2m}=0$$ is to show that in the limit $\lim x_{2n}-x_{2n+1}$ one could safely replace one $n$ by an $m$ without changing the value, then it's worth noting that that can fix the argument. However, that's not a good way to fix it, because you have to be really careful about the formal meanings of such statements and you also must be careful that you truly have proven $\lim x_{2n}-x_{2m}=0$ because this statement is extremely similar to the one you are trying to prove in the first place.
More generally, this exercise is one that would be intended to be solved from elementary means because it is not onerous to do so. You are given the following from the limits:
For all $\varepsilon>0$, there is some $N_1,N_2$ such that if $n\geq N_1$ then $|x_{2n}-a|<\varepsilon$ and if $n\geq N_2$ then $|x_{2n+1}-a|<\varepsilon$.
You want to show:
For all $\varepsilon>0$, there is some $N$ such that if $n\geq N$, then $|x_n-a|<\varepsilon$.
These statements are fairly similar - figure out how to transform the knowledge of such an $N_1$ and $N_2$ into the $N$ you desire, rather than cobbling together algebraic manipulations that, ultimately, must still include a proof of a statement like this one.