关于同态等价图与子图包含关系的技术问询

嘿，这个问题问得非常到位！答案是肯定的——确实存在一对同态等价的图，它们彼此都不是对方的子图。

举个经典且清晰的例子：

• 图G是两个不相交的5阶环（C₅∪C₅），总共10个顶点，由两个完全独立的5边环组成。
• 图H是Petersen图和一个5阶环共享一个顶点形成的图，总共14个顶点（Petersen图本身有10个顶点，加上5阶环的4个新顶点）。

这两个图是同态等价的：

• 从G到H的同态：把G中的第一个5阶环嵌入到H里Petersen图自带的5阶环子图中，第二个5阶环嵌入到H里共享顶点的那个5阶环中，完美保持边的映射关系。
• 从H到G的同态：把H里的Petersen图整体映射到G的其中一个5阶环（Petersen图本身可以同态映射到C₅），共享顶点的5阶环映射到G的另一个5阶环，同样满足同态的要求。

而它们彼此都不是对方的子图：

• G有10个顶点，H有14个顶点，G的两个5阶环完全独立，H里的两个环共享一个顶点，结构差异导致G无法作为子图嵌入到H中；
• H的顶点数比G多，显然也不可能是G的子图。

再补充一个顶点数相同的例子：Petersen图和它的线图（也叫Petersen补图）。两者都是10顶点的强正则图，互相存在同态映射，但边集结构完全不同——Petersen图是“5环加5条星边”的结构，线图则是K₅去掉一个完美匹配后的图，彼此都无法作为子图嵌入到对方中。

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