# To what degree do min-cuts specify the cut function of a graph?

Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C_G(S) = |\{(u,v) \in E : u \in S \wedge v \not\in S\}|$$

For any two vertices $i,j \in V$, let the $(i,j)$ min-cut in a graph $G$ be: $$\alpha_{i,j}(G) = \min_{S \subset V : i \in S, j \not \in S}C_G(S)$$ Now, suppose we have two unweighted graphs on the same vertex set, $G = (V,E)$ and $H = (V,E')$ such that they are identical with respect to all $(i,j)$ min-cuts: $$\forall i,j \in V, \alpha_{i,j}(G) = \alpha_{i,j}(H)$$ How much can $H$ and $G$ differ with respect to their cuts? That is, how large can the following quantity be: $$\Delta(H,G) = \max_{S \subset V} |C_G(S) - C_H(S)|$$

Note that if the graphs are allowed to be weighted (or to be multigraphs), then for any $G$, there is a tree $T$ that agrees with $G$ on all min-cuts (A Gomory-Hu tree). But I am interested in the case of unweighted graphs...

• I love how it's "function of a graph" instead of "graph of a function" – David Corwin Aug 24 '10 at 21:52