Say one has a complete graph with 1 giant clique. As we delete an edge from it at a time, the number of maximal cliques might increase or at least, the size of the maximal clique has to decrease by size one (because of the removed edge).
I was wondering, how this process affect two things:
1) the number of maximal cliques (which I will take to define, the number of cliques with maximum size in the graph)
2) the size of the maximal cliques themselves.
I drew a few examples and it seems that as we delete edge, the number of maximal cliques doubles and the size of the cliques decreases by one. Also, this only seems to happen when we do not delete edges where an edge has already been deleted (from the same node). So we try to delete edges from a new node each time basically.
I was wondering if anyone knew if this was a true fact and if it was, if they had a proof for it. I am relatively sure its true (that the number of max cliques doubles and their size decreases by one) but have been unable to find a proof of this claim.
Anyone know a proof of this? Or an intuition or something? It seemed that maybe it could be done by induction? Not sure.