これは「1-2-∞予想」と呼ばれています. 現段階では,K1,2,2,2が有限平面被覆を持たなければ, この問題が肯定的に解決したことになります.
どの辺を縮約しても,グラフの単純性が崩れてしまう三角形分割を 既約な三角形分割と呼びます. 一般に,閉曲面を固定すると,その既約三角形分割は有限個しか存在しません. この予想が正しいと,既約三角形分割の頂点数に かなりよい上界が与えられます.
射影平面上のグラフの辺表現度とは, それと非可縮単純閉曲線との交差点の最小値のことです. その積が交差点の個数の上界になることは簡単にわかります.
★この予想はすでに,次の論文の中で,肯定的に解決されています.
実に簡潔な証明です.
D. Archdeacon and C.P. Bonnington,
Two maps on one surface, preprint, 1997.
同様に,自分と自分を重ねたときの交差数を考えるのも, おもしろいかもしれません.
すでに,完全グラフや完全2部グラフに対して, 肯定的な答えが得られています.
閉曲面上の三角形分割の頂点に任意にn+3色を着色すると, かならずどこかの三角形の面の3つの頂点が異なる3色になってしまうとき, その三角形分割は n-loosely tightであるといい, n-loosely tight となる最小の n の値を その三角形分割の looseness と呼びます. looseness が 0 の三角形分割は自動的に完全グラフになります.
地図色分け定理などで知られている完全グラフの埋め込みから得られる 三角形分割の looseness は 0 になっています. したがって,問題の最小値は閉曲面の種数に関して単調増加になるのではなく, 適当な周期で 0 に戻ってしまいます.
日本の位相幾何学的グラフ理論では, 俗に「変形ネタ」と呼ばれる研究が盛んです. この問題はその究極的な形です.
例えば,1つの頂点の近傍がクモの巣のようになっていると, 辺の総和をほとんど変えずに,その部分を縮小していくことができます. この場合,クモの巣の部分はその頂点に吸収されてしまい, その操作の極限はものとのグラフとは異なってしまいます. そのような現象が起こらないグラフはどんなものかを知りたいわけです.
三角形分割の対角変形に理論において, 擬最小三角形分割は非常に重要な概念ですが, その具体的な姿はあまりよくわかっていません.
★
最近,次の論文に書かれている定理を用いることで,
K4(m)とK6(m)がそれぞれ
向き付け可能と不可能な閉曲面の擬最小三角形分割になることが
わかりました.
したがって,上の問いの答えは"YES"ということになります.
D. Archdeacon,
The medial graph and voltage-current duality,
Discrete Math.
104 (1992) 111-141.
5-連結な三角形分割ならば, そのようなものは無限個存在します. また,三角形分割でない6-連結グラフならば, やはりそのようなものは無限個存在します.
簡単な計算によって,その被覆が2重か6重であることがわかります. 6重のときには,もはや射影平面的にはなりません. 「1-2-∞予想」が正しければ,この場合は自動的に排除されますが, このくらいの事実なら,初等的に証明したいですね.
これは,やや安易な問題です. おそらく,2-連結では埋め込みが一意的でないものが作れるでしょう. まず,それを構成してみましょう. それに成功したら,「3-連結」の部分を適当な条件に変えて, 定理を作ってください. その条件がどこまで落とせるかが,勝負です.