I shall prove one way of the inequality by induction on $|V|$ (I'll post the other one later or maybe someone else will prove it if interested). For the sake of clarity we will call the vertex whose existence is guaranteed by condition (2), $k$. We first notice that $f(v)\leq d_v$ with $d_v$ degree of vertex $v$. We can prove this by coloring in red just the vertex $v$. Part I: $n\leq m(G)$ It's easy to see this for $|V|=1, 2$ so assume it's true for $|V|=n-1$. Let's add the vertex $v_n$ to $G$. Now take each of the $n-1$ good colorings of $G/v_n$ and connect an arbitrary vertex $v_i$ to $v_n$ and take $f(v_n)=1$. The condition (1) is satisfied. If you color a set not containing $v_n$ nor $v_i$, then we have no changes. If we color a set containg $v_i$ and not $v_n$ we can see that if $v_i$ is $k$ then it's $k$ when connected to $v_n$ too. By similar reasonings on the other sets we can obtain $n-1$ good colorings for $G\cup v_n$. To get the $n$-th, we connect $v_n$ to all other vertices and let $f(v_n)=n-1$. Again both conditions are satisfied.

Let's looks at condition (2) Suppose we have a good mapping $f$ of graph $G$. Colour all vertices red. By condition (2) we must have a vertex $v_0$ such that $f(v_0)\le 0$. Now uncolour $v_0$, again by (2) there must be some vertex $v_1$ such that $f(v_1)$ is not more than the number of uncoloured adjacent vertices to $v_1$ which is at most $1$. Hence $f(v_1)\le 1$. Continuing in this manner we get a sequence of vertices $v_0,v_1,...,v_n$ such that $v_i \le \min\{i,d(v_i)\}$ where $d(v_i)$ denotes the degree of vertex $v_i$. Notice that if we colour any of the vertices in the sequence red, the smallest red vertex in the sequence is the one needed to meet condition (2). It follows that we can remove $v_n$ a preserve property (2) $\qquad (*)$ Part 1 $n\le m(G)$. We proceed by induction on $|V|$. The base case $|V|=2$ there is nothing to prove. Assume it is true for $|V|=k$ and consider $|V|=k+1$. Take any vertex, $v$, and remove it and its $d(v)$ edges. By our assumption there are at least $n-1$ good mappings of the new graph. For any of these good mappings when we reattach $v$, consider it as $v_{k+1}$ in the vertex sequence and it must satisfy property (2) by $(*)$. Furthermore we have $|E|-|E'|=d(v_{k+1})$ so let $f(v_{k+1})=d(v_{k+1})$ and we also satifsy condition (1). This gives $n-1$ mappings of $G$. We selected $v$ arbitrarily so we can do the same for all vertices. Moreover, when we select a vertex, $v$ we generate $n-1$ mapping where $f(v)=d(v)$. So suppose we take a vertex, $v$, for one of the mappings, $f_1$, there must be a vertex $u$ such that $f_1(u) < d(u)$ (from (1)). Then take vertex $u$ and generate another $n-1$ mappings $f_2,f_3,...,f_n$. These must be distinct from $f_1$ because $f_k(u)=d(u)$ for $k>1$. So the inductive step is complete $\square$ Part 2 $m(G) \le n!$ Call a map nice if it satisfies condition (2), and instead of condition (1) we have $\textstyle\sum_{v\in V} f(v) = N \ge |E|$. Suppose we have a nice map, $f$, for which $\textstyle\sum_{v\in V} f(v) = N > |E|$. If we take any vertex, $v$, and reduce $f(v)$ by $1$, then we preserve property (2) and $N$ falls to $N-1 \ge |E|$. On the other hand, if we have and vertex $v$ and increase $f(v)$ by $1$ we do not necessarily preserve contition (2). It follows that the number of nice maps for a fixed $N$ cannot increase as $N$ increases $(**)$. Now we proceed by induction. It's trivial for $|V|=2$, assume true for $|V|=k$ and consider $G$ with $|V|=k+1$. Take some good mapping of $G$. From $(*)$ we can select some vertex $v_{k+1}$ and remove it and preserve condition (2). Furthermore, $f(v_{k+1})$ is uniquely determined by the other values of the function by condition (1). Then we must have $\textstyle\sum_{i=0}^k f(v_k) =N \ge |E|-d(v_{k+1}) \ge |E|-n$. So we have that the map on $G\backslash v_{k+1}$ is nice. When $N=|E|-d(v_{k+1})$ the map is good (in the original sense), so by our assumption there are no more than $(n-1)!$ such maps. As $N$ increases to $|E|-1$, at each fixed $N$ we can have no more than $(n-1)!$ maps by $(**)$. Consequently, $G\backslash v_{k+1}$ can have no more than $n\cdot (n-1)!=n!$ nice maps $\Rightarrow$ $G$ has no more than $n!$ good maps. This completes the inductive step $\square$

My boyfriend took part in it,here is his solution:

DelicateFlower wrote: Given every point a number from $1$ to $n$,there are $n!$ different ways. We can prove the following by induction: (1).Each "good map" can correspond one kind of number-giving Alright...but you haven't said anything about how a permutation of the vertices corresponds to a good map. Care to explain?

Sorry,Ocha. He didn't told me the details.

ocha wrote: DelicateFlower wrote: Given every point a number from $1$ to $n$,there are $n!$ different ways. We can prove the following by induction: (1).Each "good map" can correspond one kind of number-giving Alright...but you haven't said anything about how a permutation of the vertices corresponds to a good map. Care to explain? We can do like this: A is the set that contains all the permutation of the vertex of G. For a element in A, say $(V_{i_1},V_{i_2}......V_{i_n})$ ($i_{1},i_{2},......i_{n}$ can be any permutation of 1,2,......n) , consider this map: $f(V_{i_k}) $is the number of the points which is near to $V_{i_k}$ in $V_{i_1},V_{i_2}......V_{i_(k-1)}$. We can prove it is surjective. So the conclusion follows. My English is poor, hope you understand this.

Official solution: Given an ordering $\tau=(v_1,v_2,\cdots,v_n)$ on the vertices in $V$, we associated a map $f_{\tau}:V\rightarrow \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 computed exactly once in $\sum_{v\in V}f_{\tau}(v)$, for an edge $e\in E$ with vertices $u,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 most preceding ordering in $\tau$, then $f_{\tau}(v)$ is not greater than the number of vertices adjacent to $v$ which is not colored into red by definition of $f_{\tau}$. We verified that $f_{\tau}$ is good. Conversely, given any good map $f:V\rightarrow\mathbb{Z}$, we claim that $f=f_{\tau}$ for some ordering $\tau$ of $V$. First let the red vertices set $A=V$, by condition (2) in problem, there exists $v\in A$ such that $f(v)\leq 0$, denote one of such vertices by $v_1$. Assuming we already choose $v_1,\cdots,v_k$ from $V$, if $k<n$, set the red vertices set $A=V-\{v_1,\cdots,v_k\}$, by 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,\cdots,v_k$ that is adjacent to $v$. Denote one of such vertices by $v_{k+1}$. Continuing in this way, we order the vertices of $V$ by $\tau=(v_1,v_2,\cdots,v_n)$. By the construction we have $f(v)\leq f_{\tau}(v)$ for any $v\in V$. By condition (1) in problem, we have \[|E|=\sum_{v\in V}f(v)\leq \sum_{v\in V}f_{\tau}(v)=|E|,\] therefore $f(v)=f_{\tau}(v)$ for any $v\in V$. We have shown that for any ordering $\tau$ of $V$, $f_{\tau}$ is good, and any good map $f$ is $f_{\tau}$ for some $\tau$. Since the number of orderings on $V$ is $n!$, we see that $m(G)\leq n!$ (note that two distinct ordering may result in same map). Next we prove that $n\leq 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$, 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,\cdots,v_n)$ such that $v_k$ is adjacent to at least one of the vertices preceding it under ordering $\tau$, for any $k\geq 2$. Thus $f_{\tau}(v_1)=0$ and $f_{\tau}(v_k)>0$ for $2\leq k\leq n$. Since $v_1$ may be arbitrary, we have at least $n$ good maps, i.e. $m(G)\geq n$. In general, $G$ is a union of its connected components $G_1,\cdots,G_k$, since each vertex is adjacent to at least another vertex, each component has at least 2 vertices, denote by $n_1,\cdots,n_k\geq 2$ the number of vertices of these components. For each $G_i$, we have at least $n_i$ good maps on its vertices. It is easy to see that patching good maps on $G_i$'s together results in a good map on $G$, thus $m(G)\geq n_1n_2\cdots n_k\geq n_1+n_2+\cdots+n_k=n.$ We conclude that $n\leq m(G)\leq n!.$

Assume the graph is connected. After proving for connected graphs, it's easy to prove for disconnected graphs ($m(G)$ is multiplicative over disjoint connected components). One way to obtain such a function is as follows: orient each edge such that the resulting directed graph is a DAG, and let $f(v)$ be the outdegree of $v$. The first condition is obviously satisfied. The second condition is also satisfied: for any coloring, choose a "minimal" red vertex $v$ (such that no vertex reachable from $v$ is red. This exists because a finite poset has a minimal element.). All its immediate out-neighbors are uncolored by assumption, so $f(v)$ is $\leq$ the number of uncolored neighbors. This gives us $n \leq m(G)$: for each vertex $v$, consider a DFS spanning tree rooted at $v$. It has the property that every non-tree edge connects a vertex to one of its ancestors. Orient each edge from the vertex with lower depth to the vertex with higher depth. The $f$'s obtained from these different orientations are distinct, since in each such $f$ there is a unique vertex which satisfies $f(v) = \text{deg}(v)$ (the vertex chosen as root). Now I shall show that these are all the possible $f$s. This implies $m(G) \leq n!$, since once a topological sorting of an acyclic orientation is fixed, the orientation is uniquely determined and there are at most $n!$ possible topological sortings. The crucial lemma is the following. Lemma: If $(u,v)$ is an edge, then $f(u) = f(v) = 0$ cannot be true in any valid $f$. Proof: Suppose this is true. Let $S = \{u, v\}$. Maintain a counter $C$ and initialize it at $C=0$. We shall add all vertices to $S$ one by one in the following order: (i) As long as $S \neq V$, consider the coloring where all vertices in $S^c$ are colored red. By assumption, there exists a $t \in S^c$ such that $f(t) \leq E(t,S)$ (RHS is number of edges from $t$ to $S$). Add $E(t,S)$ to the counter and add $t$ to $S$. When all vertices are added, the counter reads $|E|-1$, since every edge other than $(u,v)$ gets counted exactly once (if $(p,q)$ is an edge and $q$ gets added later than $p$, $(p,q)$ is counted when $q$ is added). Since $f(u) = f(v) = 0$, this implies $\sum_{t \in V} f(t) \leq |E|-1$, contradiction. This proves the lemma. Now we induct on $n$. Base case is trivial. For induction, consider any coloring. It must have a vertex with $f(v) = 0$ (consider the coloring where everything is red). Consider the function $g$ on $G \setminus \{v\}$ where $g(u) = f(u)$ if $(u,v)$ is not an edge, $g(u) = f(u)-1$ otherwise. By the lemma, $g(u) \geq 0$ for all $u$. Moreover, it is easy to see $g$ is also a valid function for $G \setminus \{v\}$: the first condition is satisfied, and for the second condition, given any coloring on $G \setminus \{v\}$, consider the corresponding coloring on $G$ where $v$ is not colored. By induction, $g$ corresponds to an acyclic orientation on $G \setminus \{v\}$. Thus $f$ corresponds to an acyclic orientation on $G$ where $v$ has outdegree 0, and the induced orientation on $G \setminus \{v\}$ is the same as $g$. The induction is complete.