Cloning Nonadjacent Vertices
Extremal graph arguments often improve a graph by replacing the neighborhood of one vertex with the neighborhood of another. The useful case is when the two vertices are nonadjacent: the replacement makes them structurally identical without adding an edge between them. This operation, called Zykov symmetrization or cloning, has a precise effect on the edge count and preserves the property of containing no clique of a specified size.
Throughout, graphs are finite and simple. For a vertex \(x\), its neighborhood \(N(x)\) is the set of vertices adjacent to \(x\), and its degree is \(\deg(x)=|N(x)|\). A clique is a set of pairwise adjacent vertices; a \(K_q\) is a clique on \(q\) vertices.
The operation changes only edges incident to \(v\). Edges from \(v\) to common neighbors of \(u\) and \(v\) remain in place; edges from \(v\) to neighbors exclusive to \(v\) are removed; and edges from \(v\) to neighbors exclusive to \(u\) are added. No edges among the other vertices change.
Degrees and Edge Counts
Proof. By the definition of cloning, \(v\)'s new neighbors are exactly \(N_G(u)\), so its new degree is \(|N_G(u)|=\deg_G(u)\). The edges incident to \(u\) are unchanged: the only modified edges are incident to \(v\), and \(u\) and \(v\) are not adjacent. Thus \(u\)'s degree stays \(\deg_G(u)\). Every edge removed was incident to \(v\), and there were \(\deg_G(v)\) such edges. Exactly \(\deg_G(u)\) edges incident to \(v\) are present afterward. Therefore the net change in the number of edges is \(\deg_G(u)-\deg_G(v)\). For any other vertex \(x\), its only potentially changed incident edge is \(xv\). That edge is added if \(x\in N_G(u)\setminus N_G(v)\), removed if \(x\in N_G(v)\setminus N_G(u)\), and unchanged if \(x\) belongs to both neighborhoods or neither. This gives the stated degree changes. \(\square\)
In particular, cloning a lower-degree vertex onto a higher-degree one increases the edge count. Cloning in the opposite direction decreases it; cloning between vertices of equal degree leaves the edge count unchanged. The formula concerns the total edge count, not the degree of every vertex: some other degrees can go up while others go down.
Worked Example: Cloning Increases the Edge Count
Let \(G=(V,E)\), where \(V=\{u,v,a,b,c,d\}\) and \(E=\{ua,ub,uc,va,vd\}\). The vertices \(u\) and \(v\) are nonadjacent. Their neighborhoods are \(N(u)=\{a,b,c\}\) and \(N(v)=\{a,d\}\), so \(\deg(u)=3\) and \(\deg(v)=2\).
Clone \(u\) onto \(v\). The edge \(va\) is retained because \(a\) is a common neighbor. The edge \(vd\) is deleted because \(d\notin N(u)\). The edges \(vb\) and \(vc\) are added because \(b,c\in N(u)\setminus N(v)\). The new edge set is \(E'=\{ua,ub,uc,va,vb,vc\}\), which has \(6\) edges, compared with \(5\) initially.
The degree changes can be checked vertex by vertex. After cloning, \(v\) has neighbors \(a,b,c\), so its degree is \(3\), while \(u\)'s degree remains \(3\). Vertex \(a\) is still adjacent to \(u,v\), so its degree is \(2\). Each of \(b,c\) gains an edge to \(v\), changing its degree from \(1\) to \(2\). Vertex \(d\) loses its only edge, changing its degree from \(1\) to \(0\).
Check: the edge-count formula gives \(3-2=1\), and direct counting gives \(6-5=1\). The degree sums are \(3+3+2+2+2+0=12\) afterward, equal to \(2|E'|=2\cdot6=12\); initially they are \(3+2+2+1+1+1=10=2\cdot5\).
Worked Example: Cloning in the Other Direction
Use the same graph \(V=\{u,v,a,b,c,d\}\), \(E=\{ua,ub,uc,va,vd\}\), but now clone \(v\) onto \(u\). The target is \(u\), whose neighborhood is replaced by \(N(v)=\{a,d\}\).
The edge \(ua\) remains because \(a\) is a common neighbor, and \(ub,uc\) are deleted because \(b,c\notin N(v)\). The new edges incident to \(u\) are \(ua,ud\). Edges not incident to \(u\) remain \(va,vd\). Thus \(E'=\{ua,ud,va,vd\}\), which has \(4\) edges. The new degree of \(u\) is \(2\); \(v\)'s degree stays \(2\); \(a\)'s degree stays \(2\); \(b,c\) each have degree \(0\); and \(d\)'s degree increases from \(1\) to \(2\).
Check: the edge-count change is \(2-3=-1\), which agrees with \(4-5=-1\). The new degree sum is \(2+2+2+0+0+2=8=2\cdot4\), and the original degree sum is \(3+2+2+1+1+1=10=2\cdot5\).
Why Clique-Freeness Is Preserved
Proof. Let \(G'\) be obtained by cloning \(u\) onto \(v\), and suppose \(G\) has no \(K_q\). Assume for contradiction that \(G'\) contains a \(K_q\), with vertex set \(S\). If \(v\notin S\), none of the edges among vertices of \(S\) changed, so \(S\) was already a \(K_q\) in \(G\), a contradiction. If \(v\in S\), then \(u\notin S\), because \(uv\) is still absent and the vertices of a clique must be pairwise adjacent. Replace \(v\) in \(S\) by \(u\), forming \(S'=(S\setminus\{v\})\cup\{u\}\). The other \(q-1\) vertices were all adjacent to \(v\) in \(G'\), so they all belong to \(N_{G'}(v)=N_G(u)\). They are therefore all adjacent to \(u\) in \(G\). Their pairwise edges are unchanged by cloning, so they remain pairwise adjacent in \(G\). Thus \(S'\) is a \(K_q\) in \(G\), again a contradiction. Hence \(G'\) contains no \(K_q\). \(\square\)
The nonadjacency condition matters in this proof: it ensures that a clique containing the cloned vertex cannot also contain the vertex being copied. It also explains why the result applies to cliques of every fixed size \(q\ge2\): within any proposed new clique, the cloned vertex can be replaced by its source without identifying two vertices of that clique.
Worked Example: A Triangle-Free Graph Stays Triangle-Free
Let \(G=(V,E)\), where \(V=\{u,v,a,b,c\}\) and \(E=\{ua,ub,va,vc\}\). The graph is triangle-free: the only edges join \(u\) or \(v\) to \(a,b,c\), and there are no edges among \(a,b,c\), nor an edge \(uv\). Also, \(u\) and \(v\) are nonadjacent, with \(N(u)=\{a,b\}\) and \(N(v)=\{a,c\}\).
Clone \(u\) onto \(v\). Delete \(vc\), retain \(va\), and add \(vb\). The new edge set is \(E'=\{ua,ub,va,vb\}\). There are still no edges among \(a,b,c\), and \(u,v\) are still nonadjacent, so no three vertices are pairwise adjacent. The resulting graph is triangle-free.
Check: initially \(|E|=4\), and the degrees of \(u,v\) are \(2,2\), so the predicted edge change is \(2-2=0\). Directly, \(|E'|=4\), giving \(|E'|-|E|=4-4=0\). In the new graph, \(u\) and \(v\) are nonadjacent and both have neighborhood \(\{a,b\}\), as required by the definition.
The Limits of the Preservation Claim
The theorem is specifically about avoiding a fixed clique. It does not say that cloning preserves the absence of every fixed subgraph. In a clique, all vertices are adjacent to each other, so a clique containing the cloned vertex cannot contain its nonadjacent source. That replacement argument need not work for a subgraph whose vertices may be nonadjacent.
Worked Example: Cloning Can Create a Forbidden Path
A path \(P_3\) is a graph on three vertices with exactly two edges, forming a path. Let \(G=(V,E)\), where \(V=\{u,v,a\}\) and \(E=\{ua\}\). This graph contains no \(P_3\), since it has only one edge. The vertices \(u\) and \(v\) are nonadjacent, with \(N(u)=\{a\}\) and \(N(v)=\varnothing\).
Clone \(u\) onto \(v\). There are no edges to delete, and the edge \(va\) is added. The result has \(E'=\{ua,va\}\), which is a \(P_3\) with middle vertex \(a\). Thus cloning can destroy the property of being \(P_3\)-free.
Check: the initial edge count is \(1\), the new edge count is \(2\), and the formula gives \(\deg(u)-\deg(v)=1-0=1\). Indeed, \(2-1=1\). The example does not contradict the clique theorem: the new \(P_3\) is not a clique, since \(uv\) is absent.
Using Symmetrization Carefully
In an extremal problem with a forbidden clique, cloning is useful because it changes the graph while preserving clique-freeness. If the source vertex has larger degree than the target, the edge count strictly increases. This gives a reliable local comparison: the graph after cloning has exactly \(\deg(u)-\deg(v)\) more edges, and it remains free of the same fixed clique.
Keep three details separate when applying the operation:
- Specify the direction. “Clone \(u\) onto \(v\)” means replace \(v\)'s neighborhood by \(N(u)\), not the reverse.
- Check nonadjacency. The operation described here is defined for nonadjacent vertices; their nonadjacency is preserved.
- Use the correct preservation condition. Absence of \(K_q\) is preserved for each fixed \(q\ge2\); absence of an arbitrary forbidden graph is not guaranteed.
A common error is to count only the edges added while forgetting those removed. For instance, in the first worked example, cloning \(u\) onto \(v\) adds \(vb\) and \(vc\), but also removes \(vd\). Counting only the two additions would incorrectly predict a change of \(+2\). The correct change is \(+2-1=+1\), matching \(\deg(u)-\deg(v)=3-2=1\).
Cloning is a local transformation, not by itself a complete extremal proof. To use repeated transformations in a larger argument, one must also justify how the chosen pair is selected and why the sequence of changes establishes the desired global conclusion. The key facts available here are exact: the new neighborhood, the degree and edge-count changes, and preservation of the absence of a fixed clique.
Check Your Understanding
For each question, state the direction of cloning explicitly and distinguish the total edge-count change from individual degree changes.
- If \(u,v\) are nonadjacent with degrees \(5\) and \(2\), respectively, what is the edge-count change when \(u\) is cloned onto \(v\)?
- When cloning \(u\) onto \(v\), which vertices outside \(\{u,v\}\) gain one degree, and which lose one degree?
- Prove that the result of cloning two nonadjacent vertices is again a simple graph.
- Explain why the proof of clique-freeness preservation uses the fact that \(u\) and \(v\) are nonadjacent.
- Give a graph with no \(P_3\) for which cloning creates a \(P_3\), and verify the edge-count change.