https://i.imgur.com/3ffo8bh.jpg
https://i.imgur.com/M0y46H6.jpg
https://i.imgur.com/xgVcbzS.jpg
假设S’不为k-plex 我们已知H’的min. deg.<=H的min. deg.
想请问第三张图的（2）第四句话说 :
H' 的min. deg.<|s'|-k 是为什么
因为H' 可以为 (k+n)-plex 这样一来H’的min. deg= |s'|-(k+n)> |s'|-k
另外最后一句话老师的意思是说H' 的min. deg. node必为H的min. deg node吗？ 我觉得老师最后
一句话是要说存在一点 v 为H' min. deg. node其在H的deg. 小于H的min. deg. 故矛盾
第二张图是我画的G 设S就是所有G的node 然后取S’为右图 明显不存在4-plex 不是吗
不好意思问题比较多
谢谢大家

先回答第一个 k-plex定义是每点deg至少S-k所以如果不是k-plex 至少有一点deg<S-K然后其实我看不太懂你要问啥XD 我就解释他的证法好了因为题目要证明K-plex S的子图 S'也是K-plex所以就先假设S是k-plex 但S'不是k-plex如果结论跟假设矛盾 那假设就错误 代表S的子图S'是kplex具体怎么推就看图吧 然后你画的图右边是4plex不是1plex

我漏看at least，以为是最小的deg. 恰好为|s|-k但是请问这样的话为k-plex的图 必也为(k+n)-plex 吗 S举例题目S={a,b,c,d,e} 其induced graph 的min. deg=2所以min. deg.>=|S|-k (2>=5-3) 但是2>=5-4 所以也是4-plex吗谢谢解释

应该没错 k-plex的k越大 所需degree就越小