Subgraphs of d-regular graphs

Question

I want to prove the following, but seem to be utterly stuck as how to proceed as I feel there is not enough information given beforehand:

Let $n$ be even. Show that if $G=(V,E)$ is a $d$-regular graph on $n$ vertices, and $S\subseteq V$ is a set of size $n/2$, then $|E(S)|=|E(V\backslash S)|$.

Here $E(S)$ is the induced edge set on the vertex set $S$. Now I understand that for a $d$-regular graph that $|E|=\frac{1}{2}\sum_{v\in V}deg_G(v)=nd$ but I fail to recognize how this could help especially since we are dealing with so little information about $G$ or $S$, so I do not understand where to even start with this proof.

Answer 1

It's possible to make a shorter proof, but this hint will give you a nice intuition:

Hint:

• Let $G'$ be a graph obtained from $G$ by changing each edge into a pair of directed arcs. This makes $G'$ into a directed graph that has twice as many arcs as $G$ edges and each vertex has out-degree and in-degree equal to $d$.
• Each vertex can be assigned now two special out-degrees and two in-degrees:
  1. $\deg_{\to S}(v)$ – number of edges leading from $v$ to $S$,
  2. $\deg_{\to V\setminus S}(v)$ – number of edges leading from $v$ to $V\setminus S$,
  3. $\deg_{S \to}(v)$ – number of edges leading from $S$ to $v$,
  4. $\deg_{V\setminus S}(v)$ – number of edges leading from $V\setminus S$ to $v$.
• Observe that for any $v$ we have $$\deg_{\to S}(v) + \deg_{\to V\setminus S}(v) = d,\\\deg_{S \to}(v) + \deg_{V\setminus S \to}(v) = d.$$
• Observe that $|E(S)| = \frac{1}{2}\sum_{v \in S}\deg_{\to S}(v)$.
• Compare the three numbers: $$ \sum_{v \in S}\deg_{\to V\setminus S}(v),\\ \sum_{v \in S}\deg_{V\setminus S \to}(v), \\ \sum_{v \in V\setminus S}\deg_{\to S}(v).$$

I hope this helps $\ddot\smile$