Find proportion of 'important' edge among all edges in a graph
The problem you asked can be actually generalized to an arbitrary total order $\mathcal{O}$ on the vertices: a vertex $x$ is important iff at least $\frac{1}{3}$ of its neighbors are smaller than $x$ according to $\mathcal{O}$. For the order on degrees we can break the ties arbitrarily, which will only make important vertices and thus important edges less.

We prove it by the adjacency matrix $M$. Suppose the vertices are ordered: $x_1&lt;_\mathcal{O}\cdots&lt;_\mathcal{O}x_n$, where $n=|V|$. Then $M\in\{0,1\}^{n\times n}$ with $M_{i,j}=1$ iff $(x_i,x_j)\in E$. In the rest part of the proof we abuse the notation of $M_{i,j}$ to represent the grid in the matrix $M$, and for a set of grids $S$ we use $|S|$ to denote the number of $1$'s among these grids.

The matrix $M$ is naturally divided into two triangles:
$$L=\{M_{i,j}\mid i&gt;j\},\quad U=\{M_{i,j}\mid i&lt;j\}.$$
Denote the $i$-th row by $R_i$, so $|R_i|=\deg(x_i)$. Now $x_i$ is important iff $|L\cap R_i|\geq \frac{1}{2}|U\cap R_i|$. On the other hand, since $|L|=|U|=|E|$ which means $\sum_i |L\cap R_i|=\sum_i |U\cap R_i|=|E|$, we know
$$\begin{align*}
|E_1|&amp;\geq\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|\geq \textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\
&amp;=|E|-\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|&lt;\textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\
&amp;&gt;|E|-\frac{1}{2}\sum_{i=1}^n|U\cap R_i|=\frac{1}{2}|E|.
\end{align*}$$