Directed graph branching

Question

Let $G = (V, E)$ a directed graph then a $\textit{branching}$ $ B \ \subseteq E $ is a subset of edges such that there is at most one incoming edge for each vertex $v \in V$. Let $I = \{B \mid \text{ $B$ is a branching of $$E} \}$ and if $B_1, B_2 \in I$ with $|B_1| < |B_2|$ then show that $B_1 + b \in I$ for some $b \in B_2 \backslash B_1$. I have shown that if $B_1 \subset B_2$ or $B_1 \cap B_2 = \emptyset$ then $B_1 + b$ is a branching but still struggling with the general case. Any help is appreciated.

Answer 1

The first thing you have shown means that every subset of a branching is also a branching. Clearly, $B_2\setminus B_1 \subseteq B_2$ therefore it is a branching. Moreover, $B_1 \cap (B_2\setminus B_1) = \emptyset$ and your second result implies that their union is also a branching, which completes the proof.

Alternatively, in a more straightforward way, note that $|B_2| > |B_1|$ implies that there exists some $v$ in the neighborhood of $B_2$ but not in the neighborhood of $B_1$ thus picking as $b$ the set of edges that point to such $v$ yields the result.