graphs.RandomRegular(3,10) often returns a graph on 0 vertices

[williamstein]

The docstring for graphs.RandomRegular says

Returns a random d-regular graph on n vertices, or returns False on
failure.

However, try calling it a few times with input 3,10 and with probability about 25% you'll get back an empty graph!:

sage: graphs.RandomRegular(3,10)
Graph on 0 vertices

sage: [len(graphs.RandomRegular(3,10)) for _ in range(1000)].count(0)
232

Component: graph theory

Author: Robert Miller

Reviewer: Jason Grout

Merged: sage-4.1.1.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/5932

[rlmill]

comment:1

This is a bug in NetworkX. Their docstring says:

Definition:     networkx.random_regular_graph(d, n, seed=None)
Source:
def random_regular_graph(d, n, seed=None):
    """Return a random regular graph of n nodes each with degree d, G_{n,d}.
    Return False if unsuccessful.

[rlmill]

Attachment: trac_5932.patch.gz

[jasongrout]

comment:3

The fix looks correct, the file passes doctests, and everything looks great!

[jasongrout]

Reviewer: Jason Grout

[jasongrout]

Author: Robert Miller

[sagetrac-mvngu]

Merged: sage-4.1.1.alpha0