Graph Theory - Parity Lemma

Question

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

Answer 1

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:

1. The number of vertices in $G$ is odd or even, as determined by $|V(G)|\pmod 2$
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).
3. 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).

Answer 2

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?

Answer 3

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.$$