Show that the following problem is NPC: Subgraph Isomorphism (SI) Instance: Two graphs G 1 and G 1 • Question: Does G 1 contain a subgraph isomorphic to G 1 ? (Consider the case that G 1 is a complete...

1. 
   

   
   Show that the following problem is
   
   NPC:
   
   

   
   

Subgraph Isomorphism (SI)

<sup>Instance:



Two graphs


G</sup>

1

<sup>and




G</sup>

1

^•

<sup>Question:







Does




G</sup>

1

<sup>contain




a




subgraph




isomorphic




to




G</sup>

1

<sup>?




(Consider the




case




that




G</sup>

1

<sup>is




a




complete




graph.




In




other




words show</sup>



that

CLIQUE

cc SJ.)