第三题的二次剩余好恐怖

第四题难道不是大水题...

第一题
随意取一个点v，设与之相邻的为v[1..k]
若v[i]互不相邻，考虑这个变换：
令所有v[1]的邻点与v相邻，然后删掉v[1]，易证若此图有满足题意的子图，则原图亦有。
若有两个v[i]相邻,不妨设为v[1],v[2]
若v[1]或v[2]与其他v[i]相邻，命题成立
若有某一点同时与v[1],v[2]相邻，命题成立
对于其他情况，令所有v[1],v[2]的邻点与v相邻，然后删掉v[1],v[2]。
易证若此图有满足题意的子图，则原图亦有
用反证法和无穷递降法，知原命题成立

第二题暂时不会。。。
maple的结果：

根据答案可以猜想X(n)=n*f[n-1]，这里f[n]为fibonacci数列