Johnson graph

Johnson graph
The Johnson graph J(5,2)
Named after	Selmer M. Johnson
Vertices	${\displaystyle {\binom {n}{k}}}$
Edges	${\displaystyle {\frac {k(n-k)}{2}}{\binom {n}{k}}}$
Diameter	${\displaystyle \min(k,n-k)}$
Properties	${\displaystyle (k(n-k))}$-regular Vertex-transitive Distance-transitive Hamilton-connected
Notation	${\displaystyle J(n,k)}$

Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph ${\displaystyle J(n,k)}$ are the ${\displaystyle k}$-element subsets of an ${\displaystyle n}$-element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains ${\displaystyle (k-1)}$-elements. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.