The threshold for the Erdős, Jacobson and Lehel conjecture to be true (Q2508636)

The problem of finding the smallest even integer \(\sigma(k, n)\) such that every \(n\)-term positive graphic sequence \(\pi\) with \(\sigma(\pi)\geq\sigma(k, n)\) is potentially a \(K_{k+1}\)-graphic is studied. It was previously proven that \(\sigma(k, n)=(k-1)(2n-k)+2\), for sufficiently large \(n\). This relation is known as the EJL conjecture. The problem to determine the smallest integer \(N(k)\) so that EJL holds for \(k \geq 2\) and \(n \geq N(k)\) appears. Some particular cases of this problem were previously studied (\(k=2,3,\dots,7\)). The exact values of \(\sigma(k, n)\) were previously found and published for \(k+1 \geq n \geq 2k+1\). In this article the exact values of \(\sigma(k, n)\) for \(n \geq 2k+3\) and \(k \geq 6\) are further determined and, as a consequence, the problem of finding \(\sigma(k, n)\) is completely solved. The exact values of \(N(k)\), for \(k \geq 6\), are also obtained as a corollary of the main theorem in the article.