\documentclass[a4paper]{article}
\usepackage{latexsym}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\Remark}{ \noindent{\bf Remark:}\quad }
\newcommand{\qed}{\hfill$\Box$\medskip}
\newcommand{\adj}{\sim}

\title{The number of dominating sets of a finite graph is odd}
\author{A. E. Brouwer}
\date{May 23, 2009}
\begin{document}
\maketitle
\begin{center}
{\it To Reza Khosrovshahi on the occasion of his 70th birthday}
\end{center}

\medskip
Let $\Gamma$ be a finite graph with vertex set $V = V\Gamma$.
A subset $D$ of $V$ is called {\it dominating} when each vertex
in $V \setminus D$ has a neighbour in $D$.
The {\it domination polynomial} $p(\Gamma,X)$ is defined by
$p(\Gamma,X) = \sum_D \, X^{|D|}$ where the sum is over all
dominating sets $D$.

S. Akbari asked whether $p(\Gamma,-1)$ is always nonzero, and it is:

\begin{Theorem} The number of dominating sets of a finite graph is odd.
\end{Theorem}
\Proof
Let us write $S^+$ for the set of vertices in $S$ or with a neighbour in $S$.
By induction on $|V|$, and for fixed $|V|$ on $|S|$,
we prove the following two claims for $S \subseteq V$:

\medskip
(i) $\#\{ D \mid S \subseteq D \subseteq V,~ D^+ = V \} \equiv
\#\{ E \mid E \subseteq V,~ E^+ = V \setminus S \}~~\mbox{\rm (mod 2),}$

(ii) $\#\{ D \mid D \subseteq V \setminus S,~ D^+ = V \} \equiv
\#\{ E \mid E \subseteq V,~ V \setminus S \subseteq E^+\}
~~\mbox{\rm (mod 2).}$

\medskip\noindent
Indeed, if $S = \emptyset$ both (i) and (ii) are trivial.
Assume $S \ne \emptyset$.

\medskip\noindent
Let $U = S^+ \setminus S$ and $W = V\setminus S$. Then (i) is equivalent to

\medskip
(i') $\#\{ D \mid D \subseteq W,~ W \setminus U \subseteq D^+\} \equiv
\#\{ E \mid E \subseteq W \setminus U,~ E^+ = W \}~~\mbox{\rm (mod 2).}$

\medskip\noindent
for $U \subseteq W$. But this is precisely (ii), with $W$ instead of $V$,
and since $|W| < |V|$ this holds by induction. This proves (i).

If we sum the equality (ii) over all $S \subseteq T$, where
$T \subseteq V$, the left hand side counts pairs $(D,S)$
with $D^+ = V$ and $S \subseteq T \setminus D$, so that
each $D$ is seen $2^{|T \setminus D|}$ times, which is 0 (mod 2)
except when $T \subseteq D$.
The right hand side counts pairs $(E,S)$ with
$V \setminus T \subseteq V \setminus S \subseteq E^+$,
so that each $E$ is seen $2^{|E^+ \setminus (V \setminus T)|}$ times,
which is 0 (mod 2) except when $E^+ = V \setminus T$. The result is

\medskip
$\#\{ D \mid T \subseteq D \subseteq V,~ D^+ = V \} \equiv
\#\{ E \mid E \subseteq V,~ E^+ = V \setminus T \}~~\mbox{\rm (mod 2)}$

\medskip\noindent
which is precisely (i), but using the variable $T$ instead of $S$.
Since (i) holds, and by induction (ii) holds for all proper subsets $S$ of $T$,
it follows that (ii) also holds for $S = T$.
This completes the proof of (i) and (ii).


\medskip\noindent
Now we can prove the theorem. If $V = \emptyset$ then there is precisely
one dominating set. Otherwise, let $x \in V$ and put $W = V \setminus x$
and $S = N(x)$, the set of neighbours of $x$.
The dominating sets in $V$ are the dominating sets $D$ in $W$ that intersect
$S$, and the sets $E \cup \{x\}$ where $E \subseteq W$ with
$W \setminus S \subseteq E^+$.
By induction, the number of dominating sets (of the graph $\Gamma\setminus x$)
in $W$ is odd. Adding equation (ii) (with $W$ instead of $V$) yields the
desired conclusion.
\qed

% $p(\Gamma,-1) \equiv 1$ {\rm (mod $2$)}.

\end{document}
