Combinatorics and Graph Theory · Problem 5.3.1

Graph Theory — David Guichard

Mathematics — Combinatorics · hamilton-cycles-and-paths

Problem

Suppose a simple graph GG on nn vertices has at least (n−1)(n−2)2+2\dfrac{(n-1)(n-2)}{2} + 2 edges. Prove that GG has a Hamilton cycle. For n≥2n \geq 2, show that there is a simple graph with (n−1)(n−2)2+1\dfrac{(n-1)(n-2)}{2} + 1 edges that has no Hamilton cycle.

Related theory

Browse the problem library