The number of vertices of odd degree in any graph of n vertices with e edges is:

By the handshaking lemma, the degrees of all the vertices add up to $2e$, which is even. The even-degree vertices contribute an even amount, so the odd-degree vertices must also add up to an even number, which is possible only if there is an even number of them (zero included). The count need not be prime (it can be 0 or 4) and has no fixed link to $n - e$.