Isomorfismo do subgráfico

Temos os gráficos G_1 = (V_1, E_1), G_2 = (V_2, E_2).

Pergunta, questão: O gráfico G_1 é isomórfico para um subgrafo de G_2?

(ou seja, existe um subconjunto de vértices de G_2, V ⊆ V_2 e subconjunto das arestas de G_2, E ⊆ E_2, de modo que | V | = | V_1 | e | E | = | E_1 | e existe um uma correspondência dos vértices de G_1 no subconjunto de vértices V de G_2, f: V_1 -> V, de modo que {u, v} ∈ E_1 <=> {f (u), f (v)} ∈ E)

Mostre que o problema O isomorfismo do subgráfico pertence ao NP.Mostre que o problema está completo como NP, reduzindo o problema Clique nele. (Dica: considere que o gráfico G_1 está completo)

Eu tentei o seguinte:

Uma máquina de Turing não determinística "adivinha" primeiro o subconjunto dos nós V e o subconjunto das arestas E de G_2 e depois verifica se | V | = | V_1 | e | E | = | E_1 | e que existe uma correspondência um a um f: V_1 -> V tal que {u, v}} E_1 <=> {f (u), f (v)} ∈ E.

Como existem O (| V_2 | ^ 2) pares diferentes de vértices, a verificação requer tempo polinomial. Portanto, o problema pertence ao NP.

Deixe (G, k) uma instância arbitrária do problema de clique, em que k é o número de vértices da clique.

Podemos construir uma instância do problema de isomorfismo do subgráfico em tempo polinomial da seguinte forma: G_2 é um gráfico em n vértices.

G_1 é um gráfico completo de k vértices, para alguns k <= n. Seja G = G_2. O problema Isomorfismo do subgrafo tem uma solução se houver um subgrafo completo de G_2 com k vértices, isto é, se o gráfico G tiver um subgrafo completo com k vértices.

Assim, a instância do problema Subgráfico Isomorfismo possui uma solução se a instância inicial do problema Clique possui uma solução.

Portanto, o problema Subgráfico Isomorfismo é NP-completo.

Você poderia me dizer se está certo ou se eu poderia melhorar alguma coisa?