Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints
One way which comes to mind is to use the fact that if $\sum_{a_i \in p_j} y_i &gt; 1$ for some $j \in [m]$ then $x_j = 0$ and so the path $p_j$ is irrelevant. However, consider a graph with exponentially many paths in which the source has capacity 1 and all other vertices have capacity 2. The optimal solution is 1 and it is obtained by $y_s = 1$ and $y_v = 0$ for all $v \neq s$, and so all the inequalities considered above are tight. (For a "generic" graph, however, we can expect the optimal solution to be obtained at a vertex, and so have at most $n$ tight constraints.)

Another way is to notice that if the primal has an optimal solution then it has one which is a vertex, and so has at least $m$ tight inequalities. At least $m-n$ of them are of the type $x_j \geq 0$, and so there is an optimal solution using at most $n$ paths. However this is not helpful in the context of the exercise.