Johnson graph ($J(n,k)$)

The Johnson graph has the $k$-element subsets of an $n$-element set as vertices, with two vertices adjacent exactly when their intersection has $k-1$ elements. Relabelling the ground set gives graph automorphisms. The maximal cliques of a Johnson graph allow reconstruction of those ground-set labels when the two clique sizes are different.

One edge of a Johnson graph replaces one element of a $k$-subset, so it can increase intersection with a fixed target by at most one. Replacing each element outside the target by one missing target element gives a path reaching this lower bound. Equal-distance ordered pairs have equal sizes of intersection, the two differences and the remaining ground set; a permutation matching these four regions proves distance transitivity.

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\ge 5$, $n\ne 6$, 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.