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.


1 Answer 1


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*}$$

  • $\begingroup$ 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! :) $\endgroup$ Nov 22, 2016 at 14:18
  • $\begingroup$ 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|$?? $\endgroup$ Nov 23, 2016 at 18:31
  • $\begingroup$ @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|$. $\endgroup$
    – Wei Zhan
    Nov 23, 2016 at 18:39
  • $\begingroup$ 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$'? $\endgroup$ Nov 23, 2016 at 18:43
  • $\begingroup$ @ChenxiaoXU Basically yes. As I said in my post, we can break ties arbitrarily. $\endgroup$
    – Wei Zhan
    Nov 23, 2016 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.