On Tarjan's paper “Finding a Maximum Clique”

Question

In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here.

In the second page of the introduction he states the following lemma.

Let $G = (V,E)$ be a graph and $S \subseteq V.$ Then $$ ||G|| = \max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\} $$

where $||G||$ is the size of the maximum clique in $G$ and $A(C)$ is the set of adjacent vertices to one or more elements in $C$.

This does not make sense to me, for example if we let $S$ be the set containing just one isolated vertex, then $\max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\} = 1$, since $A(C) \setminus S = \emptyset \setminus S = \emptyset$.

Even worse, we can take $S = \emptyset$ and then the lemma falls apart.

What am I missing?

Answer 1

You definition of $A(C)$ is wrong. It is the set of vertices adjacent to all vertices in $C$: $$ A(C) = \{ v \in V : \forall u \in C, (u,v) \in E \}. $$ In particular, if $C = \emptyset$ then $A(C) = V$.

In your example, suppose that $S = \{v\}$. Let's see what $|C| + \|G_{A(C) \setminus S}\|$ amounts two for all choices of $C$:

1. If $C = \emptyset$, then $A(C) \setminus S = V \setminus \{v\}$, and so $|C| + \|G_{A(C)\setminus S}\|$ is the maximum size of a clique in $G$ that doesn't contain $v$.
2. If $C = \{v\}$, then $A(C) \setminus S = N(v)$, the set of neighbors of $v$. Therefore $|C| + \|G_{A(C) \setminus S}\|$ is the maximum size of a clique in $G$ that contains $v$.

So in this case, the formula is correct.

When $S = \emptyset$, the formula just states that $\|G\| = \|G\|$.