图论:设图有10个4度顶点,8个5度顶点,其余为7度顶点,求7度顶点的最大数量,使得G保持可平面性。

请尽量详细一点,谢谢。
2025-03-17 10:25:39
推荐回答(2个)
回答1:

由平面图的点线面公式(Euler 公式):(顶点数)n+(面数)f-(边数)m=2,d(v1)+d(v2)+d(vn)=2m,
及2m≥3f,可得:2=n+f-m ≤n+2/3m-m =n-1/3m=n-1/3[40+7/2(n-18)]
化简得:n≤36,所以7度顶点的最大数量是18.

回答2:

根据握手定理(图必须)和平面图的欧拉公式“点数-边数+面数=2”(可平面嵌入必须)可得:10