Build a graph with the biggest distance (edges) between two nodes is equal than two

I have to build an algorithm using python: i) This algorithm has to build a graph that has the minimum possible number of edges given a number n of nodes. ii) we have to go from one node to another node using at most two edges. iii) some nodes cannot be adjacent to each other. iv) it is guaranteed that for a given input we will be able to find a solution that satisfies the three items above.

The function signature can be createGraph(n: int,forbidenEdge: list[int]) -> list[int]

One example: n = 4 forbidenEdge = [[1,3]]

The function returns the edges that have to be built so we have a minimum number of edges in the graph.

For the given example we have this possible output (sometimes we can have more than one output): [[1, 2],[4, 2],[2, 3]]

I am not sure if the solution I am thinking to implement is correct.

If we do not have any restrictions or if there is at least a node that can be connected to any node the minimum number of edges is equal to (n - 1). We can choose a node that can connect to all the other nodes. The problem is when no node can connect to all the other nodes. For this, I am thinking to create the following algorithm, but I am not sure if it is correct. For this situation I am thinking about the following algorithm:

We have to check the number of connections that each node can do and order them in a list according to this number. We have to check if the nodes that cannot connect to the node center are able to be connected to all other nodes (if it is possible, we connect the nodes that can be connected to the node center and the other nodes we connect to each other ... we print the connections) if it is not possible we have to choose another node center, the next in the sorted list. We repeat it until we find a node center that when chosen is going be possible to build edges between the nodes in a way that from any node we can move to another node passing through two edges only.

For this algorithm, if we have n = 4 forbidenEdge = [[1,3],[2,4]] ... node 3 can be the node center. Node 1 cannot connect to the node center, so it connects to all the other nodes. So we have the output: [[1,2],[1,4],[2,3],[3,4]].

Is this algorithm going to get it right for any n and any forbidenEdge list? How could I prove it?

from Build a graph with the biggest distance (edges) between two nodes is equal than two