Having a graph of complaints with 10% of enemies, prove that you always may arrest more enemies than honest people Not more than 10% of people of some country are enemies. Each man knows less than 500 other people. Each honest man tells to the dictator about one enemy he knows, and each enemy tells about a random man.
Prove that the dictator is able to arrest such a set of people that strictly more than 50% of them would be enemies.
The easy thing is to arrest exactly 50%. We know that the graph definitely has the cycle, and each cycle 50% consists of enemies. The graph consists of cycles and trees, that enters the cycles.
I've tried 2 strategies: to take 10% of people with the biggest amount of votes, and to take the smallest group with at least 10% of votes. None of this helps, but it seems that I need some compromise between these strategies, though I'm not sure about it.
UPD: There should be strict proof for any number of people in the country. But I guess the most important case is when there is very big amount of people.
UPD 2: If we know that every honest man tells about one enemy, we can deduce that every man knows at least one enemy.
 A: My answer is partial, but it contains some ideas which may be useful. 
I grew in Soviet Union, so the question looks natural for me. I even allowed myself to rename some its terms to feel the situation better. :-) Conversely to san’s answer, I have assumed that to know somebody is not the same as to be known by somebody, an example are celebrities. This interpretation makes the condition “each man knows less than 500 other people” useless, because given the denounce graph we can assume a posteriori that each man knows a man he denounced. But I hoped that in a solution process the meaning of a “magic number” will become more clear.  
Indeed, I obtained a simple solution when the country is small. Assume that it consists of $N$ men among which at most $E$ are enemies. (To give a chance to The Great Leader I assumed that $E<N/2$, because otherwise given all denounce edges constitute a directed cycle, He cannot surely determine a set having more than a half of enemies. Also if $E>N/2$ then the enemies can unite and to throw down The Great Leader). 
Let $d_1\ge\dots\ge d_N$  be a number of accusations against $i$-th man. If $d_1>E$ then the first man is an obvious enemy, so farther we’ll assume that $d_1\le E$. If $d_1+d_2+d_3>2E$ and there is at most one enemy among the first three men then the people who accused the remaining men are enemies, so there are at most $E$ of them. Since $d_1\ge d_2\ge d_3$ it implies that $d_2+d_3\le E$. Then $ d_1+d_2+d_3\le 2E$, a contradiction. So there is at least two enemies among first three men. So farther we’ll assume that $d_1+d_2+d_3\le 2E$. Continuing inductively, we obtain that for each $i$ with $2^i-1\le N$ either $d_1+\dots+d_{2^i-1}>iE$ and is this case among the first $2^i-1$ men are more then a half enemies or $d_1+\dots+d_{2^i-1}\le iE$. On the other hand, at most $2E$ men can be accused, so $d_1+\dots+d_{2E}=N$. So we obtain a contradiction provided $2E\le 2^i-1\le N$ but $iE<N$. In particular for $E=N/10$ we have $9E<N$ so if $2^9-1\ge N/5$ (that is if $N\le 2555$) then there exists such $i$ and The Great Leader can surely determine a set having more than a half of enemies. 
Since a possibility to deal only with small countries is outrageous for true great leaders, I tried to drop the country size restriction. And I became to a suspicion that The Great Leader was disinformed (of course, by enemies) and His problem is not only enemies and hardly collaborating members, but even the system. I conjecture that for each $\varepsilon>0$ there exists $N$ and $E$ with $E/N<\varepsilon$ and a denounce graph for which The Great Leader cannot surely determine a set having more than a half of enemies. 
A: I've made an assumption, that the number of people $N$ is way much higher than $500$.
Then I've considered the worst case, where every man knows $500$ other people.
In this case honest man have probability of not being shown as an enemy averagely $$p_h=1^{450}.998^{50}\approx .9047$$
Analogical probability for enemies is averagely $$p_h=.98^{450}.998^{50}\approx .0001$$
Thus we can compute the probabilities of being picked:
$$P_h=1-p_h\approx .0953 \\ P_e = 1-p_e\approx .9999$$
Now if we put all picked people to the jail, there will be $$K_e=P_e\cdot.1\cdot N\approx.09999\cdot N$$ enemies and $$K_h=P_h\cdot.9\cdot N\approx.08573 \cdot N$$ honest people. 
Thus there are more enemies than honest people in jail.
Edit
I also want to refer to your 'non-cycle' strategies (to long for a comment):
Consider case, where:


*

*30 enemies voted for one honest man and this man voted against one of this enemies

*in 26 groups 19 honest men voted against one enemy

*in one group 18 honest men voted against one enemy

*all enemies from these 27 groups voted against one man from one of these groups.


So we have then:


*

*Population of 570 people with 57 enemies and 30 voted men

*2 honest men voted by 30 and 27 votes

*26 enemies voted by 19 men each 

*1 enemy voted by 18 men

*1 enemy voted by 1 man


Picking 10% with the highest ammount of votes will cause picking 2 honest men and 1 enemy - there are no more enemies than honest people in this group
Picking the smallest group with at least 10% may be problematic - this approach cause selection of 2 honest men and no enemy.
A: Arrest everyone in any given cycle (which as you point out always exist)

Each honest man tells to the dictator about one enemy he knows

This means that in any cycle, there cannot be to consecutive honest persons. 
In turn, this means that there can't be more than half honest persons in the cycle (the worse case being an alternance honest-ennemy)
