If a graph G is the union of $n$ cliques of size $n$ no two of which share more than one vertex, then $\chi_f(G)=n$. $\omega(G)=n$ Theorem: If a graph G is the union of $n$ cliques of size $n$ no two of which share more than one vertex, then $\chi_f(G)=n$. Prove that $\omega(G)=n$.

A clique is a subset of vertices of an undirected graph such that its induced subgraph is complete (every two distinct vertices in the clique are adjacent).
The clique number $\omega(G)$ of a graph $G$ is defined as the maximum size of a subset of $V(G)$ such that the subset induces a complete graph (a graph where each two vertices are adjacent) in $G$.
 A: As noted in the comment below, this answer assumes that the cliques are connected by a common edge, rather than by a common vertex as indicated in the question.

Clearly, we have $\omega(G) \geq n$.  For any graph, we have $\omega \leq \chi_f \leq \chi$.  It therefore suffices, for the purposes of this proof, to show that $\chi(G) \leq n$.  That is, it suffices to demonstrate that $G$ has a valid (vertex) coloring on $n$ colors.
Let $C_1,\dots,C_n$ denote the cliques (i.e. the sets of vertices from the cliques) that form the graph.  For each pair $i \neq j$ with $1 \leq i,j \leq n$, let $v_{i,j}$ denote the vertex in $C_i$ such that $v_{i,j} \sim w$ for some $w \in C_j$.  Note the following:, 


*

*If such a vertex exists, there is at most one such $v_{i,j}$ per pair $i \neq j$.  

*For every $j,k$, we have $v_{i,j} \sim v_{i,k}$ since both vertices are elements of the clique $C_i$.  

*In each clique $C_i$, there are at most $n-1$ vertices $v_{i,j}$ (for some $j$).  That is, there is at least one vertex $v$ such that $v$ is only adjacent to other vertices in $C_i$.


Let $B = \{v_{i,j} : i,j = 1,\dots,n\}$.  Consider the induced subgraph on the vertices of $B$.  By the last note, this graph has degree at most $n - 1$.  Thus, with a greedy coloring, we see that $B$ has a valid coloring on $n$ colors.
Now, consider an arbitrary $C_i$.  With the coloring on $B$, we have assigned distinct colors to any pair $v_{i,j}$.  This coloring on $C_i$ may be extended to a coloring of the entire clique.  Note that any newly colored vertices are adjacent only to other elements of the clique.  Thus, we have extended the coloring on $B$ to a valid coloring on $B \cup C_i$.
Doing this for all $C_i$, we have an $n$-coloring for the entirety of the graph $G$.
