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.
2

$\begingroup$ Thank you for info. Is it known if those graphs are Hamiltonian? $\endgroup$– w gApr 21 '12 at 8:05

$\begingroup$ Yes, they are. The key word is combinatorial gray codes, see for example section 4 in www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps $\endgroup$ Apr 21 '12 at 10:22