Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue. 
Suppose the following two conditions hold:


* for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$
* for any $S\subseteq V$, if $G[S]$ contains no red edges, then it contains $O(|S|)$ blue edges


My question is: can we conclude from this that the total number of blue edges is linear?
I have no strong intuition for this, but it seems that it might be possible (some averaging/probabilistic argument?). To try to give an intuition, we can rephrase it as follows. The red graph is very sparse, even locally. The blue graph is also sparse in all regions that are free of red edges. Due to the sparseness of the red graph those 'regions' are numerous, so we hope this might imply that the blue graph is also sparse. 


One can maybe consider first an easier version, if we assume that the red degree of every vertex is $O(1)$. In this case I also don't know the answer. 


Note that it's already too weak if we replace the first condition with just: the total number of red edges is linear. Look at the example: a blue $K\_{\sqrt n,n-\sqrt n}$ with a red $\sqrt n$-clique added in the corresponding part. This graph has $\Omega(n^{3/2})$ blue edges (example by D. Palvolgyi). We can still ask in this version whether one can do better than $n^{3/2}$. 



A graph with few edges everywhere
I think one can push through the probabilistic arguments of Tim Gowers and Fedor Petrov in the general case, as follows. 


Let $c$ be a constant such that the number of red edges in $G[S]$
is at most $c|S|$ for every $S \subseteq V(G)$. One can order the vertices of $G$: $v\_1, v\_2, \ldots, v\_n$, so that every vertex has at most $2c$ neighbors with lower indices. (Define the ordering starting with the highest index. If $v\_n, \ldots,v\_{i+1}$ are defined, set $v\_i$ to be the vertex with the smallest degree in the subgraph induced by the vertices which are not yet indexed. This is a standard trick.)


Now we define a random subset $S$ of $V(G)$ recursively: if $S \cap$ {$v\_1, \ldots, v\_i$} is chosen put $v\_{i+1}$ in $S$ with probability $1/2$ if it is not joined by a red edge to any of the vertices already in $S$, otherwise don't put it in $S$. Then $S$ is red-free
and, just as in Fedor's answer, we can see that the probability that a pair of vertices $u$ and $v$ joined by a blue edge both lie in $S$ is at least $2^{-4c-2}$. Therefore the number of blue edges is at most 


$2^{4c+2}c' \mathbf{E}[|S|] \leq 2^{4c+1}c'|V(G)|,$ 


where $c'$ is the constant implicitly present in the condition on the density of the blue edges. 


