A graph $ G$ with $ n$ vertices is given. Some $ x$ of its edges are colored red so that each triangle has at most one red edge. The maximum number of vertices in $ G$ that induce a bipartite graph equals $ y.$ Prove that $ n\ge 4x/y.$
Problem
Source: 2022 IFYM, Sozopol, final round
Tags: combinatorics, graph theory
18.09.2022 21:18
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!
19.09.2022 22:18
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!
20.09.2022 11:48
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.
20.09.2022 12:37
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$?
20.09.2022 12:54
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.
24.09.2022 17:01
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.