I do not think it is that as you can get at least $2^n-n-1$ with induction.

sami1618 wrote: I do not think it is that as you can get at least $2^n-n-1$ with induction. I think you mean $2^{n-1}-n$. The maximal number for $n=3$, $4$ is $1$, $4$ each. It's easy to prove it by showing we can make star graph size $2^{n-1}$ from $K_n$ using induction.

Answer: $2^{n-1}-n$ Let's define the "size" of a graph as the number of complete subgraphs of it with at least 2 vertices. In the beginning, the size of $G=K_n$ is $2^n-n-1$. Claim. The size of the graph decreases by exactly 1 after every operation. Proof. Say the operation is applied to the vertices $a$ and $b$. Let's assume their common neighbors are $c_1,c_2,\cdots,c_m$. Let $d$ be the newly added vertex. For any subset $C$ of $\{c_1,c_2,\cdots,c_m\}$, except for the empty set, if $\{a,b\}\cup C$ is the vertices of a complete graph, then this complete graph breaks, and the complete graph with vertices $C\cup\{d\}$ is formed. In the case when $C=\varnothing$, since we do not count single points as complete subgraphs, $\{a,b\}$ breaks, but no other complete subgraph is formed corresponding to this. Therefore, the number of complete subgraphs decreases by one. Claim. Graph remains connected after an operation. Proof. To be able to perform an operation to vertices $a$ and $b$, they need to have an at least one common neighbor, say $c$. The path $a-c-b$ makes up for the deficiency of $a-b$. After $x$ operations, we reach a graph with $n+x$ vertices with "size" $2^n-n-1-x$. A connected graph with $n+x$ vertices has at least $n+x-1$ edges (when it is a tree). All edges are complete subgraphs with 2 vertices, therefore, $2^n-n-1-x\geq n+x-1$. This means $x\leq 2^{n-1}-n$. Now, it remains to give a procedure with this many operations. In the described procedure, all leaf vertices are ignored since they do not contribute anything. Denote by $\boxed{n\rightarrow n-1}$ the procedure for reaching $K_{n-1}$ from $K_n$. We will show that we can do the procedure $\boxed{n\rightarrow n-1}$ in $2^{n-2}-1=(2^{n-1}-n)-(2^{n-2}-(n-1))$ operations and since $\boxed{3\rightarrow 2}$ takes 1 operation, induction will do the rest of the work. Let's assume the vertices of the $K_n$ initial graph are $P_1,P_2,\cdots, P_n$. We will perform the operation to edges $P_1P_2,P_1P_3,P_1P_4,\cdots,P_1P_n$ respectively, and after removing each of those edges, we will remove the excess and finally reach $P_2P_3\cdots P_n$, the graph $K_{n-1}$. After the operation for $P_1P_2$, we get a $K_{n-1}$ with vertices $P_3P_4P_5\cdots P_{n+1}$ where $P_{n+1}$ is the newly added vertex. We can get rid of $P_{n+1}$ with the procedure $\boxed{n-1\rightarrow n-2}$. Similarly, after the operation for $P_1P_3$, we get a $K_{n-2}$ including the newly added vertex and again with the procedure $\boxed{n-2\rightarrow n-3}$, we get rid of it. Therefore, \begin{align*} \boxed{n\rightarrow n-1}&=1+\boxed{n-1\rightarrow n-2}\\ &+1+\boxed{n-2\rightarrow n-3}\\ &\vdots\\ &+1+\boxed{3\rightarrow 2}\\ &+1 \end{align*} Using induction one more time, \begin{align*} \boxed{n\rightarrow n-1}&=1+(2^{n-2}-1)\\ &+1+(2^{n-3}-1)\\ &\vdots\\ &+1+(2^1-1)\\ &+1+(2^0-1) \end{align*}we get $\boxed{n\rightarrow n-1}=2^{n-1}-1$ as desired.