Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
The answer to all of your questions is yes. A single vertex is always vacuously both a clique and an independent set, for exactly the reasons that you give. –  Brian M. Scott May 14 '12 at 20:52
    
@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. –  Gerry Myerson May 14 '12 at 23:54

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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