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

244 Views Asked by At

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

There are 1 best solutions below

2
On BEST 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$.