1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I guess I wasn't the one mistaken with terminology, but my teacher was... $\endgroup$ – user3503384 Dec 17 '14 at 14:51
  • $\begingroup$ @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. $\endgroup$ – Casteels Dec 17 '14 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.