Let G = (V, E) be an undirected graph with subset I of V an independent set. For each a ˆˆ I and each Hamilton cycle C for G, there will be deg (a) - 2 edges in E that are incident with a and not in C. Therefore there are at least ˆ‘aˆˆI[deg(a) - 2] = ˆ‘aˆˆI deg(a) - 2|I| edges in E that do not appear in C.
(a) Why are these ˆ‘aˆˆI[deg(a) - 2 |I| edges distinct?
(b) Let v = |V|, e = |E|. Prove that if

then G has no Hamilton cycle.
(c) Select a suitable independent set I and use part (b) to show that the graph in Fig. 11.86 (known as the Herschel graph) has no Hamilton cycle.

Transcribed Image Text:

Σ deg(a) +2111 e- < u, Figure 11.86