■2.证明彼得森图是非平面图。 ■提示:要证明一个图不是平面图,首先 考虑应用库拉托斯基定理。即在要判另 的图中,找出一个K或K3的剖分 (西安交通大学1997考研)
2. 证明彼得森图是非平面图。 提示：要证明一个图不是平面图，首先 考虑应用库拉托斯基定理。即在要判别 的图中，找出一个K5或K3,3的剖分。 （西安交通大学1997考研）
■3.证明小于30条边的简单平面图G中 至少有一个度数小于等于4的结点
3. 证明小于30条边的简单平面图 G中， 至少有一个度数小于等于 4的结点
■证明:不妨设G是连通图。 因为e≤3n-6,假设所有顶点度数大 于等于5;由握手定理,Σdev(v)=2e; 所以2e5n,则有n≤2e/5。 代入e≤3n6,则es6e/5-6,从而 e≥30。所以矛盾
证明：不妨设G是连通图。 因为e3n-6，假设所有顶点度数大 于等于5；由握手定理，dev(vi)=2e; 所以2e5n，则有n2e/5。 代入e3n-6，则e6e/5-6, 从而 e30。所以矛盾
4.证明在简单平面图G中,∫和n分别表 示该图的面数和结点数, (1)如果n≥3,则fs2m-4 (2)G中结点最小的度G=4,则G中至 少有6个结点的度数小于等于5。 (西安交通大学1996考研)
4. 证明在简单平面图G中， f 和n分别表 示该图的面数和结点数， (1) 如果n3，则f 2n-4。 (2) G中结点最小的度(G)=4，则G中至 少有6个结点的度数小于等于5。 （西安交通大学1996考研）
(1)证明:假设图中的边数为e。 由于简单图的每个面至少由3条边围 成,因此3/≤2。由欧拉公式n e+=2,得e=n+f2;代入3f≤2e得到 3/2m+f2),得fS2m-4
（ 1）证明：假设图中的边数为 e 。 由于简单图的每个面至少由 3条边围 成，因此3f 2e。由欧拉公式ne+f=2，得e=n+f-2；代入3f 2e得到 3f 2(n+f-2)，得f 2n-4