text: 在圖論中，若一個圖的每個頂點度數均為三，則稱其為立方圖、3-正則圖或三次圖。彼得森圖、湯瑪森圖等都是立方圖。對稱性.1932年，首先尋找立方的例子，並收集為。許多著名的圖都是立方對稱圖，如湯瑪森圖、彼得森圖等。用滿足下列性質的最大整數"s"來對立方對稱圖進行分類：圖的自同構群在其所有長度為"s"的路徑組成的集合上作用是傳遞的。他證明了"s"最大隻能取5，也即"s"的可能值是1到5。圖著色與獨立集.根據布魯克定理，除了"K"4以外的任何連通立方圖都可以用至多三種顏色染色。也即，這樣的連通立方圖至少存在一個包含n/3個頂點的獨立集，其中n是該圖的頂點數。根據Vizing定理，任一立方圖的只能為三或四。3-邊著色又稱Tait-著色，Tait-著色方式將邊集分割為三個完美匹配。根據每個二分立方圖都有一個Tait-著色。哈密頓迴路.關於立方圖是否具有有許多研究。1880年，猜想任一立方多面體圖都有哈密頓迴路。1946年，提出了的反例，有46個點的。1971年，Tutte猜想所有的二分立方圖都有哈密頓迴路。然而Joseph Horton提出了Tutte猜想的反例，有96個點的。在這之後，又提出了兩個反例：。將Tait猜想與Tutte猜想結合起來，稱任一二分立方多面體圖都有哈密頓迴路。當一個立方圖有哈密頓迴路時，可以使用簡潔地表示。如果從所有formula_1階立方圖中隨機選取一個，那麼它有相當大機率有哈密頓迴路：當formula_1趨近於無窮時，這個機率趨近於1。猜想任一formula_1階立方圖最多有formula_4條不同的哈密頓迴路，且給出了極限情況下的例子。目前為止，得到證明的最佳估計為formula_6。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 立方圖
metadata: https://zh.wikipedia.org/wiki?curid=6561709