Graph coloring lessons for high school discrete math

I incorporated a graph coloring piece within my graphs and trees unit. For this I made use of Tom Zaremba et al's Map Coloring lessons. There are a few minor tweaks that are needed and a few extensions and modifications that I made.

Below are my notes regarding my modifications:

Chromatic color of graph should reference planar graphs since discussing maps. Will not work for non-planar graphs (see K5).

Fish tank graph should show edge BE not edge BD on the applications page.

For coloring algorithms, have students write out their algorithm. They should try their algorithm on the South America map. Students then swap their algorithm instructions and try to follow instructions. Discuss findings and those that appear to find a graphs chromatic color. Test these further.

Coloring algorithm needs to address that no two adjacent vertices are colored the same color.

Have students write out algorithm for edge coloring. Try this on South America and then exchange.

Discuss graph coloring and scheduling type problems.