If $G=(V,E)$ is a finite, simple, undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and $\text{deg}(v)= |N(v)|$. We say a vertex $v\in V$ is a *king* if $\text{deg}(v) > \text{deg}(w)$ for all $w\in N(v)$.


In the graph $G=(\{0,1,2\}, \big\{\{0,1\}, \{1,2\}\big\})$, one of the $3$ vertices is a king. Let $\text{King}(G)$ be the set of king vertices.


**Question.** Is it true that for any finite connected graph $G=(V,E)$ with $|V|>1$ we have $|\text{King}(G)|/|V|\leq 1/3$? If not, how large can this value get?



Are at most $1/3$ vertices "kings"?
For this discussion I am assuming we do not consider isolated vertices to be "Kings", even though technically your definition considers them to be so in a vacuous sense (I guess this convention goes [back to Shakespeare](https://www.enotes.com/shakespeare-quotes/king-infinite-space)). Otherwise of course one can make every vertex a king by having no edges whatseover.


For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting:
\begin{align\*}
\# \mathrm{King}(G) &= \sum\_{v \in \mathrm{King}(G)} 1 \\
&= \sum\_{(v,w) \in E'} \frac{1}{d(v)}\\
&< \sum\_{(v,w) \in E'} \frac{1}{d(w)} \\
&\leq \sum\_{w \in V \backslash \mathrm{King}(G)} 1 \\
&= \#V - \# \mathrm{King}(G)
\end{align\*}
hence
$$ \# \mathrm{King}(G) < \frac{1}{2} \# V.$$
Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of vertices) are completely optimal: the maximal number of kings in a graph on $n$ vertices is $\max( \lfloor \frac{n-1}{2} \rfloor, 0)$.


This bound can also be viewed as quantifying a variant of the "[friendship paradox](https://en.wikipedia.org/wiki/Friendship_paradox)". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)


