Homework 8 (due Thursday, October 21st)
1. 4F in Van Lint. (See the hint.)
2. 4H in Van Lint. (See the hint.)
3. 6A in Van Lint. (See the hint.)
4. Let G be a connected graph with n ≥ 3 vertices such that d(x)+d(y)
≥ n for every pair of non-adjacent vertices x, y of G, where d(x) and d(y)
are the degree of x and y respectively. Show that G has an Hamiltonian
cycle.