here is a cute problem I created from another cute problem. Prove the number of dominating sets of a bipartite graph is never exactly divisible by $2$.
A dominating set of a graph is a set of vertices $D$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$
Regards.
This is actually true for all graphs $G$, and can be proven by considering the Domination Polynomial of a graph; $D(G,x) := \sum_{k=0}^{|V(G)|} d_k(G) x^k$ where $d_k(G)$ is the number of dominating sets of cardinality $k$ in $G$.
Your problem is thus to show that $D(G,1) \equiv 1 \mod 2$. We proved it as a corollary to another result in Subset-Sum Representations of Domination Polynomials. (Graphs Combin. 30 (2014), no. 3, 647–660.)
It can also be shown by induction using this recurrence from Recurrence relations and splitting formulas for the domination polynomial: (Electron. J. Combin. 19 (2012), no. 3, Paper 47)
$$D(G, x) = xD(G/u, x) + D(G − u, x) + xD(G − N[u], x) − (1 + x)p_u(G, x)$$
When we substitute $x=1$ into this you can see that the last term is even and thus there are 3 terms belonging to smaller graphs which are necessarily odd by the induction hypothesis; 3 odd numbers added makes an odd number.
The first proofs we found of this result were published by Andries E. Brouwer: The number of dominating sets of a finite graph is odd.