Problem number 15, Anya wants to paint the circles in the picture. She wants to paint any two circles connected by a line different colors. What is the smallest number of colors she needs? Let's take a quick look at our answers. The smallest suggested answer is 2. So let's figure out if she can do it using just two colors. The problem tells us that any two circles that are connected by a line must be different colors. Let's note that here we have three circles that are connected to each other. So this circle is connected to these two, which means that this circle must be a different color than this one and then this one. But these two can't be the same color because they're also connected to each other, so they need to be different colors. So there's no way that she's going to be able to paint this using only two colors. Let's try doing three colors. We don't have the same kind of setup to show us that it definitely will not work, so let's try filling in the circles. The circle in the middle is connected to four other circles, so let's start with that one. And our first color can be blue. And I'm going to fill in any circles that are not directly connected to the blue circle with blue as well, which means that these two can be blue. The other ones have to be a color different than blue. Let's use green for our second color. We can fill this circle in green because it's only connected to blue circles. We can fill this circle in with green as well. We can fill this circle in with green, but we will not be able to fill this third circle in with green because it's connected to a green circle already. I'll just make it red. And yes, she can fill in the circles with three different colors. The answer is B.

coloring problem

interconnected circles

three colors

graph theory

color constraints