[proofplan] We induct on the number of edges $e(G)$. The base case $e(G) = 0$ (the empty graph on $n$ vertices) gives $P_G(t) = t^n$ directly by counting all functions $V(G) \to [t]$, a polynomial of degree $n = |G|$. For the inductive step, pick any edge $e \in E(G)$ and apply the [Deletion-Contraction for Chromatic Polynomials](/theorems/2031): $P_G(t) = P_{G-e}(t) - P_{G/e}(t)$. By the inductive hypothesis applied to $G - e$ (which has $e(G) - 1$ edges and $|G|$ vertices) and $G/e$ (which has at most $e(G) - 1$ edges and $|G| - 1$ vertices), $P_{G-e}$ is a polynomial of degree $|G|$ and $P_{G/e}$ is a polynomial of degree $|G| - 1$. Their difference is then a polynomial of degree $|G|$, since the $|G|$th degree term cannot cancel. [/proofplan] [step:Set up induction on $e(G)$ with a fixed vertex count $n = |G|$] Fix an integer $n \geq 1$. We prove by strong induction on $m := e(G) \in \mathbb{Z}_{\geq 0}$ that every graph $G$ with $|G| = n$ and $e(G) = m$ has $P_G$ a polynomial of degree $n$. [step:Base case: $e(G) = 0$, where $P_G(t) = t^n$] If $e(G) = 0$, then $G$ has no edges and the condition "$c$ is proper" is vacuous: every function $c: V(G) \to [t]$ is a proper colouring. Here $[t] := \{1, 2, \ldots, t\}$ for $t \in \mathbb{Z}_{\geq 1}$. Hence \begin{align*} P_G(t) = |\{c : V(G) \to [t]\}| = t^n \end{align*} for every positive integer $t$. The function $t \mapsto t^n$ is a polynomial of degree $n$, and this polynomial agrees with $P_G$ at every $t \in \mathbb{Z}_{\geq 1}$, so $P_G(t) = t^n$ identically. This establishes the base case. [/step] [step:Inductive step via deletion-contraction] Fix $m \geq 1$ and assume the claim holds for all graphs $H$ with $e(H) < m$. Let $G$ be a graph with $|G| = n$ and $e(G) = m$, and pick any edge $e \in E(G)$. By the [Deletion-Contraction for Chromatic Polynomials](/theorems/2031), \begin{align*} P_G(t) = P_{G-e}(t) - P_{G/e}(t). \end{align*} We apply the inductive hypothesis to $G - e$ and $G/e$ separately. *Application to $G - e$.* We have $|G - e| = |G| = n$ (vertex deletion is not involved) and $e(G - e) = m - 1 < m$. By the inductive hypothesis, $P_{G-e}$ is a polynomial of degree $n$. Write \begin{align*} P_{G-e}(t) = t^n + \sum_{k=0}^{n-1} a_k\,t^k \end{align*} for real coefficients $a_0, \ldots, a_{n-1}$. (The leading coefficient is $1$ because $P_H(t) \leq t^{|H|}$ for every graph $H$ and every $t \geq 1$, so its leading coefficient cannot exceed $1$; conversely the leading coefficient cannot be strictly less than $1$, as otherwise $P_H(t) < t^{|H|}$ for all sufficiently large $t$ while simultaneously $P_H(t) \geq \prod_{k=0}^{n-1}(t - k) = t^n - O(t^{n-1})$, a contradiction. We record this observation without relying on it in the degree argument below.) *Application to $G/e$.* The contracted graph $G/e$ has $|G/e| = n - 1$ (identifying the two endpoints of $e$ reduces the vertex count by one) and $e(G/e) \leq m - 1 < m$ (the edge $e$ becomes a loop and is removed, and parallel edges may be identified; in the simple graph convention, multiple edges collapse to a single edge, which only reduces the count further). By the inductive hypothesis, $P_{G/e}$ is a polynomial of degree $n - 1$. [guided] We apply the inductive hypothesis to two graphs. Let us verify carefully that both satisfy the hypothesis of the induction (edge count strictly less than $m$) and read off the degrees. First, $G - e$. The graph $G - e$ has the same vertex set as $G$ — deleting an edge does not delete its endpoints — so $|G - e| = n$. It has one fewer edge: $e(G - e) = m - 1$. Since $m \geq 1$, we have $m - 1 < m$, so the strong induction hypothesis applies: $P_{G-e}$ is a polynomial of degree $|G - e| = n$. Write it out explicitly: \begin{align*} P_{G-e}(t) = c_n\,t^n + \sum_{k=0}^{n-1} a_k\,t^k \end{align*} with $c_n \neq 0$ (since the degree is $n$). By convention for the chromatic polynomial, the leading coefficient $c_n$ equals $1$ (this follows inductively — we will use only that $c_n \neq 0$ in what follows). Second, $G/e$. Let $e = xy$. The contracted graph $G/e$ has vertex set $(V(G) \setminus \{x, y\}) \cup \{a\}$ where $a$ is the merged vertex, so $|G/e| = n - 1$. Its edge count satisfies $e(G/e) \leq m - 1$: the edge $e$ itself becomes a loop at $a$ and is deleted; each edge of $G$ from $\{x, y\}$ to a vertex $v \notin \{x, y\}$ becomes an edge $av$ in $G/e$, and if both $xv$ and $yv$ were edges of $G$, they collapse to a single edge $av$ (in the simple graph setting), reducing the edge count further. So $e(G/e) \leq m - 1 < m$, and the inductive hypothesis applies: $P_{G/e}$ is a polynomial of degree $|G/e| = n - 1$. Why does the reduction in edge count matter? The strong induction is stratified by edge count, not by vertex count, so we need $e(G/e) < m$. This is why we verify $e(G/e) \leq m - 1$ even though what we ultimately need is only that $G/e$ has strictly fewer edges than $G$. [/guided] [/step] [/step] [step:Conclude that $P_G$ has degree $n$] We combine the two expressions. Write $P_{G-e}(t) = t^n + \sum_{k=0}^{n-1} a_k\,t^k$ (a polynomial of degree $n$ with leading term $t^n$) and $P_{G/e}(t) = b_{n-1}\,t^{n-1} + \sum_{k=0}^{n-2} b_k\,t^k$ (a polynomial of degree $n - 1$ with $b_{n-1} \neq 0$). Substituting into the deletion-contraction identity: \begin{align*} P_G(t) = P_{G-e}(t) - P_{G/e}(t) = t^n + (a_{n-1} - b_{n-1})\,t^{n-1} + \sum_{k=0}^{n-2}(a_k - b_k)\,t^k. \end{align*} The coefficient of $t^n$ on the right-hand side is $1 \neq 0$ (it is unaffected by the subtraction because $P_{G/e}$ has no $t^n$ term). Hence $P_G$ is a polynomial of degree $n = |G|$. This closes the induction and proves that $P_G$ is a polynomial of degree $|G|$ for every graph $G$. [/step]