cycle of G. 50. 16. Let G be a graph. A cycle of G that contains all the vertice
ID: 3198496 • Letter: C
Question
cycle of G. 50. 16. Let G be a graph. A cycle of G that contains all the vertices in G is called a Hamilton cycle a. Show that if n 2 5, then Oh has a Hamiltonian cycle. b. Prove that the graph in the figure does not have a Hamiltonian cycle. 50.17. Consider the following algorithm. Input: A connected graph G. . Output: A spanning tree of G. (1) Let T be a graph with the same vertices as G, but with no edges. (2) Let ei , e2, . . . , em be the edges of G. (3) For k 1,2,...,m, do: (3a) If adding edge er to T does not form a cvcle with edges already in TExplanation / Answer
a. According to Dirac's Theorem
An n-vertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.
Cn complement has degree of each vertex (n-3) .Since Cn has degree of each vertex 2 and in the complement graph n will not be connected to the two neighbouring vertices in Cn and itself hence degree will be (n-3).
n?3 ? n/2 ? n/2 ? 3?n ? 6
Therefore for n ? 6 Cn complement will have a hamiltonian cycle.We need to show for n=5 only.
C5 is a self complimentary graph. Since C5 is itself a hamiltonian cycle hence its complement will also be hamiltonian.
b. The graph in the figure can be coloured with two colours W and B in the following way
B W B W B
W B W B W
B W B W B
W B W B W
B W B W B
But if the graph had a Hamiltonian Cycle then since the graph has odd number of vertices(25) it would require 3 colours at least (cycles of odd length require 3 colours at least) which is a contradiction as it can be coloured by 2 colours. Thus the graph in the picture does not have a Hamiltonian Cycle
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.