Existence of a necessary function $ f$ may be rephrased as follows: the subspaces \begin{eqnarray*} \{f\in F:f(y)-f(x)\leq \rho(x,y)\}, (x,y)\in X\times X;\\ \{f\in F:f(x)-f(y)\geq \rho(x,y)\}, (x,y)\in E, \end{eqnarray*} must have non-empty intersection. Since $ F$ is $ n$-dimensional, by Helly theorem it suffices to prove that any subfamily of at most $ n+1$ subspaces has non-empty intersection. Assume the contrary and consider the least counterexample: at first, by the number $ n+1$ of points in $ X$, next, by the number $ m\leq n+1$ of subspaces with empty intersection. Each subspace is defined by $ f(y)-f(x)\leq \pm \rho(x,y)$, sign minus is possible if $ (x,y)\in E$. Call $ x$ a starting point and $ y$ an endpoint. If some point $ x$ does not serve neither as a starting point nor as an endpoint for none of our subspaces, we have a counterexample with $ X{\setminus} \{x\}$ instead of $ X$. The same holds if $ x$ serves only as a staring point or only as an endpoint: a function from $ X{\setminus} \{x\}$ may be extended to $ x$ so that inequalities containing $ f(x)$ become true. Thus $ m=n+1$ and each point $ x\in X$ is an endpoint for exactly one subspace and a starting point for exactly one subspace. A map, which sends each starting point to the corresponding endpoint, is a permutation of $ X$. Let $ z_1\dots z_sz_1$ be one of its cycles, than $ f$ should satisfy inequalities of the form

\begin{eqnarray*} f(z_{i+1})-f(z_i)\leq \varepsilon_i \rho(z_i,z_{i+1}),i=1,\dots,s, \varepsilon_i\in \{-1,+1\}, \end{eqnarray*} (as usual, agree that $ z_{s+1}=z_1$). Such a function exists if and only if $ \sum \varepsilon_i \rho(z_i,z_{i+1})\geq 0$. Let $ A$ be a set of indices $ i$ for which $ \varepsilon_i=-1$, $ B$ be a set of other indices. Then $ (z_i,z_{i+1})\in E$ for $ i\in A$. Let $ w(i)$, for $ i\in A$, denote the (first) index preceding $ i$ in a cycle such that $ w(i)\in A$. Function $ w$ is a cyclic permutation of $ A$. Condition (iv) yields that

\begin{eqnarray*} \sum_{i\in A} \rho(z_i,z_{i+1})\leqslant \sum_{i\in A} \rho(z_i,z_{w(i)+1})\leqslant \sum_{i\in B} \rho(z_i,z_{i+1}). \end{eqnarray*} (The last inequality follows from several triangle inequalities which are summed up.). This is what we need. ⬜

1. 1. Graph with one edge satisfies (iv).
2. 2. Set $ x_1=x,x_2=y_1=y,y_2=z$ in (1) , we get $ \rho(x,z)\geqslant \rho(x,y)+\rho(y,z)$, thus equality takes place. If $ \rho$ is a strict metric, then the function $ f(z)=(\rho(y,z)-\rho(x,z))/2\in \LIP(X)$ satisfies equality $ f(a)=f(b)+\rho(a,b)$ only for $ a=x$, $ b=y$. Thus corresponding support plane has unique common point $ e_{x,y}$ with the ploytope $ \KR(X)$. This yields that $ e_{x,y}$ is a vertex of $ \KR(X)$.
3. 3. Strict metric $ \rho$ is generic iff the polytope $ \KR(X)$ is simplicial. That is, each face $ \alpha$ of dimension $ k=\dim \alpha$ contains exactly $ k+1$ vertices of $ \KR(X)$. By Lemma 1 we have $ k=n-c$, where $ c$ is a number of connected components of $ \tilde{D}(\alpha)$. By p. 2) the number of vertices of $ \KR(X)$ which belong to $ \alpha$ equals the number of edges of the graph $ \tilde{D}(\alpha)$. So, in terms of the graph $ \tilde{D}(\alpha)$ condition is the following: sum of the number $ k+1=n-c+1$ of edges and the number of connected components $ c$ should be equal to the number of vertices $ n+1$. Such graphs are exactly forests.
4. 4. Consider a facet $ \alpha$ of the polytope $ \KR(X)$. We have to check that $ \alpha$ has exactly $ n$ vertices, i.e., that the graph $ D(\alpha)$ has exactly $ n$ edges. The graph $ \tilde{D}(\alpha)$ is connected by Lemma 1. Thus it has at least $ n$ edges. each vertex of the graph $ D(\alpha)$ has indegree or outdegree 0, so, any cycle in $ \tilde{D}(\alpha)$ is alternating: $ y_1x_1y_2x_2\dots y_kx_k$, $ (x_i,y_i), (x_i,y_{i+1})\in E(D(\alpha))$. Using (1) twice we get $ \sum \rho(x_i,y_i)\leqslant \sum \rho(x_i,y_{i+1})$ and $ \sum \rho(x_i,y_{i+1})\leqslant \sum \rho(x_i,y_i)$, thus equality takes place. This contradicts to our assumption. Therefore there are no cycles and the non-oriented graph $ \tilde{D}(\alpha)$ is a tree, it has exactly $ n$ edges, as desired.

\begin{eqnarray*} f(y)-f(x)=\sum_{i=1}^k \rho(x_i,y_i)-\sum_{i=1}^{k-1} \rho(x_i,y_{i+1})\leq \rho (x_{k},y_1)=\rho(x,y) \end{eqnarray*} due to (1) . ⬜

1. 1. Let $ C_1,C_2,\dots$ be non-empty disjoint subsets of $ \{1,\dots,k\}$ which are supports of the cycles of $ \pi$. If the set of edges $ (x_i,y_i)$ is admissible, then for each $ C_j$ we have inequality \begin{eqnarray*} \sum_{i\in C_j} \rho(x_i,y_i)\leqslant \sum_{i\in C_j} \rho(x_i,y_{\pi(i)}) \end{eqnarray*} by (1) . Summing up we get \begin{eqnarray*} \sum_{i=1}^k \rho(x_i,y_i)\leqslant \sum_{i=1}^k \rho(x_i,y_{\pi(i)}), \end{eqnarray*} this yields (3) as $ \pi$ is arbitrary. Conversely, if the set of edges $ (x_i,y_i)$ is not admissible, condition (iv) of Theorem 3 means that for a certain cyclic permutation of some subset $ C\subset \{1,\dots,k\}$ the value of right hand side of (3) is less than for the identical permutation.
2. 2. If a strong metric $ \rho$ is not generic, than some admissible graph $ \tilde{D}(\alpha)$ contains a cycle. By p.2 of Corollary 1, each vertex of $ D(\alpha)$ has indegree 0 or outdegree 0, thus the vertices of this cycle alternate and we may denote it $ y_1x_1\dots y_kx_ky_1$, $ (x_i,y_i),(x_i,y_{i+1})\in D(\alpha)$. It means that the minimum in (3) is obtained both for the identical permutation $ \pi$ and for $ \pi(i)=i+1 \pmod k$.

Assume now that $ \rho$ is generic strict metric, but the minimum in (3) is obtained for two different permutations. Changing notations and considering a subset on which one of these two permutations is a cyclic shift of another, we may consider the case when one of two permutations is identical and another is a cyclic shift $ \pi(i)=i+1 \pmod k$. Let us show that a union of edges of the cycle $ y_1x_1\dots y_kx_ky_1$ is admissible, by p.4 of Corollary 1 this contradicts to our assumption that $ \rho$ is generic. We check condition $ (iv)$. Choose few disjoint edges from the cycle. They belong to some tree obtained from the cycle by removing one edge. Thus it suffices to check that such a tree is admissible. This may be checked by Theorem 4. Indeed, the condition of Theorem for any path in this tree follows from the minimality of one or another permutation. ⬜

In order to prove existence we consider the constellation $ D^*$, which minimizes $ F$. Choose an array of edges as in p. (iv) of Theorem 3. The graph $ D^*$ does not contain edges of the form $ (x_{i+1},y_i)$, since degrees of endpoints are equal to 1. Thus $ D^* {\setminus} \{(x_i,y_i)\} \cup \{(x_{i+1},y_i)\}$ is a constellation again, and the value of $ F$ is not less than for $ D^*$. It yields condition (iv) of Theorem 3, so, $ D^*$ is indeed admissible.

Now assume that there exists yet another constellation $ D'$ with the same degrees. Choose the vertices $ x_1\in V, y_1 \in X {\setminus} V$ so that $ (x_1,y_1)\in D' {\setminus} D^*$. Since degree of $ y_1$ in both $ D^*$ and $ D'$ equals 1, there exist $ x_2\in V$ such that $ (x_2,y_1)\in D^* {\setminus} D'$. Next, degree of $ x_2$ is the same in $ D^*$ and $ D'$. Thus there exists a vertex $ y_2 \in X {\setminus} V$ such that $ (x_2,y_2)\in D' {\setminus} D^*$. This process continues until $ x_m=x_1$ for some $ m$ . We got a cycle (strictly speaking, disconnected orientation of a non-directed cycle), all even edges of the cycle belong to the first constellation and all odd edges to another. Since our two constellations are admissible, both sets of odd and even edges minimize the sum in (3) . It is impossible for a generic metric by Theorem 5. ⬜

Let us prove uniqueness of such a tree $ T$. For any white vertex $ u$ the constellation $ H(T,u)$ is admissible. Degrees of white vertices in $ H(T,u)$ depend on $ u$, but not on $ T$. Lemma 2 implies that it is unique and minimizes $ \Phi_u$. The tree $ T$ is a union of all such constellations $ H(T,u)$, thus it is at most unique.

It remains to prove the existence. Consider the tree $ T$ with given outdegrees of white vertices, for which the sum of functionals $ \Phi_{u}$ ($ u$ runs over white vertices) is minimal possible. Let us claim that it is unique by verifying conditions of Theorem 4. By Claim 1, if some path $ y_1\dots x_{2k}$, where $ x_i$ are white, obeys condition of Theorem 4, then for the tree $ T'$ each functional $ \Phi_{v_i}$ takes a value lesser or equal than for $ T$, and some functionals take strictly lesser value. This contradicts the minimality assumption. ⬜

Let $ X=\{1,\ldots,n+1\}$. Consider the metric \begin{eqnarray*} \rho(i,j)=1+i/j,\, 1\leqslant i (3) is attained on the increasing permutation and only on it (this is known as "rearrangement inequality"). Thus the metric $ \rho$ is generic and the graph is admissible if and only if it does not contain edges $ (x_1,y_1), (x_2,y_2)$ for which $ x_1y_2$. Assume that there are exactly $ k$ positive numbers among $ p_1,\dots,p_{n+1}$, denote them $ r_1,\dots,r_k$ in the order of corresponding points on the real line. Denote by $ Q$, $ |Q|=n+1-k$, the set of other points of $ X$. The statement of Theorem 7 in the case under consideration reduces to the following:

The number of ways to choose subsets $ A_1,\dots,A_k$ in $ Q$ so that $ |A_i|=r_i$ for $ i=1,\dots,k$ and $ \max(A_i)\leqslant \min(A_{i+1})$ for $ i=1,\dots,k-1$ equals $ \binom{n}{m}=\binom{n}{\sum r_i}$.

This is clear. Indeed, without loss of generality we may suppose that $ Q=\{1,2,\dots,n-k+1\}$. Then the translates $ A_1,A_2+1,A_3+2,\dots,A_k+(k-1)$ of the sets $ A_1,\dots,A_k$ are disjoint and they form a set of size $ \sum r_i=m$ in $ \{1,\dots,n\}$.

Now we start to deform our metric and control that the number of admissible graphs with given outdegrees does not change.

Consider the metrics on $ X$ as point of the phase space (of dimension $ n(n+1)/2$: \begin{eqnarray*} PS=\left\{f\colon X\times X \rightarrow \mathbb{R},\, f(x,y)=f(y,x),\, f(x,x)=0\,\text{for}\,x,y\in X\right\}. \end{eqnarray*} For any sequence $ x_1,y_1,\dots,x_k,y_k$ of mutually distinct points in $ X$ we consider an exceptional plane

Consider two generic metrics $ \rho_1,\rho_2$. Theorem 4 shows that while we change a metric continuously without meeting exceptional planes, the set of admissible trees does not change. Theorem 5 guarantees that the metric remains generic.

Replace each of the metrics $ \rho_1,\rho_2$ with ones sufficiently close to them and draw a segment between two new metrics. Almost surely (in any reasonable sense, for example, with respect to Lebesgue measure) this segment is not contained in any exceptional plane, and it does not contain points which lie in at least two exceptional planes. Thus we may suppose that when we move on this segment, we meet at most one exceptional plane simultaneously. It remains to prove that the number of admissible graphs from the statement of Theorem (7) does not change after we intersect an exceptional plane. Consider the moment of the intersection of the plane (4) . Assume that before intersection the left hand side of (4) was less than the right hand side, and vice versa after intersection. Let us describe the rearrangement of the family of admissible graphs. Admissible graphs which did not contain all $ k$ edges $ (x_i,y_i)$ remain admissible (by property (iv) of Theorem 3). Graph $ G$, which contains all these edges, is no longer admissible. It corresponds to the following graph $ G'$, which was not admissible, but became admissible: for each index $ i$ such that $ G$ did not contain the edge $ (x_i,y_{i+1})$, add it and remove $ (x_i,y_i)$. Note that outdegrees do not change after such rearrangement. Let us prove that this graph $ G'$ is admissible. The old graph $ G$ was contained in some admissible tree. It contained all but one edges of the cycle $ \gamma=y_1x_1\dots y_kx_ky_1$, else it would remain admissible by Theorem 4. This tree is changed by replacing one edge to another, and new tree $ T'$ contains $ G'$. Thus it suffices to check that $ T'$ is admissible. Denote by $ \rho$ the metric in the moment of rearrangement. There exists a function $ f$ with Lipschitz constant 1 such that $ f(x)-f(y)=\rho(x,y)$ for all edges $ (x,y)$ of the tree $ T$ (condition (ii) of Theorem 3 and passing to the limit). Thus the same equation holds for the only edge of $ T'{\setminus} T$ (i.e., for the edge of the cycle $ \gamma$ which is absent in $ T$: this follows from the equation of the intersected plane). For other pairs of points we have a strict inequality $ |f(x)-f(y)|<\rho(x,y)$. Thus the graph $ T\cup T'$ is admissible in the moment of rearrangement. Denote by $ \rho'$ the metric after rearrangement. Consider a function $ f'$ such that $ f'(x)-f'(y)=\rho'(x,y)$ for $ (x,y)\in T'$. If $ (x,y)\notin T\cup T'$, then inequality $ f(x)-f(y)<\rho(x,y)$ was strict, therefore it still holds for $ f'$ and $ \rho'$. For the the unique edge of $ T'{\setminus} T$ it also holds, since we intersected the plane.

So, we see that the number of admissible graphs with given outdegrees does not decrease after we intersect the plane (the map $ G\rightarrow G'$ is injective). Analogously, it does not increase. Theorems 7 and 1 are proved. ⬜