同构图顶点特性证明：如何严谨证最大度数相关结论？

嘿，我来帮你梳理下这个图论证明的思路和可行方案～

首先明确需要证明的三个核心结论：

• 结论1：若$G \cong H$，则$G$与$H$的最大度数相同；
• 结论2：若$G \cong H$，则$G$与$H$的最大度数顶点数量相同；
• 结论3：若$G \cong H$，则最大度数顶点的导出子图间存在同构。

关于结论1、2的反证法可行性（不单纯依赖双射一一对应） #

完全可以用反证法来证明，而且能避开直接照搬“同构双射保持邻接性”的直白对应，从结构矛盾的角度切入：

证明结论1（反证法） #

假设$G \cong H$，但$G$的最大度数$\Delta(G) > \Delta(H)$。

同构的核心本质是：两个图的顶点邻域结构可以完美匹配，不存在任何结构差异。
取$G$中一个度数为$\Delta(G)$的顶点$v$，因为$G$和$H$同构，$v$的邻域（所有与$v$相邻的顶点集合）必然能在$H$中找到一个完全对应的顶点邻域。但$H$中所有顶点的度数最多是$\Delta(H)$，这意味着$v$的邻域大小（即度数）大于$H$中任何顶点的邻域大小——这直接和“同构下邻域结构完全匹配”的性质矛盾。
同理，若假设$\Delta(G) < \Delta(H)$，也会导出同样的矛盾。因此$\Delta(G) = \Delta(H)$。

证明结论2（反证法） #

假设$G \cong H$，且$\Delta(G)=\Delta(H)=\Delta$，但$G$中度数为$\Delta$的顶点数$k_G$不等于$H$中的$k_H$，不妨设$k_G > k_H$。
考虑$G$中所有$\Delta$度顶点构成的集合$S_G$，$H$中对应集合为$S_H$。由结论1的推导可知，同构映射下，$S_G$中的每个顶点在$H$中对应的顶点必然也是$\Delta$度（否则会出现邻域大小不匹配的矛盾），这意味着$S_G$在映射下的像完全包含于$S_H$。但$|S_G| > |S_H|$，根据鸽巢原理，至少有两个$S_G$中的顶点会映射到$S_H$中的同一个顶点——这和同构映射必须是双射（每个原像对应唯一像，无重复）的基本要求矛盾。
反过来假设$k_G < k_H$，同样会导出矛盾，因此$k_G = k_H$。

关于结论3的证明思路 #

基于前两个结论，取$G$中最大度数顶点的导出子图$G[S_G]$，$H$中对应导出子图$H[S_H]$。由于原同构映射$f$已经把$S_G$双射到$S_H$，并且$f$本身保持所有顶点间的邻接关系，那么$f$在$S_G$上的限制就是$G[S_G]$到$H[S_H]$的同构映射，直接可证结论成立。

内容的提问来源于stack exchange，提问作者ryno