Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you for the answer. It seems quite satisfactory for me. I will see if anyone can provide a more general condition before accepting. –  EuYu Apr 12 '12 at 1:26

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}$.

share|improve this answer
    
Thank you for a beautiful counter-example. –  EuYu Apr 12 '12 at 3:34

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

share|improve this answer
    
What if we require the graph to be connected? –  EuYu Apr 12 '12 at 1:03
1  
OK, try three vertices and two edges. –  Robert Israel Apr 12 '12 at 6:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.