If you have a k-regular graph on n vertices (we may need to relate k and n to make this work), can we transform it into any other k-regular graph on n vertices by operations of this type?
https://math.stackexchange.com/a/229491
(You have edges AB and CD and you change them to edges AD and CB, leaving everything else the same. Possibly to make this work, we may need to allow loops.)
Cf. Ryser, "Combinatorial Properties of Matrices of Zeros and Ones" (1957)
Yes, it can always be done, while having a $k$-regular simple graph at every step. This is a result of Roger Eggleton from the 1970s which is closely related to earlier work of Hakimi for multigraphs and Ryser for 0-1 matrices.[1] A later result of Richard Taylor is that if the first and last graphs are connected then you can arrange for all the intermediate graphs to be connected too.[2] Richard also showed the same for 2-connectivity.[3] All these results hold for arbitrary degree sequences and not just regular graphs.
Usually the operation is called "switching". It is actually pretty useless for generation as there is no way to efficiently tell if you have seen a graph before. It is useful for other things though; for example you can turn it into a Markov chain to make random graphs.
[1] R.B. Eggleton, Graphic sequences and graphic polynomials: a report, in Infinite and Finite Sets, Vol. l, ed. A. Hajnal et al, Colloq. Math. Soc. J. Bolyai 10, (North Holland, Amsterdam, 1975), 385-392.
[2] R. Taylor, Constrained switchings in graphs. Combinatorial mathematics, VIII (Geelong, 1980), pp. 314–336, Lecture Notes in Math., 884, Springer, Berlin-New York, 1981.
[3] R. Taylor, Switchings constrained to 2-connectivity in simple graphs. SIAM J. Algebraic Discrete Methods 3 (1982), no. 1, 114–121.
