Graph Theory - Parity Lemma I've got this lemma from class. I'm having a bit of trouble conceptualizing what it's trying to say. Would appreciate some help

What does the number of odd components of $G - S$ have to do with the evenness of the number of vertices in a graph?
Thanks for the help
 A: I think you are asking how to interpret the statement of the lemma, as opposed to asking for intuition as to why it is true. Here is a way of interpreting the statement of the lemma:


*

*The number of vertices in $G$ is odd or even, as determined by $|V(G)|\pmod 2$

*The statement is: for any set of vertices $S\subseteq G$, the difference between the number of odd components of $G-S$, and the number of elements in $S$ is always even (if $G$ has an even number of vertices), or always odd (if $G$ has an odd number of vertices).

*The difference between any two numbers is even if they have the same parity, or odd if they don't. So another version of this statement is that $o(G-S)$ and $|S|$ always have the same parity (if $G$ has an even number of vertices), or always have different parity (if $G$ has an odd number of vertices).

A: If the number of odd components in a graph is even, then it must have even number of vertices (odd + odd + ... + odd (even times, each odd corresponding to number of vertices in each odd component) + even + even + ...)
If the number of odd components in a graph is odd, then it must have an odd number of vertices (odd + odd + ... + odd (odd times) + even + even + ...)
Does that help?
A: If the number of vertices in $G-S$ is even, then there must be an even number of odd components (i.e. $o(G-S)$ is even); otherwise, $o(G-S)$ is odd. Thus, $$o(G-S) \equiv |G-S| \mod 2.$$
To count the number of vertices in $G$ (i.e. $|G|$), you can count the number of vertices in $S$ (i.e. $|S|$) and then add up the sizes of each of the components of $G-S$. Thus $$|G| =|G-S| + |S| \equiv o(G-S) + |S| \mod 2.$$
