立方体グラフ
任意の n-頂点立方体グラフのパス幅(英語版)は、最大でも n/6 である。しかし、立方体グラフのパス幅の知られている下界のうち最良のものは、より小さく、0.082n である。
グラフ理論を初めて扱った、1736年のレオンハルト・オイラーによる論文の一部分において証明された握手補題(英語版)によると、すべての立方体グラフの頂点の数は偶数であることが分かる。
ジュリウス・ピーターセンの定理は、橋(英語版)の無いすべての立方体グラフには完全マッチングが存在する、というものである。
ロヴァースとプラマーは、すべての橋の無い立方体グラフには、指数関数的な数の完全マッチングが存在すると予想した。この予想は近年、すべての橋の無い n 頂点立方体グラフには少なくとも 2 個の完全マッチングが存在する、という結果とともに証明された。
立方体グラフは位相幾何学の分野において、いくつかの方法によって自然に現れる。例えば、1-次元CW複体であるようなグラフを考えた時、立方体グラフは、そのグラフの 0-スケルトンと最大 1-セル接着写像が互いに素であるようなジェネリック(generic)である。立方体グラフはまた、どの頂点においても三つの面が接している正十二面体のような、三次元における単純多面体のグラフとして構成される。
二次元平面上の任意のグラフ埋め込み(英語版)は、graph-encoded map として知られる立方体グラフの構造によって表現される。この構造において、立方体グラフの各頂点は埋め込みの旗(英語版)、すなわち、互いに付帯した頂点、辺および平面の表面からなる組を表す。各旗の三つの隣(neighbor)は、その組の内のどれか一つを変更し、他の二つはそのままにしたものとして得られるような三つの旗である。