This study source was downloaded by 100000887385913 from CourseHero com on 07 03 2024 10 00 55 GMT 05 00 https www coursehero com file 112774286 Assessment 6 MMWdocx Polytechnic University of the PhilippinesCollege of CommunicationBayog Anthony James P Mathematics in the Modern WorldBABR 1 2Sir Edcon B Baccay Lesson 6 Assessment Mathematics of Graphs1 Let V cities of Metro Manila and E x y x and y are adjacent cities of Metro Manila a Draw the graph G defined by G V E You may use initials to name a vertex representing a city LetV Nc V MB C QC MR NV MN SJ MD PG PT TG MK PY PN LP MT E x y x and y are adjacent cities of Metro Manila This study source was downloaded by 100000887385913 from CourseHero com on 07 03 2024 10 00 55 GMT 05 00 https www coursehero com file 112774286 Assessment 6 MMWdocx Polytechnic University of the PhilippinesCollege of Communicationb Apply the Four Color Theorem to determine the chromatic number of the vertex coloring for G This study source was downloaded by 100000887385913 from CourseHero com on 07 03 2024 10 00 55 GMT 05 00 https www coursehero com file 112774286 Assessment 6 MMWdocx Polytechnic University of the PhilippinesCollege of Communication2 Apply Euler s Theorems and Fleury s Algorithm to determine Euler path and Euler circuits in each graph a Euler s Theorem 1 If a graph is connected and every vertex has an even degree then it has at leastone Euler circuit If a graph has at least one Euler circuit then it must have a Euler path Graph a has a Euler circuit and a Euler path Euler path and circuit A G B H G F E H C J E D C B Ab Euler s Theorem 2 If a graph is connected and has just two vertices of odd degree then it has at least one Euler path Any path must start at one of the odd degree vertices and end at the other one Euler path H D C H L M H G L K E J K F G C B F E A B E3 A businessman had to visit five cities A B C D and E The distance in hundred miles between the five cities is as follows ABCDEA 7684B7 856 This study source was downloaded by 100000887385913 from CourseHero com on 07 03 2024 10 00 55 GMT 05 00 https www coursehero com file 112774286 Assessment 6 MMWdocx Powered by TCPDF www tcpdf org Polytechnic University of the PhilippinesCollege of CommunicationC68 97D859 8E4678 If the businessman starts from City Aand has to come back to his startingpoint which route should he select sothat the total distance travelled is minimum Answer The businessman must travel the path A C D B E A to minimize the total distance travelled 4 Apply Kruskal s Algorithm to determine a minimum spanning tree in each graph a Minimum spanning treeSelected edges b c d e b d a b with total weight of 11b Minimum spanning treeSelected edges d e c d e f b e a b c g g h e i i j i l g k with total weight of 36Euler CircuitDistance TravelledA B C D E A36A B D C E A32A B C E D A38A D C B E A35A B E D C A36A C B D E A31A C B E D A36A C D B E A30A C E D B A33A D B C E A32A B E C D A36