本来应该(被)科普一些拓扑的姿势的，但是目前好像也不太用得上，就先咕了吧。
本文假设读者有一定的图结构知识，比较新的概念俺会努力解释的
这里的内容都比较入门，大佬轻喷(
平面图(Plane Graph)
我们称具有如下性质的图 \(G\) 为平面图：
\(V(G)\subseteq \mathbb R^2\)，\(E(G)\subseteq \mathbb R^2\) 毕竟是"平面"图
\(\forall e_1,e_2\in E(G)\), \(st(e_1)\neq st(e_2)\text{ and } ed(e_1)\neq ed(e_2)\)
\(\forall e_1,e_2\in E(G)\), \(e_1\cap e_2\in \left(V(G)\cup\varnothing\right)\)
\(\forall e\in E(G)\), \(e=(x,y)\) 是连通 \(x,\;y\) 的一段弧(arc)。
在一般图中，我们认为 \(E(G)\) 中的元素是若干二元组。在平面图中，我们认为图的边 \(e=(x,y)\) 是连通 \(x\) 和 \(y\) 的一段弧(arc)，即一个点集。此时 \(G\) 就可以代表由所有顶点以及边上的点构成的点集。
考虑点集 \(S=\mathbb R^2\backslash G\)，\(S\) 中存在着若干不相交的区域(region)。我们记 \(F(G)\) 为 \(S\) 中的所有区域，将这些区域称为图 \(G\) 的面(face)。若 \(f\in F(G)\) 是无界的(unbounded)，则记为外面，否则记为内面。
平面图的欧拉定理
对于平面图 \(G=(V,E)\)，\(F=F(G)\)，则有 \(|V|-|E|+|F|=2\)
考虑对 \(|E|\) 归纳。
当 \(|E|=|V|-1\) 且 \(G\) 连通时，\(G\) 是树，此时 \(|V|=|E|+1\)，\(|F|=1\)，带入成立。
设当 \(|E|<k\) 时成立，则对于 \(||G||=k\)，必然存在一个圈 \(C\)。取 \(e\in E(C)\)，考虑 \(G'=G-e\)。则必然存在两个面 \(f_1,f_2\)，满足 \(f_1\neq f_2\) 且 \(e\subseteq(\partial f_1\cap\partial f_2)\)。记 \(f=f_1\cup f_2\cup (\partial f_1\cap\partial f_2)\)，则 \(F(G')=F(G)-f_1-f_2+f\)。于是可以由 \(|V(G')|-|E(G')|+|F(G')|=2\) 得到 \(|V(G)|-|E(G)|+|F(G)|=|V(G')|-|E(G')|-1+|F(G')|+1=2\)
于是对于任意有限的平面图，平面图欧拉定理成立。
三角剖分定理
若对于平面图 \(G\) 中的每个面 \(f\)，\(\partial f\) 上都只有三个点，则 \(G\) 是一个三角剖分图(triangulation graph)
极大平面图(maximal plane graph)定义为 \(\forall x,y\in V(G)\)，\(G+(x,y)\) 都不是平面图。
我们有：平面图 \(G\) 是极大平面的当且仅当它是一个三角剖分
\(\Rightarrow\)：
取 \(f\in F(G)\)，则 \(\partial f\) 是一个圈 \(C\)。观察到必然有 \(|C|\leqslant 3\) (否则可以选取 \(C\) 上两个不相邻的顶点连边使得仍然是平面图，这与极大平面矛盾)
且由平面图的定义可知 \(|C|>2\) (否则存在重边)，因此 \(|C|=3\)。由 \(f\) 的任意性可知 \(G\) 是一个三角剖分。
\(\Leftarrow\)：
由反证法，假设存在 \(x,y\in V(G)\) 使得 \(xy\) 的内部在某一区域 \(f\) 内，那么必然有 \(x,y\in\partial f\)。而由 \(G\) 是三角剖分可知 \(|V(\partial f)|=3\)，故 \(x,y\) 必相邻，这与 \(G\) 不含重边矛盾。故命题成立。
平面图的必要条件
若图 \(G=(V,E)\) 是平面图，则 \(|E|\leqslant 3|V|-6\)
对三角剖分的边和面计数，则有 \(\frac{3|F|}{2}=|E|\) (每个面的边界上有三条边，每条边的两侧恰好为两个面)，带入平面图欧拉公式就有 \(|E|=3|V|-6\)。
若不含三角形的(triangle-free graph)的图 \(G=(V,E)\) 为平面图，则 \(|E|\leqslant2|V|-4\)
证明和上面类似，每个面的边界有四条边
子式和拓扑子式
拓扑子式
考虑一个固定的图 \(X\)，我们用若干不相交的路替换掉 \(X\) 的边得到新的图 \(X'\)，则我们称 \(X'\) 是 \(X\) 的一个细分，也记作 \(X'=TX\)
我们把 \(V(X)\cap V(TX)\) 称作 \(X\) 的分支顶点，把 \(V(TX)\backslash V(X)\) 称作 \(X\) 的细分顶点。很显然细分顶点度数都是 \(2\)
若 \(TX\subseteq G\)，则我们称 \(X\) 是 \(G\) 的拓扑子式
子式
考虑一个固定的图 \(X\)，我们用若干不相交的连通图 \(G_x\) 替换掉 \(X\) 中的顶点，对于 \(xy\in E(X)\) 则用 \(G_x-G_y\) 路替换掉，这样得到的图记作 \(X'\)，那么我们记作 \(X'=IX\)
若 \(IX\subseteq G\)，则我们称 \(X\) 是 \(G\) 的收缩子式，记作 \(X\preceq G\)
Kuratowski定理
这个定理很强，但是证明非常麻烦....这里打算摸了只给出结论，具体证明可以参考任意一本找得到这个定理的图论教材~
对于图 \(G\)，下列叙述等价：
\(G\) 可平面
\(G\) 不包含 \(K_5\) 或 \(K_{3,3}\) 作为子式
\(G\) 不包含 \(K_5\) 或 \(K_{3,3}\) 作为拓扑子式
极大可平面图是三连通图
这是作业里需要证明的一个小引理，不过很有用，也放上来吧
要用到三连通图的收缩列
引理1：\(\exists uv\in E(T_n)\) 使得 \(\left|{N(u)\cap N(v)}\right|=2\)
首先 \(\forall x\in V(T_n)\)，都有 \(deg(x)\geqslant 3\)。任取边 \(uv\in E(T_n)\)，\(uv\) 恰好在两个面 \(f_1,f_2\) 的边界上。而由三角剖分的定义可知 \(f_1,f_2\) 的边界是两个三角形。因此 \(\forall uv\in E(T_n)\) 都有 \(|N(u)\cap N(V)|\geqslant 2\)。
由反证法，不妨假设 \(\forall uv\in E(T_n)\) 都有 \(|N(u)\cap N(v)|\geqslant 3\)，则易知 \(|N(u)|\geqslant 4\) 且 \(|N(v)|\geqslant 4\)
不妨记 \(N(u)=\left\{\;x_1,x_2,x_3,x_4\;\right\}\)，则由 \(|N(u)\cap N(x_1)|\geqslant 3\) 可得 \(x_1x_2,x_1x_3,x_1x_4\in E(T_n)\)
同理有 \(x_2x_3,x_2x_4,x_3x_4\in E(T_n)\)，故 \(u\cup N(u)\) 的导出子图是 \(K_5\)，这与 \(T_n\) 可平面矛盾。
因此 \(\exists uv\in E(T_n)\) 使得 \(|N(u)\cap N(v)|=2\)。证明对图的阶没有要求，因此引理对 \(T_n\)，\(n\geqslant 4\) 成立。
极大可平面图是3-连通图
对极大可平面图 \(T_n\) 的阶作数学归纳法。
当 \(n=4\) 时，\(T_4=K_4\) 是三连通图；
设当 \(n=k\) 时 \(T_k\) 是三连通图，则取 \(k+1\) 阶极大可平面图 \(T_{k+1}\)，由引理1可知 \(\exists uv\in E(T_{k+1})\) 使得 \(|N(u)\cap N(v)|=2\)。
作图的收缩，记 \(G=T_{k+1}\circ uv\)，容易发现 \(||G||=||T_{k+1}||-|\left\{\;uv\;\right\}|-|N(u)\cap N(v)|\)
又因为 \(T_{k+1}\) 是三角剖分，所以 \(||G||=3(k+1)-6-1-2=3k-6=3|G|-6\)
又因为 \(G\) 仍然是平面图，所以 \(G\) 也是极大可平面图。由归纳假设，\(G\) 是三连通图，存在一个保持三连通性的收缩。因此 \(T_{k+1}\) 也是三连通图。