立方体グラフ
数学のグラフ理論の分野における立方体グラフ(りっぽうたいグラフ、英: cubic graph)とは、すべての頂点の次数が 3 であるようなグラフのことを言う。言い換えると、立方体グラフとは 3-正則グラフである。立方体グラフは 3価グラフとも呼ばれる。2部立方体グラフ(bicubic graph)とは、立方体グラフかつ2部グラフであるようなグラフのことを言う。
グラフ理論(英語版)によると、完全グラフ K4 以外のすべての立方体グラフは、多くとも 3色によって彩色される。したがって、K4 以外のすべての立方体グラフは、少なくとも n/3 個の頂点の独立集合を持つことになる。ここで n はそのグラフ内の頂点の数とする:例えば、3-彩色における最大の色の類は、少なくともこのくらい多くの頂点を含む。
ビジングの定理(英語版)によると、すべての立方体グラフは、その辺彩色のために 3色か 4色を必要とする。3-辺彩色はテイト彩色として知られ、そのグラフの辺を三つの完全マッチングへと区分する。ケーニヒの線彩色定理(英語版)によれば、すべての2部立方体グラフにはテイト彩色が存在する。
テイト彩色が存在しない、橋のない立方体グラフはスナーク(英語版)として知られる。ピーターセングラフや、ティーツェのグラフ(英語版)、ブラヌサスナーク(英語版)、フラワースナーク(英語版)、ダブルスタースナーク(英語版)、スゼッケルスナーク(英語版)、ワトキンススナーク(英語版)などが、これに該当する。スナークは無数に存在する。