(b)If Gis a graph on n vertices , for n>=2 ,and G is not connected ,prove that is connected,
修正過後的證法如下:
因為G不連通所以G可分為x個component各自為圖k1,k2,...,kx
而k1,k2,...,kx 在G的補圖中,以兩兩一組可成為kmn 且 m!=n 之bipartite圖，
因此 k1,k2,...,kx 在G的補圖中各自兩兩連通，所以G的補圖連通。
(我是先想到這樣的如下:因為G不連通所以G可分為k個component ，令K個component為K個點，那G之補圖必為這K個點之完全圖所以G之補圖連通。)
請問我這樣的證明OK嗎?
下為先前錯誤的證法
--------------------------------------
圖的網址:
http://140.126.21.8/~jackend/math.JPG
請問我這樣的證明OK嗎?
--------------------------------------
9 則留言:
抱歉, 我看不到圖, 得請您再貼一次
我重新弄好了
你最後一步 導的時候
為什麼可以說 |E'| >= n-1
就表示G' 連通?
因為C(n,2)-C(n-1,2)=n-1
呃.. 證明不是很 ok ㄟ
我猜測是你的 C^n_2 是 C(n,2)=n(n-1)/2的意思.
如果是的話, 那麼 K_{n-1}+X=C(n,2) 就不對了, 先不管你 X 是什麼 K_{n-1} 是一個圖, C(n,2) 是一個數, 怎麼相等？
再來; 先不管你怎麼推得 upper bound for |E(G)|, 一個很大的問題是 |\bar{E}|\ge n-1 並不能得到 \bar{G} 是連通的.
這題只需用一般性質證明即可.
感謝凱的指正，你的建議讓我想到如果我換成這樣的另一個證明方法呢?
MySol:
因為G不連通所以G可分為k個component ，令K個component為K個點，那G之補圖必為這K個點之完全圖所以G之補圖連通。
上一個証法沒有很清楚的寫出，
已經更新在ｐｏ的文中了。
Well, 我相信你有"感覺"到證明, 但仔細說出有邏輯性的證明, 還需多加練習.
其實凡事最好都從定義下手, 連通的定義為: 任給二個點 x,y 則有一條 x,y-path.
In this problem, G 不連通 => G 有至少 2 個 component. 任給 x,y in V(\bar{G}), 若 x,y 在 G 中落在不同 component 則在 \bar{G} x,y 有邊相連, 若 x,y 在 G 中落在同一個 component, 則在另一個component 的任一點必為 x,y 的 common neighbor. 所以有一條 x,y-path in \bar{G}. (而且這是一條 P_2) 因為 x,y 為任意點, 故 \bar{G} 連通.
謝謝你的建議，我會多多練習的。
張貼留言