※ 引述《arcadian3 (falco)》之銘言：
: 1. prove that a connected graph has k vertices of odd degree (k>0)
: there are k/2 paths, no two of which have common edge that cover
: all edges in the graph.
: 這題我看曉園出的解答是這樣的
: by corollary: in any graph, there is an even number of vertices that
: have odd degrees. 所以 k 必為偶數.
: 加入 k/2 個邊到圖形中, 將所有奇次數端點以配對方式連接起來, 在此結果下找
: 出圖中一Euler circuit, 然後再將所加入的邊去掉,結果共需 k/2 路徑
: 但是老師卻問我: how to pick up the k/2 paths without common edges
: 請問各位高手該如何解釋呢?
: 2. let G be a graph of order n. If d(G)大於等於(n-1)/2, show that G is
: connected. 其中 d(G) is the minimum degree of a graph G, defined by
: d(G)=min { deg(v): v belongs to V(G) }
: 謝謝
2.
|E(G)| = Σd(v) / 2 >= n.d(G) /2 >= n(n-1)/4
Assume G is disconnected
then G can be divided into 2 component G1,G2 without path between G1,G2
Let |V(G1)| = m , |V(G2)| = n-m
then |E(G1)| <= C(m,2) , |E(G2)| <= C(n-m,2)
but C(m,2) + C(n-m,2) < n(n-1)/4 , for m = 1,...,n-1
-><-
So G is connected
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.117.120.229