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}四个边，这样我的想法有想错吗？(因为这样每个点都可
以拜访到其他点)

了解!!谢谢

simple graph应该还是可以有循环，但不能有self-loop

loop=循环，cycle=环路，simple graph任两点至多一边，可以有cycle，不能有loop

simple graph 不是不能有循环吗 有三角形不就是循环了?

任意三个点就要多算取哪三个点吧

第一题，n取2是代表Kn的所有边数，你可以有要与不要两种选择，所以是2^n取2，包含△123代表那三个边我一定要，所以剩下n取2个-3个边可以选择要或不要，所以是2^(n取2)-3

就多一个步骤去决定哪三个点

cycle 长度不一定会>= k+1, 但是一定可以找到长度>=k+1的cycle, 我是用画图出来，然后把每个点编号

一定可以找到长度>=k+1的cycle

10个点每人5个邻居 确定至少可以取到五点形成循环 所以大小是62的问题应该是一张图deg(v)最小为k ,v属于G, 则必有一cycle长为k+1我那个说法有点太简易了 概念是最差的状况为每次取的点都是前a个的邻居 这样取到最后循环长刚好为n+1

(3)的话取一个Tree 就是graph 且|E|=|V|-1(1)和(2) 有没有完整一点的描述啊，有点看不懂想要问什

2 ,每个人deg至少k 所以大家至少k个邻居从点v0开始 每取一个其他人deg就-1取完k个结束 循环长=点数+1这是概念 严谨证明要再翻一下1是一定要有某三角形abc所以-3

1.你都讲说可取可不取，那我要取一个三角形不就等于一定要取三个便，所以扣掉3。我是这样理解，有错请告知

1.应该是一定要先选那三条边 剩下n取2 -3条可取可不取 这样就包含三角形了

3无循环连通图, 也就是tree