I met this problem when dealing with a social network problem. It is a subproblem of that. The problem is like that:
We look at a graph $G(V,E)$, where $V$ is the set of vertices and $E$ set of edges. We define $x \in V$ as an important vertex if at least $\frac 1 3\, \delta(x)$ ($\delta(x)$ refers to the degree of $x$) of the vertices in $x$'s neighborhood have degree no more than degree of $x$. We then define an edge as important when either one of the two vertices of the edge or both are 'important' vertices. We define the set of important edges as $E_1$.
We want to show $|E_1|≥\frac 1 2\,|E|$. I cannot really think out any method. Could anyone provide some suggestions?
Many thanks.