Interesting problem! Lemma: let Z be the average degree of a graph, then there exists two adjacent vertices A and B such that d(A)+d(B)>=2Z. Assume not. Separate the vertices into 2 groups - ones with degree >= Z and ones with degree <=Z. Call these groups P and Q respectively. Notice that P is an empty graph. I claim that there is a perfect matching from P to Q. We prove this by halls condition. Assume that for some subset of vertices from P, their neighborhood in Q is smaller. But that would mean that the average degree of the neighborhood is bigger, meaning that there is at least one vertices in the neighborhood with degree >= Z. Contradiction. Hence there is a perfect matching. And from here we see that at least one pair must produce average degree at least Z, otherwise the average degree of the whole graph is less than Z. Hence we have proven the Lemma. Let M be the average degree of the red graph. Then there must exist two adjacent vertices with sum of degree at least 2M. It’s not hard to see that these 2 vertices and their neighborhood produce a biparte graph of size 2M. Hence 4x/y = 4(n*M/2)/y <= 4(n*M/2)/2M = n. And we are done!

R8kt wrote: Assume that for some subset of vertices from P, their neighborhood in Q is smaller. But that would mean that the average degree of the neighborhood is bigger... No, it does not mean that! It means the average degree with respect to the induced graph on P, Q is bigger. Which is a different story!

I don’t think I understand. Since we assumed that there are no edges between two elements of P, that means all of the edges that have a starting point at P go to Q. And since Q is smaller I think that’s enough ground to say that Q has bigger average degree.

So, $P$ is the set of vertices with degrees at least some (average) number $Z$. Why there should be no edges between vertices in $P$?

Sorry if I wasn’t clear enough. Im trying to prove that there are 2 adjacent vertices that their sum of degree is more or equal to 2*(the average). So if there are edges between vertices of P - the Lemma follows instantly.

Ok, my bad, I got it. So, the main idea is to notice that two connected vertices with enough neighbors do the job. Your argument makes the final shorter. One can see some other approach here.