summary: Tricky graphs.
The Johnson graph \(J(n, k)\) is the graph where the vertices are labelled by the \(k\) element subsets of a set of size \(n\) and the edges join those subsets where the intersection is of size \(k - 1\).
Why \(J(n, k)\): Johnson graph with parameters \(n\) and \(k\).
\(\mathbb{Z}_n = \{ 0, 1, 2, \ldots, n \}\).
Vertices: \(V = \{ K \mid K \subseteq \mathbb{Z}_n, |K| = k-1 \}\).
Edges: \(E = \{ (K_i, K_j) \mid |K_i \cup K_j| = k - 1 \}\).
Example
\(J(4, 2)\): Johnson graph with parameters \(n=4\) and \(k=2\).
\(\begin{aligned} V = \big\{ & \{ 1,2 \} , \{ 1,3 \} , \{ 1,4 \} , \\ & \{ 2,3 \} , \{ 2,4 \} , \{ 3,4 \} \big\} \end{aligned}\)
\(\begin{aligned} E = \big\{ & (\{1,2\},\{1,3\}), (\{1,2\},\{1,4\}), \\ & (\{1,2\},\{2,3\}), (\{1,2\},\{2,4\}), \\ & (\{1,3\},\{1,4\}), (\{1,3\},\{2,3\}), \\ & (\{1,3\},\{3,4\}), (\{1,4\},\{2,4\}), \\ & (\{1,4\},\{3,4\}), (\{2,3\},\{2,4\}), \\ & (\{2,3\},\{3,4\}), (\{2,4\},\{3,4\}) \big\} \end{aligned}\)