準同型が存在しない条件

それでは，実際に2つのグラフが与えられたときに準同型が存在するかどうか判定するにはどうしたらよいのだろうか？

実は，これまで見てきた中で，それが難しい問題であるということが分かってしまう．

定理： 2つのグラフGとHに対して，準同型G→Hが存在するかどうかを判定する問題はNP完全である．

(証明)
グラフHとして，完全グラフK_nを選ぶと，部分問題としてn-彩色可能性問題になるので，NP完全問題が帰着できる．また，この問題がNPであることは簡単に分かる(すべての写像に関して準同型性をチェックすればよい)． □

有限なグラフを扱っているので，準同型の存在を示すには，実際に構成してあげればよい．しかし，準同型が存在しない，ということを言うのは困難である(ということを上の定理は示唆している)． ただし，いくつか簡単な非存在条件は知られているので，いくつか紹介しよう．

定理： グラフGとHに対して，χ(G)＞χ(H)なら，GからHへの準同型は存在しない．

(注：χ(G)はGの彩色数．)

(証明)
準同型f:G→Hがあったとする． もし，Hがn彩色可能であれば，準同型H→K_nが存在し，準同型G→H→K_nが存在することになるので，Gもn彩色可能ということになる． したがって，χ(G)≦χ(H)となる． □

定義： グラフGに含まれる奇数サイズのサイクルのうち，最小のサイズをGのodd girth(奇内周)と呼ぶ．ここではog(G)と表記することにする．

(注：奇数サイズに制限しない場合がgirth(内周)．)

定理： グラフGとHに対して，og(G)＜og(H)なら，GからHへの準同型は存在しない．

(証明)
まず，奇数サイズのサイクルC_2k+1の準同型による像は，k≧lのC_2l+1である，ということを確認する．（簡単に確認できる．） すると，特に，Gの最小サイズの奇数サイクルCの像も，H中のC以下のサイズの奇数サイクルになるはずである．しかし，og(G)＜og(H)だと，それは存在しないので矛盾となる． □

上の定理2つを使うと，G→HもH→Gもどちらも準同型が存在しない例の存在が分かる． というのは，任意の正整数k,lに対して，彩色数kでgirthがl以上のグラフが存在することが知られているためである． この事実を利用して，グラフGに対して，k＞χ(G)，l＞og(G)として，この条件を満たすグラフをHとして構成してあげれば，どちら向きにも準同型が存在しないペアG,Hになる．

この他，例えば
J.Matousek,「Using the Borsuk-Ulam Theorem」(Springer, 2003)
では，トポロジカルな議論による，準同型の非存在条件などが紹介されている．