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