ケイリーグラフ
無限巡回群 G = Z と S として生成元 +1 とその逆元 −1 からなる集合を考えるとケイリーグラフは無限の道である。
同様に、位数 n の有限巡回群 G = Zn と S として生成元とその逆元からなる集合を考えるとケイリーグラフは閉路 Cn である。より一般に、有限巡回群のケイリーグラフはちょうど circulant graphs に一致する。
直積群のケイリーグラフは対応するケイリーグラフの直積である。よって四元 (±1, 0), (0, ±1) を生成元とするアーベル群 Z のケイリーグラフは平面 R 上の無限格子であり、直積 Zn × Zm のケイリーグラフは同様の生成元をとるとトーラス上の n × m 有限格子である。
二面体群 D4 の生成元 a と b に関するケイリーグラフは左のように表される。赤い有向辺は a の合成を表す。b は対合なので b の合成を表す青い辺は無向とした。したがってグラフはごたまぜである:8つの頂点、8つの有向辺、そして4つの無向辺。群 D4 の乗積表は表示
D 4 = ⟨ a , b ∣ a 4 = b 2 = e , a b = b a 3 ⟩ {\displaystyle D_{4}=\langle \,a,b\mid a^{4}=b^{2}=e,\ ab=ba^{3}\,\rangle }
から導くことができる。D4 の異なるケイリーグラフは右のように表される。b は先ほどと同様に水平鏡映で、青い無向辺で表す。c は対角鏡映でピンクの無向辺で表す。どちらの鏡映も対合なので右のケイリーグラフは無向グラフである。
もし生成集合の元 s が対合ならば対応する辺は無向辺で表されることが多い。
ケイリーグラフ Γ(G, S) は生成集合 S の選び方に本質的に依存する。たとえば生成集合 S が k 個の元を持つならば、ケイリーグラフの各頂点は入次数 k かつ出次数 k である。生成集合 S が対称のとき、ケイリーグラフは次数 k の正則有向グラフである。
ケイリーグラフの閉路は生成集合 S の元の間に関係式があることを示している。
もし f : G′ → G が群の全射準同型で生成集合 S の像 S′ が互いに相異なるならば、グラフの被覆 f : Γ(G, S) → Γ(G′, S′) を誘導する。とくに群 G が k 個の生成元をもち、すべての位数が 2 と異なり、集合 S がそれらの生成元とその逆元から成るならば、ケイリーグラフ Γ(G, S) は同じ生成元を持つ自由群に対応する次数 2k の無限正則木によって被覆される。
グラフ Γ(G, S) はたとえ集合 S が群 G を生成していないときでさえ構成することができる。けれども、グラフは非連結となり、ケイリーグラフとして考えることはできない。このときグラフの各連結成分は S によって生成される部分群の剰余類を表す。
有限ケイリーグラフを無向グラフとして考えたとき、頂点連結度は少なくともグラフの次数の 2/3 はある。もし生成集合が極小ならば、頂点連結度は次数と等しい。辺連結度はどんな場合でも次数と等しい。
有限アーベル群 G のケイリーグラフ Γ(G, S) が定める隣接行列の固有値は、既約指標 χ を用いて λχ = ∑s ∈ S χ(s) と表せる。また各固有値に属する固有ベクトルも既約指標の値を並べることで得られる。
G を群、S をその生成集合とする。ケイリーグラフ Γ = Γ(G, S) とは以下のように構成されるグラフ彩色化有向グラフである:
群 G の各元 g に対して頂点を割り当てる:Γ の頂点集合 V(Γ) を G と同一視する。
生成集合 S の各元 s に対して色 cs を割り当てる。
群 G の元 g と生成集合 S の元 s に対して元 g と gs に対応する頂点を色 cs の有向辺でむすぶ。つまり辺集合 E(Γ) は (g, gs) の形をした組からなり、色は s ∈ S から定まる。
幾何学的群論ではふつう集合 S は有限かつ対称(つまり S = S)であり、単位元を含まないと仮定する。このとき色を忘れたケイリーグラフは単純グラフである:辺に向きはなく、ループを含まない。