Question

(1) In this problem, you will analyze the following graph G: For each of the following, both answer the question and in complete sentences, explain why. Include clearly labelled images where appropriate. (Saying “because Sage said so” will receive no credit.) (e) Is G Eulerian (i.e. there exists an Euler loop)? (f) Is G Hamiltonian (i.e. there exists a Hamilton loop)? (g) What is G's chromatic number (G)? (h) What is G's chromatic index ch(G)?

Answer 1

Please give me thumbs up. Thank you.

(e) Ef 19) No, G is not Eulerian. graph to be Eulerian, we reequire the degree of each vertex should be even . But hare degree of each vertex is 3 and that is odd. Gis not alwian. Yes, G is hamiltonian and the hamiltonian cycle is 0-1 -2-3-4-5-6-7 -9-10-11-12-13-0. 2 al Lets start from a vertex and procred by giving minimum Calor possible toho to every heighboring vertex. As we can observe that we can do proper coloning in exactly a colass. and since there is an evenegle in graph & less than a calon is hat possible > x6 =2 . for chromatic Index , we have to color the edges with minimum реміЪС Ss. Color all the edges in outer circle by alternating 182 colors and color all the edges inside the circle by third calor 3. . Can be colored by using 3 - colors a chromatic index should be less than equal to 3. Also since we have degree of each vertex as 3 > exactly 3 adjacent edges. Therefore, we need greater than equal to 3 roots colors. Hence, the chromatic index is equal to 13