# Recovering graph given degrees and connectivity information

I have a graph and don't know how nodes in it are connected to each other.

• I know the number of nodes in the graph.
• I know the degree of each node in the graph.
• I know that given any node $$A$$ that any other node $$B$$ is $$n$$-connected (where $$n$$ may vary per $$B$$) to a sub-graph containing $$A$$. So if I trim $$n$$ specific edges edges from $$B$$, then $$B$$ won't be connected to the sub-graph containing $$A$$.

The question I want to know is given this information, if it's possible with high probability to learn the entire graph topology.

• The word random has a very specific meaning in mathematics, which is different than its usual English meaning. Similarly, topology is a specific mathematical area, though I can imagine it being used for the “structure” of a graph rather than any topological properties. Oct 27, 2021 at 20:45
• One keyword sometimes used for learning a graph is graph reconstruction. Oct 28, 2021 at 5:43
• You want to reconstruct the graph "with high probability" — what is the probability over? Everything in your question is deterministic. Perhaps the original graph was chosen according to a specific distribution? Oct 31, 2021 at 8:31
• What do you mean when you say that $B$ is $n$-connected to a subgraph containing $A$? When is a node $n$-connected to a graph? Oct 31, 2021 at 8:32
• Maybe that's the wrong terminology. But there are n cuts before B and A are disjoint graphs Nov 1, 2021 at 13:35