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.

• Is the closure of a graph saying that we add edges between every vertex so they touch? I am not concerned about using this definition in particular, just a definition that someone knows works for undirected graphs. I think for the graph on the left to add the following edges: $\lbrace v_1, v_2\rbrace$, $\lbrace v_1, v_4\rbrace$ just so all the vertices have endpoints between them, but I am not sure. – W. G. Aug 27 '18 at 18:13
• I get the impression that this definition is intended for simple graphs. because loops and multiple edges complicate the degree. That said, the definition should extend to non-simple graphs. – Kevin Long Aug 27 '18 at 18:16
• I got that impression as a possibility too. The reason I want this definition is to look at Ore's Theorem which does use simple graphs which makes sense as to what you are saying as the definition might only apply to simple graphs. It might be more generalizable too. – W. G. Aug 27 '18 at 18:30

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.

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.

• I think that the definition means the degree before adding the new edges, not after. Hence, the graph on the left should already be closed. – Kevin Long Aug 27 '18 at 18:18
• But definition says at least so I think we can still add an edge unless we have all the vertices adjacent. But according to your understanding, my calculation on degree sums may change. – ArsenBerk Aug 27 '18 at 18:20
• I really like the picture :) – W. G. Aug 27 '18 at 18:47
• I found an example from some lecture notes on the front page of google, and if you look at figure 12.1 on page 4, it only adds an edge between the vertices which already have degree sum at least $n$. At the last stage, for example, vertices $3$ and $7$ have degrees $4$ and $1$ respectively, and adding an edge between them would make their degree sum $7$, but that edge is never added. – Kevin Long Aug 27 '18 at 20:04
• How do you justify adding either of the red edges to the left? No matter which one you start with, the sum of the degrees of $v_1$ and $v_4$ (or $v_1$ and $v_2$) is only $3$, which is not $\ge n$, because $n=4$. – Henning Makholm Aug 27 '18 at 21:45