OFFSET
1,5
COMMENTS
For Hamming embeddability see A343463. Graph G is minimally non-Hamming-embeddable if G cannot be embedded, yet G\v is embeddable for all vertices v.
I conjecture (on admittedly weak evidence) that these graphs are always planar.
REFERENCES
D. E. Knuth, The Art of Computer Programming, Volume 4B (in preparation). Section 7.2.2.3 will contain an exercise devoted to this topic.
EXAMPLE
For n=5 the a(5)=2 graphs are C5 and K32.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Don Knuth, Apr 16 2021
STATUS
approved