# Find proportion of 'important' edge among all edges in a graph

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 deg(x)$ ($deg(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 'important ' edge as the edge when either one of the two vertices of the edge or both are 'important' vertices. We define the set of 'important' edge as $E_1$.

We want to show $|E_1| \geq \frac 1 2 |E|$. I cannot really think out any method. Could anyone provide some suggestions?

Many thanks.

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<_\mathcal{O}\cdots<_\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>j\},\quad U=\{M_{i,j}\mid i<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|&\geq\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|\geq \textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\ &=|E|-\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|<\textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\ &>|E|-\frac{1}{2}\sum_{i=1}^n|U\cap R_i|=\frac{1}{2}|E|. \end{align*}
• It took me a while for the last step to click. If anyone else is stuck: in the 2nd line, for each $i$ where $|L \cap R_i| < \frac{1}{2}|U \cap R_i|$ holds, we subtract a value strictly less than $\frac{1}{2}|U \cap R_i|$, and otherwise do (or equivalently, subtract) nothing; in the 3rd line, we subtract $\frac{1}{2}|U \cap R_i|$ for each $i$. Thus in the 3rd line, in either case, we subtract a strictly greater value for each $i$. Clever! :) Commented Nov 22, 2016 at 14:18
• Hi, many thanks for your reply. Could I ask why we have $x_i$ is important iff $|L \cap R_i| \geq \frac 1 2 |U \cap R_i|$?? Commented Nov 23, 2016 at 18:31
• @ChenxiaoXU $L\cap R_i$ captures the neighbors smaller than $x_i$, so $x_i$ is important iff $|L\cap R_i|\geq \frac{1}{3}\deg(x_i)$. Notice that $\deg(x_i)=|R_i|=|L\cap R_i|+|U\cap R_i|$. Commented Nov 23, 2016 at 18:39
• Ok, so your mean for matrix $M$, we make the order so that we have $deg(x_i) \leq deg(xj)$ iff $i<j$?? I think it from the '$x_1 < \mathcal{o} /cdots \mathcal{i} x_n$'? Commented Nov 23, 2016 at 18:43