Prove that if G contains an odd vertex then every vertex of G is odd Let G be a graph with degree of each vertex either $m$ or $n$, where there are $m$ vertices of degree $m$ and $n$ vertices of degree $n$. Prove that if G contains an odd vertex then every vertex of G is odd.
how do I go about this? What does it imply if G contains an odd vertex? Also, how am I to use the first line of the given problem? Please help.

How many edges are there in $G$, in terms of $m$ and $n$? Well, there are $m$-many vertices with $m$-many edges coming out, and $n$-many vertices with $n$-many edges coming out; and this double-counts each edge (since each edge has two endpoints). So the total number of edges is $$m^2+n^2\over 2.$$ Now suppose there is an odd-degree vertex.


*

*Do you see why this means that at least one of $m$ or $n$ is odd?

*Do you see why this means in turn that both $m$ and $n$ must be odd?

*Do you see why this means that, finally, every vertex in $G$ has odd degree?
