How many vertices of odd degree are there in $\overline{G}$, the complement of graph G?

Question

Here's the full problem:

If a graph $G$ has n vertices (all of which but one have odd degree), how many vertices of odd degree are there in $\overline{G}$, the complement of $G$?

So what I originally thought was that, since $G$ has n-1 odd vertices and 1 even vertices, that $\overline{G}$ would have 1 odd vertices and n-1 even vertices. Talking to my friend, he told me this was not correct but was unable to figure it out himself (as a TA gave him the answer).

Can anyone explain why $G$ and $\overline{G}$ have the same parity in terms of degree? Have not had any luck finding such information in the book.

Answer 1

Hint $$\deg_G(v)+ \deg_{\overline{G}}(v)=n-1$$

Answer 2

let $G$ be a graph over $k$ vertices, we know the number of vertices of odd degree in any finite graph is always even. Since all vertices except one have odd degree we know $k$ is odd. If vertex $g$ has degree $d_g$ in $G$ then it has degree $(n-1)-d_g$ in $\overline G$. Thus if $g$ has odd degree in $G$ then it has odd degree in $\overline G$ (since $k-1$ is even) and if $G$ has even degree in $ G$ then it has even degree in $\overline G$.

Therefore $G$ and $\overline G$ have the same number of vertices with odd degrees and the same number of vertices with even degree