As **sri** rightly pointed out in the comments section of the previous post, clique insertion is just one way to extend an *r-regular* graph into a bigger *r-regular* graph. We should be able to extend the graph by inserting any *(r – 2)-regular *graph (provided the insertion is possible — refer sri’s comment). In fact, clique insertion is the minimal case: the smallest connected *(r-2)-regular* graph has *r -1* nodes.

There are interesting questions here. Can we insert any *(r – 2)-regular* graph? What is the procedure to do so? Are there some *(r – 2)-regular* graphs that cannot be inserted?

Let’s use some notations for ease of reference. Let *Ro* be the *r-regular* graph we start with, *Ri* be the *(r – 2)-regular* graph we want to insert and *Rn* be the graph resultant of the insertion.

A simple but important thing to be noted here is that, pairs of nodes that are adjacent in *Ri*, cannot be inserted in a single edge of *Ro* because that will result in an overlapping edge (we don’t allow multiedges between nodes); adjacent nodes in *Ri* have to be inserted in different edges. Even for small values of *r*, this becomes pretty complicated to visualize. I tried to insertions for small graphs, and it was possible to do. But I don’t know if we can always avoid creating a multigraph.

But then in the above discussion we have assumed *Ri* to be a connected graph. What if *Ri* is disconnected? If *Ri* is disconnected we can easily prove that there is no bound on the size of *Ri* that can be inserted. The simplest way to show this is by saying that our *Ri* has an arbitrarily large number of *(r – 2)*-cliques as disconnected components (disconnected edges, disconnected cycles, disconnected cubic graphs etc.). Now, you can either imagine this as adding an arbitrary number of cliques (like in the previous post) or as adding one large disconnected graph.

Of course, cliques are just one way to insert. We can simply insert nodes and add edges between the new nodes in such a way that all the new nodes have a degree of *r*.

Note that the resulting graph *Rn* is, of course, a connected graph.

***

Now, since we are talking about p2p networks, what is more important is the *minimum* number of nodes and edges that we need to add when nodes join or leave. Or more generally, the minimum change in topology that is required. When a new node comes in, let’s say we need to accommodate it without disrupting symmetry; so we may need to add dummy nodes and edges. The thing is – in a p2p network, most of the time, *unrelated* nodes join or leave *unrelated* parts of the network. So, essentially, we are dealing with disconnected components.