Нахождение пятиконечной звезды за полиномиальное время

Я хочу доказать, что это часть моей домашней работы по курсу, который я сейчас прохожу. Я ищу некоторую помощь в продолжении, а не ответ.

Это вопрос, о котором идет речь:

5-точечная звезда в неориентированном графе является 5-кликой. Покажите, что 5-POINTED-STAR , где 5-POINTED-STAR = содержит 5-точечную звезду в качестве подграфа .{ < G > : G $\in P$$\{ <G>$ $: G$$\}$

Где клика CLIQUE = - неориентированный граф с -кликой .G k $\{(G, k) : G$$G$$k$$\}$

Теперь моя проблема состоит в том, что это, кажется, решает проблему CLIQUE, определяя, содержит ли граф клику с дополнительным ограничением необходимости определять, что CLIQUE формирует 5-точечную звезду. Похоже, что это включает в себя некоторые геометрические вычисления, основанные на знании пятиконечной звезды . Тем не менее, в теории вычислений Майкла Сипсера , стр. 268, есть доказательство, показывающее, что КЛИК находится в и на странице 270 отмечает, что$NP$

Мы представили примеры языков, таких как HAMPATH и CLIQUE, которые являются членами НП , но это не известно, в . $P$[выделение добавлено]

Если КЛИК не в , почему пятиконечная звезда в ? Есть что-то, чего я не вижу? Помните, что это домашняя проблема, и прямой ответ не будет оценен. Благодарность!$P$$P$

Если - граф, сколько подмножеств V размера 5 существует?$G=(V,E)$$V$$5$

Если есть 5-клика, одно из этих подмножеств является кликой.

Спойлеры ниже:

Есть возможные подмножества для проверки, то есть самое большее| V| 5вариантов, который является полиномиальным при вводе. Это не такдля произвольногоk, так как| V| Кможет быть экспоненциальной во входных данных, и именно поэтомуCLIQUE∉P(если P = NP, agghh.).${|V| \choose 5}$$|V|^5$$k$$|V|^k$$\text{CLIQUE} \notin P$