MathCastle
Graph TheoryHardIsomorphism and Subgraphs

Isomorphism and Subgraphs · Hard problem

Let GG have vertices 1,…,61,\ldots,6 and edges 12,23,34,45,56,1612,23,34,45,56,16 (a 66-cycle) together with the chord 2525 joining opposite vertices. How many 44-cycles (sets of 44 vertices whose edges can be arranged into a cycle using 44 of GG's edges) does GG contain?