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

[killyou (xxx)]

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:那是在不失一般性情況下的假設，你說的case
推 over:也可以reduce成這種！
→ killyou:\bar{G-v}=\bar{G}-v,這樣WLOG比較順吧?
推 over:嗯嗯對！
推 ugoc:P4是自反同構，這樣G若是P4-free那G-bar也是