the edge . Then the numbers of k-colorings of these graphs satisfy: Equivalently, if and are not adjacent in G and is the graph with the edge added, then This follows from the observation that every k-coloring of G either gives different colors to and , or the same colors. In the first case this gives a (proper) k-coloring of , while in the second case it gives a coloring of . Conversely, every k-coloring of G can be uniquely obtained from a k-coloring of or (if and are not adjacent in G). The chromatic polynomial can hence be recursively defined as for the edgeless graph on n vertices, and for a graph G with an edge (arbitrarily chosen). Since the number of k-colorings of the edgeless graph is indeed , it follows by induction on the number of edges that for all G, the polynomial coincides with the number of k-colorings at every integer point x = k. In particular, the chromatic polynomial is the unique interpolating polynomial of degree at most n through the points Tutte’s curiosity about which other graph invariants satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the Tutte polynomial . Examples Properties For fixed G on n vertices, the chromatic polynomial is a monic polynomial of degree exactly n, with integer coefficients. The chromatic polynomial includes at least as much information about the colorability of G as does the chromatic number. Indeed, the chromatic number is the smallest positive integer that is not a zero of the chromatic polynomial, The polynomial evaluated at , that is , yields times the number of acyclic orientations of G. The derivative evaluated at 1, equals the chromatic invariant up to sign. If G has n vertices and c components , then The coefficients of are zeros. The coefficients of are all non-zero and alternate in signs. The coefficient of is 1 (the polynomial is monic). The coefficient of is . We prove this via induction on the number of edges on a simple graph G with vertices and edges. When , G is an empty graph. Hence per definition . So the coefficient of is , which implies the statement is true for an empty graph. When , as in G has just a single edge, . Thus coefficient of is . So the statement holds for k = 1. Using