TUYMAADA 2024 J2

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