Suppose *G* is a graph on *n* vertices. Then the ***closure*** of *G*, written [*G*], is constructed by adding edges that connect pairs of non-adjacent vertices *u* and *v* for which 


$\deg(u) + \deg(v) \geq n.$


One continues recursively, adding new edges until all non-adjacent pairs *u*, *v* satisfy


$\deg(u) + \deg(v) < n.$


Is it unique for a graph?



The uniqueness of graph closure
Many years ago Staszek Radziszowski and I published a very elementary lemma that covers this case and many similar cases.


Let $(X,\le)$ be a partially ordered set and let $\varPhi$ be a family of functions from $X$ to $X$. Suppose that, for $x,x'\in X$ and $\phi\in\varPhi$ we have $\phi(x)\le x$ and $x\le x'\implies \phi(x)\le\phi(x')$. Call $x\in X$ *$\varPhi$-stable* if $\phi(x)=x$ for all $\phi\in\varPhi$. Let $\varPhi^\*(x)$ be the closure of $\lbrace x\rbrace$ under $\varPhi$.


**Lemma.** For each $x\in X$, $\varPhi^\*(x)$ contains at most one $\varPhi$-stable element.


To apply it to this case, $X$ is the set of all (labelled) graphs on $n$ vertices and $x\le x'$ means that $x$ is a **super**-graph of $x'$. There is a function for each pair of vertices $i,j$ which makes them adjacent if their degree sum is at least $n$ and does nothing otherwise. There is at least one $\varPhi$-stable graph (add edges until you can't add more) so by the lemma it is unique.


See [Lemma 2 of this paper](http://users.cecs.anu.edu.au/~bdm/papers/r45.pdf).


