undirected_gnm_random_graph(num_nodes, num_edges, /, seed=None)#

Return a \(G_{nm}\) undirected graph, also known as an Erdős-Rényi graph.

Generates a random undirected graph out of all the possible graphs with \(n\) nodes and \(m\) edges. The generated graph will not be a multigraph and will not have self loops.

For \(n\) nodes, the maximum edges that can be returned is \(n (n - 1)/2\). Passing \(m\) higher than that will still return the maximum number of edges. If \(m = 0\), the returned graph will always be empty (no edges). When a seed is provided, the results are reproducible. Passing a seed when \(m = 0\) or \(m >= n (n - 1)/2\) has no effect, as the result will always be an empty or a complete graph respectively.

This algorithm has a time complexity of \(O(n + m)\)

  • num_nodes (int) – The number of nodes to create in the graph

  • num_edges (int) – The number of edges to create in the graph

  • seed (int) – An optional seed to use for the random number generator


A PyGraph object

Return type: