Given the number of total nodes and degrees of each node, is it possible to construct a graph?

548 views Asked by At

Take the cube as an example, there are 8 nodes and 12 edges, and each node is connected with 3 nodes.

With networkx, I must input all the edges manually. For example, the following code is to construct a graph containing all the edges of an icosahedron (12 nodes, 30 edges, 5 adjacent nodes per node).

import networkx as nx
G = nx.Graph()
nodes = list(range(12))
edges = [
    [0, 1], [0, 2], [0, 3], [0, 4], [0, 5],
    [1, 2], [1, 6], [1, 10], [1, 5],
    [2, 3], [2, 6], [2, 7],
    [3, 4], [3, 7], [3, 8],
    [4, 5], [4, 8], [4, 11], 
    [5, 11], [5, 10],
    [6, 7], [6, 9], [6, 10],
    [7, 8], [7, 9],
    [8, 9], [8, 11],
    [9, 10], [9, 11],
    [10, 11],
]
G.add_nodes_from(nodes)
G.add_edges_from(edges)

My question is how to get all the possible edges without writing them manually. The name of every node can be randomly initialized.

To the best of my knowledge, the Erdős–Rényi model in igraph cannot constrain the adjacent nodes.

from igraph import *

g = Graph.Erdos_Renyi(12, m=30, directed=False)
g.get_edgelist()
"""
[(0, 1),
 (0, 2),
 (1, 3),
 (2, 3),
 (0, 4),
 (1, 4),
 (3, 5),
 (4, 6),
 (5, 6),
 (0, 7),
 (2, 7),
 (3, 7),
 (6, 7),
 (0, 8),
 (1, 8),
 (3, 8),
 (0, 9),
 (3, 9),
 (4, 9),
 (6, 9),
 (0, 10),    node10 has more than 5 edges.
 (2, 10),
 (3, 10),
 (5, 10),
 (7, 10),
 (8, 10),
 (1, 11),
 (2, 11),
 (4, 11),
 (9, 11)]
"""
1

There are 1 answers

0
MT0 On

You cannot create a unique planar graph only knowing the number of vertices, edges, and edges-per-vertex. A simple counter example:

Take your cube example with 8 vertices, 12 edges and 3 edges-per vertex then you can have:

[
  (A,B),(B,C),(C,D),(D,A), # top face of the cube.
  (E,F),(F,G),(G,H),(H,E), # bottom face of the cube.
  (A,E),(B,F),(C,G),(D,H)  # sides of the cube connecting top and bottom.
]

This makes a planar graph with 6 faces where every face has 4 edges.

You can equally have:

[
  (A,B),(B,C),(C,D),(D,E),(E,F),(F,G),(G,H),(H,A), # cycle containing all vertices
  (A,C), # connect vertices 2 apart on the cycle.
  (B,D), # overlap previous and also connect vertices 2 apart on the cycle.
  (E,G), # connect vertices 2 apart on the cycle.
  (F,H)  # overlap previous and also connect vertices 2 apart on the cycle.
]

This creates a planar graph with 4 triangular faces and 2 faces bounded by 6 edges.