Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm
I'll try to track myself what I have been able to establish so far as an empirically working solution.


  
  Remove vertices {v0,v1,...,vp} and introduce a vertex vij for each (vi,vj)∉E in G, where 0
  


It is practical to have a function $lookup(x)$ for the supplementary vertices at your disposal, such that $lookup(i) = \{ v_{ij}| j: (v_i, v_j) \notin E\}$.


  
  Add an edge (vir,vjs) if i=j and (vr,vs)∈E in G.
  


In practice, each new supplementary vertex $v_{ij}$  in $G\prime=(V\prime, E\prime)$ must be connected to every supplementary vertex $v_{rs} \in lookup(i) \cup lookup(j)$ such that $r \neq i \land s \neq j$.


  
  Add an edge (vir,vjs) if i≠j.
  


This is the more straightforward case- for each supplementary vertex $v_{ij}$, and every edge $e_1=(v_i, v_r), e_2=(v_j, v_r); e_1,e_2 \in E$, create edge $e\prime=(v_{ij}, v_r); e\prime \in E\prime$.
∀u∈∖{v0,v1,...,vp} add the edge (vij,u) if (vi,u)∈E or (vj,u)∈E.

Result:



Still, any review of the correctness of my musings or guidance as to how to interpret and adhere to the original paper better is much appreciated!