[proofplan] We induct on the number of edges $m = e(G)$, keeping the vertex count $n$ fixed as a parameter. The base case $m = 0$ (the edgeless graph on $n$ vertices) gives $P_G(t) = t^n$, which matches the claim. The inductive step uses the [Deletion-Contraction relation](/theorems/2031) $P_G(t) = P_{G-e}(t) - P_{G/e}(t)$: deleting an edge reduces the edge count to $m - 1$ while preserving $n$ vertices, and contracting produces a graph on $n - 1$ vertices whose chromatic polynomial has degree $n - 1$ by the [Chromatic Polynomial Degree](/theorems/2032) theorem. Tracking the top two coefficients through the subtraction gives the claimed leading term $t^n$ and subleading coefficient $-m$. [/proofplan] [step:Set up induction on the number of edges with the vertex count fixed] Fix $n \geq 1$ and let $G$ be a graph with $|V(G)| = n$ vertices. We induct on $m = e(G)$, the statement being: for every graph $G$ on $n$ vertices with $m$ edges, \begin{align*} P_G(t) = t^n - m\,t^{n-1} + p(t) \end{align*} for some polynomial $p$ of degree at most $n - 2$. [guided] Before starting the induction, we fix what is varying and what is held constant. The statement has two size parameters: the vertex count $n$ and the edge count $m$. Because the [Deletion-Contraction relation](/theorems/2031) reduces $m$ (via deletion) but also reduces $n$ (via contraction), trying to induct on $m$ while letting $n$ vary confuses the recursion. The resolution is standard: fix $n$ as an outer parameter, and perform induction on $m$ only. The inductive hypothesis then says "for every graph on $n$ vertices with fewer than $m$ edges, the formula holds." The deletion step produces such a graph (same $n$, smaller $m$), so induction applies. The contraction step produces a graph on $n - 1$ vertices, which is handled by the already-established [Chromatic Polynomial Degree](/theorems/2032) theorem (applied to graphs on $n - 1$ vertices) — not by the inductive hypothesis at this level. The stated form $P_G(t) = t^n - m\,t^{n-1} + p(t)$ with $\deg p \leq n - 2$ is the full assertion we must maintain at every stage of the induction, both base and step. [/guided] [/step] [step:Verify the base case $m = 0$ by direct enumeration] If $m = 0$, then $G$ is the edgeless graph on $n$ vertices. Every assignment of colours from $\{1, \ldots, t\}$ to the vertices is proper, since there are no edges to violate. Hence \begin{align*} P_G(t) = t^n = t^n - 0 \cdot t^{n-1} + 0, \end{align*} which matches the claimed form with $m = 0$ and $p(t) = 0$ (the zero polynomial, whose degree is $-\infty \leq n - 2$ by convention). [/step] [step:Apply Deletion-Contraction to a chosen edge in the inductive step] Assume the statement holds for all graphs on $n$ vertices with strictly fewer than $m$ edges, and let $G$ be a graph on $n$ vertices with $m \geq 1$ edges. Choose any $e \in E(G)$. The [Deletion-Contraction relation](/theorems/2031) applies to $G$ and $e$ with no further hypotheses, giving \begin{align*} P_G(t) = P_{G-e}(t) - P_{G/e}(t). \end{align*} We will now expand each of $P_{G-e}(t)$ and $P_{G/e}(t)$ as polynomials with known top two coefficients, then subtract. [guided] The strategy is to evaluate $P_G$ via the recursion $P_G = P_{G-e} - P_{G/e}$ and track the top two coefficients on the right-hand side. For this to work we must verify that both $G - e$ and $G / e$ land in a regime where the inductive hypothesis (or an already-proved theorem) pins down their leading coefficients. - **$G - e$** has $n$ vertices and $m - 1 < m$ edges. This is exactly the inductive hypothesis regime: same $n$, smaller $m$. - **$G / e$** has $n - 1$ vertices (the two endpoints of $e$ merged into one). The inductive hypothesis does not apply directly — it is stated at fixed $n$, not $n - 1$. But we do know the leading term $t^{n-1}$ of $P_{G/e}$ from the [Chromatic Polynomial Degree](/theorems/2032) theorem, and that is all we need for tracking the top two coefficients of $P_G$. The [Deletion-Contraction relation](/theorems/2031) has no hypotheses beyond "$G$ is a graph and $e$ is an edge of $G$", both of which we have since $m \geq 1$ means $E(G) \neq \varnothing$. So we may apply it freely. [/guided] [/step] [step:Expand $P_{G-e}$ using the inductive hypothesis and $P_{G/e}$ using the degree theorem] **Expansion of $P_{G-e}$.** The graph $G - e$ has $n$ vertices and $m - 1$ edges. Since $m - 1 < m$, the inductive hypothesis gives \begin{align*} P_{G-e}(t) = t^n - (m-1)\,t^{n-1} + q(t), \qquad \deg q \leq n - 2. \end{align*} **Expansion of $P_{G/e}$.** The graph $G/e$ has $n - 1$ vertices. By the [Chromatic Polynomial Degree](/theorems/2032) theorem (applied to the graph $G/e$, which is a graph), $P_{G/e}(t)$ is a polynomial of degree $|V(G/e)| = n - 1$. Let \begin{align*} P_{G/e}(t) = t^{n-1} + r(t), \qquad \deg r \leq n - 2, \end{align*} where the leading coefficient is $1$ (monic) by the [Chromatic Polynomial Degree](/theorems/2032) theorem. [guided] We need to justify that $P_{G/e}$ is **monic** of degree $n - 1$ — i.e., the leading coefficient is exactly $1$, not just "degree $n - 1$". The [Chromatic Polynomial Degree](/theorems/2032) theorem as stated gives degree equal to the vertex count, but inspecting its proof shows the leading coefficient is always $1$. Indeed, this is implicit in the inductive construction: the edgeless graph on $n$ vertices has $P(t) = t^n$ (monic), and the recursion $P_G = P_{G-e} - P_{G/e}$ preserves monicity of the top term because the contraction produces a lower-degree polynomial that cannot affect the leading coefficient. So $P_{G/e}(t) = t^{n-1} + (\text{lower-order terms})$ with leading coefficient $1$. Alternative justification: the sequence $t(t-1)(t-2)\cdots(t-n+2)$ (colour choices for a spanning tree of $G/e$, if it were a tree) is the extreme case, and it has leading term $t^{n-1}$ with coefficient $1$. The chromatic polynomial of any graph on $n - 1$ vertices is bounded above by the edgeless graph's $t^{n-1}$ at every $t$, and the leading behaviour is always $t^{n-1}$ with coefficient $1$. In either reading, we conclude $P_{G/e}(t) = t^{n-1} + r(t)$ with $\deg r \leq n - 2$. [/guided] [/step] [step:Subtract the expansions and read off the leading coefficients] Substituting the two expansions into $P_G(t) = P_{G-e}(t) - P_{G/e}(t)$: \begin{align*} P_G(t) &= \bigl(t^n - (m-1)\,t^{n-1} + q(t)\bigr) - \bigl(t^{n-1} + r(t)\bigr) \\ &= t^n - (m-1)\,t^{n-1} - t^{n-1} + \bigl(q(t) - r(t)\bigr) \\ &= t^n - m\,t^{n-1} + p(t), \end{align*} where $p(t) := q(t) - r(t)$. Since $\deg q \leq n - 2$ and $\deg r \leq n - 2$, we have $\deg p \leq n - 2$. This is precisely the claimed form with the correct leading coefficient $1$ and subleading coefficient $-m$. The induction is complete, and the theorem holds for every graph $G$ on $n$ vertices with $m$ edges. [guided] The arithmetic is the heart of the argument: the $-t^{n-1}$ contributed by the monic contraction term combines with the $-(m-1)\,t^{n-1}$ from deletion to produce $-m\,t^{n-1}$, exactly the coefficient the theorem predicts. Every edge $e$ deleted subtracts one from the $t^{n-1}$ coefficient, and the contraction subtracts one more — together accounting for the single edge $e$ we have processed. Inductively, $m$ edges produce the coefficient $-m$. The lower-order polynomial $p = q - r$ absorbs all the $O(t^{n-2})$ contributions. We do **not** need to compute $p$ explicitly — the theorem only claims $\deg p \leq n - 2$, which follows immediately from $\deg q, \deg r \leq n - 2$ (the degree of a difference is at most the maximum of the two degrees). This completes the induction: we have shown that if the statement holds for all graphs on $n$ vertices with fewer than $m$ edges, it holds for graphs on $n$ vertices with $m$ edges. Together with the base case $m = 0$, the principle of mathematical induction establishes the theorem for all $m \geq 0$ and hence for all graphs $G$ on $n$ vertices. [/guided] [/step]