Encontrar una estrella de 5 puntas en tiempo polinómico

Quiero establecer que esto es parte de mi tarea para un curso que estoy tomando actualmente. Estoy buscando ayuda para proceder, NO UNA RESPUESTA.

Esta es la pregunta en cuestión:

Una estrella de 5 puntas en un gráfico no dirigido es una camarilla de 5. Muestre esa ESTRELLA DE 5 PUNTOS $\in P$ , donde ESTRELLA DE 5 PUNTOS = $\{ <G>$ $: G$ contiene una estrella de 5 puntas como un subgrafo $\}$ .

Donde una camarilla es CLIQUE = $\{(G, k) : G$ es un gráfico no dirigido $G$ con una $k$ -clique $\}$ .

Ahora mi problema es que esto parece estar resolviendo el problema de CLIQUE, determinando si un gráfico contiene una camarilla con la restricción adicional de tener que determinar que CLIQUE forma una estrella de 5 puntas. Esto parece involucrar algunos cálculos geométricos basados ​​en el conocimiento de una estrella de 5 puntas . Sin embargo, en la Teoría de la computación de Michael Sipser , página 268, hay una prueba que muestra que CLIQUE está en $NP$ y en la página 270 señala que,

Hemos presentado ejemplos de lenguajes, como HAMPATH y pandilla, que son miembros de NP, pero que no son conocidos para estar en $P$ . [énfasis añadido]

Si CLIQUE no está en , ¿por qué una estrella de cinco puntas está en P ? ¿Hay algo que no estoy viendo? Recuerde, este es un PROBLEMA DE TAREA y una RESPUESTA DIRECTA NO SERÍA APRECIADA. ¡Gracias!$P$$P$

Si es un gráfico, ¿cuántos subconjuntos de V de tamaño 5 existen?$G=(V,E)$$V$$5$

Si hay una camarilla 5, uno de estos subconjuntos es una camarilla.

Spoilers a continuación:

Hay posibles subconjuntos para verificar, es decir, como máximo| V| 5opciones, que es polinomial en la entrada. Este NO es el casopara unakarbitraria, ya que| V| kpodría ser exponencial en la entrada, y es por eso queCLIQUE∉P(a menos que P = NP, agghh).${|V| \choose 5}$$|V|^5$$k$$|V|^k$$\text{CLIQUE} \notin P$