# Homework 9

Due Monday, February 24 at 5:00 PM. Please refer to the homework policy here.

## Problems

1. Let $G = (V,E)$ be a directed graph. We define a set function $f: 2^V \to \mathbb{R}$ by defining, for a set $S \subseteq V$, $f(S)$ to be the number of edges leaving $S$:

1. A set function $g: 2^V \to \mathbb{R}$ is submodular if for any two sets $A,B \subseteq V$,

Prove that $f$ is submodular.

2. A set function $g: 2^V \to \mathbb{R}$ is symmetric if $g(S) = g(V \setminus S)$ for all $S \subseteq V$. A graph is Eulerian if every vertex has the same number of outgoing edges as incoming edges. Show that $f$ is symmetric iff $G$ is Eulerian.

3. A set function $g: 2^V \to \mathbb{R}$ is posi-modular if for all sets $A,B \subseteq V$, we have

Show that if $G$ is Eulieran, then $f$ is post-modular.

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

2. Let $G = (V,E)$ be a directed capacitated graph. Let $\lambda: V \times V \to \mathbb{R}$ be defined by

Prove the following triangle inequality'' for cuts: for all distinct $s,t,u \in V$,