The Chvátal-Erdös condition for cycles in triangle-free graphs (Q1917498): Difference between revisions

Chvátal and Erdös showed that if \(G\) is a graph whose connectivity is at least as large as its independence number, then \(G\) is Hamiltonian. Here it is established that a triangle-free graph satisfying the Chvátal-Erdös condition has cycles of every length \(n\) for \(4\leq n\leq v\), where \(v\) is the number of vertices in \(G\), unless \(G\) is \(K_{{v\over 2},{v\over 2}}\) or \(C_5\). This verifies a conjecture of D. Amar, I. Fournier and A. Germa.