ヒーウッドグラフ

ヒーウッドグラフは立方体であり、それに含まれるすべての閉路には六つ以上の辺がある。これよりも小さいすべての立方体グラフにはより短い閉路しか含まれないため、ヒーウッドグラフは 6-ケージの、内周 6 の最小の立方体グラフである。また、距離推移グラフ（フォスター調査を参照）でもあり、したがって距離正則（英語版）である^[2]。

ヒーウッドグラフには 24 の完全マッチングが存在する;各マッチングに対し、それに含まれない辺の集合はハミルトン閉路を形成する。例えば、ページ右上の図は、マッチングを形成する閉路からなる内部対角（internal diagonal）を備える閉路上の頂点を示しているグラフである。その閉路を二つのマッチングに分けることで、ヒーウッドグラフを三つの完全マッチング（すなわち、3辺彩色）に分ける方法が八通りある^[2]。どの二つの完全マッチングと、どの二つのハミルトン閉路も、グラフの対称性によってお互い交換することが出来る^[3]。

ヒーウッドグラフには 6-頂点の閉路が 28 含まれる。そのような 6-閉路は、必ず三つの他の 6-閉路と互いに素になっている;そのような三つの 6-閉路において、どの一つも必ず他の二つの対称差（symmetric difference）になっている。6-閉路に対して一つの頂点と、6-閉路の互いに素な各ペアに対して一つの辺を備えるグラフは、コクセターグラフ（英語版）である^[4]。

ヒーウッドグラフはトロイダルグラフ（英語版）である; すなわち、ヒーウッドグラフはトーラス上で交叉することなく埋め込まれる。このタイプの一つの埋め込みは、その頂点と辺を三次元ユークリッド空間へ、あるトーラスの位相を備える非凸多面体（シラッシの環状多面体）の頂点と辺の集合として配置する。

グラフの名の由来であるパーシー・ジョン・ヒーウッド（英語版）は1890年、トーラスの多角形への全ての細分割において、その多角形領域は高々七色の色で彩色されることを証明した^[5][6]。ヒーウッドグラフは、境界が tight であるような、七つの互いに近接した領域を備えるトーラスの細分割を形成する。

ヒーウッドグラフはまたファノ平面（英語版）のレヴィグラフ（英語版）でもあり、幾何における点と距離の間の incidences を表すグラフである。この解釈によると、ヒーウッドグラフに含まれる 6-閉路は、ファノ平面における三角形に対応する。

ヒーウッドグラフの交叉数（英語版）は 3 であり、そのような交叉数を持つ立方体グラフの中では最小である。ヒーウッドグラフを含む、交叉数 3 で位数 14 のグラフは 8 つある。

ヒーウッドグラフは単位距離グラフである: 隣接する頂点はちょうど距離が 1 だけ離れており、同じ点に埋め込まれている頂点はなく、また、辺に含まれるある点に埋め込まれる頂点もないような平面に、そのグラフは埋め込まれる。しかしながら、そのグラフに備わっている対称性は、このタイプの知られている埋め込みにおいては欠落している^[7]。