Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 1 / c / ii / Solution

For every $S\subseteq V$ and $x\notin S$, including $S=\varnothing$, the marginal increment isFor the empty set, this uses $w(x)\ge f(\varnothing )={\min }_{v\in V}w(v)$. The monotone set function property from (i) gives $f(A)\le f(B)$ when $A\subseteq B$. ConsequentlyThus diminishing returns holds, so $f$ is a submodular set function by (b).