すべての頂点の次数が3以上のグラフは$K_4$をマイナーとして含む話
今回は、すべての頂点の次数が3以上のグラフは$K_4$をマイナーとして含むという話を紹介しようと思います。一見簡単そうな主張ですが、厳密に証明するのは意外と大変です。
1. 主張の内容
以下の主張が成り立ちます。
$G=(V, E)$を無向単純グラフ*1とする。このとき、$G$のすべての頂点$v\in V$の次数が3以上であれば、$G$は$K_4$をマイナー*2として含む。
2. 証明
まず、グラフ$G$が非連結であれば連結成分ごとに考えればよいので、以下では$G$が連結である場合を考える。
$G$の頂点数に関する帰納法で示す。
$G$から適当に頂点$v\in V$を選ぶ。$v$の次数は3以上なので、$v$と隣接する頂点$u$が存在する。このとき、$v, u$の両方と隣接する頂点が存在しないなら、辺$(v, u)$を縮約すれば、すべての頂点の次数が3以上で頂点数が$|V|-1$の単純グラフになるので帰納法がまわる。ゆえに$v, u$の両方と隣接する頂点$w$が存在する場合を考える。
このとき、$u, v, w$を縮約して1つの頂点にしたときに多重辺ができないのであれば、そのように縮約すれば先ほどと同様に帰納法がまわる。よって、以下では$u, v, w$を縮約して1つの頂点にしたときに多重辺ができる場合、つまり$u, v, w$のうちの少なくとも2頂点と隣接する頂点$x$が存在する場合を考える（どの頂点と隣接しても同じなので、$x$は$u, w$に隣接するとする）。
このとき、$v$と$x$を結ぶ辺がある場合は$K_4$をマイナーとして含むのでOK。そうでない場合を考えると、頂点$u, v, w, x$から$V\setminus \{u, v, w, x\}$へ伸びている辺は2本である場合と3本以上である場合がある。
2本である場合を考える。この場合2本の辺は$v, x$から伸びている辺である。$v, x$と隣接している頂点をそれぞれ$a, b$とする。
ここで、$G$から$u, v, w, x$を取り除いたときに$a, b$が同じ連結成分に含まれるなら、縮約することで$v, x$の間に辺をつくることができるので$K_4$をマイナーとして含みOK。ゆえに$u, v, w, x$を取り除いた時に$a, b$が異なる連結成分に含まれる場合を考えればよいが、この場合も$v, u, w, x$を取り除き、$a$と$b$を辺でつなげば帰納法がまわる。
次に頂点$u, v, w, x$から$V\setminus \{u, v, w, x\}$へ伸びている辺が3本以上である場合を考える。このとき、$u, v, w, x$を縮約して1つの頂点にしたときに多重辺ができないなら、そのように縮約すれば帰納法がまわるので、以下では多重辺ができる場合、つまり$u, v, w, x$のうちの少なくとも2頂点と隣接する頂点$y\in V\setminus \{u, v, w, x\}$が存在する場合を考える（$y$は$v, w$と隣接するとする。$v, x$と隣接するとすると、$K_4$をマイナーとして含むことに注意）。
この場合も先ほどと同様に考えることができる。まず、上図の部分グラフ$G'$は次の2条件を満たしていることに注意する。
- 三角形をいくつか張り合わせたグラフになっている
- 次数2の頂点が2つ以上存在する
ここで、一般に条件1を満たすグラフの非隣接2頂点の間に1本辺を加えたグラフは、$K_4$を必ずマイナーに持つことに注意する*3。
$G'$に対して先ほどと同様に場合分けして考える。
まず条件2から、$G'$で次数2の2頂点を結ぶ辺が$G$にあるか、もしくは$u, v, w, x, y$から$V\setminus \{u, v, w, x, y\}$へ伸びている辺が2本以上あるかのどちらかが成り立つ。
まず$G'$で次数2の2頂点を結ぶ辺$e$が$G$にある場合、条件1から$G'$の非隣接2頂点の間に辺を加えると$K_4$をマイナーに持つので、$G'$に$e$を加えることで$K_4$をマイナーに持つグラフが得られてOK。
次に$u, v, w, x, y$から$V\setminus \{u, v, w, x, y\}$へ伸びている辺が2本以上ある場合を考える。2本なら、$G$から$u, v, w, x, y$を取り除くと$V\setminus \{u, v, w, x, y\}$の中で$x, y$に隣接していた2頂点は異なる連結成分に属する（これも先ほどと同じく条件1からわかる）ので、その2頂点を辺で結べば帰納法がまわる。3本以上なら、$u, v, w, x, y$を1頂点に縮約して多重辺ができないなら帰納法がまわり、多重辺ができるなら$u, v, w, x, y$のうち少なくとも2頂点と隣接する頂点$z\in V\setminus \{u, v, w, x, y\}$が存在する。ただし条件1から$z$が$G'$で互いに隣接しない2頂点に隣接するなら、$G$は$K_4$をマイナーに持つので、そうでない場合を考えればよい。つまり、$G'$に、頂点$z$と$z$から$u, v, w, x, y$のうちの2頂点に伸びる2辺を加えてできる$G$の部分グラフ$G''$も、三角形をいくつか張り合わせたグラフとなり、また$G''$には次数2の頂点が2つ以上存在する。よって$G''$は条件1、2を満たす。ゆえに$G''$に対しても同じ議論を繰り返していけば、帰納法がまわるか部分グラフの頂点が増えていくかのどちらかなので、$G$の頂点数が有限であることからいつかは帰納法がまわることになり、証明が完了する。
3. 余談1
話題に若干唐突感があると思うので、今回の主張を考えたくなった経緯を少し書いておきます。もともと「グラフ$G$の木幅*4が2以下⇔$G$は$K_4$をマイナーとして含まない」という主張を示したかったのですが、←側の証明をする際に、次数2以下の頂点があれば帰納法がうまく回るけど、すべての頂点の次数が3以上の時は帰納法が回らないので困っていました。そこで、$K_4$をマイナーとして含まないなら次数2以下の頂点が必ず存在すれば都合が良いなとなり、今回示した命題にたどり着きました。
4. 余談2
実は今回証明した主張よりももう少し強い主張が成り立ちます:
主張
無向単純グラフ$G$のすべてのマイナーの最小次数が2以下であることと、$G$が$K_4$をマイナーとして含まないことは等価である。
また、似たような主張として次のようなものも成り立ちます:
主張
無向単純グラフ$G$のすべてのマイナーの最小次数が3以下であることと、$G$が$K_5, K_{2, 2, 2}$をマイナーとして含まないことは等価である。
これらの主張も含め、グラフの最小次数と禁止マイナーについては
に詳しく載っているので、興味のある方は参照してみてください。
