= Maximal cliques of a Johnson graph
{title2=$n-k+1\quad\text{and}\quad k+1$}
For $1<k<n-1$, the maximal cliques of $J(n,k)$ are the families containing a fixed $(k-1)$-subset, of size $n-k+1$, and the families contained in a fixed $(k+1)$-subset, of size $k+1$. To see why these exhaust the possibilities, write two adjacent vertices as $D\cup\{a\}$ and $D\cup\{b\}$. A common adjacent vertex either contains $D$ or lies in $D\cup\{a,b\}$. A vertex of the first kind outside that union is not adjacent to a vertex of the second kind omitting an element of $D$, so a clique cannot mix these alternatives. For $J(n,3)$ and $n\ge5$, $n\ne6$, the clique sizes $n-2$ and four distinguish the families containing pairs. Their incidence recovers $J(n,2)$, whose stars of size $n-1$ distinguish the individual ground-set points from its triangular cliques.
Back to article page
