MathCastle
Graph TheoryHardIsomorphism and Subgraphs

Isomorphism and Subgraphs · Hard problem

Let GG have vertices 1,…,91,\ldots,9 and edges 12,13,14,23,24,3412,13,14,23,24,34 (a K4K_4 on {1,2,3,4}\{1,2,3,4\}), together with the pendants 15,26,37,4815,26,37,48 and the extra edge 5959. Let SS be the 55 vertices of GG with the SMALLEST degree. How many edges does the induced subgraph of G‾\overline G on SS (i.e. G‾[S]\overline G[S]) have?