The vertices of G are the ksubsets of some set of size n. Two ksubsets 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.
That's the Johnson graph: http://en.wikipedia.org/wiki/Johnson_graph 

