MathCastle
Graph TheoryMediumIsomorphism and Subgraphs

Isomorphism and Subgraphs · Medium problem

Let G1G_1 have vertices 1,…,61,\ldots,6 and edges 12,23,34,45,56,16,1412,23,34,45,56,16,14 (a 66-cycle plus the chord 1414 joining opposite vertices). Let G2G_2 have vertices a,…,fa,\ldots,f and edges ab,bc,cd,de,ef,af,bdab,bc,cd,de,ef,af,bd (a 66-cycle plus the chord bdbd). Consider the map φ\varphi sending 1,2,3,4,5,61,2,3,4,5,6 to a,b,c,d,e,fa,b,c,d,e,f in order. How many of G1G_1's 77 edges map under φ\varphi to a pair that is NOT an edge of G2G_2?