Grinberg-Introduction-Graph-Theory · Problem 2.21

Simple graphs

Mathematics — Graph Theory · k-path-dominating-sets

Problem

Let

k

be a positive integer. Let

G = (V, E)

be a simple graph. A subset

U

V

will be called

k

-path-dominating if for every

v \in V

, there exists a path of length

\leq k

from

v

to some element of

U

. Prove that the number of all

k

-path-dominating subsets of

V

is odd. [Hint: This is not as substantial a generalization as it may look. The shortest proof is very short.]