3つのユーティリティの問題

通常（平面の2次元平面上で）提示されるように、効用パズルの解は「いいえ」です。つまり、どの線も交差することなく9つの接続すべてを行う方法はありません。言い換えれば、グラフは${\displaystyle K_{3,3}}$平面ではない。カジミエシュ・クラトフスキは1930年に次のように述べた。${\displaystyle K_{3,3}}$は非平面であるため、^{[ 15 ]}問題には解がないことが導かれる。 しかし、クルマン (1979)は、「興味深いことに、クラトフスキは、[ の詳細な証明を公表しなかった」と述べている。${\displaystyle K_{3,3}}$]は非平面である」。^{[ 2 ]}

平面埋め込みを見つけることが不可能であることの証明の一つは、${\displaystyle K_{3,3}}$ジョルダン曲線定理を用いたケース分析を使用する。^{[ 16 ]}この解法では、グラフの4サイクルに関して頂点の位置のさまざまな可能性を調べ、それらがすべて平面埋め込みと矛盾することを示す。^{[ 17 ]}

あるいは、ブリッジのない二部平面グラフで あれば、${\displaystyle V}$頂点と${\displaystyle E}$エッジには${\displaystyle E\leq 2V-4}$オイラーの公式を組み合わせることによって${\displaystyle V-E+F=2}$（どこ${\displaystyle F}$は平面埋め込みの面の数です。面の数は辺の数の半分以下であるという点に注意してください（各面の周囲の頂点は家とユーティリティが交互に配置されるため、各面には少なくとも4つの辺があり、各辺はちょうど2つの面に属します）。ユーティリティグラフでは、${\displaystyle E=9}$そして${\displaystyle 2V-4=8}$したがって、効用グラフでは、${\displaystyle E\leq 2V-4}$この不等式を満たさないため、効用グラフは平面グラフにはなり得ない。^{[ 18 ]}

メビウスの帯上の解

トーラス上の解

トーラスは最大4つの公共施設と4つの住宅を収容できます。

${\displaystyle K_{3,3}}$これはトーラスグラフであり、これは、種数 1 の曲面であるトーラス上に交差なく埋め込むことができることを意味します。 ^{[ 19 ]}これらの埋め込みにより、家や会社が平面ではなくコーヒー マグカップなどの表面に描かれているバージョンのパズルが解けます。 ^{[ 20 ]}トーラス上には、4 つの家と 4 つのユーティリティがあるバージョンのパズルを解くのに十分な自由度があります。^{[ 21 ] [ 5 ]}同様に、3 つのユーティリティのパズルが透明な素材のシート上に提示されている場合、シートをねじって接着してメビウスの帯を形成することで解くことができます。^{[ 22 ]}

ヘンリー・デューデニーが提案した、パズルのルールを変更して解けるようにする別の方法は、公共施設の配線が、接続先の家屋や施設以外の家屋や施設を通過することを許可することである。^{[ 3 ]}

効用グラフ${\displaystyle K_{3,3}}$これはラマングラフであり、平面上のほぼすべての頂点の配置に対して、平面全体の剛体運動以外にすべての辺の長さを維持しながら頂点を連続的に移動する方法はなく、また、その全域部分グラフのいずれも同じ剛性特性を持たないことを意味します。これは非平面ラマングラフの最小の例です。^{[ 23 ]}最小限の剛性を持つグラフであるにもかかわらず、頂点の特別な配置を持つ非剛体埋め込みがあります。^{[ 9 ] [ 24 ]}一般位置埋め込みの場合、同じ辺の長さを持つすべての可能な配置を記述する多項式方程式の次数は16であり、一般に同じ長さの配置は最大で16個しか存在しないことを意味します。この方程式の解のうち最大8つが実現可能な配置を記述するような辺の長さのシステムを見つけることが可能です。^{[ 24 ]}

${\displaystyle K_{3,3}}$は三角形を含まないグラフであり、すべての頂点がちょうど 3 つの隣接点を持つ（立方グラフ）。このようなグラフの中で、これは最小である。したがって、これは(3,4)-ケージであり、各頂点に 3 つの隣接点があり、最短サイクルの長さが 4 である最小のグラフである。^{[ 25 ]}

他のすべての完全二部グラフと同様に、このグラフも十分に被覆されたグラフであり、すべての最大独立集合のサイズが同じであることを意味します。このグラフでは、最大独立集合は二部グラフの両側のみであり、サイズは等しくなります。${\displaystyle K_{3,3}}$これは、7つしかない3正則3連結の被覆良好グラフの1つです。 ^{[ 26 ]}

平面グラフの重要な特徴付けとして、クラトフスキーの定理（平面グラフは、どちらも含まないグラフである）がある。${\displaystyle K_{3,3}}$完全なグラフも${\displaystyle K_{5}}$細分化として、そして平面グラフはまさにどちらも含まないグラフであるというワグナーの定理${\displaystyle K_{3,3}}$または${\displaystyle K_{5}}$マイナーとして、非平面性を利用して一般化する${\displaystyle K_{3,3}}$[ ^{27 ]​}

パル・トゥランの「レンガ工場問題」は、完全二部グラフの描画における交差の最小数を求める公式をより一般的に要求するものである。${\displaystyle K_{a,b}}$頂点の数に関して${\displaystyle a}$そして${\displaystyle b}$二分割の両側に。効用グラフ${\displaystyle K_{3,3}}$交点が 1 つだけの線を描くことはできますが、交点が 0 つだけの線を描くことはできません。したがって、交点の数は 1 です。^{[ 5 ] [ 28 ]}