Number of undirected graphs with n vertices and k edges (inclusive of simple, non-simple, isomorphic, and disconnected graphs) Given the constraints (or non-constraints rather), is there a closed solution on a set of labeled vertices? One way I looked at this problem is by trying to implement a constrained stars-and-bars technique on the diagonal and diagonal-exclusive half of the n times n adjacency matrix, but I'm not getting any good leads. It seems there are multiple definitions of a self-loop in undirected graphs. In the context of this question, I define a self-loop to represent a degree of 2 in an undirected graph.

Jean Farrell

Jean Farrell

Answered question

2022-09-25

Number of undirected graphs with n vertices and k edges (inclusive of simple, non-simple, isomorphic, and disconnected graphs)
Given the constraints (or non-constraints rather), is there a closed solution on a set of labeled vertices?
One way I looked at this problem is by trying to implement a constrained stars-and-bars technique on the diagonal and diagonal-exclusive half of the n × n adjacency matrix, but I'm not getting any good leads.
It seems there are multiple definitions of a self-loop in undirected graphs. In the context of this question, I define a self-loop to represent a degree of 2 in an undirected graph.

Answer & Explanation

Genesis Rosario

Genesis Rosario

Beginner2022-09-26Added 11 answers

If you consider labeled graphs, there are n2 legitimate spots for an edge (if you allow loops). Since you accept the non-simple graphs (so parallel edges), each of the k edges can be put in any of those spots. In the end, you get (n2)k which is equal to n2k.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?