The closure of a graph $G$ is defined to be the graph obtained from $G$ by recursively joining pairs of non-adjecent vertices whose degree sum is at least $n$, until no such pair exists [$n=|V(G)|$].
I want to prove that the closure is unique.
I tried to assume the claim is incorrect, so there exist $G_1$ and $G_2$, both closures of $G$ but there exists some edge $(a,b)$ in $G_1$ (WLOG) which doesn't belong to $G_2$.
By definition of closure we know that $d(a) + d(b) < n$ (in $G_2$).
I'm not sure how to proceed, can you please give me some clues?
Best Answer
Let us say that a nonadjacent vertex pair $\{u,v\}$ is good for the graph $G$ if there is a sequence of vertex pairs $\{u_1,v_1\},\dots,\{u_k,v_k\} = \{u,v\}$ such that $d(u_i) + d(v_i) \geq n$ in $G + \{u_1v_1,\dots,u_{i-1}v_{i-1}\}$ for all $1 \leq i \leq k-1$.
How can you (uniquely) describe the closure of $G$ in terms of good vertex pairs?
Answer:
This approach can be reformulated in terms of your proof attempt, but I find it cleaner this way.