If this is correct, then on my first official USAMO I solved problem 6. WOW The answer is $f(4k-2)=6k-5, f(4k-1)=6k-3, f(4k)=6k-2$ and $f(4k+1)=6k$. Note the operation basically turns a $C_4$ into a $K_4$. We consider an alternate process that correspond to cliques of (at least 4) vertices merging into a single vertex as edges are being added. Have each singled-out vertex correspond to a blue island and each clique red. Call an edge in the island graph (map) a bridge. Note multi-edges are allowed. In the end there is one red island, and we count the number of deleted bridges, which is the number of edges in the original user graph. In the original graph, there are no cliques of size 4 because if $ABCD$ were a clique of size 4 we can remove edges $AC,BD$, so we start with $4k-2$ blue islands. In the island graph, let $g(u,v)$ denote the number of bridges between $u$ and $v$. When (blue/red) islands $u_1,\cdots,u_k$ are merged into one red island $H$, $g(v,H)=\sum\limits_{j=1}^k g(v,u_j)$ We need to analyze how a red island behaves with another island. The operation in the user graph involves an existing clique merging with another vertex or clique. Claim [Behavior of Clique to another vertex/clique] In the original user graph, either two cliques (at least one with size $\ge 4$) can be fully merged into a new clique if and only if the number of vertices shared and size of maximal matching is in total at least 2, and no edges can be added otherwise to increase the maximal matching of the crossing edges between the two vertices. Proof: We go back to the original (user) graph. Call the cliques $\{s_1,\cdots,s_k\}$ and $\{t_1,\cdots,t_k\}$. If they share one edge, call $s_it_j$, then only focusing on these cliques, $s_i, t_k$ for any $k\ne i$ only has $s_it_j$ as a common neighbour. We can check that this works. If they only share one vertex, similar thing. If they have two crossing edges that are not both incident to the same vertex, call $s_1t_2$ and $s_3t_4$, then we can connect $s_1$ to any $t_j$ with $s_1,t_2,t_j,t_4$. Therefore, $s_1,s_3,t_2,t_4$ are adjacent to all vertices in the cliques. If they share one vertex and have one crossing edge, call the shared vertex $v$ and the crossing edge $s_1t_2$. Then $s_j$ is adjacent to $t_2$ by $s_js_1t_2v$, and similarly $s_1$ is also adjacent to all the vertices in both cliques. Now, $s_is_1t_jv$ connects all $s_it_j$. If they share two vertices, call $u,v$ then all $s_i,t_j$ are connected via $s_i,u,t_j,v$. If they share no vertices and all crossing edges (take $s_1t_1,s_1t_2$) are incident to one vertex, call $s_1$, then $s_1$ is connected to all $t_j$ via $s_1t_1t_jt_2$. However, after that there is no edge that can be constructed, as $s_1$ is essentially the shared vertex between the two cliques. \newpage Therefore, in the modified graph, we join a red vertex $R$ and a blue vertex $B$ by $x$ edges where $x$ is the number of vertices adjacent to $B$ in the clique $R$ represents in the original graph. We now consider how a 4-cycle is merged. Call the 4-cycle $uvwx.$ In this process, all edges are deleted, and every edge deleted corresponds to an edge in the original graph in some way. Case 1: three vertices $u,v,w$ in the 4-cycle $uvwx$ are from the same red island $R$. In this case, $x$'s island joins the island, and we lose at least 2 bridges, namely $ux$ and $wx.$ In short, we get rid of a blue or red island for 2 bridges. Case 2: two vertices $u,v$ are in red island $R_1$ and the other two $w,x$ are in red island $R_2$. After $uvwx$ becomes a clique, it has 2 shared vertices with $R_1,R_2$ so $R_1,R_2$ are merged. At least 2 edges/bridges between $u,v$ and $w,x$ are lost. Case 3: two vertices $u,v$ are in red island $R$ and $w,x$ are in distinct islands, call $C_1,C_2$ which may be blue or red. First, note $w,x$ joins $R_1$. We will treat this shared vertex as an edge between $C_i$ and $R$ for two red vertices. i.e. the original/user vertex belongs in both red vertices and an edge represents this user vertex which is valid by our claim. If both $C_i$ are blue then we lose 3 crossing edges and 2 blue vertices. If both $C_i$ are red then nothing happens. If one is blue one is red, we lose 2 edges and a blue vertex. (alternatively, we lose 4 edges, a blue and a red) Case 4: All four vertices in different vertices in the alternate graph. Let $R$ be the red island formed by these four vertices. Let $U,V,W,X$ be the (red/blue) islands $u,v,w,x$ are in, respectively. Consider edges between $UR, VR, WR, XR$ in place of $uv, vw, wx, xu$ If $U$ is blue, $U$ gets deleted, an edge $UR$ gets deleted. If $U$ is red, $U$ and $R$ stays the way it is (because of how we handle shared vertices between red islands). Do the same to $V,W$ and $X$. Therefore for some $t\in \{0,1,2,3,4\}$ this operation gets rid of $t$ blue island and $t$ edges, and adds a red island $R$. Now, if $f(b,r)$ is the minimum number of edges I need to merge $b$ blues and $r$ reds into one red vertex, note $f(b,r)\ge \min\{ f(b-j,r+1)+j (j\in \{1,2,3,4\}), f(b-1,r)+2, f(b,r-1)+2\}$ Easy induction implies the bound is optimal if I prove that $f(2,0)=1, f(3,0)=3, f(4,0)=4$ and $f(5,0)=6$. Construction for $4k-2$: consider $k-1$ $C_4$'s, call $v_{4j+1}v_{4j+2}v_{4j+3}v_{4j+4}$ where $j=0,\cdots,k-2$. Add an edge between $v_{4j+1}v_{4j+5}$ and $v_{4j+2}v_{4j+6}$ for $j=0,\cdots, k-3$. Since these cliques share two crossing edges not incident to the same vertex, they can be merged into cliques. In short, we get a $K_{4k-4}$. Now add three edges, $v_{4k-3}v_{4k-2}, v_{4k-2}v_1, v_{4k-3}v_2$. We have a $K_4$ and $K_{4k-4}$ with 2 vertices in common, which works.

＠AwesomeYRY can we please be friends on Mathbook?

@kevinmathz I sent you a mathbook friend request, but you haven't accepted it. We have two mutual friends too!

Help I just created a Mathbook account but I have no friends currently so I can't make any new ones Who designed this stupid system

@Eyed I accepted your Mathbook friend request <3 Unfortunately, we can't get qrohn in our friend group because he only has one other friend... sadge

My problem!

This work? Replace $2022$ with $n.$ For all even positive $n$ in general, the answer is $\boxed{\frac{3}{2}n - 2}.$ We prove by induction with base case trivial. We will take any valid graph $G$, collapse any $4$ cycle $C$ in $G$ into a edge between $2$ nodes, and reassign the edges going to $C$ and maintain a valid graph. This reduces the number of nodes by $4-2=2$ and reduces the number of edges by at least $4-1 = 3.$ To get a transformed graph $G*,$ we keep all nodes in $G$ not in $C,$ delete all nodes in $C$, and add $2$ nodes $P,Q$ joined by an edge. Any node with at least $2$ edges going to the cycle initially, link it to both $P$ and $Q.$ We will assign nodes that had exactly $1$ edge going to the cycle in $G$, to go to either $P$ or $Q$ in $G*$ (to be decided later). We follow the moves on $G$ that turn it complete, and mirror them on $G*$ until we turn it complete. As we do this, we assign the nodes with exactly $1$ edge going to $C$ in a way that allows us to continue mirroring the moves. At a point in time, we call a node undecided if it joins to neither $P$ or $Q,$ problematic if it joins to only one of $P$ and $Q,$ and safe if it joins to both $P$ and $Q.$ We maintain the property that if a node is problematic in $G*,$ then it is joined to at most one vertex of $C$ back in $G,$ and if a node is undecided in $G*,$ then it is not joined to any vertex of $C$ back in $G.$ Case 1: We move on a cycle in $G$ sharing no vertices with $C.$ Just move on the same cycle in $G*.$ Case 2: We move on a cycle (call this $W-X-Y-Z$) in $G$ sharing one vertex ($W$) with $C.$ If before the move, both of $X$ and $Z$ are problematic and $Y$ is not joined to any vertex of $C$ besides $W,$ make sure $X,Y,Z$ were all pointing to the same vertex (possibly no vertex in the case of $Y$) $\in \{P,Q \}$ before the move (don't fix the vertex). Then mirror the move on $G*,$ and $Y$'s forced to join to the vertex of $X,Z$ after. Make this the only way we can force vertices to join to the same vertex $\in \{P,Q \}$ at a point in time. So vertices can only be forced to join to the same vertex $\in \{P,Q \}$ at a point in time if they all join to one vertex in $C$ (shared across all of them) back in $G.$ Otherwise: if at least one of $X$ and $Z$ is safe, then we can lift a lot of restrictions. Mirror the move on $G*,$ then we can get $X,Y,Z$ all safe in $G*$ through a series of moves (as well as all problematic vertices forced to join to the same vertex $\in \{P,Q \}$ as one of $X,Y,$ or $Z$). Similarly, if both $X$ and $Z$ are problematic, but $Y$ is already joined to a vertex of $C$ besides $W$ before the move, then fix $Y$'s vertex $\in \{P,Q \}$ before the move as different from $X$ or $Z$'s, mirror the move, and now $Y$ is safe after the move. Then $X,Z,$ and any problematic vertices that were forced to join to the same vertex $\in \{P,Q \}$ as one of $X,Y,Z$ are now safe. Case 3: We move on a cycle (call this $W-X-Y-Z$) in $G$ sharing two vertices with $C.$ If the two vertices in $C$ are not consecutive, then the other two are both safe. Then it's easy to make the corresponding moves on $G*.$ Otherwise, assume $W,X$ are in $C.$ If $Y$ or $Z$ is safe, then we can get the other safe (as well any problematic vertices that were forced to join to the same vertex $\in \{P,Q \}$ as one of $Y,Z$). If $Y$ and $Z$ are both not safe, then they must be joined to different vertices of $C$ before the move. So make sure $Y$ (and all problematic vertices forced to join to the same vertex $\in \{P,Q \}$ as it) and $Z$ (and all problematic vertices forced to join to the same vertex $\in \{P,Q \}$ as it) were joined to different vertices. Then mirror the move. But now, $Y,Z$ are safe and furthermore, we can get any problematic vertices forced to join to the same vertex $\in \{P,Q \}$ as one of $Y,Z$ as safe too. Case 4: We move on a cycle (call this $W-X-Y-Z$) in $G$ sharing three vertices with $C.$ Just do nothing. At any time, a problematic node $N$ is only forced to be assigned to the same vertex $\in \{P,Q \}$ as some problematic nodes going to the exact same single fixed node in $C$ as it. It is only forced to be assigned to a different vertex $\in \{P,Q \}$ as some problematic nodes going to some single different fixed node in $C$ (and once we force this, the node becomes safe right after and we just forget about it). Thus, a valid reassignment can be found, finishing induction. $\blacksquare$

Nice problem! I've been thinking for a long time and finally find a proof idea. My answer and ideas

Groupsolved with duk. Generalize the problem for $n$ users. Let users be vertices of a graph $G$. Two vertices are connected if and only if the users the vertices correspond to are friends. The given conditions mean that you can add edges on any $C_4$ (cycle on 4 vertices) subgraph of $G$ to create $K_4$ (complete graph on $4$ vertices). We claim the answer is $\left\lceil\frac{3n}{2}-2\right\rceil$. For even $n$, consider a $2\times\frac{n}{2}$ grid graph. For odd $n$, consider a $2\times\frac{n-1}{2}$ grid graph and the remaining vertex connected to any two vertices of the grid graph. For $n=2022$, the answer is $\boxed{3031}$. We will prove that in all graphs $G$ satisfying the given conditions, $\frac{|E(G)|-1}{|V(G)|-2}\geq\frac{3}{2}$. Start with $C_4$ and call it $S_1$ ($S_1$ will change as we build onto the graph). This contains 4 vertices and at least 4 edges so $\frac{e_1-1}{v_1-2}\geq\frac{3}{2}$ where $e_1=|E(S_1)|$ and $v_1=|V(S_1)|$ ($e_1$ and $v_1$ will change as we build onto the graph). Add edges to this $C_4$ to create $K_4$, call it $G_1$ ($G_1$ will change as we build onto the graph). In the following process, note that $e_i=|E(S_i)|$ and $v_i=|V(S_i)|$. $S_i$ is the "skeletal graph" of $G_i$, or the subgraph which arises when we remove all the added edges. Initially let $i=1$. There exists a $C_4$ with at least two vertices in $G_i$. Take any one of these $C_4$'s, call it $T$. If $T$ contains exactly $2$ vertices in $G_i$, there must exist at least $3$ new edges not in $G_i$, and two new vertices not in $G_i$. If $T$ contains exactly $3$ vertices in $G_i$, there must exist at least $2$ new edges not in $G_i$, and one new vertex not in $G_i$. Either way, you can add edges to $G_i\cup T$ to create a larger complete graph. Since $\frac{3}{2},2\geq\frac{3}{2}$, $\frac{e_i-1}{v_i-2}\geq\frac{3}{2}$ still holds. There does not exist a $C_4$ with at least two vertices in $G_i$. There exists another $C_4$, call it $S_{i+1}$ with at most one vertex among the vertices in $\bigcup_{k=1}^i G_k$. Add edges to $S_{i+1}$ to create a $K_4$, call it $G_{i+1}$. Increase the index $i$ by $1$ and go to (1), ignoring all vertices in $\bigcup_{k=1}^i G_k\setminus G_{i+1}$. Repeat the above process until we want to terminate it. Note that we can terminate the above process whenever we want, since we are constructing all graphs which satisfy the given conditions. Now, we need to add more edges between vertices in different $G_i$. In order to be able to find another $C_4$, there exists $G_i$ and $G_j$ with $i\neq j$ satisfying one of the following: There exists at least two edges, each edge incident to a vertex in $V(G_i)$ and a vertex in $V(G_j)$ when $|V(G_i)\cap V(G_j)|=0$. Let $e_p$ be the number of edges on the induced subgraph on $V(S_i\cup S_j)$, and let $v_p=|V(S_i\cup S_j)|$. Note that \begin{align*} e_p&\geq e_i+e_j+2\\ &\geq\frac{3v_i}{2}-2+\frac{3v_j}{2}-2+2\\ &=\frac{3v_p}{2}-2. \end{align*} There exists at least one edge between a vertex in $V(G_i)\setminus V(G_j)$ and a vertex in $V(G_j)\setminus V(G_i)$ when $|V(G_i)\cap V(G_j)|=1$. Let $e_p$ be the number of edges in the induced subgraph on $V(S_i\cup S_j)$, and let $v_p=|V(S_i\cup S_j)|$. Note that \begin{align*} e_p&\geq e_i+e_j+1\\ &\geq\frac{3v_i}{2}-2+\frac{3v_j}{2}-2+1\\ &\geq\frac{3v_p}{2}-2 \end{align*}where the last equality holds since $v_p=v_i+v_j-1$. Now add edges to $G_i\cup G_j$ to create a larger complete graph $P$ ($P$ will change as we add more edges). Repeat the above process, replacing $G_i$ and $G_j$ with $P$. Eventually we will arrive at a large complete subgraph $P$. The "skeletal graph" of $P$, call it $G$, satisfies the given conditions, and has $|E(G)|\geq\frac{3|V(G)|}{2}-2$. $\square$

My original sol was incomprehensible so I wrote a new comprehensible (hopefully) sol. Generalize the problem for $n$ users. Let users be vertices of a graph $G$. Two vertices are connected if and only if the users the vertices correspond to are friends. The operation turns a $C_4$ into a $K_4$. We claim the answer is $\left\lceil\frac{3n}{2}-2\right\rceil$. For even $n$, consider a $2\times\frac{n}{2}$ grid graph. For odd $n$, consider a $2\times\frac{n-1}{2}$ grid graph and the remaining vertex connected to any two vertices of the grid graph. For $n=2022$, the answer is $\boxed{3031}$. We do an algorithm to construct all possible graphs $G$ satisfying the given conditions, and show that $|E(G)|\geq\frac{3}{2}|V(G)|-2$ at the end. Start with a graph $G_1$ containing $4$ vertices and a $C_4$. Let $S_1$ be the set of the vertices of $G$. Define a function $E:\mathcal{P}(V(G))\longrightarrow\mathcal{P}(E(G))$ with \[E(S)=\{vu\in E(G)\mid v,u\in S\}\]where $\mathcal{P}(S)$ is the power set of $S$. $G_1$ contains $4$ vertices and at least $4$ edges so $|E(S_1)|\geq\frac{3}{2}|S_1|-2$. In the algorithm let $G_i$ be the induced subgraph on $S_i$. Initially let $i=1$, and repeat the following steps until we wish to terminate it. We can choose to go to either (1) or (2). (1) Let subgraph $T$ with $4$ vertices contain a $C_4$ with at least two vertices in $S_i$. If $T$ contains exactly $2$ vertices in $S_i$, $|V(T)\setminus S_i|=2$ and $|E(T)\setminus E(S_i)|\geq 3$. If $T$ contains exactly $3$ vertices in $S_i$, $|V(T)\setminus S_i|=1$ and $|E(T)\setminus E(S_i)|=2$. Either way, put the vertices of $T$ into $S_i$. Since $\frac{3}{2},2\geq\frac{3}{2}$, $|E(S_i)|\geq\frac{3}{2}|S_i|-2$ still holds. We can choose to go to either (1) or (2). (2) Let subgraph $G_{i+1}$ contain $4$ vertices and a $C_4$, satisfying $|V(G_{i+1})\cup V(G_i)|\leq 1$. Let $S_{i+1}$ be the set of vertices of $G_{i+1}$. Increase the index $i$ by $1$ and go to (1), ignoring all vertices in $\bigcup_{k=1}^i S_k\setminus S_{i+1}$. It is possible to turn $G_i$ into $K_{|S_i|}$ for all $i\geq 1$. Note that there exists no $S_i$ and $S_j$ with $i\neq j$ satisfying $|S_i\cap S_j|\geq 2$. Define an $\textit{intersection graph}$ $H$ with vertex set $\{S_1,S_2,\ldots\}$, where two vertices $S_i$ and $S_j$ are connected if and only if $|S_i\cap S_j|=1$. Define a $\textit{good}$ cycle to be a cycle for which any three vertices $X,Y,Z$ in the cycle satisfies $X\cap Y\cap Z=\emptyset$. We will retract all good triangles and all good $C_4$'s of $H$ to get a graph $H'$ (retracting a cycle is replacing the cycle with a vertex connected to all vertices adjacent to the cycle). When a good triangle $ABC$ is retracted we let the new vertex be $A\cup B\cup C$. Note that \[|E(A\cup B\cup C)|=|E(A)|+|E(B)|+|E(C)|>\frac{3}{2}|A\cup B\cup C|-2.\]When a good $C_4$ $ABCD$ is retracted we let the new vertex be $A\cup B\cup C\cup D$. Note that \[|E(A\cup B\cup C\cup D)|=|E(A)|+|E(B)|+|E(C)+|E(D)|\geq\frac{3}{2}|A\cup B\cup C\cup D|-2.\]The vertices of $H'$ are $S_1',\ldots,S_r'$. It is possible to turn the induced subgraph on $S_i'$ into $K_{|S_i'|}$ for all $1\leq i\leq r$. Note that \[\forall i\in [r]:|E(S_i')|\geq\frac{3}{2}|S_i'|-2.\] Now we need to add edges between different $S_i'$. There exists $S_i'$ and $S_j'$ with $i\neq j$ such that we must add edges in the following manner: If $|S_i'\cap S_j'|=0$, we add at least two nonadjacent edges between $S_i'$ and $S_j'$. Note that \begin{align*} |E(S_i'\cup S_j')|&\geq |E(S_i')|+|E(S_j')|+2\\ &=\frac{3}{2}|S_i'\cup S_j'|-2. \end{align*} If $|S_i'\cap S_j'|=1$, we add at least one edge between $S_i'$ and $S_j'$. Note that \begin{align*} |E(S_i'\cup S_j')|&\geq |E(S_i')|+|E(S_j')|+1\\ &>\frac{3}{2}|S_i'\cup S_j'|-2. \end{align*} Now it is possible to turn the induced subgraph on $S_i'\cup S_j'$ into $K_{|S_i'\cup S_j'|}$. Replace $S_i'$ and $S_j'$ with $S_i'\cup S_j'$. Retract all good $C_4$'s in the intersection graph for these new sets. Repeat the above steps. Eventually we arrive at \begin{align*} |E(G)|&=|E(S_1'\cup\cdots S_r')|\\ &\geq\frac{3}{2}|S_1'\cup\cdots S_r'|-2=\frac{3}{2}|V(G)|-2 \end{align*}so we are done. $\square$

I am posting an edited version of the solution that was eventually published in the Math Magazine by Bela Bajnok: With $2022$ replaced by $n$, the answer is $\left\lceil \frac 32 n \right\rceil - 2$. Terminology Standard graph theory terms: starting from a graph $G$ on $n$ vertices, we're allowed to take any $C_4$ in the graph and complete it to a $K_4$. The problem asks the minimum number of edges needed so that this operation lets us transform $G$ to $K_n$. Construction For even $n$, start with an edge $ab$, and then create $n/2-1$ copies of $C_4$ that use $ab$ as an edge, as shown below for $n=14$ (six copies of $C_4$). [asy][asy] dotfactor *= 2; pair A = (-1,0); pair B = (1,0); pair X, Y; for (int i=1; i<=6; ++i) { X = (-(i+3)/10, i/7 + 0.4); Y = ((i+3)/10, i/7 + 0.4); dot(X, grey); dot(Y, grey); draw(A--X--Y--B, grey); } draw(A--B, red+2); dot("$a$", A, 2*dir(-90), red); dot("$b$", B, 2*dir(-90), red); [/asy][/asy] This can be completed into $K_n$ by first completing the $n/2-1$ $C_4$'s into $K_4$, then connecting red vertices to every grey vertex, and then finishing up. The construction for odd $n$ is the same except with one extra vertex $c$ which is connected to both $a$ and $b$. Bound Notice that additional operations or connections can never hurt. So we will describe a specific algorithm that performs operations on the graph until no more operations are possible. This means that if this algorithm terminates with anything other $G = K_n$, the graph was never completable to $K_n$ to begin with. The algorithm uses the following data: it keeps a list $\mathcal C$ of cliques of $G$, and a labeling $\mathcal{L} \colon E(G) \to \mathcal C$ which assigns to every edge one of the cliques that contains it. Initially, $\mathcal C$ consists of one $K_2$ for every edge of $G$, and each edge is labeled in the obvious way. At each step, the algorithm arbitrarily takes any $C_4 = abcd$ whose four edges $ab$, $bc$, $cd$, $da$ do not all have the same label. Consider these labels that appear (at least two, and up to four), and let $V$ be the union of all vertices in any of these 2-4 cliques. Do the following graph operations: connect $ac$ and $bd$, then connect every vertex in $V - \{a,b,c,d\}$ to each of $\{a,b,c,d\}$. Finally, complete this to a clique on $V$. Update $\mathcal C$ by merging these 2-4 cliques into a single clique $K_V$. Update $\mathcal{L}$ by replacing every edge that was labeled with one of these 2-4 cliques with the label $K_V$. Also, update every newly created edge to have label $K_V$. However, if there were existing edges not labeled with one of the 2-4 cliques, then we do not update these! Stop once every $C_4$ has only one label appearing among its edges. When this occurs, no operations are possible at all on the graph. A few steps of the process are illustrated below for a graph on six vertices with nine initial edges. There are initially nine $K_2$'s labeled A, B, \dots, I. Original edges are always bolder than added edges. The relabeled edges in each step are highlighted in color. Notice how we need an entirely separate operation to get G to become L, even though no new edges are drawn in the graph. [diagram below because minipage's don't seem to work on this website] As we remarked, if the graph is going to be completable to $K_n$ at all, then this algorithm must terminate with $\mathcal C = \{K_n\}$. We will use this to prove our bound. We proceed by induction in the following way. For a clique $K$, let $\theta(K)$ denote the number of edges of the original graph $G$ which are labeled by $K$ (this does not include new edges added by the algorithm); hence the problem amounts to estimating how small $\theta(K_n)$ can be. We are trying to prove: Claim: At any point in the operation, if $K$ is a clique in the cover $\mathcal C$, then \[ \theta(K) \ge \frac{3 |K|}{2} - 2. \]where $|K|$ is the number of vertices in $K$. Proof. By induction on the time step of the algorithm. The base case is clear, because then $K$ is just a single edge of $G$, so $\theta(K) = 1$ and $|K| = 2$. The inductive step is annoying casework based on the how the merge occurred. Let $C_4 = abcd$ be the $4$-cycle operated on. In general, the $\theta$ value of a newly created $K$ is exactly the sum of the $\theta$ values of the merged cliques, by definition. Meanwhile, $|K|$ is the number of vertices in the union of the merged cliques; so it's the sum of the sizes of these cliques minus some error due to overcounting of vertices appearing more than once. To be explicit: Suppose we merged four cliques $W$, $X$, $Y$, $Z$. By definition, \begin{align*} \theta(K) &= \theta(W)+\theta(X)+\theta(Y)+\theta(Z) \\ &\ge \frac32(|W|+|X|+|Y|+|Z|) - 8 = \frac32(|W|+|X|+|Y|+|Z|-4) - 2. \end{align*}On the other hand $|K| \le |W|+|X|+|Y|+|Z|-4$; the $-4$ term comes from each of $\{a,b,c,d\}$ being in two (or more) of $\{W,X,Y,Z\}$. So this case is OK. Suppose we merged three cliques $X$, $Y$, $Z$. By definition, \begin{align*} \theta(K) &= \theta(X)+\theta(Y)+\theta(Z) \\ &\ge \frac32(|X|+|Y|+|Z|) - 6 = \frac32\left(|X|+|Y|+|Z|-\frac83\right) - 2. \end{align*}On the other hand, $|K| \le |X|+|Y|+|Z| - 3$, since at least $3$ of $\{a,b,c,d\}$ are repeated among $X$, $Y$, $Z$. Note in this case the desired inequality is actually strict. Suppose we merged two cliques $Y$, $Z$. By definition, \begin{align*} \theta(K) &= \theta(Y)+\theta(Z) \\ &\ge \frac32(|Y|+|Z|) - 4 = \frac32\left(|Y|+|Z|-\frac43\right) - 2. \end{align*}On the other hand, $|K| \le |Y|+|Z| - 2$, since at least $2$ of $\{a,b,c,d\}$ are repeated among $Y$, $Z$. Note in this case the desired inequality is actually strict. $\blacksquare$ Remark: Several subtle variations of this method do not seem to work. It does not seem possible to require the cliques in $\mathcal C$ to be disjoint, which is why it's necessary to introduce a label function $\mathcal L$ as well. It seems you do have to label the newly created edges, even though they do not count towards any $\theta$ value. Otherwise the termination of the algorithm doesn't tell you enough. Despite this, relabeling existing edges, like G in step 1 of the example, 1 seems to cause a lot of issues. The induction becomes convoluted if $\theta(K)$ is not exactly the sum of $\theta$-values of the subparts, while the disappearance of an edge from a clique will also break induction.

This seems too easy, so this could be a fakesolve, but here goes (also I did not get this completely on my own; I saw the answer for general even $n$ is $\frac32 n-2$, so I still have never solved a graph theory problem with no hints, oh well)... First, for upper bound, make a cycle $(P_1P_2P_3\dots P_n)$ and then connect $P_i$ and $P_{n-i}$. Now, for lower bound, use induction; $n=2$ and $n=4$ are clear. Now, suppose we have a graph that has the minimum number of edges. We must then be able to find distinct vertices $X$ and $Y$ such that we may then find distinct vertices $W$ and $Z$ such that $W$ and $Z$ are common neighbors of $X$ and $Y$. Now, we claim that we may set $X\equiv W$ and $Y\equiv Z$ and divide out by the resulting equivalence relation; in particular, we end up decreasing the amount of edges by at least $3$ (because we must remove $XW$ and $YZ$ and set $XZ\equiv YW$), and decreasing the number of vertices by exactly $2$. Now, it suffices then to check that the resulting graph will satisfy the condition from the problem. In particular, we know that any move will involve adding edge $P_1P_3$ when we already had edges in the cycle $(P_1P_2P_3P_4)$, and we claim almost the same sequence of moves that works for the original graph will work for the "quotient" graph. We drop any move involving adding an edge $P_1P_3$ where $P_1\equiv P_3$, as it will not be possible nor needed. Also, if $P_1$ or $P_3$, say $P_1$, is equivalent to one of the common neighbors, say $P_2$, then we already have an edge equivalent to $P_1P_3$ (namely $P_2P_3$), so we may also safely drop each of these moves. Finally, if $P_2\equiv P_4$, then without loss of generality let $P_2=X$ and $P_4=W$; we would have in the original graph $P_1$ and $P_3$ such that all edges of cycle $(P_1XP_2W)$ are contained, but then we could safely remove edge $XW$, contradicting minimality of the original graph, hence this case never happens. The only other steps are those in which $P_1$, $P_2$, $P_3$, and $P_4$ are pairwise inequivalent, which we may keep. Thus, we will have a sequence of steps in the "quotient" graph that completes it (and in particular, the image of all edges between inequivalent points that were present in the corresponding step of the original graph will be present in the corresponding step of the quotient graph, so all of these steps will work). Thus done; the answer of the problem is then $\frac{3}{2}(2022)-2=3031$ (I think we can handle the odd case in the same way using similar induction and a similar construction)

Could someone provide some insight into proving that the bound is tight?

Khalifakhalifa wrote: Could someone provide some insight into proving that the bound is tight? Any replies?

Not sure if anyone will read this at this point, but I do have a proof: Let $G$ be the original graph on $n = 2022$ vertices. The goal is to show that $G$ has at least $3031$ edges. $\textbf{claim}$ Every time a new friendship happens, four vertices are involved: the two becoming friends, and the two mutual friends (who also may as well become friends at that point). I'll call any set of four vertices a 4-set, and at some point if the a 4-set contains a $C_4$, then we can add the two edges to make a $K_4$: I call this "activating" the 4-set. Let $A_1, A_2, A_3, ...$ be the 4-sets that are activated (in that order) to create a complete graph. I call this process of adding edges by activating 4-sets the "original process". However, we are actually going to do something completely different. Define $G'$ by adding a "ghost vertex" $v_0$ to $G$, and adding two edges from $v_0$ to $A_1$. Here is the big claim: $\textbf{claim}$ The edges of $G'$ can be written as the union of 3 trees such that every edge of $G'$ is used by at most two of the trees. $G'$ has $n+1$ vertices, and hence each tree has $n$ edges for a total count of $3n$ edges. Since each edge of $G'$ is at most double counted, this means $G'$ has at least $\lceil \frac{3n}{2} \rceil$ edges, so $G$ has at least $\lceil \frac{3n}{2} \rceil - 2$ edges (this equals $3031$). $\textbf{Proof of Claim 2}$ We will build up the three trees one 4-set at a time. We will try to follow the original process, but note that while in the original process edges are added each time a 4-set is activated, in building up these trees we are not adding edges (at least we are trying not to: see below about ghost edges). Instead we are just using the edges of $G'$ as they are to create three trees. To start with, let's make the assumption that each $A_j$ has at least two vertices in common with previous $A_i$'s (we will handle the case where this assumption doesn't hold later). It is easy enough to create three trees spanning $v_0 + A_1$ using the edges of $G'$ where every edge is used twice As we add $A_j$, there are three cases: 1. If $A_j$ has 4 vertices in common with the previous $A_i$, then there is nothing to do, as $A_j$ is already connected to all three trees. 2. If $A_j$ has 3 vertices in common with the previous $A_i$, then the new vertex is connected by two edges and we can extend the three trees. 3. If $A_j$ has 2 vertices in common with previous $A_i$, then the two new vertices must be connected by a path of length 3, and again we can extend the three trees (see diagram). Thus, eventually the three trees cover the entire diagram. Okay, so what if the assumption about $A_j$ having two vertices in common with the $A_i$'s doesn't hold? This is annoying to do, but we will need to reorder the 4-sets $A_1, A_2, A_3, ...$. Let's relabel them as $A_1 = B_1, B_2, B_3, ...$, where each $B_j$ shares two vertices in common with previous 4-sets. We know we can do this since, if there wasn't such a reordering, the original process wouldn't work. Now, since we are not following the original order, $B_j$ may be activated earlier than normal. As a result, we may not actually have the edges we need to extend the three trees for $B_j$, because the edges needed would have been "added later" while activating some $B_k$ (under the assumptions of the original problem ... under our new process of creating trees we aren't even adding edges anymore). What we will do in this situation is add one or more "ghost edges from the future" so we can successfully extend the three trees. In the original order, $B_k$ was before $B_j$ (and in the original process the ghost edge was created by activating $B_k$). For us, we will use $B_k$ as an opportunity to delete the ghost edge and connect those two points in a different way. We can do this since $B_k$ has a $C_4$ not counting the ghost edge, so we can then extend the three trees while at the same time deleting the ghost edge (see diagram). Now I say that $B_k$ has four edges not counting the ghost edge, but this might not quite be true: it is possible an edge is actually not there for two reasons: 1. It is possible $B_k$ also needs a ghost edge added. This is fine, just add the edge, we will delete it later. 2. Remember we are also not adding the edges that were added during the original process. However, in this case both sides of the edge are already connected to all three trees, so the edge isn't needed. Okay, and that covers it -- we eventually extend the three trees to cover the whole graph.