I'm reading a book about (survivable) network design and i have a problem understanding a lemma. Given an undirected graph G and $V(G)$ its nodes and $E(G)$ its edges.
The book defines a proper function $f:2^{U} \rightarrow \mathbb{Z}_+$ sucht it holds that $f(S)=f(U\backslash S)$ for $S\subseteq U$, called symmetry, $f(A\cup B)\le \max\{f(A),f(B)\}$ for $A,B\subseteq U, A\cap B=\emptyset$, called maximality, and $f(\emptyset)=0$.
Now for a set $X\subseteq V(G)$ and $F\subseteq E(G)$ it defines that,
- $X$ is violated regarding $F$, if $|\delta_F(X)|=|\delta(X)\cap F|<f(X)$
- $F$ almost satisfies $f$ if for every $Y\subseteq V(G): |\delta_F(Y)|\ge f(Y)-1$
where $\delta(X)$ means the cut regarding node set $X$, so its the set of edges where exactly one node of each edge is within $X$.
The lemma i dont get is: Given some proper function g, some $F\subseteq E(G)$ almost satisfying g, and two violated sets $A$ and $B$. Then either $A\backslash B$ and $B\backslash A$ are both violated or $A\cap B$ and $A\cup B$ are both violated.
The book doesnt contain a proof, but just a note that its easy to proof. What i dont get here is why does the either-or hold? I mean why cant it be that all four sets are violated, but only exactly those two given?
A proper function has the property that for $A,B\subseteq U$ at least one of the following holds:
- $f(A)+f(B)\le f(A\cup B)+f(A\cap B)$
- $f(A)+f(B)\le f(A\backslash B)+f(B\backslash B)$
Using this i can proof that if the first holds, then $A\cup B$ and $A\cap B$ must be violated. If the second holds, the other sets are violated. But why cant it be that all sets are violated?
As a note: if $F$ almost satisfies f, that means $|\delta_F(Y)|\ge f(Y)-1$, it follows, that $Y$ is violated if $f(Y)-|\delta_F(Y)|=1$ and its not violated if $f(Y)=|\delta_F(Y)|$. Its because violated means $|\delta_F(Y)|<f(Y)$ thus the difference must be either zero (not violated) or one (violated). It seems this is the key to my problem, but i dont get it.
Im thinking about this for days now, so any thought on this would be highly appreciated.