I have a social network in the form of an undirected graph $G = (V,E)$ with distinct non-negative integer keys. For each node $u \in V$, let the set $\Gamma(u) = \{ v \in V : (u,v) \in E \}$ be the neighbourhood of $u$. Clearly, I got that $d(u) = \left | \Gamma(u) \right |$, where $d(u)$ is the degree of $u$.I now want to split $\Gamma(u)$ into two sets of nodes$$\Gamma_{\text{low}}(u)  = \{ v \in V : v \in \Gamma(u) \text{ and } v < u \}$$$$\Gamma_{\text{high}}(u) = \{ v \in V : v \in \Gamma(u) \text{ and } v > u \}$$i.e. $\Gamma_{\text{low}}(u)$ and $\Gamma_{\text{high}}(u)$ contain neighbours of $u$ whose key is less than or greater than $u$'s, respectively.Assuming that the graph has got $m$ edges, is there a way to obtain an upper bound for $d_{\text{low}}(u) = \left | \Gamma_{\text{low}}(u) \right |$ and $d_{\text{high}}(u) = \left | \Gamma_{\text{high}}(u) \right |$ for varying $m$? I just can obtain the following relationship$$\sum_{u \in V} d_{\text{low}}(u) + \sum_{u \in V} d_{\text{high}}(u) = 2m,$$because the graph is undirected. I read somewhere that $d(u) = O\left ( \sqrt{m} \right )$ is a good bound for social networks, but how do I prove it?
Need an upper bound for node degree
algorithms;graph theory;social networks