The number of dominating sets of a finite graph
is odd
A. E. Brouwer
June 2, 2009
Let Γ be a finite graph with vertex set V = V Γ. A subset D of V is called
dominating when each vertex in V \ D has a neighbour in D. The following
theorem answers a question by S. Akbari.
Theorem The number of dominating sets of a finite graph is odd.
Today, there are three proofs, by Andries Brouwer, Péter Csorba and Lex
Schrijver, respectively. Let us give all three.
First 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 ⊆ V :
(i) #{D | S ⊆ D ⊆ V, D+ = V } ≡ #{E | E ⊆ V, E + = V \ S} (mod 2),
(ii) #{D | D ⊆ V \ S, D+ = V } ≡ #{E | E ⊆ V, V \ S ⊆ E + } (mod 2).
Indeed, if S = ∅ both (i) and (ii) are trivial. Assume S 6= ∅.
Let U = S + \ S and W = V \ S. Then (i) is equivalent to
(i’) #{D | D ⊆ W, W \ U ⊆ D+ } ≡ #{E | E ⊆ W \ U, E + = W } (mod 2).
for U ⊆ 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 ⊆ T , where T ⊆ V , the left hand side
counts pairs (D, S) with D+ = V and S ⊆ T \ D, so that each D is seen 2|T \D|
times, which is 0 (mod 2) except when T ⊆ D. The right hand side counts pairs
+
(E, S) with V \ T ⊆ V \ S ⊆ E + , so that each E is seen 2|E \(V \T )| times, which
+
is 0 (mod 2) except when E = V \ T . The result is
#{D | T ⊆ D ⊆ V, D+ = V } ≡ #{E | E ⊆ V, E + = V \ T } (mod 2)
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).
Now we can prove the theorem. If V = ∅ then there is precisely one dominating
set. Otherwise, let x ∈ V and put W = V \ 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 ∪ {x} where E ⊆ W with W \ S ⊆ E + . By
induction, the number of dominating sets (of the graph Γ \ x) in W is odd.
Adding equation (ii) (with W instead of V ) yields the desired conclusion. 2
1
Second proof: Let n > 0, and look at the simplicial complex P of all
nonempty non-dominating sets. The Euler characteristic χ(P ) is an alternating
sum, and mod 2 one has |P | = χ(P ). The Euler characteristic of a simplicial
complex equals that of its barycentric subdivision. In this case that means that
we go to the simplicial complex of all chains in the poset P .
Let f (A) be the set of all vertices of Γ not equal or adjacent to anything in
A. If A is non-dominating, then also f (A) is non-dominating, and f defines a
Galois correspondence so that f 2 is a closure operator.
Consider an increasing chain C = (A1 , ..., Am ) in P . If all Aj in C are
closed, then pair C with (f (A1 ), ..., f (Am )). Otherwise, if Aj is the last non-
closed element in the chain, and f 2 (Aj ) = Aj+1 then pair C with C \ Aj+1 ,
otherwise pair C with C ∪ f 2 (Aj ).
This pairing shows that the complex of all chains in the poset P has an even
number of vertices, and hence |P | is even. Including the empty set we see that
the total number of non-dominating sets is odd, and therefore the number of
dominating sets is odd. 2
Third proof: Let
A := {(S, T ) | S, T ⊆ V, S ∩ T = ∅, s 6∼ t for all s ∈ S, t ∈ T }.
A subset S of V is dominating precisely when #{T | (S, T ) ∈ A} is odd, and
hence the number of dominating sets equals |A| (mod 2). But (S, T ) ∈ A iff
(T, S) ∈ A, and (S, T ) = (T, S) only if S = T = ∅, so |A| is odd. 2
