Solutions to practice probs

There are many correct solutions to these problems. The solutions shown here are one way of solving, not the only way of solving.

7.

Solution to prob 7

8.

Solution to prob 8

9.

Solution to problem 9

10.

Solution to problem 10

11.

Solution to problem 11

12.

Solution to problem 12

13. Triangulate:

Triangulation

Color:

Coloring for prob 13

Choose guards. Note that to have the smallest number of guards, we need the ones labelled G : there are 5 R's and 5 B's, but only 4 G's.

Guards for problem 13

14. If a gallery has 10 walls, what is the most number of cameras/guards you would need to watch the gallery?

At most you would need 3 guards. You can find 3 by doing 10/3 and throwing away the remainder. This works because any way you can split the 10 vertices into red, blue and green, at least one color has 3 or fewer vertices.

15. If a gallery has 22 walls, what is the most number of cameras/guards you would need to watch the gallery?

At most you would need 7 guards. You can find 3 by doing 22/3 and throwing away the remainder. This works because any way you can split the 22 vertices into red, blue and green, at least one color has 7 or fewer vertices.