Menemukan Bintang Berujung 5 dalam waktu polinomial

Saya ingin memastikan bahwa ini adalah bagian dari pekerjaan rumah saya untuk kursus yang sedang saya ikuti. Saya mencari bantuan dalam melanjutkan, BUKAN JAWABAN.

Ini pertanyaannya:

5-menunjuk-bintang dalam grafik tidak terarah adalah 5-klik. Tunjukkan bahwa 5-POINTED-STAR , di mana 5-POINTED-STAR = berisi bintang berujung 5 sebagai subgraph .$\in P$$\{ <G>$ $: G$$\}$

Di mana sebuah klik adalah CLIQUE = adalah grafik tanpa arah dengan -clique .$\{(G, k) : G$$G$$k$$\}$

Sekarang masalah saya adalah bahwa ini tampaknya menyelesaikan masalah CLIQUE, menentukan apakah grafik berisi klik dengan batasan tambahan karena harus menentukan bahwa CLIQUE membentuk bintang berujung 5. Ini tampaknya melibatkan beberapa perhitungan geometris berdasarkan pengetahuan bintang berujung lima . Namun, dalam Teori Komputasi Michael Sipser , hal 268, ada bukti yang menunjukkan bahwa CLIQUE ada dalam dan pada halaman 270 mencatat bahwa,$NP$

Kami telah menyajikan contoh-contoh bahasa, seperti HAMPATH dan CLIQUE, yang merupakan anggota dari NP tetapi yang tidak diketahui berada di . $P$[penekanan ditambahkan]

Jika CLIQUE tidak di , mengapa bintang berujung lima berada di ? Apakah ada sesuatu yang tidak saya lihat? Ingat, ini adalah MASALAH RUMAH TANGGA dan JAWABAN LANGSUNG TIDAK AKAN DIHARGAI. Terima kasih!$P$$P$

Jika adalah graf, berapa banyak himpunan bagian dari dari ukuran yang ada?$G=(V,E)$$V$$5$

Jika ada 5-klik, salah satu himpunan bagian ini adalah klik.

Spoiler di bawah ini:

Ada subset yang mungkin untuk memeriksa, yaitu, paling banyak opsi, yang jumlahnya banyak dalam input. Ini BUKAN kasus untuk arbitrary , karena mungkin eksponensial dalam input, dan inilah sebabnya (kecuali P = NP, agghh.).${|V| \choose 5}$$|V|^5$$k$$|V|^k$$\text{CLIQUE} \notin P$