不含N个不交环的图

l4m2

定义两个无向图等价，如果可以通过将一条边切成两端，中间增加一个节点；或者增减叶子，使得两个图相同。
不含1个不交环的图，只有树一种（注意所有树都等价）。
不含2个不交环的图，有K1,K3,K4,K33,K23五种（由rolamni证明）。
那么，对于更大的N，都有几种？是否存在N达到无穷种？

mathe

你这里应该还有连通的约束，也就是求所有点度数大于2的连通图的分类。主要是最大有多少个不交环不容易计算。

l4m2

附上他的证明：
rolamni
—
2025/2/13 凌晨1:16
Let's make the search space as small as possible:
We can assume that each vertex has degree at least 3. (Else we can delete that vertex if it is not the last vertex, so we only get rid of the single point graph (trees) and the circle case.) Thus |E| >= |V| * 3/2.
Lemma: Each graph G with |E| >= |V| + 4 has two edge-disjoint cycles.
Proof: Assume otherwise. Take a minimal example. Then |E| = |V| + 4. As established before, also  |E| >= |V| * 3/2 and thus |V| <= 8, |E| <= 12. Now if G had a 3- or 4-cycle, then G\C would have |E| >= |V| and thus have a cycle. Thus, all cycles would have to be of length at least 5. Take any vertex v. That vertex has at least 3 neighbors, each of those not having a common neighbor besides v. Thus, we have at least 1 + 3*3 = 10 vertices, which is a contradiction to |V| <= 8. QED
Thus, we have |V| + 3 >= |E| >= |V| * 3/2 and hence |V| <= 6. So, all equivalence classes have a representative with at most 6 vertices (and at most 9 edges).
The graphs with 6 vertices are not allowed to have 3-cycles (then the same argument would be doable with |E| >= |V| + 4, which leads to K_3,3 being the only example with 6 vertices.
rolamni
—
2025/2/13 凌晨1:26
With 5 vertices you still can't have 2-cycles (double edges). Also, not all vertices can have degree 3, so one of them has to have degree >=4 and thus is connected to all other vertices. Then you can pretty quickly rule out any examples with 5 vertices.
So now only graphs with at most 4 vertices. They can have at most one double (or triple) edge.
Without any double edges, the only example would be K_4.
Having a double edge, all cycles must contain one of these edges, leaving only the triple edge graph and the two graphs that we first ignored (point and circle).
If I didn't make any mistake, these are the 5 equivalence classes you were looking for.

mathe

所以这里不相交的环是指两个环不能有公共边，但是可以有公共点了？不然K34也应该满足

l4m2

另外，这五种都是K33去掉一些边得来的。对别的N，这种特性保留吗？

mathe

有一个问题，很可能一个图原先没有重边，但是删除一些二度点以后就变成重边了。
比如现在图中AB两点有一边相邻，然后还有很多个点，它们都和A,B相邻，但是它们之间没有任何边。这个图也是简单连通图，不包含两个不相交环。但是如果对它进行简化，删除所有二度点，就会形成很多重边。

mathe

我们需要寻找一种可以通过计算机进行构造的方案。
由于去除所有不形成环的边，以及合并度数为2的边的左右两边后，最终形成每条边去除都会减少环。
除掉无环图(树）以外，最简单的图只有一个环，等价K3,如下图左上角。
通过它，可以派生出两个图，一个是从K3上取一个点，添加一个自环，构成它下面的图，等价两个共享一个顶点的三角形。另外一个是从K3上取两个不同的点，再连接一条边，构成等价K23的图。
可以看到K3下边的图已经包含至少两个不相交环。如果仅寻找只包含一个环的图，就不需要继续从这个节点派生了。
然后K23, 类似可以通过添加一条边得到更多图，其中边的两个端点可以是原先某条边上一个点，也可以是原先某个点，同样只有K4指包含一个环。后面通过K4可以继续派生出K33等。最后只要验证K33派生的所有图都至少有两个不相交环即可。类似，使用计算机应该可以计算包含更多的环的情况，为了降低计算复杂度，我们还需要的是将等价的图进行合并, 这部分工作，可以使用 nauty and trace。