Proof The argument follows from Figure 5. Indeed, (v1, v2, v3, v4) is a P4 in the original graph if and only if (v3, v1, v4, v2) is a P4 formed by the added edges.