1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Martin S.
    Dec 13, 2020 at 15:50
  • $\begingroup$ 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 :) $\endgroup$ Dec 13, 2020 at 16:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .