效用圖

效用問題提出三個房子和三個公用事業公司——例如，煤氣、電力和水——並詢問是否可以將每個公用事業公司連線到每個房子，而煤氣/水/電線/管道不會跨越任何其他線路/管道。這等同於問題“是否可以從三個節點（‘房子’）中的每一個到另三個節點（‘公用事業公司’）中的每一個構建一個平面圖？”這個問題最初由 H. E. Dudeney 於 1917 年以這種形式提出 (Gardner 1984, p. 92)。

答案是不存在這樣的平面圖，並且可以使用約旦曲線定理來證明，而包含這一結果的更一般的結果是庫拉托夫斯基歸約定理。效用圖是顯示上述關係的圖，也稱為湯姆森圖（例如，Coxeter 1950），並且在更正式的圖論術語中，被稱為完全二分圖 （並且也等同於迴圈圖 ）。

它在 Wolfram 語言中實現為GraphData["UtilityGraph"].

效用圖的圖交叉數為 1，最小交叉嵌入如上圖最右側的圖形所示。

效用圖的非平面性的一個簡單證明可以透過注意到該圖由一個圖環 組成，必須向其新增三條邊 、 和 。現在，對於每條邊，我們必須選擇是將邊繪製在圖環內部還是外部，因此對於兩條邊，我們必須做出相同的選擇。但是兩條線不能在同一側繪製而不交叉，因此該圖不是平面的。

它可以使用 LCF 符號表示為 。效用圖是一個積分圖，其圖譜為 。

上面的圖顯示了效用圖的鄰接矩陣、關聯矩陣和圖距離矩陣。

刪除效用圖的一條邊會得到四面體圖。

效用圖的圖虧格為 ，因此它可以無交叉地繪製在環面上，如上圖所示 (M. Malak, 私人通訊，2006 年 2 月 15 日)。