路徑多項式

人們可能會認為，與匹配生成多項式、獨立多項式等類似，應該定義一個路徑多項式，其係數是長度為的路徑的數量。 雖然在文獻中似乎沒有定義這樣的多項式，但這項工作對它們進行了定義。

路徑多項式，也許是首次在此處定義，因此是多項式

其係數給出圖中存在的長度為的簡單路徑的數量，圖有個節點。

由於最短的可能路徑長度為 1，因此路徑多項式的多項式次數至少為 1。 特別是，，其中是圖的邊數。

一個圖是可追蹤的 當且僅當路徑多項式的次數等於。 特別是，給出哈密頓路徑的數量，因此一個圖是可追蹤的 當且僅當 。

由於非連通圖中的路徑計數是其連通分量中路徑計數的總和，因此路徑多項式在連通分量上是可加的。