Trouver une étoile à 5 branches en temps polynomial

Je veux établir que cela fait partie de mes devoirs pour un cours que je suis en train de suivre. Je cherche de l'aide pour procéder, PAS UNE RÉPONSE.

Telle est la question en question:

Une étoile à 5 branches dans un graphique non orienté est une 5-clique. Montrez cette ÉTOILE À 5 POINTS , où ÉTOILE À 5 POINTS = contient une étoile à 5 pointes comme sous-graphique .$\in P$$\{ <G>$ $: G$$\}$

Où une clique est CLIQUE = est un graphe non orienté avec une -clique .$\{(G, k) : G$$G$$k$$\}$

Maintenant, mon problème est que cela semble résoudre le problème CLIQUE, déterminer si un graphique contient une clique avec la contrainte supplémentaire d'avoir à déterminer que le CLIQUE forme une étoile à 5 pointes. Cela semble impliquer un calcul géométrique basé sur la connaissance d'une étoile à 5 branches . Cependant, dans Theory of Computation de Michael Sipser , p. 268, il y a une preuve montrant que CLIQUE est en et à la page 270 note que,$NP$

Nous avons présenté des exemples de langues, comme HAMPATH et CLIQUE, qui sont membres de NP , mais qui ne sont pas connus pour être en . $P$[non souligné dans l'original]

Si CLIQUE n'est pas en , pourquoi une étoile à cinq branches est en ? Y a-t-il quelque chose que je ne vois pas? Rappelez-vous, il s'agit d'un PROBLÈME DE DEVOIR ET UNE RÉPONSE DIRECTE NE SERAIT PAS APPRÉCIÉE. Merci!$P$$P$

Si est un graphe, combien existe-t-il de sous-ensembles de de taille ?$G=(V,E)$$V$$5$

S'il existe une 5-clique, l'un de ces sous-ensembles est une clique.

Spoilers ci-dessous:

Il y a sous-ensembles possibles à vérifier, c'est-à-dire au plus options, qui est polynomial en entrée. Ce n'est PAS le cas pour un arbitraire , car peut être exponentiel en entrée, et c'est pourquoi (sauf si P = NP, agghh.).${|V| \choose 5}$$|V|^5$$k$$|V|^k$$\text{CLIQUE} \notin P$