我正在寻找一种多项式时间算法，该算法以图形 G 和整数 K 的形式接受输入，并确定 G 是否是 K 顶点连接的。我认为这可能会利用深度优先搜索。我可以看到使用非多项式解决方案是如何实现的，即仅删除 K 个随机顶点，运行 DFS 以检查连通性，然后使用不同的顶点组再次执行此操作。〜O（n ^ K）的运行时间虽然有点多，但显然可以将其降低到多项式时间。知道我在这里缺少什么吗？我想这与我们在运行 DFS 后得到的非树顶点有关，但我不完全确定我在寻找什么？提前致谢！
编辑：要清楚，我不想确定图表的连通性。相反，输入时给出了一个数字 k，我希望检查该图是否是 k 连接的。它不会产生给出图形连通性的答案，只是一个是或否。