Guichard-Combinatorics-Graph-Theory · Problem 5.3.1
Graph Theory
Mathematics — Probability · hamilton-cycles-and-paths
Problem
Suppose a simple graph G on n vertices has at least 2(n−1)(n−2)+2 edges. Prove that G has a Hamilton cycle. For n≥2, show that there is a simple graph with 2(n−1)(n−2)+1 edges that has no Hamilton cycle.