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).

0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469

Offset: 0

Author

Gus Wiseman, Jan 22 2024

Keywords

• nonn

Comments

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

Examples

			The a(0) = 0 through a(6) = 7 simple graphs:
  .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
                                         {{12}{13}{14}{15}{23}{45}}
                                         {{12}{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{35}}
                                         {{12}{13}{14}{23}{24}{56}}
                                         {{12}{13}{14}{23}{25}{45}}
                                         {{12}{13}{14}{25}{35}{45}}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

Crossrefs

Without the choice condition we have A001434, covering A006649.

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

The complement is counted by A137917, labeled A137916.

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

For labeled set-systems we have A368600.

The case with loops is A368835, labeled A368596.

The labeled version is A369143, covering A369144.

A006129 counts covering graphs, unlabeled A002494.

A007716 counts unlabeled multiset partitions, connected A007718.

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

A129271 counts connected choosable simple graphs, unlabeled A005703.

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

Programs

Mathematica

brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]

Formula

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

Extensions

a(25) onwards from Andrew Howroyd, Feb 02 2024