Ore’s theorem. A connected graph with N vertices is said tosatisfy Ore’s condition i...

Ore’s theorem. A connected graph with N vertices is said tosatisfy Ore’s condition if deg (X) + deg (Y) ≥ N for everypair of vertices X and Y of the graph. Ore’s theorem statesthat if a graph satisfies Ore’s condition, then it has a Hamiltoncircuit.

(a) Explain why the complete bipartite graph K_{m, n} (seeExercise 71) satisfies Ore’s condition.

(b) Explain why for m ≠ n, the complete bipartite graphK_{m, n} (see Exercise 71) does not satisfy Ore’s condition.

(c) Ore’s condition is sufficient to guarantee that a connected graph has a Hamilton circuit but is not a necessary condition. Give an example of a graph thathas a Hamilton circuit but does not satisfy Ore’s condition.