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.

  • $\begingroup$ Hint: A vertex of degree $d$ in $G$ has degree $n-1-d$ in $\overline G$. $\endgroup$ – Quimey Jun 2 '14 at 19:21

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.