Here is an answer to help get started, namely the count of connected
non-isomorphic graphs. With $\mathcal{G}$ the species of
non-isomorphic graphs and $\mathcal{C}$ of connected non-isomorphic
graphs we have a multiset relationship, namely
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{G}
= \textsc{MSET}(\mathcal{C}).$$
The astute reader will note that this holds for digraphs and graphs
with self-loops as well (with a different $\mathcal{G}$). Translating
to generating functions the species equation yields (we use $z$ for
the number of vertices and $u$ for the number of edges)
$$G(z, u) = \exp\left(\sum_{l\ge 1} \frac{C(z^l, u^l)}{l}\right).$$
Differentiatiation will produce
$$G'(z, u) = G(z, u) \sum_{l\ge 1} C'(z^l, u^l) z^{l-1}.$$
Extracting coefficients on $[z^n]$ we obtain
$$(n+1) G_{n+1} = \sum_{q=0}^n G_{n-q}
[z^q] \sum_{l\ge 1} C'(z^l, u^l) z^{l-1}
\\ = \sum_{q=0}^n G_{n-q}
\sum_{l=1}^{q+1} [z^{q-(l-1)}] C'(z^l, u^l)
\\ = \sum_{l=1}^{n+1}
\sum_{q=l-1}^n G_{n-q} [z^{q-(l-1)}] C'(z^l, u^l)
= \sum_{l=1}^{n+1}
\sum_{q=0}^{n-(l-1)} G_{n-q-(l-1)} [z^{q}] C'(z^l, u^l).$$
Here we must have $q = pl$ and we get
$$\sum_{l=1}^{n+1}
\sum_{p=0}^{\lfloor (n+1)/l \rfloor -1}
G_{n+1-(p+1)l} [z^{pl}] C'(z^l, u^l)
\\ = \sum_{l=1}^{n+1}
\sum_{p=0}^{\lfloor (n+1)/l \rfloor -1}
G_{n+1-(p+1)l} [z^{p}] C'(z, u^l)
\\ = \sum_{l=1}^{n+1}
\sum_{p=0}^{\lfloor (n+1)/l \rfloor -1}
G_{n+1-(p+1)l} (p+1) C_{p+1}(u^l)
= \sum_{l=1}^{n+1}
\sum_{p=1}^{\lfloor (n+1)/l \rfloor}
G_{n+1-pl} p C_p(u^l)
\\ = \sum_{pl\le n+1} G_{n+1-pl} p C_p(u^l).$$
Introducing $k=pl$ we finally obtain
$$\sum_{k=1}^{n+1} G_{n+1-k} \sum_{p|k} p C_p(u^{k/p})
\\ = \sum_{k=1}^{n} G_{n+1-k} \sum_{p|k} p C_p(u^{k/p})
+ \sum_{p|n+1 \wedge p\lt n+1} p C_p(u^{(n+1)/p})
+ (n+1) C_{n+1}(u).$$
We thus have the recurrence
$$C_{n+1}(u) = G_{n+1}
\\ - \frac{1}{n+1}
\sum_{k=1}^{n} G_{n+1-k} \sum_{p|k} p C_p(u^{k/p})
- \frac{1}{n+1}
\sum_{p|n+1 \wedge p\lt n+1} p C_p(u^{(n+1)/p})$$
or alternatively for $n\ge 2$
$$\bbox[5px,border:2px solid #00A000]{
C_n(u) = G_{n}
- \frac{1}{n} \sum_{k=1}^{n-1} G_{n-k} \sum_{p|k} p C_p(u^{k/p})
- \frac{1}{n} \sum_{p|n \wedge p\lt n} p C_p(u^{n/p}).}$$
Note however that the coefficients $G_n$ for all graphs rather than
connected only are not difficult to compute, for the details consult
the following MSE
link, where we
encounter the following classification according to the number of
edges.
For $n=4,$ we get
$$G_4 = {u}^{6}+{u}^{5}+2\,{u}^{4}+3\,{u}^{3}+2\,{u}^{2}+u+1$$
and for $n=5,$
$$G_5 = {u}^{10}+{u}^{9}+2\,{u}^{8}+4\,{u}^{7}+6\,{u}^{6}+6\,{u}^{5}
\\+6\,{u}^{4}+4\,{u}^{3}+2\,{u}^{2}+u+1$$
and for $n=6,$ the last one,
$$G_6 = {u}^{15}+{u}^{14}+2\,{u}^{13}+5\,{u}^{12}+9\,{u}^{11}
\\+15\,{u}^{10}+21\,{u}^{9}+24\,{u}^{8}+24\,{u}^{7}+21\,{u}^{6}
\\+15\,{u}^{5}+9\,{u}^{4}+5\,{u}^{3}+2\,{u}^{2}+u+1.$$
Setting $u=1$ we obtain the total count of non-isomorphic graphs which
starts with
$$1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168,\ldots$$
which point us to OEIS A000088 where we
find that we have the right values.
Using these values together with the recurrence that was derived above
yields the generating functions for connected non-isomorphic
graphs. (We must pay attention to get the base cases right, they are
$1$ and $1$ for $G_0$ and $G_1$ and $0$ and $1$ for $C_0$ and $C_1.$)
We thus have
$$C_4 = {u}^{6}+{u}^{5}+2\,{u}^{4}+2\,{u}^{3}$$
and furthermore
$$C_5 = {u}^{10}+{u}^{9}+2\,{u}^{8}+4\,{u}^{7}
\\+5\,{u}^{6}+5\,{u}^{5}+3\,{u}^{4}$$
and finally
$$C_6 = {u}^{15}+{u}^{14}+2\,{u}^{13}+5\,{u}^{12}
\\+9\,{u}^{11}+14\,{u}^{10}+20\,{u}^{9}+22\,{u}^{8}+19\,{u}^{7}
\\+13\,{u}^{6}+6\,{u}^{5}.$$
Observe that the smallest degree term ($n-1$ edges) counts trees and
indeed we obtain
$$1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741,
\\ 19320, 48629, 123867, 317955, 823065,\ldots$$
which point us to OEIS A000055. (We
compute these with the Maple code that will be presented at the end
and it works quite nicely where resource allocation is concerned.)
Setting $u=1$ in the $C_n$ terms yields the sequence
$$1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565,
\\ 164059830476, 50335907869219, 29003487462848061,
\\ 31397381142761241960, 63969560113225176176277,\ldots $$
which is OEIS A001349 and presumably
motivated this entire calculation.
To conclude we answer the question of the OP who asks about the number
of non-isomorphic graphs with $2n-2$ edges. We get for the general
case the sequence
$$1, 0, 0, 1, 2, 15, 131, 1646, 27987, 596191, 15108047,
\\ 440393606, 14441470390,\ldots$$
which does not yet have an OEIS entry. We get for the connected case
the sequence
$$1, 0, 0, 1, 2, 14, 126, 1579, 26631, 561106, 14013042, 401665379,
\\ 12932769342, 461011580013, 18001615191104,
\\ 763685360909770, 34964179546197292,\ldots$$
which is not yet in the OEIS either.
The Maple code for this computation follows. We include everything
here even though there is some overlap with the link that we
referenced, so that the reader does not have to look for and join the
different constituents.
with(numtheory);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;
terml := [];
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), [op(1,v), d]];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_edg :=
proc(n)
option remember;
local all, term, res, cycs, l1, l2, inst1, flat, u, v,
uidx, vidx;
if n=0 then return 1; fi;
all := 0:
for term in pet_cycleind_symm(n) do
flat := pet_flatten_termA(term);
cycs := flat[2]; res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res *
(a[l1]^(1/2*(l1-1)))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res *
(a[l1/2]*a[l1]^(1/2*(l1-2)))^inst1;
fi;
od;
all := all + flat[1]*res;
od;
all;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
G :=
proc(n)
option remember;
if n=0 then return 1 fi;
expand(pet_varinto_cind(1+u, pet_cycleind_edg(n)));
end;
C :=
proc(n)
option remember;
local res;
if n=0 then return 0 fi;
if n=1 then return 1 fi;
res := G(n)
- 1/n*add(G(n-k)
*add(p*subs(u=u^(k/p), C(p)),
p in divisors(k)), k=1..n-1)
- 1/n*add(p*subs(u=u^(n/p), C(p)),
p in divisors(n) minus {n});
expand(res);
end;
TRIANG_G :=
proc(m)
seq(seq(coeff(G(n), u, k), k=0..n*(n-1)/2),
n=1..m);
end;
TRIANG_C :=
proc(m)
seq(seq(coeff(C(n), u, k), k=n-1..n*(n-1)/2),
n=1..m);
end;
Addendum I, Mar 15 2017. Here are the data for the case of
digraphs and weakly connected digraphs. The cycle index is simpler
actually than in the case of ordinary graphs because the edges are now
ordered pairs rather than sets. We must be careful however not to
include self loops. With these observations we obtain for $n=3$ the
corresponding
$$G_3 = {u}^{6}+{u}^{5}+4\,{u}^{4}+4\,{u}^{3}+4\,{u}^{2}+u+1$$
and for $n=4$
$$G_4 =
{u}^{12}+{u}^{11}+5\,{u}^{10}+13\,{u}^{9}+27\,{u}^{8}+38\,{u}^{7}
\\+48\,{u}^{6}+38\,{u}^{5}+27\,{u}^{4}+13\,{u}^{3}+5\,{u}^{2}+u+1$$
and finally
$$G_5 =
{u}^{20}+{u}^{19}+5\,{u}^{18}+16\,{u}^{17}+61\,{u}^{16}
\\+154\,{u}^{15}+379\,{u}^{14}+707\,{u}^{13}+1155\,{u}^{12}
\\+1490\,{u}^{11}+1670\,{u}^{10}+1490\,{u}^{9}+1155\,{u}^{8}
\\+707\,{u}^{7}+379\,{u}^{6}+154\,{u}^{5}+61\,{u}^{4}
\\+16\,{u}^{3}+5\,{u}^{2}+u+1$$
The sequence here is
$$1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848,
\\ 13027956824399552, 341260431952972580352,\ldots$$
which points us to OEIS A000273 where
these values are confirmed. We get for weakly connected digraphs the
corresponding
$$C_3 = {u}^{6}+{u}^{5}+4\,{u}^{4}+4\,{u}^{3}+3\,{u}^{2}$$
and
$$C_4 =
{u}^{12}+{u}^{11}+5\,{u}^{10}+13\,{u}^{9}+27\,{u}^{8}
\\+38\,{u}^{7}+47\,{u}^{6}+37\,{u}^{5}+22\,{u}^{4}+8\,{u}^{3}$$
and finally
$$C_5 =
{u}^{20}+{u}^{19}+5\,{u}^{18}+16\,{u}^{17}+61\,{u}^{16}+154\,{u}^{15}
\\+379\,{u}^{14}+707\,{u}^{13}+1154\,{u}^{12}+1489\,{u}^{11}
\\+1665\,{u}^{10}+1477\,{u}^{9}+1127\,{u}^{8}+667\,{u}^{7}
\\+326\,{u}^{6}+108\,{u}^{5}+27\,{u}^{4}$$
The lowest entries in these count directed trees and we obtain the
sequence
$$1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180,
\\ 2266502, 10598452, 50235931,\ldots $$
which is OEIS A000238. Setting $u=1$ in the
$C_n$ sequence we obtain
$$1, 2, 13, 199, 9364, 1530843, 880471142, 1792473955306,
\\ 13026161682466252, 341247400399400765678,\ldots$$
which is OEIS A003085. The new Maple code
goes as follows (making use of the material included above).
pet_cycleind_edg_dg :=
proc(n)
option remember;
local all, term, res, cycs, l1, l2, inst1, flat, u, v,
uidx, vidx;
if n=0 then return 1; fi;
all := 0:
for term in pet_cycleind_symm(n) do
flat := pet_flatten_termA(term);
cycs := flat[2]; res := 1;
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx to nops(cycs) do
v := cycs[vidx];
if uidx <> vidx then
# cycles of different sizes
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/lcm(l1, l2))*
op(2, u)*op(2, v));
else
# same size cycles, no self loops
l1 := op(1, u); inst1 := op(2, u);
res := res *
a[l1]^(l1*inst1*(inst1-1)) *
a[l1]^((l1-1)*inst1);
fi;
od;
od;
all := all + flat[1]*res;
od;
all;
end;
GDG :=
proc(n)
option remember;
if n=0 then return 1 fi;
expand(pet_varinto_cind(1+u, pet_cycleind_edg_dg(n)));
end;
CDG :=
proc(n)
option remember;
local res;
if n=0 then return 0 fi;
if n=1 then return 1 fi;
res := GDG(n)
- 1/n*add(GDG(n-k)
*add(p*subs(u=u^(k/p), CDG(p)),
p in divisors(k)), k=1..n-1)
- 1/n*add(p*subs(u=u^(n/p), CDG(p)),
p in divisors(n) minus {n});
expand(res);
end;
TRIANG_GDG :=
proc(m)
seq(seq(coeff(GDG(n), u, k), k=0..n*(n-1)),
n=1..m);
end;
TRIANG_CDG :=
proc(m)
seq(seq(coeff(CDG(n), u, k), k=n-1..n*(n-1)),
n=1..m);
end;
The OP asked for $2n-2$ edges. We get without restrictions the
sequence
$$1, 1, 4, 48, 1155, 43863, 2271936, 148148461,
\\11647251760, 1072087150138,\ldots$$
and in the connected case
$$1, 1, 4, 47, 1127, 42148, 2144407, 137134237,
\\10565885538, 952629680882,\ldots$$
Addendum II, Mar 16 2017. For the sake of completeness let us also
solve the case of ordinary graphs with loops permitted. The cycle
index here is augmented term by term by multiplying the contribution
from ordinary graphs, which is the symmetric group of vertex
permutations acting on the edges, by the action factorized into cycles
of that same vertex permutation on the $n$ possible self-loops
attached to the vertices. The code for this is obtained almost
instantly from the code for the case of ordinary graphs but we do have
to get the base cases right which now demand $G_1 = C_1 = 1 + u.$ This
yields for $G_3$
$$G_3 = {u}^{6}+2\,{u}^{5}+4\,{u}^{4}+6\,{u}^{3}+4\,{u}^{2}+2\,u+1$$
and for $G_4$
$$G_4 = {u}^{10}+2\,{u}^{9}+5\,{u}^{8}+11\,{u}^{7}+17\,{u}^{6}
\\+18\,{u}^{5}+17\,{u}^{4}+11\,{u}^{3}+5\,{u}^{2}+2\,u+1$$
and finally for $G_5$
$$G_5 = {u}^{15}+2\,{u}^{14}+5\,{u}^{13}+13\,{u}^{12}
\\+29\,{u}^{11}+52\,{u}^{10}+76\,{u}^{9}+94\,{u}^{8}
\\+94\,{u}^{7}+76\,{u}^{6}+52\,{u}^{5}+29\,{u}^{4}
\\+13\,{u}^{3}+5\,{u}^{2}+2\,u+1.$$
The sequence now becomes
$$2, 6, 20, 90, 544, 5096, 79264, 2208612, 113743760, 10926227136,
\\ 1956363435360, 652335084592096, 405402273420996800, \ldots $$
which is OEIS A000666 and which looks to
be the right entry. We obtain for connected graphs with self-loops
that
$$C_3 = {u}^{6}+2\,{u}^{5}+3\,{u}^{4}+3\,{u}^{3}+{u}^{2}$$
and that
$$C_4 = {u}^{10}+2\,{u}^{9}+5\,{u}^{8}+10\,{u}^{7}+13\,{u}^{6}
\\+11\,{u}^{5}+6\,{u}^{4}+2\,{u}^{3}$$
and finally
$$C_5 = {u}^{15}+2\,{u}^{14}+5\,{u}^{13}+13\,{u}^{12}
\\+28\,{u}^{11}+49\,{u}^{10}+68\,{u}^{9}+75\,{u}^{8}+61\,{u}^{7}
\\+35\,{u}^{6}+14\,{u}^{5}+3\,{u}^{4}.$$
Observe that the lowest degree term once more counts trees and we get
$$ 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, \ldots$$
as before. The sequence corresponding to the $C_n$ is
$$2, 3, 10, 50, 354, 3883, 67994, 2038236, 109141344, 10693855251,
\\ 1934271527050, 648399961915988, 404093642681273382,\ldots$$
which is OEIS A054921, and looks correct.
The modified Maple code now runs as follows.
pet_cycleind_edg_sl :=
proc(n)
option remember;
local all, term, res, cycs, l1, l2, inst1, flat, u, v,
uidx, vidx;
if n=0 then return 1; fi;
all := 0:
for term in pet_cycleind_symm(n) do
flat := pet_flatten_termA(term);
cycs := flat[2]; res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res *
(a[l1]^(1/2*(l1-1)))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res *
(a[l1/2]*a[l1]^(1/2*(l1-2)))^inst1;
fi;
od;
all := all + term*res;
od;
all;
end;
GSL :=
proc(n)
option remember;
if n=0 then return 1 fi;
if n=1 then return 1+u fi;
expand(pet_varinto_cind(1+u, pet_cycleind_edg_sl(n)));
end;
CSL :=
proc(n)
option remember;
local res;
if n=0 then return 0 fi;
if n=1 then return 1+u fi;
res := GSL(n)
- 1/n*add(GSL(n-k)
*add(p*subs(u=u^(k/p), CSL(p)),
p in divisors(k)), k=1..n-1)
- 1/n*add(p*subs(u=u^(n/p), CSL(p)),
p in divisors(n) minus {n});
expand(res);
end;
TRIANG_GSL :=
proc(m)
seq(seq(coeff(GSL(n), u, k), k=0..n*(n+1)/2),
n=1..m);
end;
TRIANG_CSL :=
proc(m)
seq(seq(coeff(CSL(n), u, k), k=n-1..n*(n+1)/2),
n=1..m);
end;
