MathDB

A graph

G

has

n

vertices (

n>1

). For each edge

e

let

c(e)

be the number of vertices of the largest complete subgraph containing

e

. Prove that the inequality (the summation is over all edges of

G

\sum_{e} \frac{c(e)}{c(e)-1}\le \frac{n^2}{2}.

Problem Statement