{"id":4735,"date":"2026-02-08T19:36:59","date_gmt":"2026-02-09T03:36:59","guid":{"rendered":"https:\/\/bendwavy.org\/wp\/?p=4735"},"modified":"2026-05-08T08:41:59","modified_gmt":"2026-05-08T16:41:59","slug":"tours","status":"publish","type":"post","link":"https:\/\/bendwavy.org\/wp\/?p=4735","title":{"rendered":"tours"},"content":{"rendered":"<p>How many Euler circuits are there in the complete directed graph on N vertices?  More interesting to me, how many equivalence classes under reversal and relabeling? <!--more--><\/p>\n<table>\n<tbody>\n<tr>\n<td> N <\/td>\n<td> circuits: n<sup>(n-2)<\/sup> (n-2)!<sup>n<\/sup> <\/td>\n<td> classes <\/td>\n<\/tr>\n<tr>\n<td> 3 <\/td>\n<td> 3 <\/td>\n<td> 1 <\/td>\n<\/tr>\n<tr>\n<td> 4 <\/td>\n<td> 256 <\/td>\n<td> 6 <\/td>\n<\/tr>\n<tr>\n<td> 5 <\/td>\n<td> 972000 <\/td>\n<td> 4089 <\/td>\n<\/tr>\n<tr>\n<td> 6 <\/td>\n<td> 247669456896 <\/td>\n<td> 171454588 (I expected &gt;171992678, but am not motivated to inquire further) <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>I made models of the six cases on four vertices (and tried to put them on Thingiverse and Thangs, but no images show up).  The vertices are those of a tetrahedron, of course.  I knew from the start that the corners of the path ought to be rounded, to make it easier to follow; my favorite design so far is a Fourier series (six components) that matches the derivative at the midpoint of each edge.  They look like martian game-pieces.  I was surprised to find that all of them have u-turns.<\/p>\n<p>Loosening the rules, to allow the path to include an edge twice in the same direction, gives 15 more classes (of which three have no u-turns).  I may have those printed later in a contrasting color.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"\/doodle\/18996-e3.png\" width=\"280\" height=\"280\"> <img loading=\"lazy\" decoding=\"async\" src=\"\/doodle\/18973-e3.png\" width=\"280\" height=\"280\"> <img loading=\"lazy\" decoding=\"async\" src=\"\/doodle\/18614-e3.png\" width=\"280\" height=\"280\"> <img loading=\"lazy\" decoding=\"async\" src=\"\/doodle\/18949-e3.png\" width=\"280\" height=\"280\"> <img loading=\"lazy\" decoding=\"async\" src=\"\/doodle\/18607-e3.png\" width=\"280\" height=\"280\"> <img loading=\"lazy\" decoding=\"async\" src=\"\/doodle\/18634-e3.png\" width=\"280\" height=\"280\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>How many Euler circuits are there in the complete directed graph on N vertices? More interesting to me, how many equivalence classes under reversal and relabeling?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-4735","post","type-post","status-publish","format-standard","hentry","category-mathematics"],"_links":{"self":[{"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=\/wp\/v2\/posts\/4735","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4735"}],"version-history":[{"count":23,"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=\/wp\/v2\/posts\/4735\/revisions"}],"predecessor-version":[{"id":4787,"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=\/wp\/v2\/posts\/4735\/revisions\/4787"}],"wp:attachment":[{"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4735"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4735"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bendwavy.org\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4735"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}