1
$\begingroup$

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).

3 Answers 3

2

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.

  • 0
    Thank you for the answer. It seems quite satisfactory for me. I will see if anyone can provide a more general condition before accepting.2012-04-12
2

For the connected (and planar) version consider an icosohedron with a Y on each face (put a vertex in the center of each face and connect it to each of the vertices of that face. It is a graph with 20 vertices of degree 3 and 12 of degree 10 for an average of $5\frac{5}{8}$. But every edge either connects two vertices of degree 10 (the original edges of the icosahedron), or a vertex of degree 3 to a vertex of degree 10 (the edges of the added Y's), all the sums are $\ge 13$ which is more than $11\frac{1}{4}$.

  • 0
    Thank you for a beautiful counter-example.2012-04-12
1

This is not possible in general. For example, let $\Gamma$ be the graph with three vertices and one edge.

  • 1
    OK, try three vertices and two edges.2012-04-12