MathCastle
Graph TheoryMediumIsomorphism and Subgraphs

Isomorphism and Subgraphs · Medium problem

Graph GG has vertices 1,…,71,\ldots,7 with a triangle on {1,2,3}\{1,2,3\} (edges 12,13,2312,13,23) and a 44-cycle on {4,5,6,7}\{4,5,6,7\} (edges 45,56,67,4745,56,67,47), with no edges between the two groups. Graph HH has the same 77 vertices arranged in a single 77-cycle (edges 12,23,34,45,56,67,1712,23,34,45,56,67,17). Both have 77 edges. By how much do the numbers of triangles in GG and HH differ?