Grades 5-6 Video Solutions 2024-2024_5-6

Video Transcription

Question 23. The figure shows the plan of the 7 train routes of a small town. The circles indicate the stations. Martin wants to paint the lines in such a way that if two lines  share a common station, then they are painted with different colors. What is the smallest number of colors that he can use?  First of all, we can see that a minimum of 3 colors is required. For example, we have routes 1, 2, and 4, which all intersect each other, so they all need different colors.  We can also show that we do not need a 4th color. Notice how we can split the 7 routes  into 3 groups, where each route does not intersect with any other route from its own group. Because  of this, we can color all the routes in the same group 1 color. We have our red group with routes 1 and 3, our blue group with routes 2 and 7, and our green group with routes 4,  5, and 6. Since we are able to color all 7 routes with 3 colors, and we know that we need at least 3 colors, we can conclude that the smallest number of colors that Martin  can use is 3.

Video Summary

Martin needs a minimum of 3 colors to paint the train routes so that no two intersecting routes share the same color. The routes are split into three groups where no routes in the same group intersect: group one includes routes 1 and 3, group two includes routes 2 and 7, and group three includes routes 4, 5, and 6. This grouping allows each group to be painted with the same color, confirming that 3 colors are both necessary and sufficient.

Keywords

train routes

coloring problem

graph theory

non-intersecting

minimum colors