# On Tarjan's paper “Finding a Maximum Clique”

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?

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$$.
When $$S = \emptyset$$, the formula just states that $$\|G\| = \|G\|$$.