MathCastle
Graph TheoryChallengeIsomorphism and Subgraphs

Isomorphism and Subgraphs · Challenge problem

Graph PP has vertices 1,…,61,\ldots,6 and edges 12,23,34,45,56,1612,23,34,45,56,16 (a 66-cycle). Graph QQ has the same vertices and edges 12,23,13,45,56,4612,23,13,45,56,46 (two disjoint triangles). Graph RR has vertices 1,…,61,\ldots,6 with all 99 cross edges between {1,2,3}\{1,2,3\} and {4,5,6}\{4,5,6\} (i.e. K3,3K_{3,3}). Graph TT has vertices 1,…,61,\ldots,6 and edges 31,15,54,42,26,6331,15,54,42,26,63 (read as a cyclic sequence). Among P,Q,R,TP,Q,R,T, how many distinct isomorphism classes are represented?