Generating all possible edge permutations for a given number of nodes in a graph?

Question

My problem is best explained using an example. Suppose we have a graph of $6$ vertices. I would like to generate all the possible edge combinations this graph would have, including the graph with zero edges. Is it right to say that the number of possible combinations would be $6!$?

Is there an existing algorithm recursive or iterative which outputs such a list of combinations for example on MATLAB?

I require this because I am trying to build an algorithm which outputs all possible combinations of a neural network given the number of layers and edges, so this would indeed require some further conditions applied upon it, but I imagine that the upperbound for the number of possibilites should not exceed $6!$.

Answer 1

As has been pointed out in the comments, for a graph with $n$ nodes, there will be $$\large 2^{n \choose 2} = 2^\frac{n(n+1)}{2}$$ distinct labeled graphs. Of course, relabeling will indeed show that many are equivalent. This sequence on OEIS lists the number of isomorphism types.

To my knowledge, Matlab doesn't have the kind of functionality your'e looking for. However, Sage does. (Well, it can generate all isomorphism types of graphs, which I'm sure can be tweaked to only list their edges, if you want). Here's their documentation on undirected graphs. A statement like,

for g in graphs(5):

would let you work each representative of isomorphism classes of graphs with $5$ nodes, one at a time. There are quite a few of these for large values of $n$, so don't expect things to go too quickly!

Answer 2

[Found issue with my reasoning] Possible permutations of graph with N vertices should be $2^{n^2 - N}$ given it's a labeled graph and no renaming of vertices?

My reasoning:

1. There are a total of $n*{n-1}$ possible edges where n is total vertices. This is because every node can connect with every other node. Example: each node has 6 edges in a graph with 7 vertices. Total edges would be $7 * 6$ or $n*(n-1)$
2. Per each possible edge, the edge either does exist in the graph or does not.
3. That gives us a binary variable for each possible connection.
4. Each addition of a binary choice will double your total permutations. Example: if I have two coins, both can be heads, both can be tails, 1 is heads and the other is tails, or vice versa. That gives you $2^2$ permutations or configurations of the coins. If there were just one coin, it would be $2^{1}$ permutations.
5. So where p is possible edges $2^{p}$ is the total permutations of the graph
6. That gives us $2^{n^2 - n}$

Update:

I now think $2^{\frac{n^2 - n}{2}}$ is the correct answer Half of the vertices in such a enumeration are redundant. My math would be correct for directed graphs but not for not directed graphs. This code I put together highlighted my error: https://play.golang.com/p/bhxWMiFLpsq