对一个p个顶点的可平面图，若其为d正则图，如何证明这个图的色数大于等于p/（p-d）

### 回答1：
首先，我们可以使用Euler公式：对于任意一个可平面图，有 $p-q+r=2$，其中 $p$ 是顶点数，$q$ 是边数，$r$ 是面数。

对于一个 $d$ 正则图，每个顶点的度数都为 $d$。因此，边数 $q$ 等于 $\frac{pd}{2}$。我们可以将它代入Euler公式中，得到 $r=2-\frac{p}{2}+\frac{pd}{2}$，即 $r=2+\frac{p(d-2)}{2}$。

接下来，我们可以使用染色定理来证明该图的色数大于等于 $p/(p-d)$。染色定理指出，对于任意一个图，它的色数不超过最大度数 $Δ$ 加一，即 $χ(G)≤Δ+1$。

对于一个 $d$ 正则图，最大度数为 $d$，因此，其色数不超过 $d+1$。根据上面的推导，我们有 $r=2+\frac{p(d-2)}{2}$，即 $r≥2$。因此，该图至少有两个面。

现在，我们考虑将一个顶点 $v$ 以及与之相邻的所有边和面从图中删除，得到一个新的图 $G'$。由于 $v$ 的度数为 $d$，因此 $G'$ 中的每个顶点度数都不超过 $d-1$。因此，$G'$ 的色数不超过 $d$。

现在，我们可以使用归纳法来证明该图的色数大于等于 $p/(p-d)$。当 $p=2$ 时，该结论显然成立。假设对于 $p=k-1$ 的情况，该结论成立。现在考虑 $p=k$ 的情况。

我们可以选择一个面 $f$，并将其边界上的所有顶点染成同一种颜色。由于 $f$ 至少有三个顶点，因此，我们可以在 $G'$ 中找到一个顶点 $v$，使得 $v$ 与 $f$ 的边界上的至少两个顶点相邻。我们可以将 $v$ 染成与这两个顶点不同的颜色。然后，我们可以将 $v$ 以及与之相邻的所有边和面从图中删除，得到一个新的图 $G''$。由于 $G''$ 的顶点数为 $k-1$，根据归纳假设，$G''$ 的色数不小于 $(k-1)/(k-d-1)$。因为 $v$ 的度数为 $d$，所以 $G''$ 的最大度数不超过 $d-1$，因此 $G$ 的色数不小于 $(k-1)/(k-d-1)+1=k/(k-d)$。

因此，对于任意一个 $d$ 正则图，其色数不小于 $p/(p-d)$。

### 回答2：
要证明一个p个顶点的可平面图的色数大于等于p/（p-d），需要使用归纳法。

首先，当d=0时，即为一个无向图，根据图的可平面性质，色数大于等于p/（p-0），即色数大于等于1，这是显然成立的。

然后假设当d=k时，对于一个p个顶点的可平面图，其色数大于等于p/（p-k）成立。

接下来考虑d=k+1的情况，即一个p个顶点的k+1正则图。

根据握手定理，每个顶点的度数为d，则整个图的边数为p*d/2。

考虑图中一个度数为d的顶点v，与v相邻的顶点可以构成一个度数为d的子图，记为G'。根据归纳假设，G'的色数大于等于(p-d)/（p-(k+1)）。

将G'从原图中移除后，剩下的顶点数为p-d，边数为p*d/2 - d^2/2。

设移除G'后余下的图为G''，通过将G''中的每个顶点与v连接，可以构成一个度数为k的子图。根据归纳假设，该子图的色数大于等于(p-d)/（p-k）。

因此，整个图的色数至少为G'和子图的色数之和。

即色数大于等于 (p-d)/（p-(k+1)） + (p-d)/（p-k）。

化简上述不等式得到色数大于等于2 * (p-d)/（2p-d-k）。

又因为 p-d >= 2p-d-k，所以 2 * (p-d)/（2p-d-k） >= (p-d)/（p-(k+1)）。

综上所述，对于一个p个顶点的可平面图，若其为d正则图，可以证明其色数大于等于p/（p-d），且不等式成立。

### 回答3：
要证明对一个p个顶点的可平面图，若其为d正则图，则这个图的色数大于等于p/（p-d），可以使用归纳法来证明。

首先考虑边界条件：当d=0时，表示该图为0正则图，也就是一个不含边的图，此时显然色数为0，而p/（p-d）也等于0。所以边界条件成立。

其次，假设对于某个d值，当p小于等于n时，该结论成立，即可平面图中的色数大于等于p/（p-d）。

再考虑当d的值增加一个单位时，即d+1时，我们需要证明当p小于等于n+1时，该结论仍然成立。

设G为一个p个顶点的d+1正则图，它的平均度为a，即度数和2E等于2a。

根据握手定理，当我们对于每个顶点取出相邻的边后，度数和为2E，而由于图G为d+1正则图，每个顶点的度数为d+1，所以2E=p(d+1)。

根据平均度的定义，p个顶点的平均度为a，即p*d=p+a，可以得到p=a/(1-d)。

另一方面，根据归纳假设，对于其子图G'（删去一个顶点后的子图）来说，色数大于等于（p-1）/（p-d-1），即要证明p-1整除p-d-1。

由于p=a/(1-d)，所以p-d-1=a/(1-d)-(1-d)=a/(1-d)^2。

由此，我们需要证明 (p-1)*(1-d) 能整除 a。这可以通过图论的定理得到，对于一个d+1正则图，其色数大于等于d+2。因此，色数至少为d+2。

而 p/(p-d) >= (d+2) 也即 p >= (d+2)*(p-d) 也即 p >= (d+2)*p - (d+2)*d. 注意到 p>=(d+2)*p 不等式恒成立，而不等式 p >=(d+2)*d 事实上也是成立的，因为右边的表达式大于等于0。

因此，p>=(d+2)*p - (d+2)*d 成立，即 p - d*p >= 2*p - (d+2)*d; p*(1-d)>=2p - (d+2)*d; -p>=-d^2 - 2*d -2.

因为 p>=d^2 + d + 2, 显然这个不等式是成立的。

所以，按照归纳法的假设，对于一个p个顶点的d+1正则图，其色数大于等于p/（p-d）也成立。

综上所述，对于一个p个顶点的可平面图，若其为d正则图，则这个图的色数大于等于p/（p-d）。