400 views
0 votes
0 votes

One day, Dumbledore assigns Harry Potter the task of obtaining the Philosopher’s Stone that lies in an inner chamber surrounded by many rooms. To guide him along, he is given the Marauder’s Map which contains the following graph

 

Harry wishes to color every wall with colors such that walls that meet at a corner get different colors. Harry also wishes to color every room so that adjacent rooms get different colors. What is the minimum number of colors to accomplish this?

(a) 4 colors for walls and 4 colors for the rooms

(b) 3 colors for walls and 4 colors for the rooms

(c) 2 colors for walls and 3 colors for the rooms

(d) 2 colors for walls and 5 colors for the rooms

2 Answers

0 votes
0 votes

Handdrawn answer

 

My answer is ( 4,5 ).

However the official answer is ( b ).
Could somebody explain to me if-then how I may be wrong ?
I did not understand their explanation.

0 votes
0 votes

(b) 3 colors for walls and 4 colors for the rooms
Consider the undirected graph G where every vertex corresponds to a wall and there
is a edge between two vertices whenever two walls are incident on (or adjacent to)
each other. Now, coloring for walls is the same as coloring the vertices of G such that
no two adjacent vertices get the same color. This can be done with 3 colors and the
graph G is often called the line graph (of the image given above).
Consider the undirected graph G where every region(polygon in the above image)
is a vertex and there is an edge between two vertices whenever the regions share a
boundary. Now, coloring the rooms is the same as coloring the vertices of G such
that no two adjacent vertices get the same color. This can be done using 4 colors.
Interestingly, note that you can draw G on paper (or a plane) such that no two
edges cross each other. Such a graph is said to be a planar graph. The question is a
rephrasing of the Planar 4-Color Theorem.

Related questions