# Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$ [closed]

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a annulus made from wood and then to string yarn between them. Since $K_{37}$ is a complete graph, it has a Hamiltonian path. My knowledge of computational graph theory is nil, and I am aware that this is not exactly an easy problem (see wikipedia: Hamiltonian Path Problem, for instance)

• Every permutation of nodes induces a Hamiltonian path in a complete graph. I'm confused; what's the problem? – Raphael Feb 26 '15 at 11:11
• To make a "regular" Hamiltonian path (in the string-like fashion you propose) take any peg/node and connect it to a peg/node a certain number of pegs/nodes from the starting position. Repeat with the same distance. This should work for any distance, as 37 is prime. (Otherwise, I support the comment by @Raphael.) – Hendrik Jan Feb 26 '15 at 12:44
• @Raphael: some are more optimal for laying string than others. – graveolensa Feb 26 '15 at 13:14
• so I need a permutation that's a derangement? – graveolensa Feb 26 '15 at 13:36
• @deoxygerbe Then your query should be, "how do I find an X-path so that..." -- we can't possibly know which criteria you have in mind. – Raphael Feb 26 '15 at 13:49

It seems that you're trying to construct the graph $K_{37}$ from string and nails without cutting the string. For this, you don't want a Hamiltonian path (a path that visits every vertex exactly once) but an Euler trail (a walk that visits every edge exactly once).
$K_n$ has $(n-1)!/2$ Hamiltonian circles and it has $\lfloor(n-1)/2 \rfloor$ distinct Hamiltonian circles (I mean no edge in common), every Hamiltonian circle in a graph with $|V| = n$ has $n$ edges. By removing any of the edges in a Hamiltonian circle the result path is a Hamiltonian path so $k_n$ has $n \times (n-1)!/2 = n!/2$ Hamiltonian paths and it is the permutation of nodes. What exactly do you want? You can select any of these paths.