7.9 证明: χ ( G − e ) = min { χ ( G ) , χ ( G ⋅ e ) } \chi(G-e) = \min \{\chi(G),\chi(G\cdot e) \} χ(G−e)=min{χ(G),χ(G⋅e)}
证:
-
色多项式的递推公式: P k ( G ) = P k ( G − e ) − P k ( G ⋅ e ) P_k(G) =P_k(G-e)-P_k(G\cdot e) Pk(G)=Pk(G−e)−Pk(G⋅e)
-
χ ( G − e ) = min { k ∣ P k ( G − e ) ≠ 0 } = min { k ∣ P k ( G ) + P k ( G ⋅ e ) ≠ 0 } = min { χ ( G ) , χ ( G ⋅ e ) } \begin{aligned} \chi(G-e) &= \min\{k | P_k(G-e) \ne 0 \} \\ &= \min\{k | P_k(G)+P_k(G\cdot e) \ne 0 \} \\ &= \min \{\chi(G),\chi(G\cdot e) \} \end{aligned} χ(G−e)=min{k∣Pk(G−e)=0}=min{k∣Pk(G)+Pk(G⋅e)=0}=min{χ(G),χ(G⋅e)}