[Math] Show that $G$ contains two adjacent vertices $u$ and $v$ such that $\deg u + \deg v$ is even.

Question

Let $G$ be a nontrivial connected graph that is not bipartite. Show that $G$
contains two adjacent vertices $u$ and $v$ such that $\deg u + \deg v$ is even.

Progress

I know the $\deg(u)$ and $\deg(v)$ are either both even or odd and that this is going to be true because the graph is not bipartite, but I don't really know where to go to connect those two things.

Answer 1

If there are no vertices $u,v$ such that $\deg u + \deg v$ is even, let $U$ be the set of even-degree vertices and $V$ the set of odd-degree vertices. Then $(U,V)$ is a bipartition of $G$.