[proofplan] We fix an edge $e = xy \in E(G)$ and partition the proper $t$-colourings of $G - e$ into two classes according to whether $x$ and $y$ receive different colours or the same colour. The first class is in bijection with the proper $t$-colourings of $G$ (since adding $e$ back creates no conflict precisely when $x$ and $y$ differ), and the second is in bijection with the proper $t$-colourings of $G/e$ (where the merged vertex inherits the common colour). Counting gives $P_{G-e}(t) = P_G(t) + P_{G/e}(t)$, which rearranges to the stated identity. The argument is valid for every positive integer $t$; since $P_G$, $P_{G-e}$, $P_{G/e}$ are polynomials, agreement at infinitely many inputs extends the identity to all $t$. [/proofplan]

[step:Fix $t \in \mathbb{Z}_{\geq 1}$ and label the colouring sets] Fix an edge $e = xy \in E(G)$ and a positive integer $t \geq 1$. Write $[t] := \{1, 2, \ldots, t\}$ for the set of $t$ available colours. We introduce the three sets of proper colourings we will compare: \begin{align*} \mathcal{C}(G) &:= \{c: V(G) \to [t] \mid c(u) \neq c(v) \text{ for all } uv \in E(G)\}, \\ \mathcal{C}(G - e) &:= \{c: V(G) \to [t] \mid c(u) \neq c(v) \text{ for all } uv \in E(G) \setminus \{e\}\}, \\ \mathcal{C}(G/e) &:= \{c: V(G/e) \to [t] \mid c(u) \neq c(v) \text{ for all } uv \in E(G/e)\}. \end{align*} Note that $V(G - e) = V(G)$ (deleting an edge does not delete its endpoints), while $V(G/e) = (V(G) \setminus \{x, y\}) \cup \{a\}$ where $a$ is the new vertex obtained by identifying $x$ and $y$. By definition of the chromatic polynomial, \begin{align*} P_G(t) = |\mathcal{C}(G)|, \quad P_{G-e}(t) = |\mathcal{C}(G - e)|, \quad P_{G/e}(t) = |\mathcal{C}(G/e)|. \end{align*} [/step]

[step:Partition $\mathcal{C}(G - e)$ according to the colours of $x$ and $y$]Every proper colouring of $G - e$ either assigns $x$ and $y$ different colours or the same colour. Define \begin{align*} \mathcal{C}_{\neq}(G - e) &:= \{c \in \mathcal{C}(G - e) \mid c(x) \neq c(y)\}, \\ \mathcal{C}_{=}(G - e) &:= \{c \in \mathcal{C}(G - e) \mid c(x) = c(y)\}. \end{align*} These two sets are disjoint and their union is $\mathcal{C}(G - e)$, so \begin{align*} |\mathcal{C}(G - e)| = |\mathcal{C}_{\neq}(G - e)| + |\mathcal{C}_{=}(G - e)|. \end{align*}[/step]

[guided]The strategy is a classical bijective partition. To count proper colourings of $G - e$, we consider the single edge $e = xy$ that distinguishes $G$ from $G - e$: a colouring of $G - e$ places no constraint on the pair $(c(x), c(y))$, but a colouring of $G$ insists that $c(x) \neq c(y)$. This suggests splitting $\mathcal{C}(G - e)$ into two pieces based on whether this extra constraint is satisfied. Accordingly, define \begin{align*} \mathcal{C}_{\neq}(G - e) &:= \{c \in \mathcal{C}(G - e) \mid c(x) \neq c(y)\}, \\ \mathcal{C}_{=}(G - e) &:= \{c \in \mathcal{C}(G - e) \mid c(x) = c(y)\}. \end{align*} Every colouring $c \in \mathcal{C}(G - e)$ either satisfies $c(x) \neq c(y)$ or $c(x) = c(y)$; these conditions are mutually exclusive and exhaustive. Hence \begin{align*} \mathcal{C}(G - e) = \mathcal{C}_{\neq}(G - e) \sqcup \mathcal{C}_{=}(G - e), \end{align*} a disjoint union, and taking cardinalities yields \begin{align*} |\mathcal{C}(G - e)| = |\mathcal{C}_{\neq}(G - e)| + |\mathcal{C}_{=}(G - e)|. \end{align*} The strategy now is to identify each piece with one of the colouring sets of $G$ and $G/e$.[/guided]

[step:Identify $\mathcal{C}_{\neq}(G - e)$ with $\mathcal{C}(G)$] We claim $\mathcal{C}_{\neq}(G - e) = \mathcal{C}(G)$ as sets of functions $V(G) \to [t]$. ($\subseteq$) Let $c \in \mathcal{C}_{\neq}(G - e)$. Then $c$ is proper on $G - e$, so $c(u) \neq c(v)$ for every edge $uv \in E(G) \setminus \{e\}$. Moreover $c(x) \neq c(y)$ by definition of $\mathcal{C}_{\neq}(G - e)$. Since $E(G) = (E(G) \setminus \{e\}) \cup \{e\}$, the two conditions together give $c(u) \neq c(v)$ for every edge $uv \in E(G)$, so $c \in \mathcal{C}(G)$. ($\supseteq$) Let $c \in \mathcal{C}(G)$. Then $c$ is proper on $G$, so $c(u) \neq c(v)$ for every edge $uv \in E(G)$, in particular for $uv = xy = e$, giving $c(x) \neq c(y)$. Restricting to $E(G) \setminus \{e\}$ shows $c$ is proper on $G - e$, so $c \in \mathcal{C}_{\neq}(G - e)$. Hence $|\mathcal{C}_{\neq}(G - e)| = |\mathcal{C}(G)| = P_G(t)$. [/step]

[step:Identify $\mathcal{C}_{=}(G - e)$ with $\mathcal{C}(G/e)$ via a canonical bijection]Define a map \begin{align*} \Phi: \mathcal{C}_{=}(G - e) &\to \mathcal{C}(G/e) \\ c &\mapsto \Phi(c), \quad \Phi(c)(v) := \begin{cases} c(v) & \text{if } v \in V(G) \setminus \{x, y\}, \\ c(x) & \text{if } v = a, \end{cases} \end{align*} where $a \in V(G/e)$ is the vertex obtained by identifying $x$ and $y$. The second branch is well-defined because $c(x) = c(y)$ for $c \in \mathcal{C}_{=}(G - e)$. We verify $\Phi(c) \in \mathcal{C}(G/e)$. The edge set of $G/e$ is \begin{align*} E(G/e) = \{uv \in E(G) \mid u, v \notin \{x, y\}\} \cup \{au \mid u \in V(G) \setminus \{x, y\}, \, ux \in E(G) \text{ or } uy \in E(G)\}. \end{align*} For an edge $uv \in E(G/e)$ with $u, v \notin \{x, y\}$: $\Phi(c)(u) = c(u)$ and $\Phi(c)(v) = c(v)$, and $uv \in E(G) \setminus \{e\}$, so $c(u) \neq c(v)$ by properness of $c$ on $G - e$. For an edge $au \in E(G/e)$ with $u \notin \{x, y\}$: $\Phi(c)(a) = c(x)$ and $\Phi(c)(u) = c(u)$. Either $ux \in E(G)$ or $uy \in E(G)$ (or both). If $ux \in E(G)$, then $ux \in E(G) \setminus \{e\}$ (as $e = xy$ and $u \neq y$), so $c(u) \neq c(x) = \Phi(c)(a)$. If $uy \in E(G)$, then $uy \in E(G) \setminus \{e\}$ similarly, so $c(u) \neq c(y) = c(x) = \Phi(c)(a)$. In all cases $\Phi(c)(a) \neq \Phi(c)(u)$. We exhibit the inverse. Define \begin{align*} \Psi: \mathcal{C}(G/e) &\to \mathcal{C}_{=}(G - e) \\ c' &\mapsto \Psi(c'), \quad \Psi(c')(v) := \begin{cases} c'(v) & \text{if } v \in V(G) \setminus \{x, y\}, \\ c'(a) & \text{if } v \in \{x, y\}. \end{cases} \end{align*} The analogous verification shows $\Psi(c') \in \mathcal{C}_{=}(G - e)$: the edges of $G - e$ correspond to the edges of $G/e$ under the quotient, with edges incident to $a$ in $G/e$ pulling back to edges incident to $x$ or $y$ in $G - e$, and $\Psi(c')(x) = c'(a) = \Psi(c')(y)$ ensures $\Psi(c') \in \mathcal{C}_{=}$. Direct computation shows $\Psi \circ \Phi = \mathrm{id}_{\mathcal{C}_{=}(G-e)}$ and $\Phi \circ \Psi = \mathrm{id}_{\mathcal{C}(G/e)}$, so $\Phi$ is a bijection. Hence $|\mathcal{C}_{=}(G - e)| = |\mathcal{C}(G/e)| = P_{G/e}(t)$.[/step]

[guided]We want a bijection between the two sets. The intuition: a colouring $c$ of $G - e$ with $c(x) = c(y)$ gives $x$ and $y$ a single common colour, and this common colour is precisely what a colouring of the quotient graph $G/e$ assigns to the merged vertex $a$. Concretely, define \begin{align*} \Phi: \mathcal{C}_{=}(G - e) &\to \mathcal{C}(G/e) \\ c &\mapsto \Phi(c), \quad \Phi(c)(v) := \begin{cases} c(v) & \text{if } v \in V(G) \setminus \{x, y\}, \\ c(x) & \text{if } v = a. \end{cases} \end{align*} The second branch looks asymmetric — why $c(x)$ and not $c(y)$? Because they are equal: the hypothesis $c \in \mathcal{C}_{=}(G - e)$ gives $c(x) = c(y)$, so we could equivalently write $c(y)$. The map $\Phi$ simply reads the common colour off the pair $(x, y)$ and transports it to $a$. We must verify $\Phi(c)$ is a proper colouring of $G/e$. Recall that \begin{align*} E(G/e) = \{uv \in E(G) \mid u, v \notin \{x, y\}\} \cup \{au \mid u \in V(G) \setminus \{x, y\}, \, ux \in E(G) \text{ or } uy \in E(G)\} \end{align*} (edges of $G$ not touching $\{x, y\}$ are kept; edges from $\{x, y\}$ to a vertex $u \notin \{x, y\}$ collapse to a single edge $au$; and the edge $e = xy$ itself disappears, since it would become a loop at $a$). Take an edge $uv \in E(G/e)$. Two cases. *Case 1: $u, v \notin \{x, y\}$.* Then $uv \in E(G)$ and $uv \neq e$ (since $e = xy$). So $uv \in E(G) \setminus \{e\}$, and properness of $c$ on $G - e$ gives $c(u) \neq c(v)$. Since $\Phi(c)(u) = c(u)$ and $\Phi(c)(v) = c(v)$, we conclude $\Phi(c)(u) \neq \Phi(c)(v)$. *Case 2: one endpoint is $a$.* Without loss of generality $v = a$ and $u \notin \{x, y\}$. Then by definition of $E(G/e)$, we have $ux \in E(G)$ or $uy \in E(G)$. In either sub-case the edge lies in $E(G) \setminus \{e\}$ (since neither $ux$ nor $uy$ equals $e = xy$, as $u \neq y$ and $u \neq x$). Properness of $c$ on $G - e$ gives $c(u) \neq c(x)$ (if $ux \in E(G)$) or $c(u) \neq c(y)$ (if $uy \in E(G)$). Either way, since $c(x) = c(y)$, we get $c(u) \neq c(x)$, i.e., $\Phi(c)(u) \neq c(x) = \Phi(c)(a)$. So $\Phi(c) \in \mathcal{C}(G/e)$. We now define the inverse $\Psi$: given a proper colouring $c'$ of $G/e$, lift it to $G - e$ by sending the common colour $c'(a)$ to both $x$ and $y$: \begin{align*} \Psi: \mathcal{C}(G/e) &\to \mathcal{C}_{=}(G - e) \\ c' &\mapsto \Psi(c'), \quad \Psi(c')(v) := \begin{cases} c'(v) & \text{if } v \in V(G) \setminus \{x, y\}, \\ c'(a) & \text{if } v \in \{x, y\}. \end{cases} \end{align*} The verification that $\Psi(c') \in \mathcal{C}_{=}(G - e)$ is the mirror image of the above. First, $\Psi(c')(x) = c'(a) = \Psi(c')(y)$, so the colouring lies in the $=$ class. Second, for an edge $uv \in E(G) \setminus \{e\}$ we check properness: if $u, v \notin \{x, y\}$ the edge corresponds to the same edge in $G/e$ and properness comes from $c'$; if exactly one endpoint, say $u$, lies in $\{x, y\}$, the edge corresponds to $av \in E(G/e)$ and $\Psi(c')(u) = c'(a) \neq c'(v) = \Psi(c')(v)$ by properness of $c'$. There is no case where both endpoints lie in $\{x, y\}$, because the only such edge in $G$ is $e$ itself, which we excluded. Finally, checking the compositions: $(\Psi \circ \Phi)(c) = c$ because both assignments leave $c$ unchanged on $V(G) \setminus \{x, y\}$ and, on $\{x, y\}$, $\Psi(\Phi(c))(x) = \Phi(c)(a) = c(x)$ and similarly for $y$ (using $c(x) = c(y)$). The reverse composition $(\Phi \circ \Psi)(c') = c'$ is similar. Hence $\Phi$ is a bijection, and \begin{align*} |\mathcal{C}_{=}(G - e)| = |\mathcal{C}(G/e)| = P_{G/e}(t). \end{align*}[/guided]

[step:Combine the counts and extend from integers to polynomials] Combining the cardinality identities from the previous three steps: \begin{align*} P_{G-e}(t) = |\mathcal{C}(G - e)| = |\mathcal{C}_{\neq}(G - e)| + |\mathcal{C}_{=}(G - e)| = P_G(t) + P_{G/e}(t). \end{align*} Rearranging, \begin{align*} P_G(t) = P_{G-e}(t) - P_{G/e}(t). \end{align*} This identity holds for every positive integer $t \geq 1$. The chromatic polynomials $P_G$, $P_{G-e}$, $P_{G/e}$ are polynomials in $t$ (by the [Chromatic Polynomial Degree](/theorems/???) theorem). Two polynomials that agree at infinitely many values of $t$ agree as polynomials, so the identity $P_G(t) = P_{G-e}(t) - P_{G/e}(t)$ holds for all $t \in \mathbb{R}$ (indeed for all $t \in \mathbb{C}$). This completes the proof. [/step]