Let n ∈ Z+ with n ≥ 4, and let the vertex set V' for the complete graph Kn-1 be {v1, v2, v3, . . . , vn-1}. Now construct the loop-free undirected graph Gn = (V, E) from Kn-1 as follows:
V = V' ∪ {v}, and E consists of all the edges in Kn-1 except for the edge {v1, v2}, which is replaced by the pair of edges {v1, v} and {v, v2}.
(a) Determine deg(x) + deg(y) for all nonadjacent vertices x and y in V.
(b) Does Gn have a Hamilton cycle?
(c) How large is the edge set E?
(d) Do the results in parts (b) and (c) contradict Corollary 11.6?