Corollary 11.6: If G = (V,E) is a loop-free undirected graph with |V| = n ≥ 3, and if |E| ≥ ("₂¹) +2, then G has a Hamilton cycle.
Assignment 4
Please submit your assignments on Moodle.
Show all the steps of your solution for the full mark.
1. Solve the following:
a) Show that the Petersen graph [Fig. 11.52(a)] has no Hamilton cycle but that it has a
Hamilton path.
b) Show that if any vertex (and the edges incident to it) is removed from the Petersen graph,
then the resulting subgraph has a Hamilton cycle.
2. Find a counterexample to the converse of Theorem 11.8.
Theorem 11.8: Let G = (V, E) be a loop-free graph with |V | = n ≥ 2. If deg(x) +
deg(y) ≥ n − 1 for all x, y ∈ V, x̸ = y, then G has a Hamilton path.
3. Let G = (V, E) be a loop-free undirected n-regular graph with |V | ≥ 2n + 2. Prove that G
(the complement of G) has a Hamilton cycle.
4. 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?
Step by step
Solved in 2 steps with 12 images
