(a) Apply theorems or necessary/sufficient conditions to determine (without attempting to find one) whether the following...

   

Transcribed Image Text:

(a) Apply theorems or necessary/sufficient conditions to determine (without attempting to find one) whether the following graph H has: (i) an Euler circuit and/or an Euler path which is not a circuit. (Explain clearly for each.) (ii) a Hamilton circuit. g H (b) Determine whether each simple graph G described below is planar. Explain. (i) G has six vertices with degrees 3.4.4.5, 5, 7. (ii) G has ten vertices where four of them have degree 6 and the other six have degree 7. (iii) G has no subgraph either isomorphic or homeomorphic to K33. (c) (i) The following table describes 5 committees in an organization, each with a list of members. Technology Education Health Transport Security Burhan Azizah Maimun Burhan Gopal Daud James Malik Johnny Haris Jamil Maimunah Sabri Malik Jamil May Li Sabri Thomas Tahir Tahir Woo Woo Wahid Tom Willy (ii) These committees would like to schedule weekly four-hour meeting times. While it would be possible to schedule the five committee meetings at five different times, this would consume 20 hours of the working week, and it was decided that it would be better to schedule the committees so that two or more of them are meeting at the same time whenever possible (in different rooms, of course). However, not all committees can meet at the same time, because some people are members of more than one committee. Show a method by graph that can determine the best way to schedule these five committee meetings? (Label your graph appropriately.) [Hint: Start by identifying people with more than one membership.] (Note: Avoid lengthy explanation. Summarize your deduction as much as possible.) Give a reason why graphs G and H below are nonisomorphic. d 12 h g b W C u y x (a) Apply theorems or necessary/sufficient conditions to determine (without attempting to find one) whether the following graph H has: (i) an Euler circuit and/or an Euler path which is not a circuit. (Explain clearly for each.) (ii) a Hamilton circuit. g H (b) Determine whether each simple graph G described below is planar. Explain. (i) G has six vertices with degrees 3.4.4.5, 5, 7. (ii) G has ten vertices where four of them have degree 6 and the other six have degree 7. (iii) G has no subgraph either isomorphic or homeomorphic to K33. (c) (i) The following table describes 5 committees in an organization, each with a list of members. Technology Education Health Transport Security Burhan Azizah Maimun Burhan Gopal Daud James Malik Johnny Haris Jamil Maimunah Sabri Malik Jamil May Li Sabri Thomas Tahir Tahir Woo Woo Wahid Tom Willy (ii) These committees would like to schedule weekly four-hour meeting times. While it would be possible to schedule the five committee meetings at five different times, this would consume 20 hours of the working week, and it was decided that it would be better to schedule the committees so that two or more of them are meeting at the same time whenever possible (in different rooms, of course). However, not all committees can meet at the same time, because some people are members of more than one committee. Show a method by graph that can determine the best way to schedule these five committee meetings? (Label your graph appropriately.) [Hint: Start by identifying people with more than one membership.] (Note: Avoid lengthy explanation. Summarize your deduction as much as possible.) Give a reason why graphs G and H below are nonisomorphic. d 12 h g b W C u y x