= Supermodularity of graph component count
{title2=$k(S\cap T)+k(S\cup T)\ge k(S)+k(T)$}
For open-edge sets $S,T$ in a fixed finite graph, including isolated <graph vertices> in $k$, one has $k(S\cap T)+k(S\cup T)\ge k(S)+k(T)$. Incidence-vector spans have rank $r(S)=|V|-k(S)$; their union span is the sum of the two spans, while the intersection-edge span is contained in the intersection of spans. The vector-space <dimension formula for a sum of subspaces> proves submodularity of $r$, equivalently supermodularity of $k$.
Back to article page
