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$

Question

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$.

Answer 1

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$.