格子グラフ

同義語：grid graphグリッドグラフ

概要

前提知識: グラフ, 誘導部分グラフ, 道(グラフ), 二部グラフ, 距離(グラフ)

格子グラフ（grid graph）とは、平面の整数点の集合 $\mathbb{Z}^2$ の有限部分集合 $P$ を頂点とし、上下左右に隣り合う 2 点（距離がちょうど $1$ の 2 点）を辺で結んだグラフである。方眼紙の格子点と格子線のうち、選んだ点とその間の線分だけを残したものと思えばよい。とくに長方形 $\{1,\dots,m\}\times\{1,\dots,n\}$ の上の格子グラフ $G_{m,n}$ は、2 本の道(グラフ) $P_m$ と $P_n$ の直積 $P_m\,\square\,P_n$ であり、格子グラフの代表例である。
格子グラフは二部グラフで、辺を長さ $1$ の線分として平面に交わらずに描けるので、平面グラフ・マッチ棒グラフ・ペニーグラフの基本的な例になる。この記事では、長方形の格子グラフ $G_{m,n}$ の頂点間の距離が座標の差の絶対値の和であること、$G_{m,n}$（$m,n\ge2$）が Hamilton閉路をもつのは $mn$ が偶数のときに限ること（主定理）、一般の格子グラフの辺数の上界、そして直積の Laplacian スペクトルが因子のスペクトルの和で与えられることを証明する。
用語に注意する。スペクトルグラフ理論などでは、「$m\times m$ grid」「lattice graph」が完全グラフの直積 $K_m\,\square\,K_m$（同じ行か同じ列にある 2 点をすべて結ぶグラフ）を指すことがある（BH11 §1.4.5–1.4.6（p. 10）、§9.1.1（p. 114））。この記事の格子グラフは隣り合う点だけを結ぶもので、これとは別物である。また、マッチ棒グラフの記事の三角格子グラフは各頂点が 6 本の辺をもつ別のグラフである。

定義

この記事では、グラフは有限で単純な無向グラフとする（無限グラフ $\mathbb{L}$ だけは例外）。点 $p=(x,y)$ と $p'=(x',y')$ の間の $\ell^1$ 距離を $\|p-p'\|_1:=\lvert x-x'\rvert+\lvert y-y'\rvert$ と書く。整数点の間では、$\|p-p'\|_1=1$ はユークリッド距離が $1$ であることと同値である。

正方格子グラフと格子グラフ

$\mathbb{Z}^2$ を頂点集合とし、$\|p-p'\|_1=1$ となる 2 点 $p,p'$ を辺で結んだ無限グラフを 正方格子グラフ といい、$\mathbb{L}$ と書く。$\mathbb{Z}^2$ の空でない有限部分集合 $P$ について、$\mathbb{L}$ の $P$ の上の誘導部分グラフ $\mathbb{L}[P]$ を $P$ の上の 格子グラフ という。すなわち、$\mathbb{L}[P]$ の頂点集合は $P$ で、$p,p'\in P$ は $\|p-p'\|_1=1$ のときに限り隣接する。

$\mathbb{L}$ の各頂点 $p$ の隣接頂点は $p\pm(1,0)$、$p\pm(0,1)$ の 4 点であり、$\mathbb{L}$ は 4-正則グラフである。$\mathbb{L}$ は加法群 $\mathbb{Z}^2$ の生成系 $\{\pm(1,0),\pm(0,1)\}$ に関する Cayleyグラフでもある。

グラフの直積

グラフ $G=(V,E)$ と $H=(W,F)$ の直積（Cartesian product）$G\,\square\,H$ とは、頂点集合を $V\times W$ とし、$(v,w)$ と $(v',w')$ を、「$v=v'$ かつ $ww'\in F$」または「$w=w'$ かつ $vv'\in E$」のときに限り辺で結んだグラフである。

直積の定義は BH11 §1.4.6（p. 10）による。$G\,\square\,H$ で頂点 $(v,w)$ の次数は $d_G(v)+d_H(w)$ である。$G\,\square\,H$ と $H\,\square\,G$ は $(v,w)\mapsto(w,v)$ で同型であり、$K_2$ を $d$ 個かけた直積は $d$ 次元の超立方体グラフ $Q_d$ である。

長方形の格子グラフ

$m,n\ge1$ とする。$[m]:=\{1,\dots,m\}$ と書き、$\{1,\dots,m\}\times\{1,\dots,n\}$ の上の格子グラフ $\mathbb{L}[\,[m]\times[n]\,]$ を $G_{m,n}$ と書いて、$m\times n$ の 長方形の格子グラフ という。

長方形の格子グラフは道の直積

頂点を $1,\dots,m$、辺を $\{i,i+1\}$（$1\le i< m$）とする道を $P_m$ と書く。このとき $G_{m,n}=P_m\,\square\,P_n$ である（頂点集合はどちらも $[m]\times[n]$ で、辺集合が等しい）。

$(x,y),(x',y')\in[m]\times[n]$ について、$\lvert x-x'\rvert+\lvert y-y'\rvert=1$ となるのは、2 つの非負整数の和が $1$ になる場合なので、「$x=x'$ かつ $\lvert y-y'\rvert=1$」または「$y=y'$ かつ $\lvert x-x'\rvert=1$」の場合に限る。$P_n$ で $y$ と $y'$ が隣接することは $\lvert y-y'\rvert=1$ と同値なので、これは直積の隣接の条件そのものである。$\square$

以下、$x$ を「列」、$y$ を「行」の番号と呼ぶ。$G_{1,n}$ は道 $P_n$ と同型、$G_{2,2}$ は 4 頂点の閉路 $C_4$、$G_{2,n}$ は はしごグラフ（ladder graph）と呼ばれる。

直感

格子グラフは「方眼の上を 1 マスずつ縦か横に進む」動きを記録したグラフである。1 歩で $x+y$ の偶奇が必ず変わるので、市松模様の 2 色で塗り分けられる（二部グラフ）。また長方形の中では、縦と横の歩数の和より短く移動できないが、遠回りせずに進めばちょうどその歩数で着く（距離が $\ell^1$ 距離になる）。一方、$P$ に穴やくびれがあると、遠回りを強いられて距離は $\ell^1$ 距離より大きくなる。
長方形の格子グラフは、2 本の道の直積として、1 次元の対象の「積」から作られる。このため Laplacian 行列の固有値は、道の固有値の和として明示的に求まる。これは偏微分方程式の差分法で、2 次元の Laplace 作用素を 1 次元の差分の和として扱うことの組合せ論的な対応物である。

基本的な性質

頂点数・辺数・次数

$m,n\ge2$ とする。$G_{m,n}$ の頂点数は $mn$、辺数は $m(n-1)+n(m-1)=2mn-m-n$ である。次数 $2$ の頂点は 4 隅の 4 個、次数 $3$ の頂点は隅以外の周上の $2(m-2)+2(n-2)$ 個、次数 $4$ の頂点は内部の $(m-2)(n-2)$ 個である。

横の辺 $\{(x,y),(x+1,y)\}$ は $1\le x< m$、$1\le y\le n$ で $(m-1)n$ 本、縦の辺は同様に $m(n-1)$ 本ある。頂点 $(x,y)$ の隣接頂点は $(x\pm1,y)$、$(x,y\pm1)$ のうち $[m]\times[n]$ に入るものなので、次数は $4$ から「$x\in\{1,m\}$ の個数」と「$y\in\{1,n\}$ の個数」を引いたものである（$m,n\ge2$ なので $1\ne m$、$1\ne n$）。これから次数の分布が従う。検算として次数の和は $4\cdot2+3\bigl(2(m-2)+2(n-2)\bigr)+4(m-2)(n-2)=4mn-2m-2n$ で、辺数の 2 倍に等しい。$\square$

二部性

すべての格子グラフ $\mathbb{L}[P]$ は二部グラフであり、$x+y$ の偶奇で頂点を分けたものが二部分割を与える。とくに $\mathbb{L}[P]$ は長さ奇数の閉路をもたず、$G_{m,n}$（$m,n\ge2$）の最短の閉路の長さは $4$ である。

辺の両端は一方の座標が $1$ だけ異なり他方は等しいので、$x+y$ の偶奇が異なる。よって偶奇による分割は二部分割である。二部グラフは長さ奇数の閉路をもたない（二部グラフの定理「閉路の長さによる特徴付け」）。$G_{m,n}$ の閉路の長さは $3$ 以上の偶数なので $4$ 以上であり、$(1,1),(2,1),(2,2),(1,2)$ が長さ $4$ の閉路をなす。$\square$

長方形の格子グラフの距離

$G_{m,n}$ の 2 頂点 $p,p'$ の距離は $d(p,p')=\|p-p'\|_1$ である。とくに $G_{m,n}$ は連結で、直径は $m+n-2$ である。一般の格子グラフ $\mathbb{L}[P]$ では、$p,p'$ が同じ連結成分にあれば $d(p,p')\ge\|p-p'\|_1$ である。

辺に沿って 1 歩進むと座標の一方が $1$ だけ変わるので、$\|q-p'\|_1$ は 1 歩あたり高々 $1$ しか減らない。よって $p$ から $p'$ への歩道の長さは $\|p-p'\|_1$ 以上であり、これは一般の $\mathbb{L}[P]$ で成り立つ。逆に $G_{m,n}$ では、$p=(x,y)$ から $x$ 座標を 1 ずつ $x'$ まで動かし、次に $y$ 座標を 1 ずつ $y'$ まで動かす。途中の点の座標は $x$ と $x'$ の間、$y$ と $y'$ の間にあるので $[m]\times[n]$ に入り、長さ $\|p-p'\|_1$ の道が得られる。直径は $\|p-p'\|_1$ の最大値で、$(1,1)$ と $(m,n)$ で $m+n-2$ をとる。$\square$

一般の格子グラフでは等号は成り立たない（後の節「反例」）。次の上界は、格子グラフが「辺の少ない」平面グラフであることを数で表す。

格子グラフの辺数の上界

$P\subset\mathbb{Z}^2$ を $N$ 点の有限集合とすると、格子グラフ $\mathbb{L}[P]$ の辺数は $2N-2\sqrt N$ 以下である。$N=k^2$ のとき、$G_{k,k}$ で等号が成り立つ。

$P$ の点の $y$ 座標として現れる値の個数を $r$、$x$ 座標として現れる値の個数を $c$ とする。$y=b$ をみたす $P$ の点の集合を $P_b$ とすると、横の辺は同じ $P_b$ の中で $x$ 座標が $1$ 違う 2 点を結ぶ。$P_b$ の $x$ 座標の集合を連続する整数の極大な区間に分けると、区間が $s$ 個のとき横の辺は $\lvert P_b\rvert-s\le\lvert P_b\rvert-1$ 本である。$b$ について足すと横の辺は $N-r$ 本以下、同様に縦の辺は $N-c$ 本以下である。一方 $P$ は「現れる $x$ 座標」と「現れる $y$ 座標」の直積に含まれるので $N\le rc\le\bigl(\tfrac{r+c}{2}\bigr)^2$、すなわち $r+c\ge2\sqrt N$ である。よって辺数は $2N-(r+c)\le2N-2\sqrt N$ である。$G_{k,k}$ の辺数は prop-gg-counts により $2k^2-2k$ である（$k=1$ でも $0$ で成り立つ）。$\square$

平面への描画

格子グラフ $\mathbb{L}[P]$ は、各頂点を $P$ の点そのものに置き、各辺を長さ $1$ の線分で描くと、辺どうしが端点以外で交わらない。とくに $\mathbb{L}[P]$ は平面グラフであり、マッチ棒グラフでもある。$G_{m,n}$（$m,n\ge2$）のこの描画の有界な面は $(m-1)(n-1)$ 個の単位正方形である。

2 本の辺の線分は、どちらも水平か垂直な長さ $1$ の線分で、端点は整数点である。2 本が水平なら、同じ高さで $[a,a+1]$ と $[a',a'+1]$（$a\ne a'$ は整数）の形なので、共有点は高々端点 1 つである。一方が水平で他方が垂直なら、交点は水平な線分の高さ（整数）と垂直な線分の $x$ 座標（整数）をもつ整数点で、どちらの線分でも整数点は端点だけなので、交点は共通の端点である。垂直どうしも同様である。また頂点はどの辺の内部にもない（辺の内部に整数点はない）。$G_{m,n}$ の辺の和集合は長方形 $[1,m]\times[1,n]$ を単位正方形に分ける。$\square$

検算として、Eulerの公式(平面グラフ) は $mn-(2mn-m-n)+\bigl((m-1)(n-1)+1\bigr)=2$ となって成り立つ。半径 $1/2$ の円板を $P$ の各点に置くと、円板が接するのは距離 $1$ の点どうしに限るので、$\mathbb{L}[P]$ はペニーグラフでもある（ペニーグラフの記事の例「道・閉路・格子のペニーグラフ」）。

量	$G_{m,n}$（$m,n\ge2$）	$G_{2,2}=C_4$	$G_{3,3}$
頂点数	$mn$	$4$	$9$
辺数	$2mn-m-n$	$4$	$12$
次数	$2,3,4$	$2$	$2,3,4$
直径	$m+n-2$	$2$	$4$
最短の閉路の長さ	$4$	$4$	$4$
Hamilton 閉路	$mn$ が偶数のときに限りある	ある	ない
有界な面の数	$(m-1)(n-1)$	$1$	$4$

主定理：Hamilton 閉路

Hamilton閉路は、すべての頂点をちょうど 1 回ずつ通る閉路である。長方形の格子グラフでは、その有無が頂点数の偶奇だけで決まる。

長方形の格子グラフの Hamilton 閉路

$m,n\ge2$ とする。$G_{m,n}$ が Hamilton 閉路をもつのは、$mn$ が偶数のとき、かつそのときに限る。また、すべての $m,n\ge1$ について $G_{m,n}$ は Hamilton 路（すべての頂点をちょうど 1 回ずつ通る道）をもつ。

段 1（必要性）．prop-gg-bipartite により、$x+y$ が偶数の頂点の集合 $A$ と奇数の頂点の集合 $B$ は $G_{m,n}$ の二部分割である。Hamilton 閉路をたどると頂点は $A$ と $B$ に交互に現れ、閉路は出発点に戻るので $\lvert A\rvert=\lvert B\rvert$ である（Hamilton閉路の命題「二部グラフのHamilton閉路」）。$mn$ が奇数なら、$m,n$ はともに奇数である。各列 $x$ の $n$ 個の頂点のうち $A$ に入るものの個数は、$x$ が奇数なら $(n+1)/2$、偶数なら $(n-1)/2$ である。奇数の $x$ は $(m+1)/2$ 個、偶数の $x$ は $(m-1)/2$ 個なので
$$ \lvert A\rvert=\frac{m+1}{2}\cdot\frac{n+1}{2}+\frac{m-1}{2}\cdot\frac{n-1}{2}=\frac{mn+1}{2} $$
であり、$\lvert B\rvert=(mn-1)/2\ne\lvert A\rvert$ である。よって Hamilton 閉路はない。
段 2（十分性）．$mn$ が偶数とする。$G_{m,n}$ と $G_{n,m}$ は座標の入れ替えで同型なので、$n$（行の数）が偶数としてよい。次の頂点の列を考える。

行 $1$ を左から右へ：$(1,1),(2,1),\dots,(m,1)$。
行 $2,3,\dots,n$ を、列 $2,\dots,m$ の範囲で蛇行する：偶数の行 $y$ は $(m,y),(m-1,y),\dots,(2,y)$ と右から左へ、奇数の行 $y\ge3$ は $(2,y),(3,y),\dots,(m,y)$ と左から右へ。
最後に列 $1$ を上から下へ：$(1,n),(1,n-1),\dots,(1,2)$。
行 $1$ の終点 $(m,1)$ と行 $2$ の始点 $(m,2)$ は隣接する。偶数の行 $y$ の終点 $(2,y)$ と次の行の始点 $(2,y+1)$、奇数の行 $y$ の終点 $(m,y)$ と次の行の始点 $(m,y+1)$ も隣接する。$n$ は偶数なので最後の行 $n$ は右から左へ進んで $(2,n)$ で終わり、これは $(1,n)$ に隣接する。列 $1$ を下って $(1,2)$ に着くと、これは出発点 $(1,1)$ に隣接する。各頂点は、行 $1$ か、列 $1$ の行 $2$ 以上か、列 $2$ 以上かつ行 $2$ 以上のどれか 1 つにだけ属するので、ちょうど 1 回ずつ現れる。頂点数は $mn\ge4\ge3$ なので、これは Hamilton 閉路である。

段 3（Hamilton 路）．行 $1,2,\dots,n$ を、奇数の行は左から右、偶数の行は右から左にたどると、行の終点と次の行の始点は同じ列で上下に隣接するので、Hamilton 路が得られる（$m=1$ や $n=1$ でもよい）。$\square$

例えば $G_{3,4}$（3 列 4 行）では、段 2 の閉路は
$$ (1,1)\to(2,1)\to(3,1)\to(3,2)\to(2,2)\to(2,3)\to(3,3)\to(3,4)\to(2,4)\to(1,4)\to(1,3)\to(1,2)\to(1,1) $$
である。$G_{3,3}$ は Hamilton 路をもつが Hamilton 閉路をもたないので、二部性による偶奇の議論が真に効く例である。この偶奇の議論は、市松模様に塗った $3\times3$ の盤の上を、隣のマスへ 1 歩ずつ動く駒が全マスを 1 回ずつ通って元に戻れないことと同じである。

直積の Laplacian スペクトル

Laplacian行列 $L=D-A$ の固有値（Laplacian スペクトル）は、直積について加法的にふるまう。$G$ の Laplacian 固有値を重複度こめて $\lambda_1,\dots,\lambda_{\lvert V\rvert}$、$H$ のものを $\mu_1,\dots,\mu_{\lvert W\rvert}$ と書く。

直積の Laplacian スペクトル

$G\,\square\,H$ の Laplacian 固有値は、重複度こめて $\lambda_i+\mu_j$（$1\le i\le\lvert V\rvert$、$1\le j\le\lvert W\rvert$）である。

$L_G$、$L_H$ は実対称行列なので、固有ベクトルからなる正規直交基底 $u_1,\dots,u_{\lvert V\rvert}$（$L_Gu_i=\lambda_iu_i$）と $v_1,\dots,v_{\lvert W\rvert}$（$L_Hv_j=\mu_jv_j$）がある（スペクトル定理）。$V\times W$ 上の関数 $w_{ij}(x,y):=u_i(x)\,v_j(y)$ を考える。単純グラフの Laplacian は $(Lf)(z)=\sum_{z'\sim z}\bigl(f(z)-f(z')\bigr)$（和は $z$ の隣接頂点にわたる）と書ける。$G\,\square\,H$ での $(x,y)$ の隣接頂点は、$x'\sim x$ となる $(x',y)$ と、$y'\sim y$ となる $(x,y')$ なので
$$ (L\,w_{ij})(x,y)=\sum_{x'\sim x}\bigl(u_i(x)-u_i(x')\bigr)v_j(y)+u_i(x)\sum_{y'\sim y}\bigl(v_j(y)-v_j(y')\bigr)=(\lambda_i+\mu_j)\,w_{ij}(x,y) $$
である。また
$$ \langle w_{ij},w_{kl}\rangle=\sum_{x,y}u_i(x)v_j(y)u_k(x)v_l(y)=\langle u_i,u_k\rangle\langle v_j,v_l\rangle $$
なので、$\{w_{ij}\}$ は $\lvert V\rvert\,\lvert W\rvert$ 個の正規直交系、すなわち $\mathbb{R}^{V\times W}$ の正規直交基底である。固有ベクトルからなる基底が得られたので、固有値は重複度こめて $\lambda_i+\mu_j$ で尽くされる。$\square$

この命題は BH11 §1.4.6（p. 10）に固有ベクトルの形で述べられている。隣接行列についても同じ計算で、$G\,\square\,H$ の隣接行列の固有値は因子の固有値の和である。

長方形の格子グラフのスペクトル

$G_{m,n}$ の Laplacian 固有値は、重複度こめて
$$ \Bigl(2-2\cos\frac{\pi k}{m}\Bigr)+\Bigl(2-2\cos\frac{\pi l}{n}\Bigr)\qquad(0\le k\le m-1,\ 0\le l\le n-1) $$
である。$\max(m,n)\ge2$ なら、2 番目に小さい固有値（代数的連結度）は $2-2\cos\bigl(\pi/\max(m,n)\bigr)$ である。

道 $P_m$ の Laplacian 固有値は $2-2\cos(\pi k/m)$（$k=0,\dots,m-1$）である（Laplacian行列の例「閉路と道」）。prop-gg-product と thm-gg-product-spectrum から 1 つ目の主張が従う。$t\mapsto2-2\cos t$ は $[0,\pi]$ で狭義増加なので、正の固有値のうち最小のものは、$(k,l)=(1,0)$ か $(0,1)$ のどちらかで、$\pi/m$ と $\pi/n$ の小さいほうを与える側である。$k,l\ge1$ の固有値はこれより大きい。$\square$

例えば $G_{2,3}$（はしご）では、$P_2$ の固有値 $0,2$ と $P_3$ の固有値 $0,1,3$ の和として、固有値は $0,1,2,3,3,5$ である。行列木定理により、連結グラフの全域木の個数は 0 でない Laplacian 固有値の積を頂点数で割ったものなので、$G_{2,3}$ の全域木は $1\cdot2\cdot3\cdot3\cdot5/6=15$ 個である。$G_{2,2}=C_4$ では固有値 $0,2,2,4$ から $2\cdot2\cdot4/4=4$ 個で、$C_4$ から辺を 1 本除いた 4 通りと一致する。
代数的連結度 $2-2\cos(\pi/\max(m,n))$ は、細長い長方形ほど小さい。これは、長い向きの真ん中で切ると少ない辺で 2 つに分かれることの、スペクトルの側の現れである（Laplacian行列の節「代数的連結度と Fiedler ベクトル」）。

マイナーと木幅

格子グラフは、平面グラフ全体の「普遍的な」例でもある。この節の 2 つの定理は、この記事では証明しない。

任意の平面グラフは、十分大きい $G_{k,k}$ のマイナー（辺の縮約と頂点・辺の削除で得られるグラフ）である。平面グラフの描画の頂点と辺を太らせ、十分細かい方眼を重ねればよい（Die25 Corollary 12.6.4 の証明、p. 393）。
$G_{k,k}$ の木幅は $k-1$ 以上である（Die25 p. 375。行と列の和集合「十字」の族を使う）。
Die25 では $G_{k,k}$ を $\{1,\dots,k\}^2$ の上で $\lvert i-i'\rvert+\lvert j-j'\rvert=1$ の点を結んだ「$k\times k$ grid」として定義している（p. 372）。

反例

主な命題の仮定を 1 つずつ外すと、次のように崩れる。

外す条件	反例	成り立たなくなること
thm-gg-hamilton の「$mn$ が偶数」	$G_{3,3}$	二部分割が $5$ 個と $4$ 個で、Hamilton 閉路がない
thm-gg-hamilton の「$m,n\ge2$」	$G_{1,4}=P_4$	$mn=4$ は偶数だが、閉路をもたず Hamilton 閉路もない
prop-gg-distance の「$P$ が長方形」	U 字形 $P=\{(1,1),(1,2),(2,1),(3,1),(3,2)\}$	$(1,2)$ と $(3,2)$ の距離は $4$ で、$\ell^1$ 距離 $2$ より大きい
prop-gg-bipartite の「正方格子の部分グラフ」（端を巻き付ける）	トーラス格子 $C_3\,\square\,C_3$	長さ $3$ の閉路をもち、二部グラフでない
prop-gg-edge-bound の「正方格子」	三角格子の正六角形 $H_1$（7 頂点 12 辺）	$12>14-2\sqrt7\approx8.7$ で上界が成り立たない

反例の確認

各行の確認を開く

1 行目：$G_{3,3}$ では $x+y$ が偶数の点が $(1,1),(1,3),(2,2),(3,1),(3,3)$ の 5 個、奇数の点が 4 個である（prf-gg-hamilton の段 1）。

2 行目：$G_{1,4}$ は道 $P_4$ と同型で、木なので閉路をもたない。

3 行目：$P$ の格子グラフは道 $(1,2)-(1,1)-(2,1)-(3,1)-(3,2)$ であり、$(1,2)$ と $(3,2)$ を結ぶ道はこれだけで長さ $4$ である。$(2,2)\notin P$ なので近道はない。

4 行目：$C_3\,\square\,C_3$ は $(\mathbb{Z}/3)^2$ の上で一方の座標が $\pm1$ だけ違う点を結ぶグラフで、$(0,0),(1,0),(2,0)$ が長さ $3$ の閉路をなす。巻き付けた辺は正方格子の辺ではないので、この記事の格子グラフではない。

5 行目：$H_1$ は中心と正六角形の 6 頂点からなり、マッチ棒グラフの例「三角格子の六角形状の部分」で $s=1$ とすると頂点 $3+3+1=7$、辺 $9+3=12$ である。三角格子では 1 点の隣接点が 6 個あるので、prf-gg-edge-bound の「1 行の横の辺は点の数より少ない」という数え方が 3 方向に分かれ、上界が崩れる。