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

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