Are at most $1/3$ vertices "kings"?

Question

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?

Answer 1

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). 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". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)

Answer 2

The fact that the number of kings is less than the number of non-kings is essentially equivalent to the following problem, proposed by Alexander Razborov to Tournament of Towns in 1990:

Given an $m\times n$ matrix, $m<n$. Some entries are starred, and each column contains a starred entry. Then there exists a star whose row contains more stars than its column.

(Here columns correspond to kings, rows to non-kings, stars to edges, and the strictness of inequalities is different.)

Answer 3

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

Answer 4

If we consider the complete bipartite graph $K_{n,m},$ where $n,m$ are natural numbers with $n < m,$ then the maximum degree of a vertex in this graph is $=m$ and there are at least $n$ many vertices having degree $m$, and so the number of "kings" (as per the definition above) in this graph is $ = n,$ and the total number of vertices $=n+m.$

Now, since $n,m$ can be anything (with $n \le m$), so one can take $n,m$ to be such that $n/(n+m) > \frac{1}{3},$ and thus in this case we see that the number of kings in this graph is $> \frac{1}{3} \cdot$ the number of vertices in the graph.

For such graphs you can just set $n=m-1$ to see that you cannot get an "asymptotic" bound of $< 1/2.$