A large set of non-Hamiltonian graphs
It is proved that the set of not-1-edge-tough graphs (N1ET) is a better approximation for the set of non-Hamiltonian graphs then the previously given sets. The best previous approximation is the set of non-sub-2-factor graphs (NS2F). The main result of the present article is that the set N1ET?NS2F is -complete, which suggests that N1ET is essentially larger than NS2F.
edge-toughness toughness hamiltonian cycle