（五）

1.1.5节内容关于平面图。

1. 概念：1. 图G是平面图，如果R(G)同胚(homeomorphic)于R2的子集。 其中R(G) = ∪{(pi,pj):xi,xj∈E}∪∪{pi}，pi是R3中的点，并且至多三点共面。R(G)是拓扑空间。2. 将G再分割(subdivision)形成G的拓扑图，所谓再分割，就是用路将线替代，记为TG。例如，TK3是一个随机圈。3. 通过收缩得到的图称为G的收缩图，所谓收缩就是删去一条边(x,y)，将x，y等而视之。

   注：这个拓扑的部分我一头雾水。。

2. 欧拉公式：n-m+f = 2（使用归纳法证明）：其中，n为顶点数，m为边数，f为面数。

3. 记fi为由i边包围成的面，有：（1）∑fi = f，（2）∑ifi = 2m。由此可以证明：可平面图至多有max{g(n-2)/g-2, n-1}边，其中g是最长的周长。

4. 如果G非平面图，其拓扑图也非平面图。TH17指出，图是不可平面的当且仅当它包含K3,3或K5的一个再分割（Kuratowski,1930）TH18指出，图是可平面的当且仅当它的收缩图没有K3,3或K5。