A common approach (at least in theory) to generating a random $n$ vertex graph uniformly subject to having a given (feasible) degree sequence $(d_i)_{i = 1}^n$ is to use the configuration model, i.e. just attach $d_i$ half-edges to vertex $i$ and then pair up all the half-edges uniformly at random.

Loops or double edges can occur- if they do, repeat the procedure until you obtain a simple graph.

(The probability of obtaining a simple graph is usually small in practice so the expected number of restarts is large, and this algorithm isn't used much in practice for $n$ large.)

Now, the pairings in the configuration model can performed sequentially:

- Select a half-edge arbitrarily. (SELECT)
- Sample a remaining half-edge uniformly at random. (SAMPLE)
- Pair up the SELECT'd half-edge and SAMPLE'd half-edge (to form or 'reveal' an edge).
- If there are half-edges remaining then return to 1.

Of course, in practice, you'd also restart the whole procedure when the **first** loop or double edge is discovered.

**You want to find any loop or double edge as quickly as possible.**

What is the best (adapted) strategy for SELECT'ing half-edges in step 1?

Easy guess: SELECT any half-edge from a vertex with maximal (conditional) probability of being incident to a double edge or loop. I.e. letting $H_i$ be the number of half-edges remaining at vertex $i$, then we choose the vertex that maximises $B_i = (H_i - 1) + \sum_{j\sim i} H_j$, where the sum is over vertices $j$ that *already* have an edge revealed to vertex $i$. (B_i is the number of remaining half-edges which, if SAMPLE'd, would lead to a loop/double edge). So you'd begin by SELECT'ing a half-edge from a vertex of maximal degree.

Is this strategy known to minimise the expected number of pairings needed to find the first loop/double edge (assuming there is one)?

**N.b. I'm specifically asking about the best way to select the half-edge in step 1 of the algorithm given above**, (just for curiosity, not because I think it will yield a practical improvement over other approaches to simulating random graphs)

Small update:

- I implemented this algorithm (c++), and it does offer a marked improvement over naively pairing up half-edges from vertices chosen in a lexicographic way. The speed up is not as much as I'd hoped though (less than a factor of 1/2 for the degree sequences I looked at).
- Computing the "badness" scores $B_i$ above isn't too computationally intensive. In fact the scores can be updated on the fly and this seems pretty quick.
- For anyone generally interested in efficiently sampling graphs Igor's link below or Blitzstein-Diaconis survey some methods (probably better).