This is a problem inspired by Hard planar graph problem.
Let $\nu$ be the average vertex degree of a graph $\Gamma$. Is it always possible to find an edge $\{u, v\}$ of $\Gamma$ such that $$\deg(u) + \deg(v) \le 2\nu$$ Intuitively, it seems like that this is the case, but I can't seem to find a nice way to prove it.
Edit/Update: Since the result seems to be trivially false for disconnected graphs, let us consider the case of connected graphs.
It seems intuitively true that this should be the case (atleast for connected graphs).
Best Answer
The inequality should go the other way, I think (assuming, of course, that there exists at least one edge).
Let $V$ and $E$ be the sets of vertices and edges respectively.
$|V| \nu = \sum_{v \in V} \text{deg}(v) = 2 |E|$ (each edge is counted twice)
Let $R = \sum_{\{u,v\} \in E} \text{deg}(u) + \text{deg}(v) = \sum_{v \in V} \text{deg}(v)^2$ (each vertex $v$ occurs $\text{deg}(v)$ times on the left side). Since there are $|E|$ terms in the sum on the left, at least one $\deg(u) + \deg(v)\ge R/|E|$.
By Cauchy-Schwarz, $|V|\nu = \sum_{v \in V} \text{deg}(v) \le \left(\sum_{v \in V} 1\right)^{1/2} \left(\sum_{v \in V} \text{deg}(v)^2\right)^{1/2} = |V|^{1/2} R^{1/2}$
i.e. $R \ge |V| \nu^2 = 2 |E| \nu$. Thus at least one $\text{deg}(u) + \text{deg}(v) \ge 2 \nu$.
But as Chris's example shows, you can't always get $\text{deg}(u) + \text{deg}(v) \le 2 \nu$. Indeed, any case where $\deg(u) + \deg(v)$ are equal for all edges but not all vertices have the same degree will be a counterexample, because the Cauchy-Schwarz inequality will be strict.