Question: Suppose v = 2k and consider a graph G consisting of two complete graphs, one with k vertices, x1,...xk and one with k + 1 vertices, xk,...x2k. Notice that we get a graph with exactly 2k vertices, because the two complete graphs have one vertex in common. How do the degrees of the vertices relate to v? Does the graph you get have a Hamiltonian cycle? What does this say about whether we can reduce the lower bound on the degree in Theorem?
Theorem: If every vertex of a v-vertex simple graph G with at least three vertices has degree at least v/2, then G has a Hamiltonian cycle.