靠近最下面的地方G1G2是acycle
因為G是acycle，但是這個不是要證明的結果嗎
還沒證明怎麼可以拿來用?
為什麼不用證明 不具 degree 0 和 n 的情形呢
因為很明顯可以用鴿籠證明出來嗎
(2) 如果有三角形 (最小cycle長度是3)
那e > 2v -4 也不能保證是非平面圖嗎
6-1 從題目哪裡可以得知
任兩點至多一個邊相連?
訂閱：
張貼留言 (Atom)
Research Space for Linear Algebra & Discrete Mathematics
2 則留言:
1. 這裡的"G是acyclic"是trivial, 是根據tree的定義而來的(connected, acyclic), 所以嚴格來講不是沒證而是證完了, 證完的話就可以拿來用, 這邊主要要證的只有|E|=|V|-1那個式子而已
2. 如果說G具H.C., 這樣就已經imply了|V_1|和|V_2|一定都大於等於 2 了, 所以不用寫也沒關係
3. 這題有勘誤過, 請至離散勘誤區看一下
4. 是的, 反例可取 K_4
5. 一般若題目沒有特別說明, G指的都是simple graph, 所以任兩點間至多只會有一個邊相連
感謝您~~
張貼留言