(二)、色多项式的两种求法 1、递推计数法 定理1设G为简单图，则对任意 e∈E(G)有： P(G)=P(G-e)-P(Ge) 证明：设e=uv。则对G-e的着色方式数可以分为两部分： (1)u与v着不同颜色。此时，等于G的着色方式数； (2)u与v着同色。此时，等于Ge的着色方式数； 所以，得：P(G)=P(G-e)-P(Ge)0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 1、递推计数法 (二)、色多项式的两种求法 定理1 设G为简单图，则对任意 有： e EG  ( ) () ( ) ( ) Pkk k G P G e P Ge   证明：设e=uv。则对G-e的着色方式数可以分为两部分： (1) u与v着不同颜色。此时，等于G的着色方式数； (2) u与v着同色。此时，等于Gꞏe 的着色方式数； 所以，得： () ( ) ( ) Pkk k G P G e P Ge  