1
$\begingroup$

I seemed to see this from some place I don't remember

In a graph $G$, for any subset $S$ of vertices, $|S| + o(G - S)$ has the same parity (odd or even) as $n(G)$, by counting the vertices modulo 2, where $o(G-S)$ is the number of odd components of $G-S$ and $n(G)$ is the number of vertices in $G$.

I wonder why? What does counting the vertices modulo 2 mean?

Note that it is the only way I know to prove $|S| - o(G-S)$ has the same parity as $n(G)$.

Thanks!

1 Answers 1

2

If $n$ is the number of vertices, $n\bmod 2$ is the number of vertices reduced modulo $2$; it’s $1$ if $n$ is odd and $0$ if $n$ is even. Counting modulo $2$ is keeping track only of this reduced number, which amounts simply to keeping track of whether your total is odd or even.

Suppose that $G-S$ has $k$ components with an odd number of vertices (‘odd components’) and $m$ with an even number of vertices (‘even components’). Let $K$ be the total number of vertices in the odd components and $M$ the total number of vertices in the even components. $M$ is a sum of even numbers, so it’s even; modulo $2$ it’s $0$. $K$ is the sum of $k$ odd numbers, so it’s odd iff $k$ is odd. That is, $K$ and $k$ have the same parity: both are odd, or both are even. Mod $2$ both are $1$, or both are $0$, so mod $2$ we have $K=k$; in more careful notation that’s $K\equiv k\pmod 2$.

Clearly $n(G)=|S|+K+M\;.$ Expand that mod $2$:

$\begin{align*} n(G)&\equiv|S|+K+M\\ &\equiv|S|+k+0\\ &\equiv|S|+k\pmod2\;, \end{align*}$

which is exactly what you wanted to prove, since $k=o(G-S)$.

  • 0
    @Tim: You’re welcome!2012-11-10