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.