Grinberg-Introduction-Graph-Theory · Problem 3.5

Multigraphs

Mathematics — Graph Theory · multigraph-average-neighbor-degree

Problem

Let

G = (V, E, \varphi)

be a multigraph that has no loops. If

e \in E

is an edge that contains a vertex

v \in V

, then we let

e/v

denote the endpoint of

e

distinct from

v

. For each

v \in V

, we define a rational number

q_v

q_v = \sum_{\substack{e \in E;\\ v \in \varphi(e)}} \frac{\deg(e/v)}{\deg v}.

(Note that the denominator

\deg v

on the right hand side is nonzero whenever the sum is nonempty!) (Thus,

q_v

is the average degree of the neighbors of

v

, weighted with the number of edges that join

v

to the respective neighbors. If

v

has no neighbors, then

q_v = 0

.) Prove that

\sum_{v \in V} q_v \geq \sum_{v \in V} \deg v.

(In other words, in a social network, your average friend has, on average, more friends than you do!) [Hint: Any positive reals

x

and

y

satisfy

\dfrac{x}{y} + \dfrac{y}{x} \geq 2

. Why, and how does this help?]