So we know that the number of distinct simple undirected graphs (i.e. no loops or double edges) in $n$ vertices is $2^{\binom{n}{2}}$, but what if we allow loops or double edges? My thought: For each pair of vertices $v_i, v_j$, there are now 3 distinct possibilities (no edge $v_iv_j$, single edge $v_iv_j$ or double edge $v_iv_j$). Also for each vertex there are two possibilities (there is or there isn't a loop), so in total I count $2 \times 3^{\binom{n}{2}}$ distinct undirected graphs, is that correct?
Number of distinct graphs in $n$ vertices
combinatoricsgraph theory
Related Solutions
In the particular case of 4 vertices and 6 edges, we can generate them exhaustively. I use some GAP code below.
Step 1: generate all labelled digraphs:
nrVert:=4;;
nrEdges:=2*(nrVert-1);;
LabelledDigraphs:=[];
DigraphBacktracking:=function(v,edgeSet)
local deg,outNeighborSet,newedgeSet;
for deg in [0..Minimum(nrEdges-Size(edgeSet),nrVert-1)] do
for outNeighborSet in Combinations([1..nrVert],deg) do
# loops are not allowed
if(v in outNeighborSet) then continue; fi;
# add new directed edges
newedgeSet:=Concatenation(edgeSet,List(outNeighborSet,u->[v,u]));
if(v<nrVert) then
DigraphBacktracking(v+1,newedgeSet);
else
if(Size(newedgeSet)=nrEdges) then
LabelledDigraphs:=Concatenation(LabelledDigraphs,[newedgeSet]);
fi;
fi;
od;
od;
end;;
# start backtracking
DigraphBacktracking(1,[]);
Then we filter out isomorphic representatives, which we can do by brute force (i.e., compute the entire isomorphism class) since the parameters are small:
# brute-force computes the isomorphism class; finds minimum
IsomorphismClassRepresentative:=function(edgeSet)
local alpha,permutededgeSet,IsomorphismClass;
IsomorphismClass:=[];
for alpha in SymmetricGroup(nrVert) do
permutededgeSet:=SortedList(List(edgeSet,e->[e[1]^alpha,e[2]^alpha]));
IsomorphismClass:=Concatenation(IsomorphismClass,[permutededgeSet]);
od;
return Minimum(IsomorphismClass);
end;;
UnlabelledDigraphs:=Set(LabelledDigraphs,edgeSet->IsomorphismClassRepresentative(edgeSet));
Then I wrote a script to print them, giving the 48 digraphs drawn below:
For 4-vertex 4-edge digraphs, we get these four:
This agrees with Marko Riedel's answer in these cases.
Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)
Best Answer
I think you mean $2^n 3^{\binom n 2}$. That should be correct assuming there's either one or no loop at each vertex.
Usually, once you allow multiple edges you can have any number of edges between two vertices, so there are infinitely many possible graphs.