Let $G=(V,E)$ be a counterexample that minimizes the sum $|V|+|E|$.  Let $K$ be the set of kings in $G$, and $R$ the rest of the nodes, so $|K| \ge |R|$. If $|K|>|R|$ then removing one king would yield a smaller counter-example, 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.

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