新浪博客

1）归纳基础：一条边，欧拉公式成立；
（2）归纳步骤：假设m-1条边，欧拉公式成立；
考察m条边的连通平面图：
1）若有度数为1的顶点，则删去该顶点及其关联边，便得到连通平面图G’，G’满足欧拉公式，再将删去的点和边加回G’得到G也满足欧拉公式；
2）若没有度数为1的顶点，则删去有界面边界上的任一边，便得到连通平面图G’， G’满足欧拉公式，再将删去的边加回G’得到G也满足欧拉公式。


推论1
若G是n≥3的平面简单图，则e≤3n-6。
证明：只证明连通的平面简单图的情况，G是n≥3的平面简单图，每个面由3条或更多条边围成，因此边的总数大于等于3f，因为每条边至多被计算两次，所以G中至少有3f/2条边，即e≥3f/2。
根据欧拉公式，有n-e+2e/3≥2。
所以3n-6≥e。

推论2
在平面简单图G中至少存在一个顶点v0，
d(v0)≤5
证明方法：反证法，假设所有顶点度数大于5，则所有顶点度数和不小于6n,由于每条边用了2次所以有 e≥3n由推论1得3n-6≥3n，导致矛盾。


我的更多文章

下载客户端阅读体验更佳

APP专享