2
$\begingroup$

In my textbook, they provide a graph $H$ and then list examples of the cliques and the independent sets in $H$. $\begin{align*}V(H)&=\{1,2,3,4,5,6,7,8,9\}\\E(H)&=\{12,23,39,98,87,74,41,26,25,56,36,69,68,57\}\end{align*}$

They list the set $\{4\}$ to be both a clique and an independent set. I am having trouble understanding why $\{4\}$ is both a clique and an independent set.

I know that a subset $S$ is a clique provided that any two distinct vertices are adjacent. So, since $\{4\}$ has only vertex, is it vacuously a clique?

I know that a set $S$ is independent provided $G[S]$ is an edgeless graph. I can see clearly how $\{4\}$ is an edgeless graph since it only has one vertex.

So, can a subset be both a clique and an independent set? Is $\{4\}$ both a clique and an independent set?

  • 0
    @Brian, unless, of course, you allow your graphs to have loops, in which case a single vertex may or may not be an independent set.2012-05-14

1 Answers 1

2

Converting my comment to an answer for the sake of having one:

The answer to all of your questions is yes. In a simple graph (one without loops or multiple edges) a singleton vertex is always vacuously both a clique and an independent set, for exactly the reasons that you give. As Gerry Myerson noted in his comment, a singleton vertex need not be an independent set if you allow your graph to contain loops, but it will still be a clique.