[proofplan] We count proper colorings by inclusion-exclusion over the edge set. For each subset $A \subset E$, the condition that every edge of $A$ is monochromatic identifies exactly the vertices lying in the same connected component of the spanning subgraph $(V,A)$, so the number of compatible colorings is $q$ raised to the number of those connected components. We rewrite this exponent using the graphic matroid rank formula, then group the resulting subset expansion by matroid flats. The grouped coefficients are exactly the Möbius coefficients defining the characteristic polynomial, and the remaining power of $q$ is $q^{c(G)}$ because $r_{M(G)}(E)=|V|-c(G)$. [/proofplan]

[step:Count proper colorings by inclusion-exclusion over monochromatic edge constraints]Fix an integer $q \geq 1$, and let $Q := \{1,\dots,q\}$ be the set of colors. Define the coloring set \begin{align*} \mathcal{C} := \{f: V \to Q\}. \end{align*} For each edge $e \in E$ with endpoints $u_e,v_e \in V$, define \begin{align*} B_e := \{f \in \mathcal{C} : f(u_e)=f(v_e)\}. \end{align*} Because $G$ has no loops, a coloring $f:V \to Q$ is proper exactly when $f \notin B_e$ for every $e \in E$. Hence, by the finite [Inclusion-Exclusion Principle](/theorems/751) applied to the finite family $(B_e)_{e \in E}$, \begin{align*} P_G(q)=\sum_{A \subset E}(-1)^{|A|}\left|\bigcap_{e \in A}B_e\right|. \end{align*} For a subset $A \subset E$, let $c(V,A)$ denote the number of connected components of the spanning subgraph $(V,A)$. The intersection $\bigcap_{e \in A}B_e$ consists exactly of the colorings that are constant on each connected component of $(V,A)$. Such a coloring is determined by independently choosing one color for each of the $c(V,A)$ components, so \begin{align*} \left|\bigcap_{e \in A}B_e\right|=q^{c(V,A)}. \end{align*} Therefore \begin{align*} P_G(q)=\sum_{A \subset E}(-1)^{|A|}q^{c(V,A)}. \end{align*}[/step]

[guided]Fix an integer $q \geq 1$, and write $Q := \{1,\dots,q\}$ for the set of available colors. The set of all colorings is \begin{align*} \mathcal{C} := \{f: V \to Q\}. \end{align*} For an edge $e \in E$, let $u_e,v_e \in V$ be its endpoints, and define \begin{align*} B_e := \{f \in \mathcal{C} : f(u_e)=f(v_e)\}. \end{align*} Thus $B_e$ is the set of colorings for which the edge $e$ violates properness. Since the graph has no loops, an edge is properly colored exactly when its two endpoints receive different colors, so a coloring is proper exactly when it lies in none of the sets $B_e$. We now apply the finite [Inclusion-Exclusion Principle](/theorems/751) to the finite family $(B_e)_{e \in E}$. The family is finite because $E$ is finite by hypothesis. This gives \begin{align*} P_G(q)=\sum_{A \subset E}(-1)^{|A|}\left|\bigcap_{e \in A}B_e\right|. \end{align*} It remains to count the intersection for a fixed subset $A \subset E$. Let $c(V,A)$ be the number of connected components of the spanning subgraph $(V,A)$. A coloring lies in $\bigcap_{e \in A}B_e$ precisely when every edge in $A$ has equal-colored endpoints. Along a path in $(V,A)$, this equality propagates edge by edge, so the coloring is constant on each connected component of $(V,A)$. Conversely, if a coloring is constant on every connected component of $(V,A)$, then every edge in $A$ has equal-colored endpoints, so the coloring belongs to $\bigcap_{e \in A}B_e$. Thus the only choices are the colors assigned to the connected components of $(V,A)$. There are $c(V,A)$ components, and each can be assigned any of the $q$ colors independently. Hence \begin{align*} \left|\bigcap_{e \in A}B_e\right|=q^{c(V,A)}. \end{align*} Substituting this into inclusion-exclusion yields \begin{align*} P_G(q)=\sum_{A \subset E}(-1)^{|A|}q^{c(V,A)}. \end{align*}[/guided]

[step:Rewrite the inclusion-exclusion exponent using the graphic matroid rank]Let $r := r_{M(G)}$ be the rank function of the [graphic matroid](/theorems/5811) $M(G)$. For every subset $A \subset E$, the independent subsets of $A$ in $M(G)$ are precisely the forests in the spanning subgraph $(V,A)$, so a maximal independent subset of $A$ has one fewer edge than the number of vertices in each connected component of $(V,A)$. Therefore \begin{align*} r(A)=|V|-c(V,A). \end{align*} Equivalently, \begin{align*} c(V,A)=|V|-r(A). \end{align*} The inclusion-exclusion formula becomes \begin{align*} P_G(q)=\sum_{A \subset E}(-1)^{|A|}q^{|V|-r(A)}. \end{align*}[/step]

[guided]Let $r := r_{M(G)}$ be the rank function of the [graphic matroid](/theorems/5811) $M(G)$. The rank $r(A)$ is, by definition, the maximum size of an independent subset of $A$ in the matroid. For a graphic matroid, the independent subsets are exactly the forests in the spanning subgraph $(V,A)$. Fix $A \subset E$. In each connected component of $(V,A)$ with vertex set $W$, a maximal forest has $|W|-1$ edges. Summing over all connected components gives \begin{align*} r(A)=|V|-c(V,A). \end{align*} Equivalently, \begin{align*} c(V,A)=|V|-r(A). \end{align*} Substituting this identity into the inclusion-exclusion expansion obtained in the previous step yields \begin{align*} P_G(q)=\sum_{A \subset E}(-1)^{|A|}q^{|V|-r(A)}. \end{align*}[/guided]

[step:Group the subset expansion by closures in the lattice of flats]Let $L(M(G))$ be the lattice of flats of $M(G)$, and let \begin{align*} \operatorname{cl}: 2^E \to L(M(G)) \end{align*} denote the matroid closure map. Since closure preserves rank, $r(A)=r(\operatorname{cl}(A))$ for every $A \subset E$. For each flat $F \in L(M(G))$, define the fiber of the closure map over $F$ by \begin{align*} \mathcal{A}_F := \{A \subset E : \operatorname{cl}(A)=F\}. \end{align*} Hence \begin{align*} P_G(q)=\sum_{F \in L(M(G))}\left(\sum_{A \in \mathcal{A}_F}(-1)^{|A|}\right)q^{|V|-r(F)}. \end{align*} Define the coefficient function \begin{align*} \alpha: L(M(G)) &\to \mathbb{Z} \end{align*} by, for each flat $F \in L(M(G))$, \begin{align*} \alpha(F):=\sum_{A \in \mathcal{A}_F}(-1)^{|A|}. \end{align*} Then \begin{align*} P_G(q)=\sum_{F \in L(M(G))}\alpha(F)q^{|V|-r(F)}. \end{align*}[/step]

[guided]The purpose of this step is to replace a sum over all subsets of $E$ by a sum over flats, because the characteristic polynomial of a matroid is naturally written over the lattice of flats. Let $L(M(G))$ be the lattice of flats of $M(G)$, and let \begin{align*} \operatorname{cl}: 2^E \to L(M(G)) \end{align*} be the matroid closure map. For every $A \subset E$, closure does not change rank, so \begin{align*} r(A)=r(\operatorname{cl}(A)). \end{align*} For a flat $F \in L(M(G))$, define \begin{align*} \mathcal{A}_F := \{A \subset E : \operatorname{cl}(A)=F\}. \end{align*} The sets $\mathcal{A}_F$ partition $2^E$, because every subset $A \subset E$ has a unique closure. Grouping the subset expansion by these fibers gives \begin{align*} P_G(q)=\sum_{F \in L(M(G))}\left(\sum_{A \in \mathcal{A}_F}(-1)^{|A|}\right)q^{|V|-r(F)}. \end{align*} Now define the coefficient function \begin{align*} \alpha: L(M(G)) &\to \mathbb{Z} \end{align*} by, for each flat $F \in L(M(G))$, \begin{align*} \alpha(F):=\sum_{A \in \mathcal{A}_F}(-1)^{|A|}. \end{align*} With this notation, \begin{align*} P_G(q)=\sum_{F \in L(M(G))}\alpha(F)q^{|V|-r(F)}. \end{align*}[/guided]

[step:Identify the grouped coefficients with the Möbius function of the flat lattice]Let $\mu$ be the Möbius function of the finite poset $L(M(G))$, where the order on flats is inclusion, normalized by $\mu(\varnothing,\varnothing)=1$ and, for each nonempty flat $F$, by \begin{align*} \sum_{H \leq F}\mu(\varnothing,H)=0. \end{align*} We prove that $\alpha(F)=\mu(\varnothing,F)$ for every flat $F \in L(M(G))$. Fix a flat $F \in L(M(G))$. Since $G$ is loopless, $\operatorname{cl}(\varnothing)=\varnothing$, so the minimum flat is $\varnothing$. The subsets $A \subset F$ are partitioned by their closures, and $\operatorname{cl}(A) \leq F$ for every $A \subset F$. Hence \begin{align*} \sum_{H \leq F}\alpha(H)=\sum_{A \subset F}(-1)^{|A|}. \end{align*} If $F=\varnothing$, the right-hand side is $1$. If $F \neq \varnothing$, the right-hand side is \begin{align*} \sum_{A \subset F}(-1)^{|A|}=(1-1)^{|F|}=0. \end{align*} Thus the function $\alpha$ satisfies the same defining recursion as $F \mapsto \mu(\varnothing,F)$ on the finite lattice $L(M(G))$. Therefore \begin{align*} \alpha(F)=\mu(\varnothing,F) \end{align*} for every flat $F$.[/step]

[guided]Let $\mu$ be the Möbius function of the finite poset $L(M(G))$, where the order on flats is inclusion, normalized by $\mu(\varnothing,\varnothing)=1$ and, for every nonempty flat $F$, by \begin{align*} \sum_{H \leq F}\mu(\varnothing,H)=0. \end{align*} We prove that the coefficient $\alpha(F)$ obtained by grouping subsets by closure satisfies this same recursion. Fix a flat $F \in L(M(G))$. Because $G$ is loopless, the graphic matroid has no loops, so $\operatorname{cl}(\varnothing)=\varnothing$ and the minimum flat is $\varnothing$. The subsets $A \subset F$ are partitioned according to their closures, and if $A \subset F$ then $\operatorname{cl}(A) \leq F$ because $F$ is closed. Therefore \begin{align*} \sum_{H \leq F}\alpha(H)=\sum_{A \subset F}(-1)^{|A|}. \end{align*} If $F=\varnothing$, then the only subset of $F$ is $\varnothing$, so the right-hand side equals $1$. If $F \neq \varnothing$, the [binomial theorem](/theorems/750) gives \begin{align*} \sum_{A \subset F}(-1)^{|A|}=(1-1)^{|F|}=0. \end{align*} Thus $\alpha$ satisfies exactly the defining recursion for $F \mapsto \mu(\varnothing,F)$ on the finite lattice $L(M(G))$. By uniqueness of the Möbius function determined by this recursion, \begin{align*} \alpha(F)=\mu(\varnothing,F) \end{align*} for every flat $F$.[/guided]

[step:Compare the grouped expansion with the characteristic polynomial]By the previous step, \begin{align*} P_G(q)=\sum_{F \in L(M(G))}\mu(\varnothing,F)q^{|V|-r(F)}. \end{align*} Let $r(E):=r_{M(G)}(E)$ be the rank of the [graphic matroid](/theorems/5811). Applying the graphic rank formula to $A=E$ gives $r(E)=|V|-c(G)$. Therefore $|V|-r(F)=c(G)+r(E)-r(F)$ for every flat $F \in L(M(G))$. Substituting this into the grouped expansion gives \begin{align*} P_G(q)=q^{c(G)}\sum_{F \in L(M(G))}\mu(\varnothing,F)q^{r(E)-r(F)}. \end{align*} By the [definition of the characteristic polynomial of a matroid](/pages/1421), \begin{align*} \chi_{M(G)}(q)=\sum_{F \in L(M(G))}\mu(\varnothing,F)q^{r(E)-r(F)}. \end{align*} Thus $P_G(q)=q^{c(G)}\chi_{M(G)}(q)$ for every integer $q \geq 1$. Since both sides are polynomials in $q$ and they agree at infinitely many integers, they are identical as polynomials. This proves the theorem.[/step]

[guided]The grouped expansion already has the same coefficients as the characteristic polynomial; only the exponent of $q$ must be aligned with the standard matroid convention. From the previous step we have \begin{align*} P_G(q)=\sum_{F \in L(M(G))}\mu(\varnothing,F)q^{|V|-r(F)}. \end{align*} Let $r(E):=r_{M(G)}(E)$ be the rank of the [graphic matroid](/theorems/5811). The graphic rank formula applied to the full edge set $E$ says $r(E)=|V|-c(G)$, because the spanning subgraph $(V,E)$ is the graph $G$ itself and has $c(G)$ connected components. Rearranging gives $|V|=c(G)+r(E)$, and hence, for each flat $F \in L(M(G))$, $|V|-r(F)=c(G)+r(E)-r(F)$. Substituting this exponent identity into the grouped expansion factors out the term that does not depend on $F$: \begin{align*} P_G(q)=q^{c(G)}\sum_{F \in L(M(G))}\mu(\varnothing,F)q^{r(E)-r(F)}. \end{align*} The remaining sum is exactly the [definition of the characteristic polynomial of a matroid](/pages/1421): \begin{align*} \chi_{M(G)}(q)=\sum_{F \in L(M(G))}\mu(\varnothing,F)q^{r(E)-r(F)}. \end{align*} Therefore $P_G(q)=q^{c(G)}\chi_{M(G)}(q)$ for every integer $q \geq 1$. Since both sides are polynomials in $q$ and a nonzero polynomial cannot have infinitely many roots, agreement on all positive integers implies equality as polynomials. This proves the theorem.[/guided]