Constructing Edge-labellings of \(K_{n}\) with Constant-length Hamilton Cycles

We present an optimal algorithm to label the edges of a complete graph with integer lengths so that every Hamilton cycle has the same length. The algorithm is complete in the sense that every edge-labelling with this property is the output labelling of some run of this algorithm. Such edge-labellings are induced by half-integer vertex-labellings by adding the vertex labels on an edge’s ends to determine its label. The Fibonacci sequence arises in this connection.