# Can a K1 graph be a maximal clique of a graph?

I had a discussion with my teacher, whether $K_1$, the complete graph on a single vertex, can be a maximal clique of a given graph. I was notified that it couldn't be a maximal clique, because $K_1$ doesn't have any edges. But that statement didn't convince me.

So, can $K_1$ be a maximal clique of a graph $G$, given that $G$ has a vertex that isn't incident with any edges?

## 1 Answer

Yes, you are correct as you've written your question, but let's be careful with terminology.

A maximal clique means a clique that isn't contained in any larger clique in $G$. So isolated vertices in $G$ (which are $K_1$'s) are certainly maximal cliques.

On the other hand, a maximum clique is a clique in $G$ of largest possible size. So if $G$ has at least one edge, then an isolated vertex would not be a maximum clique since somewhere in $G$ there would at least be a $K_2$.

• I guess I wasn't the one mistaken with terminology, but my teacher was... – user3503384 Dec 17 '14 at 14:51
• @user3503384 Yeah, it's a common mistake. In combinatorics maximum and maximal usually refer to slightly different concepts, but in other areas of math, they are often synonymous. – Casteels Dec 17 '14 at 14:56