On the "strength" of Chvátal’s Hamiltonian degree condition vs. that of Bondy’s for k-connectedness

A graph is called Hamiltonian if it contains a spanning cycle. In 1972 Chvátal gave a well-known sufficient condition for a graphical sequence to be forcibly Hamiltonian, and showed that in some sense his condition is best possible. Even though, for each \(n \geq 3\), we have constructed exponentially many forcibly Hamiltonian \(n\)-sequences that do not satisfy Chvátal’s condition, in this talk we will discuss why we conjecture that the proportion of forcibly Hamiltonian \(n\)-sequences that satisfy Chvátal’s condition approaches \(1\) exponentially fast. Informally, with probability approaching \(1\) as \(n\to\infty\), we conjecture that a graphical \(n\)-sequence \(\pi\) is forcibly Hamiltonian if and only if \(\pi\) satisfies Chvátal’s condition. In contrast, we can essentially prove that for every \(k \geq 1\) the similar sufficient condition of Bondy for forcible \(k\)-connectedness is not necessary in the same way, where a graph \(G\) is called \(k\)-connected if at least \(k\) vertices must be removed from \(G\) to result in a disconnected graph.