多面体的边

nnd

请证明，任何一个多面体，至少有一个顶点，它的棱只有3条。

hujunhua

不成立！你不知道正8面体和正20面体吗？ 多面体有带洞和不带洞的，洞的多少对命题的成立范围影响很大，提问时应该给予明确。对于不带洞的多面体（简单多面体），易证当面数F=4, 5, 6, 7时成立（即必有3度点）。 貎似F=9也成立，不过我没有证好。 感觉提问不明确是楼主的特色，以那个连线问题为甚。

hujunhua

1) 简单多面体的欧拉公式：V+F-E=2 2) 将$V_k$表示k度点（即发出k条边的顶点），有$V=V_3+V_4+V_5+...+V_{max}$ 3) 逐点对边计数可得：$2E=3V_3+4V_4+5V_5+...+mV_m=-V_3+4V+(V_5+...+(m-4)V_m)$ 4) 由极大图可得 $2V>=F+4$ 5) 由以上3式可得 $V_3=4+2(V-F)+(V_5+...+(m-4)V_m)>=8-F+V_5$ ，可知F=4,5,6,7时$V_3>0$ 。

hujunhua

由 5) 与其对偶式相加得：$V_3+F_3=8+(V_5+...)+(F_5+...)>=8$ 即简单多面体要么有3度点，要么有3角面，并且3度点与三角面之和不小于8.

hujunhua

而且3度点与三角面之和远远大于5度以上顶点数和5边以上的面数的总和

hujunhua

由$V>=F/2+2$, 得$V>=7$, 于是 5) 式变为$V_3>=V_5+2V_6+...+(m-4)V_m$ 所以如果F=9时存在反例，即存在$V_3=0$的平面图G，那么G必是4-正则图，即$V=V_4$。 对于4-正则图G，3#的3)式为 2E=4V，由此解得V=7，E=14。 由$2E=3F_3+4F_4+5F_5+...=3F+F_4+2F_5+...$得$1=F_4+2F_5+...$, 故$F_4=1, F_{>=5}=0$, 由5#得$F_3=8$. 现在可以描述反例G了：4-正则图，$F=9, V=V_4=7，E=14，F_3=8, F_4=1, F_5$以上没有。 只要将G唯一的$F_4$连一条对称线划分成2个三角面，它就成为一个7阶极大平面图G'，并且有两个相邻的$V_5$, 5个$V_4$. 将G'的一个5度点v及从它发出的5条边擦去，得到图G":$ V''=7-1=6, F''=10-5+1=6, F''_5=1, F''_3=5$. 显然，这是一个5棱锥。故6个顶点包括$V''_5=1, V''_3=5$. 但是追溯擦图过程可知 6个顶点包括$V''_3=4$（由G'的与v相邻的4个4度点失1边而来）, $V''_4=2$（1个由G'的与v相邻的另一个5度点失1边而来，另1个是由G'的4度点遗传而来），矛盾。故所设反例不存在。

hujunhua

F=8以上的偶数不成立，即都存在无3度点的简单多面体，比如下图所示F=10的扭柱体。

nnd

7# hujunhua 确实不成立 提问不明确是因为基础太差。

hujunhua

看你对四色定理蛮上心的，那你应该研习一本《图论》教科书。 建议你探讨一下F=11的情况，是一个不錯的练习。

nnd

前些天在画一个比较复杂的PCB板（二阶埋盲孔的八层板），因为不是专业的layout，所以比较艰难。画累了就想想连线的问题，然后联想到了四色定理。觉得挺有意思的。 适合业余爱好者看的图论入门书，能否推荐一下？