Then the result is again that the vertices of this polyhedron correspond to paths joining s to t. Again, a caution. This is an unlimited polyhedron so that we can only minimise non-negative linear functions and we know that we can solve easily the shortest path problem with non-negative cost, but not the max path problem, which is NP-complete as well. This is a symmetric result with respect to the previous one. And this was the basic result where we have seen the description of the polyhedron can be done in a very compact way by only having a description in terms of a polynomial number of inequalities. Now we have some intermediate results where we still have the complete description, but not in terms of a polynomial number of equalities.

---