I was reading lecture notes of graphs(from MIT 6042) and am having trouble understanding this proof:
I can't understand Let d be value such that deg(l) >= x >= deg(r), what values do d and x represent here and why did we consider them?
And how did we arrive at |N(S)|x >= |S|x?
Note:
I suspect that $d$ should be replaced by $x$. The consideration of $x$ must arise from the definition of "degree-constrained" - this is a term I am not familiar with.
Now for any subset $S$ of vertices in $L$, we have $d(v) \ge x$ for all $v \in S$. Hence the number of edges leaving $S$ is $\sum_{v \in S} d(v) \ge x |S|$.
On the other hand, every such edge goes to $N(S)$ (by definition of what $N(S)$ is). Every vertex in $v \in N(S)$ is in $R$, and hence receives $d(v) \le x$ edges. Thus the number of edges from $S$ to $N(S)$ is at most $\sum_{v \in N(S)} d(v) \le x |N(S)|$ (note that vertices in $N(S)$ could also receive edges from vertices not in $S$, so even the sum of degrees is just an upper bound here).
Hence, by double-counting edges from $S$ to $N(S)$, we have $$ |N(S)| x \ge e(S, N(S) ) \ge |S|x . $$