How to prove a function is a submodular function?

Question

For a graph $G(V,E)$ and each edge has a non-negative weight. Let $x(U)$ is the summation of the edge weight of cut. Then, for any two subsets $A$, $B$ how to prove that $x(.)$ is a submodular function. That is, $x(A)+x(B) ≥ x(A ∪ B) + x(A ∩ B)$.

Answer 1

The proof is straightforward. For any disjoint subsets $V’,V’’$ of $V$ let $x(V’,V’’)$ be the sum of weights of all edges with one vertex in $V’$ and the other in $V’’$.

Then the left hand side of the inequality equals

$$x(A,V\setminus A)+ x(B,V\setminus B)= x(A\cap B, V\setminus (A\cup B))+ x(A\setminus B, V\setminus (A\cup B))+ x(A\cap B, B\setminus A)+x(A\setminus B, B\setminus A)+ x(A\cap B, V\setminus (A\cup B))+ x(B\setminus A, V\setminus (A\cup B))+ x(A\cap B, A\setminus B)+x(B\setminus A, A\setminus B),$$

whereas the right hand side of the inequality equals

$$x(A\cup B,V\setminus (A\cup B))+ x(A\cap B, V\setminus (A\cap B))= x(A\cap B,V\setminus (A\cup B))+ x(A\setminus B,V\setminus (A\cup B))+ x(B\setminus A,V\setminus (A\cup B))+ x(A\cap B, V\setminus (A\cup B))+x(A\cap B, B\setminus A)+ x(A\cap B, A\setminus B).$$

So the difference between the left hand side and the right hand side is $$x(A\setminus B, B\setminus A)+x(B\setminus A, A\setminus B)\ge 0.$$