Meredith Graph -- 來自

Meredith 圖是一個有 70 個節點和 140 條邊的四次非哈密頓圖，它是對每個 4-正則 4-連通圖都是哈密頓圖的猜想的反例。

它在 Wolfram 語言中實現為GraphData["MeredithGraph"].

Meredith 圖的色數為 3，邊色數為 5。

上面的圖顯示了該圖的鄰接矩陣、關聯矩陣和距離矩陣。

參考文獻

Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236-239, 1976.

Bondy, J. A. 和 Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, p. 407, 2008.

Holton, D. A. 和 Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, p. 103-104, 1993.

Meredith, G. H. J. "Regular

-Valent

-Connected Nonhamiltonian Non-

-Edge-Colorable Graphs." J. Combin. Th. B 14, 55-60, 1973.

Meredith 圖