Revolving-door Gray code for all 4-vertex graphs [video]

archive.org

34 pointsfs1236 comments

In February 2022, Don Knuth found a cool graph which contains all 4-vertex graphs as subgraphs. Furthermore, they can be visited in revolving-door Gray code order.

He reported about it in exercise 291 in pre-fasicle 7a, and asked if someone could make an animated video of it. This is my attempt at it.

Any remarks or suggestions for improvement are welcome.

suggestion: remove the audio.

Why? I understood the audio to be proof that it is a Gray code?

Or turn on mute.

Fantastic. The audio (as suggested by Knuth) is a nice touch. If people don't like it, they can easily mute.

Thanks. The original idea by Knuth was to have each vertex have both a separate tune and a separate instrument/timbre, with each combination sounding not too bad.

I couldn't make this sound good with 8 separate instruments, so I went for the next best thing: a single instrument, with each vertex playing one note (0->B, 1->C,...7->a).

Reply on news.ycombinator.com