On the minimal degree condition of graphs implying some properties of subgraphs

Abstract

Erdős posed the problem of finding conditions on a graph $G$ that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let ${\delta }_r$ be the least number so that any graph $G$ on $n$ vertices with minimum degree ${\delta }_{r}n$ has the property $P_{r-1}(G)=K_{r}f(G),$ where $P_{r-1}(G)$ is the largest number of edges in an $(r-1)$-partite subgraph and $K_{r}f(G)$ is the largest number of edges in a $K_r$-free subgraph. We show that $\frac{3r-4}{3r-1}<{\delta }_r\le \frac{4(3r-7)(r-1)+1}{4(r-2)(3r-4)}$ when $r\ge 4.$ In particular, ${\delta }_4\le \mathrm{0.9415.}$

16 pages