图的笛卡尔积正则性逆命题的正确性验证及相关问题咨询

你好呀！先给你吃个定心丸：你用逆否命题推导的过程完全正确！

咱们再理一遍这个逻辑，确保没漏洞：

• 笛卡尔积图$G \times H$中，任意顶点$(g, h)$的度数等于$G$中顶点$g$的度数加上$H$中顶点$h$的度数，这是笛卡尔积图的核心度数性质。
• 当$G$不是正则图时，必然存在两个顶点$g_1, g_2 \in V(G)$，使得$\deg(g_1) \neq \deg(g_2)$。随便取$H$中的一个顶点$h$，那么笛卡尔积里的顶点$(g_1, h)$和$(g_2, h)$的度数分别是$\deg(g_1) + \deg(h)$和$\deg(g_2) + \deg(h)$，两者的差是$\deg(g_1) - \deg(g_2) \neq 0$，所以这两个顶点度数不同，$G \times H$肯定不是正则图。

这就完美证明了逆命题：如果$G \times H$是正则图，那么$G$和$H$都必须是正则图。

再来说你提到的第二个问题：确实有很多性质是“$G,H$满足则$G \times H$满足”，但并不是所有这类性质都是双向等价的，这里给你举几个典型的反例：

• 树的性质：如果$G$和$H$都是树（连通无环的图），它们的笛卡尔积不一定是树。比如两个$K_2$（也就是两个单边图）的笛卡尔积是一个4-cycle（正方形），明显包含环，不是树。
• 平面图的性质：$G$和$H$都是平面图（可以画在平面上没有边交叉），但它们的笛卡尔积可能不是平面图。比如$K_4$是平面图，但$K_4 \times K_4$会包含非平面图的子图（比如$K_{3,3}$），因此不是平面图。
• 欧拉图的双向性反例：如果$G$和$H$都是欧拉图（连通且每个顶点度数为偶数），那么$G \times H$一定是欧拉图；但反过来，$G \times H$是欧拉图，不代表$G$和$H$都是欧拉图。比如$G$和$H$都是连通的3-正则图（每个顶点度数为3，奇数），它们的笛卡尔积中每个顶点的度数是$3+3=6$（偶数），且笛卡尔积连通，所以是欧拉图，但$G$和$H$本身因为顶点度数是奇数，不符合欧拉图的条件。

备注：内容来源于stack exchange，提问作者Kilkik