I wanted to find a proof that uses Hall's marriage theorem [1] instead of double-counting.

Given a graph $G=(V,E)$, let $K$ be the set of kings in $V$, and $R:=V \setminus K$ the rest. 

**Claim:** $|K| < |R|$.

**Proof** Let $G=(V,E)$ be a counterexample that minimizes the sum $|V|+|E|$, so $|K| \ge |R|$. Then $G$ is bipartite, since any edge between nodes in $R$ can be removed.  If $|K|>|R|$ then removing one king would yield a smaller counterexample, so $|K|=|R|$.  If there was a  subset $S$ of $K$  where its neighborhood satisfies $|N(S)|< |S|$, then the induced graph on  $S \cup N(S)$ would be a smaller counterexample.    Thus the Hall condition is met in $G$. Removing from   $G$ a perfect matching of $K$ to $R$  yields a smaller counterexample.

[1] https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem