ファーリの定理とは？わかりやすく解説

ファーリの定理（ファーリのていり、英: Fáry's theorem, 洪: Fáry-tétel）はグラフ理論の定理で、任意の単純平面的グラフについて、その辺を交差しない線分によって描画（英語版）できることを主張する^[1]。ハンガリーの数学者ファーリ・イシュトヴァーンの名を冠する。

Klaus Wagner (1936)、 Fáry (1948)、Sherman K. Stein (1951) によって独立して証明された。定理にヴァーグナーの名を付すこともある。

すべての辺が直線分であるような埋め込みを Fáry embedding という^[2]。また Fáry embedding を持つ平面グラフを直線グラフという^[3]。

証明

ファーリの定理の証明の一つに数学的帰納法を用いるものがある^[4]。 $n$ 個の頂点を持つ単純平面グラフ $G$ を考える。 $G$ が極大となるように必要に応じて辺を加える。 $n < 3$ の場合は明らか。 $n \geq 3$ の場合を考える。 $G$ を極大としたので $G$ のすべての面は三角形である。ある面を選びその頂点を $a, b, c$ とする。 $n$ に関する帰納法によって、三角形 $abc$ が外領域となる、直線的で組合せ的同型^{[注 1]}である埋め込みの存在を証明する。 $n = 3$ のとき $G$ の頂点は $a, b, c$ に限られ、 $G$ の求めるべき埋め込みの存在は明らかである。次に $n \geq 4$ の場合を考える。

オイラーの多面体定理より $G$ は $3 n - 6$ 個の辺を持つ。グラフの頂点 $v$ の欠損を $6 - deg (v)$ と定義すると、すべての頂点の欠損の和は $12$ となる。 $G$ は少なくとも4つの頂点を持ち、その面はすべて三角形であるので、すべての頂点の次数は3以上である。したがってすべての頂点の欠損は3以下であって、少なくとも4つの頂点が正の欠損を持つ。よって $a, b, c$ でなく、5つ以下の頂点としか繋がっていないある頂点 $u$ を選ぶことができる。 $G$ から頂点 $u$ を除き、 $u$ の除去で出現した面 $f$ を三角化したグラフを $G'$ とする。 $n - 1$ における先の帰納法の仮定より、 $G'$ について三角形 $abc$ が外領域となる、直線的で組合せ的同型である埋め込みが存在する。この埋め込みにおいて $f$ の三角化に使用した辺を除去すると、 $f$ に対応する面は多くとも5つの辺しか持たない多角形 $P$ となる。美術館定理（英語版）より、 $P$ の頂点と $v$ を結んだ直線状の辺が $P$ のどの辺とも交わらないような頂点 $v$ を $P$ 内部に設置することができる。このとき埋め込みのすべての辺は直線であるので、 $n$ においても命題が成立し、よって任意の $n$ で辺が直線状である埋め込みの存在が確認できる。

脚注

[脚注の使い方]

注釈

^ 組合せ的同型とは、2つの埋め込みについて頂点・辺・面がそれぞれすべて対応していて、頂点や辺、面の接続関係が保たれている状態を指す。

出典

^ C.L.リウ著、伊理正夫, 伊理由美訳『組合せ数学入門 2』共立出版、1972年。ISBN 9784320005426。NDLJP:12623794。
^ de Fraysseix, Pach & Pollack 1990.
^ R.G.バサッカー、T.L.サーティ著、矢野健太郎, 伊理正夫訳『グラフ理論とネットワーク基礎と応用』培風館、1970年。 NCID BN00664833。NDLJP:12622032。
^ Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (5th ed.), CRC Press, pp. 259–260, ISBN 9781439826270 .
^ Tutte 1963.
^ Harborth et al. 1987; Kemnitz & Harborth 2001; Mohar & Thomassen 2001; Mohar 2003.
^ Geelen, Guo & McKinnon 2008.

参考文献

Fáry, István (1948), “On straight-line representation of planar graphs”, Acta Sci. Math. (Szeged) 11: 229–233, MR 0026311 .
de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), “Small sets supporting Fary embeddings of planar graphs”, Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433, doi:10.1145/62212.62254, ISBN 0-89791-264-0, http://purl.umn.edu/4760 .
de Fraysseix, Hubert; Pach, János; Pollack, Richard (1990), “How to draw a planar graph on a grid”, Combinatorica 10: 41–51, doi:10.1007/BF02122694, MR 1075065 .
Geelen, Jim; Guo, Anjie; McKinnon, David (2008), “Straight line embeddings of cubic planar graphs with integer edge lengths”, Journal of Graph Theory 58 (3): 270–274, doi:10.1002/jgt.20304 .
Harborth, Heiko; Kemnitz, Arnfried; Möller, Meinhard; Süssenbach, Andreas (1987), “Ganzzahlige planare Darstellungen der platonischen Körper”, Elemente der Mathematik 42 (5): 118–122, MR 905393, https://eudml.org/doc/141411 .
Kemnitz, A.; Harborth, H. (2001), “Plane integral drawings of planar graphs”, Discrete Mathematics 236 (1–3): 191–195, doi:10.1016/S0012-365X(00)00442-8 .
Mohar, Bojan (2003), Problems from the book Graphs on Surfaces .
Mohar, Bojan; Thomassen, Carsten (2001), Graphs on Surfaces, Johns Hopkins University Press, pp. roblem 2.8.15, ISBN 0-8018-6689-8 .
Sachs, Horst (1983), “On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem”, in Horowiecki, M.; Kennedy, J. W.; Sysło, M. M., Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, 1018, Springer-Verlag, pp. 230–241, doi:10.1007/BFb0071633, ISBN 978-3-540-12687-4 .
Schnyder, Walter (1990), “Embedding planar graphs on the grid”, Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148, ISBN 9780898712513 .
Stein, S. K. (1951), “Convex maps”, Proceedings of the American Mathematical Society 2 (3): 464–466, doi:10.2307/2031777, JSTOR 2031777, MR 0041425, https://jstor.org/stable/2031777 .
Tutte, W. T. (1963), “How to draw a graph”, Proceedings of the London Mathematical Society 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387 .
Wagner, Klaus (1936), “Bemerkungen zum Vierfarbenproblem”, Jahresbericht der Deutschen Mathematiker-Vereinigung 46: 26–32 .

ファーリの定理とは？わかりやすく解説