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