Question

11. The twenty-two regions of France are shown on this map. MOROS BASSE LORRAIN PONTOU CHARENTES COTE DA (a) When this map is turned into a graph, how many edges will be at the vertex CENTER? (b) When this map is turned into a graph, would the graph be planar or non-planar? (c) When this map is turned into a graph, how many edges would be at the vertex ILE-DE-FRANCE? (d) When this map is turned into a graph. could LORRAINE and BOURGOGNE have the same color? (e) Is it possible that five colors are required properly color this map? (Yes or Na)

Answer 1

can The map or frame be represented of graph as shown below. where vertices Shows region and edges them bol and vestices has edge between only when these two region connected to each other. (ie. when region are neighbouring region) direetly. two region ILE-DE -FRANCE LORRAINE centre Bourgoone. Map of or founce graph.

cy From cen above graph see that Cente vestex is adjacent to so be there eight edges will be at 8 other vertices are the e vertex centre. b) since above graph is drawn on plane without intersecting edges, so, map turned into a plane is planner. CJ Since the vertese ILE -DE - FRANCE is adjacent to five vertices, so, There are five ve edges would be at vertex ILE - DE - FRANCE DJ since Bourgoone and LORRAINE is bot dues not have any edge between them, so, Bourgoone and Looraine can have colour. same

hare E] suppose we five coolours namely A, 13, C, D, E. Then colouring of greeph is given by, B D. A c A с В D B A B А since above have used only u-colours namely A,B,C,D so, So only four colours are required to pouperly colour this graph. So, the answer is No. not five but only ferry colours required to properly colour this graph. ise