## 2 Existence of a Stable Multicommodity Flow
We consider the polyhedron \(\Pi\) described by the following inequalities:  
\[y_{a}^{j} \geq 0 \forall a\in A\;\forall j\in[\ell]\] (1) \[x^{j}(\mathcal{P}^{\prime})-y_{a}^{j} \leq 0 \forall\mathcal{P}^{  
First let us determine the set of extreme directions of \(\Pi\). Clearly \(-x_{P}^{j}\) for \(P\in\mathcal{P},j\in[\ell]\) and \(y_{a}^{j}\) for \(a\in A,j\in[\ell]\) give infinite directions. Since \(x_{P}^{j}\) is bounded from above and \(y_{a}^{j}\) from below, there is no infinite direction that is not in the cone of the above. So the number of extreme directions equals the dimension.  
Now let us assign colours (that is, variables, since each variable corresponds to an extreme direction of \(\Pi\)) to each inequality:  
* to an inequality of type (1) or type (2) we assign \(y_{a}^{j}\),
* to an inequality of type (3) we assign \(x_{P}^{j}\) for a longest possible quasi-paths \(P\in\mathcal{P}^{\prime}\),
* to an inequality of type (4) we assign \(x_{P}^{j}\) for a quasi-path \(P\in\mathcal{P}^{\prime}\) in which the outgoing arc from \(v\) is smallest possible in the order \(<_{v}^{j}\) from \(\mathcal{P}^{\prime}\), and among these, we choose \(P\) to be one of the longest quasi-paths,
* to an inequality of type (5) we assign \(x_{P}^{j}\) for a quasi-path \(P\in\mathcal{P}^{\prime}\) in which the incoming arc to \(v\) is smallest possible in the order \(<_{v}^{j}\) from \(\mathcal{P}^{\prime}\), and among these, we choose \(P\) to be one of the longest quasi-paths,
* to an inequality of type (6) we assign \(x_{P}^{j}\) where \(j\) is the commodity that is smallest in the order \(<_{a}\) among those with nonempty \(\mathcal{P}^{\prime}_{j}\), and from \(\mathcal{P}^{\prime}_{j}\) we choose \(P\) to be one of the longest quasi-paths.  
Since the assigned colour of each inequality is a coordinate with nonzero coefficient, the colouring fulfils the criteria of Theorem 1.2. Thus there exists a multicoloured vertex \((\overline{x},\overline{y})\) of \(\Pi\).  
**Claim 2.2**.: \(\overline{x}\geq\mathbf{0}\)_, and \(\overline{y}^{j}\leq c^{j}\) for every \(j\in[\ell]\)._  
Proof.: Suppose that \(\overline{x}_{P}^{j}\) is negative for some \(P\in\mathcal{P}\). Then by increasing \(\overline{x}_{P}^{j}\) to zero we get a vector that is still in \(\Pi\), because every inequality where \(x_{P}^{j}\) has positive coefficient is also present with the coefficient changed to zero (except for the inequalities where \(\mathcal{P}^{\prime}=\{P\}\), but changing the coefficient of \(x_{P}^{j}\) in those to zero is satisfied too since \(y_{a}^{j}\) and \(c_{a}^{j}\) are nonnegative). On the other hand we know that \(-x_{P}^{j}\) is an infinite direction, so \((\overline{x},\overline{y})\) could not have been a vertex. Thus \(\overline{x}_{P}^{j}\) is nonnegative for every \(P\in\mathcal{P}\) and \(j\in[\ell]\). Similarly we get that \(\overline{y}_{a}^{j}\leq c_{a}^{j}\) for every \(a\in A\) and \(j\in[\ell]\).  
**Claim 2.3**.: \(\overline{x}^{j}(\mathcal{P}_{a})=\overline{y}_{a}^{j}\) _for every arc \(a\in A\) and \(j\in[\ell]\)._  
Proof.: Since \((\overline{x},\overline{y})\) is multicoloured, there is a tight inequality that has colour \(y_{a}^{j}\). If this inequality is of type (1), then using Claim 2.2 we have \(0\leq\overline{x}^{j}(\mathcal{P}_{a})\leq\overline{y}_{a}^{j}=0\), thus equality holds. If the tight inequality is of type (2) for some \(\mathcal{P}^{\prime}\subseteq\mathcal{P}_{a}\), then by Claim 2.2, \(\overline{x}^{j}(\mathcal{P}_{a})\geq\overline{x}^{j}(\mathcal{P}^{\prime})= \overline{y}_{a}^{j}\geq\overline{x}^{j}(  
Using \(\overline{x}_{P}^{j}>0\), and considering the sum of inequalities of type (2) for the arcs in \(\delta^{in}(v_{2})\), we get  
\[\overline{y}^{j}(\delta^{out}(v_{2}))=\overline{x}^{j}(\mathcal{P}_{v_{2}}^{ \mathrm{in}})<\overline{x}^{j}(\bigcup_{a\in\delta^{in}(v_{2})}\mathcal{P}_{a} )\leq\overline{y}^{j}(\delta^{in}(v_{2}))\.\]  
By the same argument for the subwalk \(R\), we get  
\[\overline{y}^{j}(\delta^{in}(v_{2}))=\overline{x}^{j}(\mathcal{P}_{v_{2}}^{ \mathrm{out}})<\overline{y}^{j}(\delta^{out}(v_{2}))\]  
which is a contradiction.