A combinatorial property of flows on a cycle

Abstract

In this paper, we prove a combinatorial property of flows on a cycle. $C(V,E)$ is an undirected cycle with two commodities: $\{s_1,t_1\},\{s_2,t_2\}$;$r_1>0,r_2>0,\mathbf{r}=(r_i{)}_{i=1,2}$ and $f,f^{\prime }$ are both feasible flows for $(C,(s_i,t_i{)}_{i=1,2},\mathbf{r})$. Then $\exists i\in \{1,2\},p\in P_i,f(p)>0,\forall e\in p,f(e)\ge f^{\prime }(e)$ ; Here for each $i\in \{1,2\}$, let $P_i$ be the set of $s_i$-$t_i$ paths in $C$ and $P={\cup }_{i=1,2}{P}_i$. This means given a two-commodity instance on a cycle, any two distinct network flow $f$ and $f^{\prime }$, compared with $f^{\prime }$, $f$ can't decrease every path's flow amount at the same time. This combinatorial property is a generalization from single-commodity case to two-commodity case, and we also give an instance to illustrate the combinatorial property doesn't hold on for $k-$commodity case when $k\ge 3$.