K-Regular Graphs

k-regular graph: a graph in which all vertices have degree k.

(From left) 3-regular, 4-regular, and 5-regular graphs

Scenario 1

If G is a k-regular graph, then T₁(G) = 1 if k is even and 2 if k is odd.

If k is even the design can be created directly from an Eulerian tour by labeling the cohesive ends in a manner consistent with the direction of the edges. If k is odd the design can be created by adding augmenting to edges to the graph (so all nodes have even degree), finding an Eulerian tour, labeling the edges accordingly, and then removing the augmenting edges.