Prove that for any directed graph G = (V, E), the following inequality holds: d(A) + d(B) ≥ d(A ∩ B) + d(A ∪ B)

Question

Let $G = (V, E)$ be a directed graph. For any subsets $X, Y \subseteq V$ of vertices, let \begin{align} E(X, Y ) := \left\{(u, v) \in E \mid u \in X \text{ and } v \in Y \right\} \end{align} denote the set of edges going from a vertex in $X$ to a vertex in $Y$.

For a subset $A \subseteq V$ of vertices, let $d(A) = \left|E(A, V - A)\right|$ denote the total number of edges exiting $A$ and going to a vertex outside of $A$. Note that, by definition, $d(\varnothing ) = 0$.

Prove that for any directed graph $G = (V, E)$, and for all subsets $A, B \subseteq V$ of its vertices, the following inequality holds: \begin{align} d(A) + d(B) \geq d(A \cap B) + d(A \cup B) . \end{align}

My idea is to take the sets E(A, V −A), E(B, V −B), E(A∪B, V −(A∪B)), and E(A∩B, V − (A ∩ B)) and somehow partition these sets into appropriate parts, to show that the inequality holds. However I'm not sure how to do this?

Answer 1

Consider the disjoint subsets $A\cap B, A-B, B-A, S-A - B$.
Consider an edge that goes from one subset to another distinct subset.
How many times is this edge counted on the LHS?
How many times is this edge counted on the RHS?

Is the first number always larger than or equal to the second number?

IE An edge from $A-B$ to $B-A$ is counted in $d(A)$ but not in $ d(B)$, $d( A \cap B)$, or $d(A \cup B)$, so the edge is counted at least as many times on the LHS as it is on the RHS.
If we can show this for each of these types of edges, then the inequality holds.

Answer 2

Let $C=V-A-B$, i.e. the set of all vertices not in $A$ or $B$ and $D=A \cap B$, i.e. the set of all vertices in both $A$ or $B$ . Then, as Calvin was saying, let $$ a= \vert (-D,C)\vert$$ $$ b= \vert (B-D,C)\vert$$ $$ c= \vert (D,C)\vert= \vert ((A \cap B),C)\vert$$ $$ d= \vert (D,A-D)\vert$$ $$ e= \vert (D,B-D)\vert$$ i.e. we count all the directed edges from the enclosed components in the diagram below (where D is to be imagined as intersecting A and B)

$$\require{enclose} {\scriptstyle \enclose{box} { \kern 1em \huge C \text{ } \kern 1em \enclose{circle}{\kern 1em {\huge {A-D}}\kern 2em} \enclose{circle}{ {\huge {D}}} \enclose{circle}{\kern 1em {\huge {B-D}}\kern 2em}}} $$

Then $d(A \cap B) = c + d + e$ and $d(A \cup B) = a + b + c$, i.e their sum is $a + b + 2c + d + e$

$d(A) = a + c + e$ and $d(B) = b + c + d$, giving their sum as $a + b + 2c + d + e$.

So the inequality is in fact an equality? No! In the second line we haven't counted the edges from $A - D$ to $B - D$. So $$d(A) + d(B) \geq d(A \cap B) + d(A \cup B) $$