graph - 具有 n 个顶点的无向图必须具有的最小边数是多少才能始终连接？

Question

我知道对于要连接的具有 n 个顶点的无向图，它必须具有 n - 1 条边。但是，我的问题是它可以始终连接的最小边数是多少。例如，是否必须始终连接具有 n 个顶点和 n + 2 条边的图？如果不是，它必须有多少边才能始终连接？

Answer 1

如果您允许重复连接，则没有最大数量。（例如，您有 3 个顶点 a、b、c 并且边 (a,b) 多次出现无穷大，但没有与 c 连接的边）。所以为了让这个有趣，假设你不能有重复的连接。

对于 n+2 边的情况，请考虑是否有一个具有 10 个顶点的图，并且它的边形成k5的两个不相交的副本。k5 有 10 条边，因此我们有一个包含 10 个顶点和 20 条边的图，作为您声明的反例。但是，如果您在我的示例中注意到如果我们不断开任何边，则您无法在不连接图形的情况下添加边。

我们可以考虑的另一个例子（同样有 10 个顶点）是 k9 和单个顶点。k9 有 36 条边（比我之前的示例多），并且单个顶点使图不相交。通常，您的最大示例将是 k(n-1) 和单个顶点。

km 具有 m(m-1)/2 条边，因此您可以拥有并且仍然具有不相交图的最大边数为 (n-1)(n-2)/2。这意味着保证顶点图（没有自环或多个连接）的最小边数是 (n-1)(n-2)/2 + 1。

Answer 2

顶点图不能连接的最大边数是n-2。 对于具有 3 个顶点的图，您需要至少 2 条边才能使其连接，这n-1比这少一条边将为您提供最大的边，而该边将与该图断开连接。

是否必须始终连接具有 n 个顶点和n + 2边的图：取决于是否允许自循环例如考虑 3 个顶点和 5 条边的情况，因此它将通过 2 个边和 3 个自环连接，但首先是这种情况4 个顶点和 6 个边，它也是可能的，也是不可能的。