The smallest degree sum that yields potentially P k -graphical sequences
Jiong-Sheng Li, Zi‐Xia Song · Journal of Graph Theory · 1998
A simple graph G is said to have property Pk if it contains a complete subgraph of order k + 1, and a sequence π is potentially Pk-graphical if it has a realization having property Pk. Let σ (k, n) denote the smallest degree sum such that every n-term graphical sequence π without zero terms and with degree sum σ (π) ≥ σ (k, n) is potentially Pk-graphical. Erdos, Jacobson, and Lehel [Graph Theory, 1991, 439449] conjectured that σ (k, n) = (k - 1)(2n - k) + 2. In this article, we prove that the conjecture is true for k = 4 and n e 10. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 6372, 1998