Problem 814

Let $k\geq 2$ and $G$ be a graph with $n\geq k-1$ vertices and

(k-1)(n-k+2)+\binom{k-2}{2}+1

edges. Does there exist some $c_k>0$ such that $G$ must contain an induced subgraph on at most $(1-c_k)n$ vertices with minimum degree at least $k$ ?

Source: erdosproblems.com/814

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved: the site labels the problem PROVED. The status-defining source is Theorem 1.3 of Sauermann (Sauermann et al. 2019) (J. Combin. Theory Ser. B 134 (2019), 36--75; refereed; cited from arXiv v2): for $k\ge2$ and every integer $1\le t\le\frac{(k-2)(k+1)}2-1$ , every graph on $n\ge k-1$ vertices with at least $(k-1)n-t$ edges contains a subgraph on at most $\bigl(1-\frac1{\max(10^4k^2,100kt)}\bigr)n$ vertices with minimum degree at least $k$ . With $t=\frac{(k-2)(k+1)}2-1$ the edge count is $(k-1)n-t=t_k(n)+1$ , so the answer is yes with $c_k=\varepsilon_k=1/\max\bigl(10^4k^2,100k(\tfrac{(k-2)(k+1)}2-1)\bigr)>1/(10^4k^3)$ , the bound the site records as $c_k\gg1/k^3$ . The range of $t$ is empty for $k=2$ , so the theorem as printed covers $k\ge3$ ; the case $k=2$ is elementary and is checked on this page with $c_2=1/5$ . Earlier bounds: $n-\lfloor\sqrt n/\sqrt{6k^3}\rfloor$ vertices (Theorem 1 (Erdős 1990) of [EFRS90], p. 53) and $n-n/(8(k+1)^5\log_2n)$ (Theorem 1.3 (Mousset, Noever and Škorić 2017) of [MNS17], refereed: the journal version, Electron. J. Combin. 24 (2017), Paper 4.9, p. 2, after a revised proof; arXiv v1 prints $4$ for $8$ ). The result and its acceptance evidence are recorded on the claim page Sauermann's proof, from which the frontmatter is derived.

EFRS90: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Subgraphs of minimal degree $k$ . Discrete Math. 85 (1990), no. 1, 53--58, doi:10.1016/0012-365X(90)90162-B (as its Crossref record gives it; the site's reference text gives "Discrete Math. (1990), 53-58"). The printed article, pp. 53--58: Theorem 1 and the generalized wheel, p. 53; the attribution of the $k=3$ case, the Conjecture, Theorem 2 and Lemma 3, p. 54; the sharpness sentence and Lemma 4, p. 55; Lemma 5, p. 56; the proof of Theorem 1 and the $C^{k-1}$ example, p. 57; the Problems section and the references, p. 58. Library home: Erdős 1990; paged at Erdős 1990, Theorem 1, Erdős 1990, Conjecture (p. 54), Erdős 1990, Lemma 3 and Erdős 1990, Lemma 4.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley (1991), 397--406. The site's source for the case $k=3$ "of Erdős and Hajnal". Not held: past the Rényi archive's 1989 cutoff; no open copy located, so the passage is known only from the site.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350, doi:10.1080/16073606.1993.9631741. The site cites p. 344; [Sa19] (p. 2) cites "[1, p. 13]" for the $k=3$ conjecture. Chapter V, problem 5, printed p. 344: the question for $k=3$ ("every $G(n;2n-1)$ has an induced subgraph of $m$ vertices with $m<n(1-\epsilon)$ , every vertex of which has degree $\ge3$ "), the bound $m<n-c\sqrt n$ from its reference [48] ([EFRS90] with the 1988 Ars Combinatoria paper), and "we found no counterexample to the stronger conjecture"; a problem paper without proofs. Library home: Erdős 1993.
MNS17: Mousset, F., Noever, A. and Škorić, N., Smaller subgraphs of minimum degree $k$ . Electron. J. Combin. 24 (2017), no. 4, Paper 4.9, 8 pp., doi:10.37236/7167 (published 6 October 2017, as its Crossref record gives it); arXiv:1703.00273 (v1, 1 March 2017, 6 pp.; the only arXiv version, with no journal reference in the arXiv record). Conjecture 1.1 and Theorem 1.2, p. 1; Theorem 1.3, p. 2; Lemma 2.1, p. 2. Library home: Mousset, Noever and Škorić 2017; paged at Mousset, Noever and Škorić 2017, Theorem 1.3.
Sa19: Sauermann, L., A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree $k$ . J. Combin. Theory Ser. B 134 (2019), 36--75, doi:10.1016/j.jctb.2018.05.002 (as its Crossref record gives it; the site's reference text gives "(2019), 36-75"); arXiv:1705.09979 (v1 28 May 2017; v2 26 June 2018, 34 pp.; no journal reference in the arXiv record). Fact 1.1, p. 1; Conjecture 1.2, Theorem 1.3 and the deduction, p. 2; the induced-subgraph remark, p. 3. Library home: Sauermann et al. 2019; paged at Sauermann et al. 2019, Theorem 1.3 and Sauermann et al. 2019, Fact 1.1.

Problem 814

Status

Proof claims

Discussion