Sizes of graphs with induced subgraphs of large maximum degree (Q1815328): Difference between revisions

The following conjecture is considered: Let \(n\geq k\geq j\geq 1\) and \(n\geq 3\), let \(G\) be a graph with \(n+k\) vertices in which every \(n+j\) vertices induce a subgraph which contains a vertex of degree at least \(n\). Then \(G\) has at least \((k-j+1)n+\binom{k-j+1}{2}\) edges. The authors prove that this conjecture holds for \(j\geq 2\) and \(n\geq \max\{j(k-j),\binom{k-j+2}{2}\}\).