Let be a directed graph. We define a set function by defining, for a set , to be the number of edges leaving :

A set function is submodular if for any two sets ,

Prove that is submodular.

A set function is symmetric if for all . A graph is Eulerian if every vertex has the same number of outgoing edges as incoming edges. Show that is symmetric iff is Eulerian.

A set function is posi-modular if for all sets , we have

Show that if is Eulieran, then is post-modular.

Note that the above properties hold also in capacitated (i.e., weighted) graphs, where we define to be the total capacity of all edges leaving .

Let be a directed capacitated graph. Let be defined by

Prove the following ``triangle inequality'' for cuts: for all distinct ,