Question

离散数学作业，求正解

证明K33不是平面图。

Answer 1

定义：若一个图能画在平面上，使它的边互不相交（除在结点外），则称该图为平面图。

如下图，图1是K3,3，图2是图1的边交叉最少的一种画法，但总无法避免边的交叉，故K3,3为非平面图。

Answer 2

(k3,3图片无法附带，可以自己画，下面给出证明)

证明：
K3,3的图中，定点数v=6，e=9。
根据平面图公式v-e+r=2,代入，v和e的值，得r=5。从图中可知每个面至少由4条边组成，平面图满足公式kr<=2*e,其中k为面的次数，r为面数，e为边数，而k3,3图中有，4*r=20,2*e=18,而20>18 ,与公式kr<=2*e矛盾，所用k3,3图不是平面图。