python generate random connected graph with certain constraint on the vertex degree
A simple algorithm I can think to is:

Start with one vertex
Repeat one of two random moves:
2A) Pick a random vertex with degree less than 4 and add a new vertex connected to it
2B) Pick two random vertices with degree less than 4 that are not connected and add an edge between them

until you've enough vertices/edges.
Is there any python package that could random generate connected graph (there is a path between every pair of vertices) on which each vertex has degree at most 4? 
Thank you!