here is a cute problem I created from another not so cute problem I made from a cute problem. Prove the number of total dominating sets of a bipartite graph is never exactly divisible by $2$ ( of the form $2k$ with $k$ odd).
A total dominating set is a set of vertices such that all vertices in the graph (including the vertices in the dominating set themselves) have a neighbor in the dominating set.
Regards.
We call a set of vertices in one of the parts of the bipartite graph a dominator if every vertex in the other part of the graph is a neighbour of at least one of the vertices in the dominator.
Therefore a set of a bipartite graph with parts $A$ and $B$ is a totally dominating set if and only if the set of its vertices that are in $A$ is a dominator set and the set of vertices in $B$ is a dominator set. therefore the number of totally dominating sets of a bipartite graph with parts $A$ and $B$ is equal to the product of the number of dominator sets of vertices in $A$ multiplied by the number of dominator sets of vertices in $B$.
We shall prove that these last two numbers have the same parity, which proves this number must be odd or a product of two even numbers (hence not exactly divisible by $2$). To prove this consider all of the pairs of sets of vertices $A'\subseteq A$ and $B'\subseteq B$ such that there are no edges between $A'$ and $B'$.
Given a specific subset $A'$ how many such pairs $A',B'$ are there? consider the set of vertices in $B$ not in the neighbourhood of $A$. Then we have $B'$ must be any subset of the set of these vertices, hence the number of pairs $A'B'$ where $A'$ is fixed is odd if and only if $A'$ is a dominator set. Hence the parity of the number of pairs $A',B'$ is equal to the number of dominator sets $A'$. Using the exact same argument fixing a given $B'$ it is also equal to the the number of dominator sets $B'$