[習題] 1.13 (b)似乎不完整

看板Chang_Course作者killyou (xxx)時間18年前 (2007/11/07 15:51)推噓4(4推 0噓 1→)

留言5則, 3人參與討論串1/1

the answer: _ G P4-free, both G, G connected with min n(G) ___ G-v P4-free, so one of G-v and G-v is disconnected _ if G_v disconnceted, then v isolated in G......# ___ 可是還有一個case: 要是 G-v connected 當然 G-v disconnected. ex: C4 join 或許你可以假設 G-v= ▽ G_i, then ___ 1. v 至少會連到一個 component of G-v,since G connected _ 2. 而且每個G_i都會有一點不連到v, since G connceted 再由此去找出P4, 得到矛盾. p.s.我的做法是證明: If G connctedand P4-free, then G is a complete bipartite graph. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.231.114

推

over

11/08 02:13, , 1^F

11/08 02:13, 1^F

推

over

11/08 02:14, , 2^F

11/08 02:14, 2^F

→

killyou

11/08 22:47, , 3^F

11/08 22:47, 3^F