削除・短縮式

スパニングツリーの数${\displaystyle t(G)}$DCを満たす。^{[ 3 ]}

証拠。${\displaystyle t(G\setminus e)}$は、eを含まない全域木の数を表します。${\displaystyle t(G/e)}$eを含む数。2 番目を見るには、TがGの全域木である場合、 eを縮約すると、別の全域木が生成されます。${\displaystyle G/e}$逆に、全域木Tがある場合${\displaystyle G/e}$すると、辺eを拡張すると2 つの切断された木が得られます。e を追加すると2つの木が接続され、 Gの全域木が得られます。 

キルヒホッフの定理によれば、グラフ内の全域木の数はラプラシアン行列の余因子によって数えられます。しかし、ラプラシアン特性多項式はDC を満たしません。頂点重み付きラプラシアンを研究することで、スケーリングされた頂点重み付きラプラシアン特性多項式間の削除縮約関係を見つけることができます。^{[ 4 ]}

彩色多項式${\displaystyle \chi _{G}(k)}$Gのk彩色数を数えることはDC を満たさないが、少し修正された式 (等価にすることができる) は次のようになる: ^{[ 1 ]}

${\displaystyle \chi _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k)。}$

証明。e = uvの場合、Gのk彩色は、 uとvが異なる色を持つG \ eのk彩色と同じである。  ${\displaystyle \chi _{G\setminus e}(k)}$合計G  \ e彩色。ここで、 uとvが同じ色になっているものを差し引く必要があります。しかし、そのような彩色は、 k彩色に対応します。 ${\displaystyle \chi _{G/e}(k)}$ここで、uとvは結合される。

上記の性質は彩色多項式を示すために使用できます${\displaystyle \chi _{G}(k)}$は確かにkに関する多項式です。これは、辺の数に関する帰納法と、辺がない基本ケースでは であることに注目することで証明できます。 ${\displaystyle k^{|V(G)|}}$可能な彩色（ kに関する多項式） 

• Dong, FM; Koh, KM; Teo, KL (2005年6月).グラフの彩色多項式と彩色性. World Scientific. doi : 10.1142/5814 . ISBN 978-981-256-317-0。