点,k条边和r-1个面. 由归纳假设, n-k+(r-1)=2, 即n-(k+1)+r=2, 得证m=k+1时结论也成立. 证毕. 欧拉公式的推广
设G是有 p (p?2) 个连通分支的平面图, 则 n ? m + r = p + 1
证 设第 i 个连通分支有 ni个顶点, mi 条边和 ri 个面. 对各连通分支用欧拉公式,
ni ? mi + ri = 2, i = 1, 2, … , p 求和并注意 r = r1+…+rp+ p?1, 即得
n ? m + r = p + 1 与欧拉公式有关的定理
定理: 设G为有 p (p?2) 个连通分支的平面图,
且每个面的次数不小于l (l ?3), 则则? (G)?5.
定理 设G为简单平面图，
库拉图斯基定理
定理 G是平面图?G中不含与K5同胚的子图, 也不 含与K3,3同胚的子图.
定理 G是平面图?G中无可收缩为K5的子图, 也无 可收缩为K3,3的子图.
平面图的对偶图
定义 设平面图G, 有n个顶点, m条边和r个面, 构造G 的对偶图G*=
在G的每一个面Ri中任取一个点vi*作为G*的顶点,
V*= { vi*| i=1,2,…,r }.
对G每一条边ek, 若ek在G的面Ri与Rj的公共边界上,
则作边ek*=(vi*,vj*), 且与ek相交; 若ek为G中的桥且在 面Ri的边界上, 则作环ek*=(vi*,vi*). E*={ ek*| k=1,2, …,m }.
性质：
? G*是平面图，而且是平面嵌入. ? G*是连通图
? 若边e为G中的环，则G*与e对应的边e*为桥; 若e为桥，则G*中与e对应的边e*为环.
? 在多数情况下，G*含有平行边. ? 同构的平面图的对偶图不一定同构.
上面两个平面图是同构的, 但它们的对偶图不同构.
平面图与对偶图的阶数、边数与面数之间的关系: 设G*是平面图G的对偶图，n*, m*, r*和n, m, r分别 为G*和G的顶点数、边数和面数，则 (1) n*= r (2) m*=m
(3) r*=n-p+1, 其中p是G的连通分支数
(4) 设G*的顶点vi*位于G的面Ri中, 则d(vi*)=deg(Ri)
离散数学第八章一些特殊的图知识点总结
