1.
n个点包含三角形(v1,v2,v3)的simple graph为什么是2^(n取2 - 3)
我知道n个点可以决定n取2个边,再分可取可不取,但是包括三角形v1v2v3,代表有3个边
不取,为什么会是在次方扣3?
2.
每个点的degree至少为2保证一定有cycle这个定理我可以了解,因为有进入边一定有出来
边
但是每个点degree至少为k时,为什么保证cycle长>=k+1,证明怎么样也看不懂,为什么
抓一点vk(以degree当做点编号是为了什么?)
3
连通图,|E|>=|V|-1
这个证明我看的懂,是用数学归纳法推出来的,但是我拼命在想什么情况下刚好|E|=|V|-
1
是一个刚好由起点拜访到终点的walk吗?
比如5个点的图{v1,v2,v3,v4,v5}四个边,这样我的想法有想错吗?(因为这样每个点都可
以拜访到其他点)