What conditions must eigenvalues satisfy for degenerate states? Due to comments below this answer I note the term "degenerate states" was subjective so firstly I'll give a formal definition: 

Degenerate states results when two (or more) different eigenstates to an eigenvalue equation correspond to the same eigenvalue. 

I'm tasked with the following question on a problem sheet set by my lecturer:

Do degenerate states always have the same energy?

The answer given was:

False (they have the same eigenvalue of any operator, not necessarily energy)

My interpretation of the quotation above is as follows: The eigenvalues of any operator can be the same but the energy can be different. At the moment it is my understanding that Eigenvalues=Energy Eigenvalues=Energies. Is there a distinction between these terms when considering the Hamiltonian? If my interpretation of the answer is wrong could someone please explain what the correct interpretation is? If you are able to do this there is no need to read any more of the content below until you reach the line, where below is my main question.
I do not understand how this answer can be false, so I will use the eigenvalues to the two dimensional Simple Harmonic Oscillator as an example that I believe contradicts the answer statement:
The TISE eigenvalue equation for the SHO is 
$$\hat Hu(x,y)=\left[-\frac{\hbar^2}{2m}\left(\frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}\right)+\frac{m\,{\omega_{x}}^2x^2}{2}+\frac{m\,{\omega_{y}}^2y^2}{2}\right]u(x,y)=E\,u(x,y)\tag{1}$$
Using separation of variables $u(x,y)=X(x)Y(y)$ such that $(1)$ becomes
$$-\frac{\hbar^2}{2m}\left(Y\frac{\partial^2X}{\partial x^2}+X\frac{\partial^2Y}{\partial y^2}\right)+\frac{m\,{\omega_{x}}^2x^2}{2}XY+\frac{m\,{\omega_{y}}^2y^2}{2}XY=EXY$$
and dividing throughout by $XY$ gives 
$$\left(-\frac{\hbar^2}{2m}\frac{1}{X}\frac{\partial^2X}{\partial x^2}+\frac{m\,{\omega_{x}}^2x^2}{2}\right)+\left(-\frac{\hbar^2}{2m}\frac{1}{Y}\frac{\partial^2Y}{\partial y^2}+\frac{m\,{\omega_{y}}^2y^2}{2}\right)=E$$
Where $E=E_x+E_y$, I can now write equations involving $x$ and $y$:
$$-\frac{\hbar^2}{2m}\frac{\partial^2X}{\partial x^2}+\frac{m\,{\omega_{x}}^2x^2}{2}X=E_xX\tag{a}$$
$$-\frac{\hbar^2}{2m}\frac{\partial^2Y}{\partial y^2}+\frac{m\,{\omega_{y}}^2y^2}{2}Y=E_yY\tag{b}$$
Since $(\mathrm{a})$ and $(\mathrm{b})$ are one dimensional SHO eigenstate equations in $x$ and $y$ respectively; then we immediately know the eigenvalues:
$$E_x=\left(n_x + \frac12\right)\hbar\,\omega_x\quad\text{&}\quad E_y=\left(n_y + \frac12\right)\hbar\,\omega_y$$ 
Hence, the total energy $E$ is 
$$E=E_x+E_y=\left(n_x + \frac12\right)\hbar\,\omega_x+\left(n_y + \frac12\right)\hbar\,\omega_y\tag{2}$$
So we now need two quantum numbers $n_x$ and $n_y$ to label eigenstates $$u_{{n_{x}}{n_{y}}}\equiv u_{n_{x}}(x)\,u_{n_{y}}(y)\tag{c}$$
Now suppose we are given a Central Potential such that $\omega_{x}=\omega_{y}=\omega_0$ 
Then
$$V(x,y)=\frac{m\,{\omega_{x}}^2x^2}{2}+\frac{m\,{\omega_{y}}^2y^2}{2}=\frac{m\,{\omega_0}^2(x^2+y^2)}{2}=\frac{m\,{\omega_0}^2r^2}{2}=V(r)\tag{3}$$
As a result of $(2)$ and $(3)$ the energies are now given by
$$E=E_x+E_y=(n_x+n_y+1)\hbar\,\omega_0$$
The ground state clearly has $n_x=n_y=0$, for which $E_0=\hbar\,\omega_0$. However, there are now two first excited states, given by $n_x=1,n_y=0$ and $n_x=0,n_y=1$, both of which have $\fbox{$\color{blue}{E_1=2\hbar\,\omega_0}$}$. So from the definiton $(\mathrm{c})$ I have two degenerate states: $u_{10}$ and $u_{01}$ with eigenvalue equations 
$$\hat H u_{10}=E_1 u_{10}$$
and 
$$\hat H u_{01}=E_1 u_{01}$$
So I have found a case where same eigenvalues $E_1$ are the same energy.
Is this just a one-off coincidence, or can anyone provide me with an example where the energies are different but the Eigenvalues are the Same?

More importantly suppose we have a free particle with $$E=\frac{{\hbar}^2 k^2}{2m}$$
and a wavefunction $\psi$ satisfying 
$$\frac{d^2 \psi}{dx^2}+k^2\psi=0\tag{4}$$
$(4)$ has two possible solutions:
$$\psi_1(x)=Ae^{ikx}\quad\text{and}\quad\psi_2(x)=Ae^{-ikx}$$
Applying the momentum operator 
$$\hat p=-i\hbar\frac{d}{dx}$$ to the two wavefunctions that solve $(4)$ gives for $\psi_1(x)$
$$\hat p\psi_1(x)=-i\hbar\frac{d}{dx}\left(Ae^{ikx}\right)=-i\hbar(ik)Ae^{ikx}=(\hbar k)Ae^{ikx}=\color{red}{(\hbar k)}\psi_1(x)$$
Similarly for $\psi_2(x)$
$$\hat p\psi_2(x)=\color{red}{-(\hbar k)}\psi_2(x)$$
So I have two degenerate states: $\psi_1(x)$ and $\psi_2(x)$ that apparently share eigenvalues. 
But $$\color{red}{\hbar k} \ne \color{red}{-\hbar k}$$ If the eigenvalues are different how can the states be degenerate? 
Or put in another way; since $\psi_1(x)$ and $\psi_2(x)$ no longer have the same eigenvalue this violates the definition of degenerate states in the first quotation at the beginning of this post.  

EDIT:
It was my understanding that the minus sign belongs to the eigenvalue.
Do we simply consider the absolute value of the eigenvalue so that $\color{red}{\hbar k}$ will be the same for $\psi_1(x)$ and $\psi_2(x)$?
 A: 
Question: do degenerate states always have the same energy?

The answer depends on what one means by degenerate. This word typically means two or more states with the same energy, in which case the answer is trivially yes.
On the other hand, it seems that according to your professor, degenerate means two or more states that share the eigenvalue with respect to some operator. This definition is not particularly useful, because all states are eigenvectors of the identity, with eigenvalue one, which means that all states are degenerate. And even if we restrict ourselves to operators other than the identity, the notion of degenerate is still trivial, because one may consider arbitrary projectors of the form $$P=|\varphi_1\rangle\langle\varphi_1|+|\varphi_2\rangle\langle\varphi_2|$$
which would make $\varphi_1,\varphi_2$ degenerate, for any pair of states $\varphi_1,\varphi_2$. In this sense, this definition of degenerate is vacuous.
Finally, if by degenerate we mean eigenvectors that share the eigenvalue with respect to a particular operator $A$ (fixed, i.e., not arbitrary), then the question becomes more interesting: given a pair of states $a_1,a_2$, such that
$$
\begin{aligned}
A|a_1\rangle&=a|a_1\rangle\\
A|a_2\rangle&=a|a_2\rangle
\end{aligned}
$$
then do we necessarily have
$$
\begin{aligned}
H|a_1\rangle&=E|a_1\rangle\\
H|a_2\rangle&=E|a_2\rangle
\end{aligned}
$$
for some energy $E$?
The answer is not necessarily, as can be seen by constructing simple counter-examples.
A: The most common reference to the word 'degenerate' is when we refer to the energy eigenstates. If the eigenvalue of the energy operator is same for more than one state of the system, such states are called degenerate. 
\begin{aligned}
H|a_1\rangle&=E|a_1\rangle\\
H|a_2\rangle&=E|a_2\rangle
\end{aligned}
There is also a different definition of degenerate, in a general sense. 
If two or more eigenstates for some fixed("given") operator say A have the same eigenvalue, then those states are called as degenerate. The interesting observation about eigenstates is that if you have two eigenstates say,  \begin{aligned}
|a_1\rangle, |a_2\rangle
\end{aligned}
for some observable A, then any linear combination of them is also an eigenstate and hence, we have a 2 dimensional eigenspace, and we have a degree of freedom in the choice of the two eigenvectors from the eigenspace. Similarly, the more the degeneracy, the higher the dimension of the eigenspace. 
Okay, now let's suppose you want to uniquely specify a quantum state. What do you do?
This is how we can do it :- 
1) You find the eigenvalues corresponding to some observable,(say X) but it turned out to show degenerate values for some of it's eigenstates. Hence, just labeling the states using only X is not enough to distinguish the states uniquely.
2)You find another observable which commutes with X,(say Y) so that it has the same set of eigenvectors as X. The eigenvalues of this operator provided unique values for some of the eigenvectors and hence, a greater number of states can 
now be uniquely specified but suppose there are still eigenvectors which are degenerate that is have the same eigenvalue for both X and Y. What do we do?
We execute step 3.
3)Find another such commuting observable and keep on doing so till every eigenstate can be labeled uniquely. This is why we say that in QM, the state of any system is specified by the Complete set of Commuting Observable's. 
The above mentioned thought process was carried out to show the role of degeneracy and what it exactly is, in a general sense.
There is much more to degenracy than just this. For example, Symmetry of a system with respect to some observable results in degenrate states of that observable.
As I am a 2nd year undergrad. Hence, some of the things mentioned might be wrong. If anyone wants to correct or add something, feel free to do so. I love critics. They help us be better versions of ourselves!! 
