車輪グラフ

頂点は $n+1\ge4$ 個ある。高々 2 個の頂点の集合 $Z$ を除く。$h\in Z$ なら、残りは閉路 $C_n$ から高々 1 頂点を除いたもので、閉路か道なので連結である。$h\notin Z$ なら、残りのどの頂点も $h$ と隣接するので連結である。$\square$

$W_n$ の頂点彩色では、ハブの色は外周のどの頂点の色とも異なる。外周の頂点に使う色は $C_n$ の頂点彩色をなすので、色の数は $C_n$ の彩色数に $1$ を加えたもの以上である。逆に、$C_n$ を彩色数ぶんの色で塗り、ハブに新しい色を塗れば $W_n$ の頂点彩色になる。よって $W_n$ の彩色数は $C_n$ の彩色数に $1$ を加えたものである。$C_n$ は $n$ が偶数なら二部グラフで彩色数 $2$、奇数なら奇閉路で 2 色では塗れず（彩色 の記事の注意「反例：奇閉路の2-頂点彩色」）、色 $1,2,\dots,1,2,3$ と塗れば 3 色で足りるので彩色数 $3$ である。$\square$

正の整数 $k$ について、$k$ 色による頂点彩色の個数を数える。ハブの色の選び方は $k$ 通りである。ハブの色を決めると、外周の頂点はどれもハブと隣接するので残りの $k-1$ 色から選び、外周の隣り合う頂点の色は異なる。その塗り方は $C_n$ の $k-1$ 色による頂点彩色の個数 $P_{C_n}(k-1)$ に等しい。彩色多項式 の記事の例「基本的なグラフの彩色多項式」の 4 により $P_{C_n}(q)=(q-1)^n+(-1)^n(q-1)$ なので、$q=k-1$ を代入して $P_{W_n}(k)=k\,P_{C_n}(k-1)$ が主張の式になる（$k=1$ では両辺とも $0$）。両辺は多項式で、すべての正の整数で値が一致するので、多項式として等しい。$\square$

1：$T$ は閉路を含まないので外周の辺をすべては含まず、$S\neq\emptyset$ である。閉路から $s\ge1$ 本の辺を除くと $s$ 個の道に分かれる。
2：弧 $Q$ の頂点から出る $T$ の辺は、$Q$ の中の外周の辺か、スポークである（隣の弧への外周の辺は $S$ に属する）。$Q$ のどの頂点からも $T$ のスポークが出ていなければ、$Q$ の頂点は $T$ の中で $h$ と結ばれず、$T$ の連結性に反する。$Q$ の 2 頂点 $v,v'$ から $T$ のスポークが出ていれば、$h$、$v$、$Q$ に沿った $v$ から $v'$ への道、$v'$、$h$ が $T$ の中の閉路をなし矛盾する。
3：選んだ辺の集合を $T$ とする。$T$ の辺は外周の $n-\lvert S\rvert$ 本とスポーク $\lvert S\rvert$ 本で、合わせて $n$ 本である。各弧の頂点はその弧に沿って選んだ頂点に、そこからスポークで $h$ に結ばれるので、$T$ は $n+1$ 頂点すべてを結ぶ連結なグラフである。全域木 の記事の命題「木の判定」により $T$ は全域木であり、その $S$ と選んだ頂点は与えたものに一致する。1・2 で $T$ から得たものに 3 を使えば $T$ に戻るので、2 つの対応は互いに逆である。弧ごとに頂点の選び方は弧の頂点数だけあるので、最後の主張が従う。$\square$

外周を $v_1$、辺 $v_1v_2$、$v_2$、辺 $v_2v_3$、…、$v_n$、辺 $v_nv_1$ の順にたどり、各時点で「いまいる弧で、選んだ頂点をもう通ったか」を状態 $1$（通った）、$0$（まだ）で記録する。頂点を通るときは、状態 $0$ からは $0$ のまま（選ばない）か $1$ へ（選ぶ）移り、状態 $1$ からは $1$ のまま（選ばない）である。辺を通るときは、辺を残すなら状態はそのままで、辺を切る（$S$ に入れる）のは状態 $1$ のときだけ許し、切ったら次の弧に入るので状態 $0$ に戻る。状態の移り方の数を行列で表すと、頂点の段は $V=\begin{pmatrix}1&1\\0&1\end{pmatrix}$、辺の段は $E=\begin{pmatrix}1&0\\1&1\end{pmatrix}$（行が移る前、列が移った後の状態）であり、頂点 1 つと辺 1 本をまとめると
$$ M:=VE=\begin{pmatrix}2&1\\1&1\end{pmatrix} $$
となる。一周して最初の状態に戻る状態の列の個数は $\operatorname{tr}(M^n)$ である。
状態の列と全域木の対応．$S\neq\emptyset$ と各弧の選んだ頂点が与えられたとき、各時点の状態は上の意味で決まり、一周すると最初の状態に戻る（同じ時点だから）。逆に、切る辺が 1 本以上ある状態の列が与えられたとする。切った直後は状態 $0$ で、次に辺を切るときには状態 $1$ でなければならず、$0$ から $1$ へは頂点で選ぶときにだけ、ちょうど 1 回移る。よって各弧（$v_n$ から $v_1$ へまたがる弧も、最初と最後の状態が等しいので同様）で選ぶ頂点はちょうど 1 つで、lem-wh-arcs の 3 の組が得られる。この 2 つの対応は互いに逆である。切る辺がない状態の列では、状態は $1$ から $0$ に戻らないので一周して戻るには一定でなければならず、すべて $0$ ですべての頂点を選ばない列と、すべて $1$ ですべての頂点を選ばない列の 2 つである。lem-wh-arcs により
$$ \tau(W_n)=\operatorname{tr}(M^n)-2 $$
である。
跡の計算．$M$ の固有多項式は $\lambda^2-3\lambda+1$ で、固有値は $\lambda_\pm=\frac{3\pm\sqrt5}{2}$ である。異なる 2 つの固有値をもつので $M$ は対角化でき、$\operatorname{tr}(M^n)=\lambda_+^n+\lambda_-^n$ となる。$\varphi=\frac{1+\sqrt5}{2}$、$\psi=\frac{1-\sqrt5}{2}$ とすると $\lambda_+=\varphi^2$、$\lambda_-=\psi^2$ であり、$L_m=\varphi^m+\psi^m$（Fibonacci数列 の一般項の公式と同じ形）から $\operatorname{tr}(M^n)=L_{2n}$ である。ここで $L_m=\varphi^m+\psi^m$ は、$m=0,1$ で成り立ち、$\varphi,\psi$ が $x^2=x+1$ の根なので右辺も同じ漸化式を満たすことから従う。$\square$

標準的な描画で、$i=1,\dots,n$ について三角形 $hv_iv_{i+1}$ の内部を $t_i$、正 $n$ 角形の外部を $o$ とする。これらは互いに交わらない $n+1$ 個の連結な開集合で、描画と交わらず、境界は描画に含まれる。描画の面（描画を除いた残りの連結成分）で $t_i$ と交わるものは $t_i$ を含み、その面が $t_i$ からはみ出せば、はみ出す道は $t_i$ の境界、すなわち描画の点を通るので矛盾する。よって $t_i$ と $o$ はそれぞれ面である。平面グラフ の記事の定理「Eulerの公式」により面の数は $2-(n+1)+2n=n+1$ なので、面はこれで全部である。
外周の辺 $v_iv_{i+1}$ の両側の面は $t_i$ と $o$ であり、スポーク $hv_i$ の両側の面は $t_{i-1}$ と $t_i$ である（$n\ge3$ なので $t_{i-1}\neq t_i$）。よって $W_n^{*}$ は、$o$ と各 $t_i$ を 1 本ずつ結ぶ辺 $(v_iv_{i+1})^{*}$ と、$t_{i-1}$ と $t_i$ を結ぶ辺 $(hv_i)^{*}$ からなり、平行辺もループもない。対応 $h\mapsto o$、$v_i\mapsto t_i$ は、外周の辺 $v_iv_{i+1}$ を $t_it_{i+1}=(hv_{i+1})^{*}$ に、スポーク $hv_i$ を $ot_i=(v_iv_{i+1})^{*}$ に移す。これは頂点の全単射で辺の全体を辺の全体に移すので、同型 $W_n\cong W_n^{*}$ である。$\square$