I just finished this question from Allen Downey's book Think Complexity, and thought I'll just share my algorithm (which is the same as Gerry's answer but just fleshed out) :
Preconditions: 0 < k and k < n
**If n is odd, k must be even
Number of Vertex (n) : Possible Number of degrees for each Vertex (k) 2 : 1 3 : 2 4 : 1,2,3 5 : 2,4 6 : 1,2,3,4,5 7 : 2,4,6 8 : 1,2,3,4,5,6,7 9 : 2,4,6,8 10 : 1,2,3,4,5,6,7,8,9
Examples:
if n is 7: if k is 2: make_edge_for_each_vertice_x_steps_away(1) if k is 4: make_edge_for_each_vertice_x_steps_away(1) make_edge_for_each_vertice_x_steps_away(3) if k is 6: make_edge_for_each_vertice_x_steps_away(1) make_edge_for_each_vertice_x_steps_away(3) make_edge_for_each_vertice_x_steps_away(5) if n is 8: if k is 1: make_edge_for_each_vertice_x_steps_away(4) if k is 2: make_edge_for_each_vertice_x_steps_away(1) if k is 3: make_edge_for_each_vertice_x_steps_away(4) make_edge_for_each_vertice_x_steps_away(3) if k is 4: make_edge_for_each_vertice_x_steps_away(1) make_edge_for_each_vertice_x_steps_away(2) if k is 5: make_edge_for_each_vertice_x_steps_away(4) make_edge_for_each_vertice_x_steps_away(3) make_edge_for_each_vertice_x_steps_away(2) if k is 6: make_edge_for_each_vertice_x_steps_away(1) make_edge_for_each_vertice_x_steps_away(2) make_edge_for_each_vertice_x_steps_away(3) if k is 7: make_edge_for_each_vertice_x_steps_away(4) make_edge_for_each_vertice_x_steps_away(3) make_edge_for_each_vertice_x_steps_away(2) make_edge_for_each_vertice_x_steps_away(1) make_edge_for_each_vertice_x_steps_away(x): for each vertice, adds an edge to a neighbor x steps away. if x == 1, edges will be created between v1 and v2, v2 and v3,..., vn to v1
There is a pattern where
-If n is odd, we add edges between vertices x positions away, where x is all odd numbers between 1 to k.
-If n is even, and k is even, we add edges between vertices x positions away, where x is a range of numbers starting from 1 to n/2, and the range of these numbers is limited by the number of even numbers from 1 to k, including k
-If n is even, and k is odd, we add edges between vertices x positions away, where x is a range of numbers starting from n/2 to 1, and the range of these numbers is limited by the number of odd numbers from 1 to k, including k
Algorithm:
Layout_all_vertices_in_a_circle() if n is even: if k is even: countEvenNumbers = n/2 #add an edge for each even number between 1 to k, including k for i in range(countEvenNumbers): make_edge_for_each_vertice_x_steps_away(i+1) else if k is odd: countOddNumbers = ((n-1)/2) + 1 #add an edge for each odd number between 1 to k, including 1 and k for i in range(countOddNumbers): make_edge_for_each_vertice_x_steps_away((n/2)-i) if n is odd: for i in range(1, k): if i is odd: make_edge_for_each_vertice_x_steps_away(i)
Hope this helps!