China National Team Selection Test

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!$.