Question 141
Let $G = G(V; E)$ be a simple graph with vertex set $V$ and edge set $E$, and assume that $|V| = n$. A map $f: V \rightarrow \mathbb{Z}$ is said to be good if $f$ satisfies:
$$
(1) \quad \sum_{v \in V} f(v) = |E|;
$$
(2) If one colors arbitrarily some vertices into red, there exists a red vertex $v$, such that $f(v)$ is not greater than the number of vertices adjacent to $v$ that are not colored into red.
Let $m(G)$ be the number of good maps $f$. Show that if each vertex of $V$ is adjacent to at least one other vertex, then $n \le m(G) \le n!$.
$$
(1) \quad \sum_{v \in V} f(v) = |E|;
$$
(2) If one colors arbitrarily some vertices into red, there exists a red vertex $v$, such that $f(v)$ is not greater than the number of vertices adjacent to $v$ that are not colored into red.
Let $m(G)$ be the number of good maps $f$. Show that if each vertex of $V$ is adjacent to at least one other vertex, then $n \le m(G) \le n!$.