The chromatic polynomial counts a graph’s proper colorings, that is, the number of ways to assign colors to vertices such that adjacent vertices are colored differently. For 10 points each:
[10e] The chromatic polynomial of a planar graph evaluated at this integer or greater is always positive, since any planar graph can be properly colored using only this many colors.
ANSWER: 4
[10h] To show that the chromatic polynomial is actually a polynomial in the number of colors, one can use induction and these two graph operations, both of which reduce the number of edges by one. Name both operations.
ANSWER: edge deletion AND contraction [prompt on constructing graph minors]
[10m] The chromatic polynomial on this kind of graph is a falling factorial of the number of colors, since all vertices must be properly colored differently. The simplest non-planar graph by number of vertices is this kind of graph.
ANSWER: complete graphs
<Other Science>