Given an ordering $\tau = (v_1, v_2, ..., v_n)$ on the vertices in $V$, we associate a map $f_\tau: V \to \mathbb{Z}$ as follows: $f_\tau(v)$ is equal to the number of vertices in $V$ that are ordered preceding $v$. We claim that $f_\tau$ is good.

Each edge is counted exactly once in $\sum_{v \in V} f_\tau(v)$, for an edge $e \in E$ with vertices $u, v \in V$ such that $u$ is ordered before $v$ in $\tau$; then $e$ is counted once in $f_\tau(v)$. Thus,
$$\sum_{v \in V} f_{\tau}(v) = |E|.$$
For any nonempty subset $A \subseteq V$ of all red vertices, choose $v \in A$ with the most preceding orderings in $\tau$. Then by definition, $f_\tau(v)$ is not greater than the number of vertices adjacent to $v$ that are not colored into red. We have verified that $f_\tau$ is good.

Conversely, given any good map $f: V \to \mathbb{Z}$, we claim that $f = f_\tau$ for some ordering $\tau$ of $V$.

First, let the red vertex set $A = V$. By the condition (2) in the problem, there exists $v \in A$ such that $f(v) \le 0$, and denote one of such vertices by $v_1$. Assuming that we have already chosen $v_1, ..., v_k$ from $V$, if $k < n$, set the red vertex set $A = V - \{v_1, ..., v_k\}$. By the condition (2) in the problem, there exists $v \in A$ such that $f(v)$ is less than or equal to the number of vertices in $\{v_1, ..., v_k\}$ that are adjacent to $v$. Denote one of such vertices by $v_{k+1}$. Continuing in this way, we order the vertices by $\tau = (v_1, v_2, ..., v_n)$. By the construction we have $f(v) \le f_r(v)$ for any $v \in V$. By the condition (1) in the problem, we have
$$|E| = \sum_{v \in V} f(v) \le \sum_{v \in V} f_r(v) = |E|,$$
and therefore $f(v) = f_r(v)$ for any $v \in V$.

We have shown that for any ordering $\tau$, $f_r$ is good, and any good map $f$ is $f_r$ for some $\tau$. Since the number of orderings on $V$ is $n!$, we see that $m(G) \le n!$ (note that two distinct orderings may result in the same map).

Next, we prove that $n \le m(G)$. Assume at the moment that $G$ is connected. Pick arbitrarily $v_1 \in V$. By the connectivity, we may choose $v_2 \in V - \{v_1\}$ such that $v_2$ is adjacent to $v_1$, and again we may choose $v_3 \in V - \{v_1, v_2\}$ such that $v_3$ is adjacent to at least one of $v_1, v_2$. Continuing in this way, we get an ordering $\tau = (v_1, v_2, ..., v_n)$ such that $v_k$ is adjacent to at least one of the vertices preceding it under ordering $\tau$, for any $2 \le k \le n$. Thus, $f_r(v_1) = 0$ and $f_r(v_k) > 0$ for $2 \le k \le n$. Since $v_1$ may be arbitrary, we have at least $n$ good maps.

In general, if $G$ is a union of its connected components $G_1, ..., G_k$, since each vertex is adjacent to at least another vertex, each component has at least two vertices, denote by $n_1, ..., n_k \ge 2$ the number of vertices of these components. For each $G_i$, we have at least $n_i$ good maps on its vertices, $i = 1, ..., k$. It is easy to see that patching good maps on $G_i$'s together results in a good map on $G$, and thus
$$m(G) \ge n_1 n_2 \cdots n_k \ge n_1 + n_2 + \cdots + n_k = n.$$
We conclude that $n \le m(G) \le n!$.