关于同度序列且各阶环数量相同的非同构二部图的存在性问询

嘿，这个问题提得特别好！答案是肯定存在这样的二部图——它们有完全相同的度序列，对任意整数k，k-环的数量也完全一致，但就是非同构。我给你举两个不同类型的例子，帮你理解：

无环的例子（树） #

树本身都是二部图，而且树里没有任何环，所以对所有k≥3，k-环的数量都是0。现在找两个度序列相同但非同构的树就行：

• 第一个树：两个度数为3的顶点直接相连，每个顶点再各自连接2个叶子（总共8个顶点）
• 第二个树：一个度数为3的顶点连接三个顶点，其中一个顶点也是度数3，这个顶点再连接2个叶子，剩下两个是直接连在根顶点的叶子（也是8个顶点）

这两个树的度序列都是[3,3,1,1,1,1,1,1]，没有任何环，所以所有k-环的数量都是0，但它们的结构明显不一样，完全不同构。

带环的例子（共谱二部图） #

如果你想要带环的例子，那可以找共谱的非同构二部图——共谱图指的是它们的邻接矩阵有完全相同的特征值（包括重数）。因为图中k-环的数量可以通过特征值的幂次和计算出来，所以共谱图的k-环数量必然完全一致；同时它们的度序列也相同（度序列的平方和等于特征值的平方和，而度序列的和等于特征值的和，对二部图来说特征值是对称的，所以度序列必然匹配）。

比如有一对8顶点的二部图，二分划都是4个顶点，每个顶点的度数都是3：

• 第一个图的连接方式：把二分划的X={a,b,c,d}和Y={w,x,y,z}，边为a-w,a-x,a-y；b-w,b-x,b-z；c-w,c-y,c-z；d-x,d-y,d-z
• 第二个图的连接方式：X={a,b,c,d}和Y={w,x,y,z}，边为a-w,a-x,a-y；b-w,b-y,b-z；c-x,c-y,c-z；d-w,d-x,d-z

这两个图没有相同的结构，不同构，但它们的度序列完全一样，而且对任意k，k-环的数量也完全相同。

总结一下：度序列和k-环数量只是图同构的必要条件，远不是充分条件——不管是无环的树还是带环的二部图，都存在满足前两个条件但不同构的例子。

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