# Efficiently generate a random subgraph (Gs) with maximum degree K, using only edges from an existing graph G

I am looking find a way of efficiently generating a random, undirected subgraph $G_s$ with $N$ vertices, using a subset of edges from an exisiting undirected graph $G$, also of size $N$, where the subgraph has only nodes with degree $k \leq k_{max}$.

In other words, I want to create a new random graph with the same number of vertices, but with a random set of the original edges from $G$ removed such that the maximum degree of the new graph is less than some threshold.

I have already developed a working algorithm (MATLAB) which randomly prunes edges from nodes with degree $k > k_{max}$ until this condition is met - however I feel it is far from optimal. It is important that the new random subgraph has the same number of vertices and remains undirected (symmetric). Disconnected vertices (with no in/out edges are allowed).

Ideally both original graph $G$ and new random subgraph $G_s$ should result in sparse matrices (i.e. an edge list), however a full adjacency matrix will suffice.

Thanks!!

• Are you looking for any special kind of randomness properties? Commented Jan 13, 2017 at 17:40
• Somehow my question was added when I wasn't logged in properly! Raiziman T.V. - I'm not necesarily looking for special randomness properties. Commented Jan 13, 2017 at 18:29

Okay, here is an efficient but partial solution: Randomly select a vertex, and from that create the minimum spanning tree. This will make sure that you select each vertex and an associated edge, with minimal degree. Of course this graph is unlikely to include any disconnected vertices. So just include them if they exist in the original graph. If you would like to impose a degree constraint on the MST, you could check here.

At this stage, a minimal graph is established. You could then select some random edges from the original graph and add them until your degree criteria is satisfied. I call this a partial solution because the graph will be pseudo-random, i.e. the only randomness source stem from the selection of initial vertex, and the random edges added afterwards. But that might still work for you.