在一个无向图中，最简单的环必须有三个节点吗？

Question

我正在尝试编写有关循环和无向图的证明，但是有些困惑。

如果我的图只有2个顶点，并且它们之间有一条边相连，那不算作一个循环，对吗？

所以，我需要至少3个顶点，在2个顶点之间有2条连接到另一个顶点的边，并在另外两个顶点之间有一条边，才能在图中具有最小可能的循环（三角形）。或者我是错误的吗？

- OHHH

Answer 1

是的，最简单的循环可以由3个节点创建。

有两个节点的图形不是一个循环，也不能成为循环，因为它与一组节点包含循环的规则相冲突。如果您有3个节点，则在每个节点至少具有2个边的情况下，可能会存在循环。

为了检查循环，您必须检查以下规则：

如果您查看节点的所有邻居，并且有一个邻居已经被访问过，并且与先前访问的邻居不同，则表示存在循环。

- Christo S. Christov

Answer 2

根据维基百科的文章https://en.wikipedia.org/wiki/Cycle_graph所述：

循环图或圆形图是由单个循环组成的图，换句话说，是一些通过闭合链相连的顶点。具有n个顶点的循环图称为Cn。Cn中的顶点数等于边数，并且每个顶点的度数为2；也就是说，每个顶点恰好与两条边相连。

因此，“如果我的图仅具有2个顶点和一条连接它们的边，那不是一个循环，对吗？” 不是..

“因此，我需要至少3个顶点，其中2个顶点之间有2个连接，另外两个顶点之间有1个连接，才能在图中具有最小可能的循环（三角形）”- 是的。

- GorvGoyl