It was the first thing I tried. But, unfortunately it's not the way. Abhinandan18 wrote: ... Thus, by virtue of $A,B,D$ in $X$, the edges $AD$ and $BD$ exist, and similarly the edges $AC$ and $BC$ exist, but $CD$ does not exist. However, this contradicts the given condition in the problem... It would have contradicted the given condition if $A$ and $B$ were not connected. But they are. The condition in the statement reads: ryan17 wrote: ...there is no quartet of different guests $a, b, c, d$ such that in pairs $\lbrace a, b \rbrace, \lbrace b, c \rbrace, \lbrace c, d \rbrace, \lbrace d, a \rbrace$ guests know each other but in pairs $\lbrace a, c \rbrace, \lbrace b, d \rbrace$ guests don't know each other. ... It just says there doesn't exist a minimal cycle of length $4$ and asks for some upper bound for the number of maximal cliques.

Here is a solution with Muriatic . First of all, we use the obvious graph theoretical interpretation of the problem, which is as follows. For a graph $G$ with $n$ vertices, given that whenever vertices $a, b$ are not connected, the subgraph of $G$ spanned by $N(a) \cap N(b)$ is a clique, show that $G$ has at most $\binom{n}{2}$ subgraphs which are maximal cliques. Here, $N(v)$ denotes the set of neighbors of vertex $v$, and a maximal clique is one which is not contained in any other clique. We will prove this result by induction on $n$, with the base case $n =1$ being trivial. Suppose that our hypothesis holds when $n = k.$ When $n = k+1$, select an arbitrary vertex $v$. Call a maximal clique on $G / \{v\}$ a house. From the induction hypothesis, we know that there are at most $\binom{k}{2}$ houses. We can now classify all maximal cliques of $G$ into three categories. Indeed, any maximal clique $C \subseteq G$ is either: 1) A house 2) A house, plus $\{v\}$ 3) $\{v\}$ plus a non-maximal clique of $G \ \{v\}.$ Let $S_1, S_2, S_3$ be the set of maximal cliques of $G$ which fall into category 1), category 2), and category 3) respectively. It's clear that $S_1, S_2, S_3$ are pairwise disjoint sets. Lemma 1. $|S_1| + |S_2| \le \binom{k}{2}$ Proof. We consider the following mapping from $S_1 \cup S_2$ to the set $H$ of houses. For a maximal clique in $S_1$, we simply map it to itself. For a maximal clique in $S_2$, we map it to the house which results from removing $\{v\}$. We claim that this map is injective, from which the lemma follows by the inductive hypothesis. Indeed, if there was a house $h \in H$ which was mapped to twice, then we would know that $h, h \cup \{v\}$ are both maximal cliques of $G$. However, this is clearly absurd, since then $h$ is not a maximal clique of $G$ (contained by $h \cup \{v\}$). $\blacksquare$ Lemma 2. $|S_3| \le k.$ Proof. We will prove this lemma in a similar manner. Let $A \cup \{v\}$ be a clique in $S_3$, where $A$ is some non-maximal clique of $G / \{v\}$ (possibly empty). Let $B$ be any house which contains $A$ (this exists because $A$ is a non-maximal clique of $G / \{v\}$), and let $w \in B / A$ be a vertex. Observe that $v, w$ are not connected because otherwise $A \cup \{v, w\}$ would be a clique containing $A \cup \{v\}.$ Now, since $\{v\} \cup (N(v) \cap N(w))$ is a clique, and $A \subseteq N(v) \cap N(w)$, we must actually have $A = N(v) \cap N(w)$ and $\{v\} \cup A = \{v\} \cup (N(v) \cap N(w)).$ In view of these previous results, we will now consider the mapping which maps a maximal clique $\{v\} \cup A \in S_3$ to $w$. If we showed that this mapping was injective, the lemma would clearly be proven, since there are only $k$ vertices in $G / \{v\}.$ Indeed, observe that from the results above, every vertex $w \in G / \{v\}$ could only be mapped to by $\{v\} \cup (N(v) \cap N(w))$. The lemma is proven. $\blacksquare$ From the two lemmas above, the induction is complete, and hence so is the problem. $\square$ Remark. It's clear that this bound is not sharp. For instance, the same proof in Lemma 2 above can be used to show that $|S_3| \le \min (2^d, n-d),$ where $d = deg (v).$ This can be used to imply a bound which is $\binom{n}{2} - O(n \log n).$

The estimate can be sharpen. Let $G$ be the corresponding graph, and $\overline{G}$ its complement. Then there are at most $|E(\overline{G})|+1$ maximal cliques (ingroups). In other words, the number of maximal cliques is at most the number of non edges in $G$ plus one. It indeed sharpens the estimate in the OP, since the only case it yields a worse result is when all $n$ vertices of $G$ are isolated, but then the number of maximal cliques is exactly $n$. The idea is to construct a bijection between the maximal cliques in $G$ and the edges of $\overline{G}$ plus an additional object, say $\emptyset$. The construction is implementing by induction on the number of vertices. When $G$ consists of an isolated vertex $v$, we apparently have only one clique, namely $\{v\}$, so the bijection is $\{v\}\to \emptyset$. Suppose we have a graph $G$ with $|V(G)|\geq 2$. We take a vertex $v_0$ and remove it with all incident edges. Denote the resulting graph by $G'$. By the induction hypothesis, we can construct a bijection between the maximal cliques in $G'$ and $E(\overline{G'})\cup\{\emptyset\}$. Consider a maximal clique $C\subset G$. Either $v_0\notin C $ or $v_0\in C$. In the former case $C$ is also a maximal clique in $G'$ and we map to $C$ the same object that is mapped to $C$ as a maximal clique in the graph $G'$. Let's consider the latter case $v_0\in C$. Again, if $C' := C\setminus \{v_0\}$ is a maximal clique in $G'$ we map the same object mapped to $C'$ (as a maximal clique in the graph $G'$). Finally, suppose $C'$ is not a maximal clique in $G'$. Then, there exists a maximal clique $C''\supsetneq C'$ in $G'$. Take any vertex $v_1\in C''\setminus C'$. Clearly $v_0v_1$ is not an edge in $G$, since otherwise $C$ would not be maximal. Then we map $C$ to the non edge $v_0v_1$ (which is an edge in $\overline{G}$). It remains to see that $v_0v_1$ cannot be mapped to any other maximal clique in $G$, say $C_1$ , that contains $v_0$ (and $v_1$) . On the contrary, assume it's possible. Then, by the problem's condition all vertices in $C$ are connected with all vertices in $C_1$. Hence, if $C\neq C_1$ there would be a larger clique $C\cup C_1$ in $G$, a contradiction.