Domination number is at most $n/2$ 
Let $G$ be a graph of $n$ vertices with no isolated vertex. Prove that the domination number of $G$ is at most $\lfloor n/2 \rfloor.$

Turns out this result can easily solve a combinatorics problem I'm working on right now. And since the problem only asks for even $n$ I'm going to ignore the odd numbers for the moment.
I tried induction like this: The base case is clear so assume the result hold for some even number $n$. Now given a graph of $n+2$ vertices I want to remove $2$ vertices so I can use the induction hypothesis. The problem is that for some graphs, removing any two vertices will give a graph with isolated vertices.
 A: Let $V$ denote the set of vertices of the graph $G$, let $D \subseteq V$ denote a dominating set, and let $N = V - D$ be the set of neighboring vertices. Also, put $n = |V|$. We can establish your result with the following two claims. Try to write down proofs before revealing them.
Claim: Either $|D| \leq \lfloor \frac{n}{2} \rfloor$ or $|N| \leq \lfloor \frac{n}{2} \rfloor$.

 Proof: If both $|D|$ and $|N|$ are greater than $\lfloor \frac{n}{2} \rfloor$, then $$ n = |V| = |D| + |N| \geq \bigl(1 + \lfloor \tfrac{n}{2} \rfloor \bigr) + \bigl(1 + \lfloor \tfrac{n}{2} \rfloor \bigr) > n, $$ a contradiction.

Now, the dominating number $\gamma(G)$ is the minimum $|D|$ over all dominating sets $D \subseteq V$, so in order to prove the claim, we have to guarantee that there exists some dominating set $D$ with $|D| \leq \lfloor \frac{n}{2} \rfloor$. The trick is symmetry:
Claim: If $(D, N)$ is a pair consisting of a dominating set and its neighbors, then so is $(N, D)$.

 Proof: Since $V = D \sqcup N$, every vertex is in exactly one of the two sets. The relation on vertices of being neighbors is symmetric: if $v$ and $w$ share an edge, then the same can be said about $w$ and $v$. Therefore, from the perspective of $N$, every vertex is either in $N$ or is a neighbor in $D$. Hence, $N$ is a dominating set for $G$.

Together, the two claims demonstrate that at least one of $D$ or $N$ is a dominating set of size no more than $\lfloor \frac{n}{2} \rfloor$, as desired.
