The vertices of G are the k-subsets of some set of size n. Two k-subsets are connected by an edge of G if their symmetric difference is of size 2. The integers n and k are chosen so that the graph is not trivial.



Is this graph well known?
That's the Johnson graph: <http://en.wikipedia.org/wiki/Johnson_graph>


