MathDB

We will call a hedgehog a graph in which one vertex is connected to all the others and there are no other edges; the number of vertices of this graph will be called the size of the hedgehog. A graph

G

is given on

n

vertices (where

n > 1

). For each edge

e

, we denote by

s(e)

the size of the maximum hedgehog in graph

G

, which contains this edge. Prove the inequality (summation is carried out over all edges of the graph

G

\sum_e \frac{1}{s(e)} \leqslant \frac{n}{2}.

Proposed by D. Malec, C. Tompkins

Problem Statement