A369201 - OEIS

A369201

Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

%I #10 Feb 02 2024 14:22:33

%S 0,0,0,0,0,1,7,30,124,507,2036,8216,33515,138557,583040,2503093,

%T 10985364,49361893,227342301,1073896332,5204340846,25874724616,

%U 131937166616,689653979583,3693193801069,20247844510508,113564665880028,651138092719098,3813739129140469

%N Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

%C These are graphs with n vertices and n edges having at least two cycles in the same component.

%H Andrew Howroyd, <a href="/A369201/b369201.txt">Table of n, a(n) for n = 0..50</a>

%H Gus Wiseman, <a href="/A369201/a369201.png">The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges</a>.

%F a(n) = A001434(n) - A137917(n).

%e The a(0) = 0 through a(6) = 7 simple graphs:

%e . . . . . {{12}{13}{14}{23}{24}} {{12}{13}{14}{15}{23}{24}}

%e {{12}{13}{14}{15}{23}{45}}

%e {{12}{13}{14}{23}{24}{34}}

%e {{12}{13}{14}{23}{24}{35}}

%e {{12}{13}{14}{23}{24}{56}}

%e {{12}{13}{14}{23}{25}{45}}

%e {{12}{13}{14}{25}{35}{45}}

%t brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];

%t Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]

%Y Without the choice condition we have A001434, covering A006649.

%Y The labeled version without choice is A116508, covering A367863, A367862.

%Y The complement is counted by A137917, labeled A137916.

%Y For any number of edges we have A140637, complement A134964.

%Y For labeled set-systems we have A368600.

%Y The case with loops is A368835, labeled A368596.

%Y The labeled version is A369143, covering A369144.

%Y A006129 counts covering graphs, unlabeled A002494.

%Y A007716 counts unlabeled multiset partitions, connected A007718.

%Y A054548 counts graphs covering n vertices with k edges, with loops A369199.

%Y A129271 counts connected choosable simple graphs, unlabeled A005703.

%Y Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.

%K nonn

%O 0,7

%A _Gus Wiseman_, Jan 22 2024

%E a(25) onwards from _Andrew Howroyd_, Feb 02 2024