# Proof for connected simple undirected graph with more than one vertex

Given a connected simple undirected graph G with more than one vertex, I am asked to show that there is at least one vertex $$v$$ that fulfills $$\frac{1}{deg(v)} \sum_{w \in N(v)} deg(w) \geq \frac{2 |E|}{|V|},$$ where $$N(v)$$ is the neighborhood of vertex v, $$|E|$$ is the number of edges and $$|V|$$ is the number of vertices.

I have tried this by induction over $$|E|$$ or $$|V|$$ with the base case of $$|E|=1$$ being trivial, but having trouble to show that it holds when adding an edge or a vertex. Also I suspect it might help to use $$\sum_{v \in V} deg(w) = 2 |E|$$, but I don't understand how to quantify the $$\frac{1}{deg(v)} \sum_{w \in N(v)} deg(w)$$ part. Another idea would be to show that the average of the L.H.S. over all vertices is $$\geq \frac{2 |E|}{|V|}$$, from which the result would follow, but I am unable to show this as well.

Any help or hints would be appreciated, I am new to graph theory.

Suppose, for a contradiction, that for all vertices that inequality is true. Summing over all vertices $$v \in V$$. We get

$$\sum _{v \in V} \sum_{w \in N(v)} \deg(w) < 2 \frac{|E|}{|V|} \sum_{v \in V} \deg(v) = \frac{1}{|V|} \left(\sum_{v \in V} \deg(v) \right)^2$$

where the last equality is by the handshake lemma.

Note that on the LHS each $$\deg (w)$$ will be counted once for each of its neighbours, so it will be counted $$\deg(w)$$ times. Hence, we have the inequality

$$\sum_{v \in V} \deg(v) ^2 < \frac{1}{|V|} \left( \sum_{v \in V} \deg(v) \right)^2$$

But this is false by the Cauchy Schwartz inequality applied to the vectors $$(1,...,1)$$ and $$(\deg v_1,..., \deg_{|V|})$$.

• Thanks for the very quick reply! I understand the statement "where the last inequality is by the handshake lemma" to mean "... the last EQUALITY ...", since the handshake lemma is an equality(?) Not sure whether I am "supposed to" use the generalized mean here, since I am in first year math and we have not covered it yet, but this certainly helps. Thank you. Dec 13, 2020 at 15:50
• Yes, sorry, that's equality. As for the generalised mean inequality, you can also use the Cauchy-Schwartz inequality. Just added an edit to show this. Please mark the question as solved if this is enough :) Dec 13, 2020 at 16:24