无向非加权图的最大顶点对数

给定具有任何类型连通性的无向非加权图,即它可以包含1到多个组件,有或没有单个节点,每个节点可以有0到多个连接,允许循环(但不允许从节点到自身的循环)。

我需要找到最大数量的顶点对,假设每个顶点只能使用一次,例如,如果图有节点1,2,3,并且节点3连接到节点1和2,则答案是1(1-3或2-3)。

我正在考虑以下方法:

1. 删除所有单个节点。
2. 找到边数最少的节点与边数最多的节点之间连接的边(如果有多条,则取其中任何一条),计算并从图中删除这对节点。
3. 当图形具有连接的节点时,重复步骤2。

我的问题是:

1. 它是否提供了任何情况下的最大对数?我是 担心一些极端情况,比如 单个或多个路径等。

2. 有没有更快更正确的算法?

   我可以使用java或python,但伪代码或仅仅是algo描述就可以了。