Closure of an Undirected Graph

$\textbf{Definition:}$ Let $G$ be a graph with $n$ vertices. The $cl(G)$ (i.e. the closure of $G$) is the graph obtained by adding edges between non-adjacent vertices whose degree sum is at least $n$, until this can no longer be done.

$\textbf{Question:}$ I have $\textbf{two}$ separate graphs above (i.e. one on the left and one on the right). What is the closure of both of these graphs looking at them again separately? I am having a hard time understanding this definition and a description of where the edges would go would be very helpful between vertices.

Solution 1:

In the first graph, no more edges can be added, because the pairs $(v_1,v_2)$ and $(v_1,v_4)$ have degree sum $3$, and every other pair is already adjacent. So this graph is its own closure.

For the second graph, we can add edges $v_1v_3$ and $v_2v_4$ immediately, since for both pairs the degree sum is $4$. Now the degree sum of $v_1,v_4$ is $5$, so we can add this edge too (note that we could not add this edge initially). There are no more non-adjacent pairs, so we've reached the closure.

The point of this definition is that a simple graph is Hamiltonian if and only if its closure is Hamiltonian - this is the Bondy-Chvátal theorem.

Solution 2:

If I don't misunderstand the definition, the following graphs must be the closure of your graphs:

The first graph stays as it was because $d(v_1)+d(v_2) = 3 < 4$ and $d(v_1) + d(v_4) = 3 < 4$ and rest of the vertex pairs are already adjacent.

In the second graph, my answer stays the same but with a little difference: Order of adding edges matters here because if we try to add $e_7$ first, then since $d(v_1) + d(v_4) = 3 < 4$, we can't do that. Therefore, we first add $e_5$ and $e_6$, then $e_7$ to get the graph above. After adding these three edges, since each vertex becomes adjacent to other vertices, we can no longer add an edge.