I do not quite think that your approach can provide a contradiction.
A set of vertices, no two of which are joined to each other, is called an independent set. I will use this terminology. So our question is this : in a graph with hundred vertices and maximum degree four, we can find an independent set of size $20$.
Here's a better and easier way to do things. We will provide an algorithm that will find an independent set of size $20$ within the setup. Start with an empty set $S$.
Take any vertex $v$ in the graph, and add it to $S$.
Remove $v$ and its neighbours from the graph, and repeat the above step with the new graph.
End when there are no vertices left.
Now, what is the size of $S$? Note that at each step, at most five vertices removed at each step,since you remove the chosen vertex $v$ and its neighbours, of which there can't be more than four. Now, there are hundred vertices, which means that the steps given above repeat at least $20$ times. For each step, some new vertex is added to $S$. It follows that $S$ has at least $20$ elements.
Now, $S$ is an independent set. To see this, if two vertices $A$ and $B$ are in $S$ and are connected by an edge, then if (without loss of generality) $A$ was chosen before $B$ as a member of $S$ by the algorithm, then $B$ would have been removed from the graph, so it cannot have been made a member of $S$.
Consequently, $S$ is an independent set of size $20$.
Use the above approach for a generalization :
In every graph with $v$ vertices and maximum degree $d$, one can find an independent set of size $\frac n{d+1}$.
I am not sure that one can improve the number $\frac n{d+1}$. You can test this by trying trivial examples.
The proof is fine.
A more general setup for the proof would be to consider the graph $G$ with vertex set $S$ and an edge between $x, y\in S$ whenever $A_x \cap A_y = \varnothing$. (It might be more convenient to put an edge between $x,y$ for every element of $A_x \cap A_y$, making $G$ a multigraph.) Then we are looking for an independent set of $100$ vertices in $G$.
Your bipartite graph between $B'$ and $C$ has a sort of incarnation within $G$. Consider the subgraph of $G$ consisting of all edges between $B$ and $B'$. Every $b \in B$ has degree $101 \cdot 100$ in $G$ ($b$ has an edge to $b + a_1 - a_2$ for every $a_1, a_2 \in A$ with $a_1 \ne a_2$), and these edges must all go to $B'$, since $B$ is independent. Every $b' \in B'$ has at least $1$ edge to $B$, because $B$ is a maximal independent set. So the number of edges between $B$ and $B'$ is $101 \cdot 100 \cdot |B|$, but it's also at least $|B'| = 10^6-|B|$. Therefore
$$
10100 |B| \ge 10^6-|B| \iff |B| \ge \frac{10^6}{10101} > 99.
$$
This is essentially a restatement of your argument: rather than have $10100$ elements of $C$ with degree $1$ for every $b \in B$, we combine them into a single vertex $b$ with degree $10100$.
More generally, this shows that in a graph (or multigraph) $G$ with $n$ vertices and maximum degree $\Delta(G)$, there is an independent set of size $\frac{n}{\Delta(G)+1}$.
The probabilistic method can be used here to get a bound that's better in general, but not an improvement in this problem. In general, we can get to $\frac{n}{d+1}$, where $d$ is the average degree in $G$. But here, the average degree is also quite close to $10100$, so this is not much help.
Here is the probabilistic argument. Randomly permute the elements of $S$ as $b_1, b_2, \dots, b_{10^6}$, and go through them one at a time to create an independent set $B$. For each $b_i$, add $b_i$ to $B$ if every element of the form $b_i + a_1 - a_2$ (with $a_1, a_2 \in A$ and $a_1 \ne a_2$) comes after $b_i$ in our random ordering.
This is guaranteed to create an independent set: if $b_i + a_1 - a_2 = b_j$, then either $i<j$ (and so we are guaranteed not to have picked $b_j$) or $i>j$ (and so we are guaranteed not to have picked $b_i$). For any $b \in S$: of $b$ and its at-most-$10100$ adjacent elements, each is equally likely to come first in the random ordering, and it's $b$ itself with probability $\frac{1}{10101}$, in which case we add it to $B$.
So the expected size of $B$ is at least $\frac1{10101}|S| = \frac{10^6}{10101} > 99$, as before, and therefore some random ordering produces a $B$ of size at least $100$.
Best Answer
Your final simplification is incorrect; $\binom{100}{50}\cdot 1=\frac{100}{50}\cdot\binom{99}{49}$, so the penultimate inequality is true.
This method couldn't possibly be sufficient since you haven't yet used the fact that each set only has one label. (Your solution so far would still apply if multiple labels are allowed and you have an edge if any one of the labels of $M-s$ is $s$, when the result clearly isn't true.)