Introduction to Graph Theory · Problem 5.4

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · dominating-sets-forests

Problem

A dominating set of a multigraph GG is defined to be a dominating set of its underlying simple graph GsimpG^{\mathrm{simp}}. Let GG be a forest. Prove that ∑D is a dominating set of G(−1)∣D∣=±1.\sum_{D \text{ is a dominating set of } G} (-1)^{|D|} = \pm 1.

Browse the problem library